-
Previous Article
On polycyclic codes over a finite chain ring
- AMC Home
- This Issue
-
Next Article
On the non-Abelian group code capacity of memoryless channels
A construction of $ \mathbb{F}_2 $-linear cyclic, MDS codes
1. | Instituto de Matemática, Estatística e Computação Científica, Universidade Estadual de Campinas, Campinas, Brazil |
2. | Departament de Matemàtiques, Universitat d'Alacant, Alacant, Spain |
3. | School of Mathematics and Statistics, Carleton University, Ottawa, Canada |
In this paper we construct $ \mathbb{F}_2 $-linear codes over $ \mathbb{F}_{2}^{b} $ with length $ n $ and dimension $ n-r $ where $ n = rb $. These codes have good properties, namely cyclicity, low density parity-check matrices and maximum distance separation in some cases. For the construction, we consider an odd prime $ p $, let $ n = p-1 $ and utilize a partition of $ \mathbb{Z}_n $. Then we apply a Zech logarithm to the elements of these sets and use the results to construct an index array which represents the parity-check matrix of the code. These codes are always cyclic and the density of the parity-check and the generator matrices decreases to $ 0 $ as $ n $ grows (for a fixed $ r $). When $ r = 2 $ we prove that these codes are always maximum distance separable. For higher $ r $ some of them retain this property.
References:
[1] |
M. Barbier, C. Chabot and G. Quintin,
On quasi-cyclic codes as a generalization of cyclic codes, Finite Fields and Their Applications, 18 (2012), 904-919.
doi: 10.1016/j.ffa.2012.06.003. |
[2] |
R. Barbulescu, C. Bouvier, J. Detrey, P. Gaudry, H. Jeljeli, E. Thomé, M. Videau and P. Zimmermann, Discrete logarithm in $GF(2^{809})$ with FFS, PKC 2014: Public-Key Cryptography-PKC 2014, (2014), 221–238, http://dx.doi.org/10.1007/978-3-642-54631-0_13.
doi: 10.1007/978-3-642-54631-0. |
[3] |
M. Blaum, J. Brady, J. Bruck and J. Menon,
EVENODD: An efficient scheme for tolerating double disk failures in RAID architectures, IEEE Transactions on Computers, 44 (1995), 192-202.
doi: 10.1109/12.364531. |
[4] |
M. Blaum and J. Bruck,
Decoding the Golay code with Venn diagrams, IEEE Transactions on Information Theory, 36 (1990), 906-910.
doi: 10.1109/18.53756. |
[5] |
M. Blaum, J. Bruck and A. Vardy,
MDS array codes with independent parity symbols, IEEE Transactions on Information Theory, 42 (1995), 529-542.
doi: 10.1109/ISIT.1995.535761. |
[6] |
M. Blaum, P. G. Farrell and H. C. A. van Tilborg, Array codes, in Handbook of Coding Theory, North-Holland, Amsterdam, 1/2 (1998), 1855–1909. |
[7] |
M. Blaum and R. M. Roth,
New array codes for multiple phased burst correction, IEEE Transactions on Information Theory, 39 (1993), 66-77.
doi: 10.1109/18.179343. |
[8] |
M. Blaum and R. M. Roth,
On lowest density MDS codes, IEEE Transactions on Information Theory, 45 (1999), 46-59.
doi: 10.1109/18.746771. |
[9] |
S. D. Cardell, Constructions of MDS Codes over Extension Alphabets, PhD thesis, Departamento de Ciencia de la Computación e Inteligencia Artificial, Universidad de Alicante, Alicante, España, 2012. Google Scholar |
[10] |
S. D. Cardell, J.-J. Climent and V. Requena,
A construction of MDS array codes, WIT Transactions on Information and Communication Technologies, 45 (2013), 47-58.
doi: 10.2495/DATA130051. |
[11] |
S. D. Cardell and A. Fúster-Sabater, Recovering decimation-based cryptographic sequences by means of linear CAs, (2018), https://arXiv.org/abs/1802.02206. Google Scholar |
[12] | G. A. Gibson, Redundant Disk Arrays: Reliable, Parallel Secondary Storage, Cambridge, MA: MIT Press, 1992. Google Scholar |
[13] |
K. Huber,
Some comments on Zech's logarithms, IEEE Transactions on Information Theory, 36 (1990), 946-950.
doi: 10.1109/18.53764. |
[14] |
A. Kotzig, Hamilton graphs and Hamilton circuits, Theory of Graphs and its Applications, Publ. House Czechoslovak Acad. Sci., Prague, (1964), 63–82. |
[15] |
E. Louidor and R. M. Roth,
Lowest density MDS codes over extension alphabets, IEEE Transactions on Information Theory, 52 (2006), 3186-3197.
doi: 10.1109/TIT.2006.876235. |
[16] |
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. I, North-Holland Mathematical Library, Vol. 16. North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. |
[17] |
E. Mendelsohn and A. Rosa,
One-factorizations of the complete graph-A survey, Journal of Graph Theory, 9 (1985), 43-65.
doi: 10.1002/jgt.3190090104. |
[18] |
M. Sudan, Algorithmic Introduction to Coding Theory, 2002, https://people.csail.mit.edu/madhu/FT02/scribe/lect16.ps. Google Scholar |
[19] |
L. H. Xu and J. Bruck,
X-code: MDS array codes with optimal encoding, IEEE Transactions on Information Theory, 45 (1999), 272-276.
doi: 10.1109/18.746809. |
[20] |
G. V. Zaitzev, V. A. Zinov'ev and N. V. Semakov,
Minimum-check-density codes for correcting bytes of errors, erasures, or defects, Problems of Information Transmission, 19 (1983), 197-204.
|
show all references
References:
[1] |
M. Barbier, C. Chabot and G. Quintin,
On quasi-cyclic codes as a generalization of cyclic codes, Finite Fields and Their Applications, 18 (2012), 904-919.
doi: 10.1016/j.ffa.2012.06.003. |
[2] |
R. Barbulescu, C. Bouvier, J. Detrey, P. Gaudry, H. Jeljeli, E. Thomé, M. Videau and P. Zimmermann, Discrete logarithm in $GF(2^{809})$ with FFS, PKC 2014: Public-Key Cryptography-PKC 2014, (2014), 221–238, http://dx.doi.org/10.1007/978-3-642-54631-0_13.
doi: 10.1007/978-3-642-54631-0. |
[3] |
M. Blaum, J. Brady, J. Bruck and J. Menon,
EVENODD: An efficient scheme for tolerating double disk failures in RAID architectures, IEEE Transactions on Computers, 44 (1995), 192-202.
doi: 10.1109/12.364531. |
[4] |
M. Blaum and J. Bruck,
Decoding the Golay code with Venn diagrams, IEEE Transactions on Information Theory, 36 (1990), 906-910.
doi: 10.1109/18.53756. |
[5] |
M. Blaum, J. Bruck and A. Vardy,
MDS array codes with independent parity symbols, IEEE Transactions on Information Theory, 42 (1995), 529-542.
doi: 10.1109/ISIT.1995.535761. |
[6] |
M. Blaum, P. G. Farrell and H. C. A. van Tilborg, Array codes, in Handbook of Coding Theory, North-Holland, Amsterdam, 1/2 (1998), 1855–1909. |
[7] |
M. Blaum and R. M. Roth,
New array codes for multiple phased burst correction, IEEE Transactions on Information Theory, 39 (1993), 66-77.
doi: 10.1109/18.179343. |
[8] |
M. Blaum and R. M. Roth,
On lowest density MDS codes, IEEE Transactions on Information Theory, 45 (1999), 46-59.
doi: 10.1109/18.746771. |
[9] |
S. D. Cardell, Constructions of MDS Codes over Extension Alphabets, PhD thesis, Departamento de Ciencia de la Computación e Inteligencia Artificial, Universidad de Alicante, Alicante, España, 2012. Google Scholar |
[10] |
S. D. Cardell, J.-J. Climent and V. Requena,
A construction of MDS array codes, WIT Transactions on Information and Communication Technologies, 45 (2013), 47-58.
doi: 10.2495/DATA130051. |
[11] |
S. D. Cardell and A. Fúster-Sabater, Recovering decimation-based cryptographic sequences by means of linear CAs, (2018), https://arXiv.org/abs/1802.02206. Google Scholar |
[12] | G. A. Gibson, Redundant Disk Arrays: Reliable, Parallel Secondary Storage, Cambridge, MA: MIT Press, 1992. Google Scholar |
[13] |
K. Huber,
Some comments on Zech's logarithms, IEEE Transactions on Information Theory, 36 (1990), 946-950.
doi: 10.1109/18.53764. |
[14] |
A. Kotzig, Hamilton graphs and Hamilton circuits, Theory of Graphs and its Applications, Publ. House Czechoslovak Acad. Sci., Prague, (1964), 63–82. |
[15] |
E. Louidor and R. M. Roth,
Lowest density MDS codes over extension alphabets, IEEE Transactions on Information Theory, 52 (2006), 3186-3197.
doi: 10.1109/TIT.2006.876235. |
[16] |
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. I, North-Holland Mathematical Library, Vol. 16. North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. |
[17] |
E. Mendelsohn and A. Rosa,
One-factorizations of the complete graph-A survey, Journal of Graph Theory, 9 (1985), 43-65.
doi: 10.1002/jgt.3190090104. |
[18] |
M. Sudan, Algorithmic Introduction to Coding Theory, 2002, https://people.csail.mit.edu/madhu/FT02/scribe/lect16.ps. Google Scholar |
[19] |
L. H. Xu and J. Bruck,
X-code: MDS array codes with optimal encoding, IEEE Transactions on Information Theory, 45 (1999), 272-276.
doi: 10.1109/18.746809. |
[20] |
G. V. Zaitzev, V. A. Zinov'ev and N. V. Semakov,
Minimum-check-density codes for correcting bytes of errors, erasures, or defects, Problems of Information Transmission, 19 (1983), 197-204.
|
5 | 7 | 11 | 13 | 17 | 19 | 23 | 29 | 31 | 37 | 41 | 43 | ||
2 | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | |
3 | × | √ | √ | √ | √ | √ | |||||||
4 | × | × | √ | √ | × | ||||||||
5 | × | × | × | ||||||||||
6 | × | × | × | × | × | ||||||||
7 | × | × | |||||||||||
8 | × | × | |||||||||||
9 | × | × | |||||||||||
10 | × | × | |||||||||||
11 | × | ||||||||||||
12 | × | ||||||||||||
13 | |||||||||||||
14 | × | × | |||||||||||
15 | × |
5 | 7 | 11 | 13 | 17 | 19 | 23 | 29 | 31 | 37 | 41 | 43 | ||
2 | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | |
3 | × | √ | √ | √ | √ | √ | |||||||
4 | × | × | √ | √ | × | ||||||||
5 | × | × | × | ||||||||||
6 | × | × | × | × | × | ||||||||
7 | × | × | |||||||||||
8 | × | × | |||||||||||
9 | × | × | |||||||||||
10 | × | × | |||||||||||
11 | × | ||||||||||||
12 | × | ||||||||||||
13 | |||||||||||||
14 | × | × | |||||||||||
15 | × |
[1] |
W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349 |
[2] |
Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006 |
[3] |
Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247 |
[4] |
Raj Kumar, Maheshanand Bhaintwal. Duadic codes over $ \mathbb{Z}_4+u\mathbb{Z}_4 $. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2020135 |
[5] |
Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119 |
[6] |
Arunima Bhattacharya, Micah Warren. $ C^{2, \alpha} $ estimates for solutions to almost Linear elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021024 |
[7] |
Peter Benner, Jens Saak, M. Monir Uddin. Balancing based model reduction for structured index-2 unstable descriptor systems with application to flow control. Numerical Algebra, Control & Optimization, 2016, 6 (1) : 1-20. doi: 10.3934/naco.2016.6.1 |
[8] |
Denis Bonheure, Silvia Cingolani, Simone Secchi. Concentration phenomena for the Schrödinger-Poisson system in $ \mathbb{R}^2 $. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1631-1648. doi: 10.3934/dcdss.2020447 |
[9] |
Misha Bialy, Andrey E. Mironov. Rich quasi-linear system for integrable geodesic flows on 2-torus. Discrete & Continuous Dynamical Systems - A, 2011, 29 (1) : 81-90. doi: 10.3934/dcds.2011.29.81 |
[10] |
Lei Liu, Li Wu. Multiplicity of closed characteristics on $ P $-symmetric compact convex hypersurfaces in $ \mathbb{R}^{2n} $. Discrete & Continuous Dynamical Systems - A, 2020 doi: 10.3934/dcds.2020378 |
[11] |
Jong Yoon Hyun, Yoonjin Lee, Yansheng Wu. Connection of $ p $-ary $ t $-weight linear codes to Ramanujan Cayley graphs with $ t+1 $ eigenvalues. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2020133 |
[12] |
Thomas Alazard. A minicourse on the low Mach number limit. Discrete & Continuous Dynamical Systems - S, 2008, 1 (3) : 365-404. doi: 10.3934/dcdss.2008.1.365 |
[13] |
Daoyin He, Ingo Witt, Huicheng Yin. On the strauss index of semilinear tricomi equation. Communications on Pure & Applied Analysis, 2020, 19 (10) : 4817-4838. doi: 10.3934/cpaa.2020213 |
[14] |
Guillermo Reyes, Juan-Luis Vázquez. Long time behavior for the inhomogeneous PME in a medium with slowly decaying density. Communications on Pure & Applied Analysis, 2009, 8 (2) : 493-508. doi: 10.3934/cpaa.2009.8.493 |
[15] |
F.J. Herranz, J. de Lucas, C. Sardón. Jacobi--Lie systems: Fundamentals and low-dimensional classification. Conference Publications, 2015, 2015 (special) : 605-614. doi: 10.3934/proc.2015.0605 |
[16] |
Jérôme Ducoat, Frédérique Oggier. On skew polynomial codes and lattices from quotients of cyclic division algebras. Advances in Mathematics of Communications, 2016, 10 (1) : 79-94. doi: 10.3934/amc.2016.10.79 |
[17] |
Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437 |
[18] |
Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311 |
[19] |
Nizami A. Gasilov. Solving a system of linear differential equations with interval coefficients. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2739-2747. doi: 10.3934/dcdsb.2020203 |
[20] |
Manfred Einsiedler, Elon Lindenstrauss. On measures invariant under diagonalizable actions: the Rank-One case and the general Low-Entropy method. Journal of Modern Dynamics, 2008, 2 (1) : 83-128. doi: 10.3934/jmd.2008.2.83 |
2019 Impact Factor: 0.734
Tools
Metrics
Other articles
by authors
[Back to Top]