Explicit Cyclic and Quasi-Cyclic Codes With Optimal, Best Known Parameters, and Large Relative Minimum Distances
Authors: 
Conghui Xie, Hao Chen, Chen YuanAuthors Info & Claims
Pages 8688 - 8697
Abstract
In this paper, we construct many infinite families of distance-optimal codes with new parameters, some of which are BCH codes and quasi-cyclic codes. In particular, we report the first infinite family of binary distance-optimal BCH codes with the minimum distance 8. Secondly, several infinite families of binary BCH codes and quasi-cyclic codes are presented. Many codes in these families have optimal or best known parameters. Thirdly, we construct infinite families of binary cyclic <inline-formula> <tex-math notation="LaTeX">$\left [{{n, \geq \frac {n+1}{2},d}}\right]_{2}$ </tex-math></inline-formula> codes with minimum distances <inline-formula> <tex-math notation="LaTeX">$d \geq \lceil \frac {n-1}{\prod _{i=1}^{s}p_{i}}\rceil $ </tex-math></inline-formula>, <inline-formula> <tex-math notation="LaTeX">$n=(2^{p_{1}}-1)(2^{p_{2}}-1) \cdots (2^{p_{s}}-1)$ </tex-math></inline-formula>, <inline-formula> <tex-math notation="LaTeX">$p_{1}, \ldots, p_{s}$ </tex-math></inline-formula> are different primes. Our construction extends the main result of a recent paper published by Sun et al. to much more general binary cyclic codes with various lengths. We also construct an infinite family of binary quasi-cyclic codes with the rate around <inline-formula> <tex-math notation="LaTeX">$\frac {1}{2}$ </tex-math></inline-formula> and relative minimum distance lower bounded by <inline-formula> <tex-math notation="LaTeX">$O\left ({{\frac {1}{\log _{2} \log _{2} n}}}\right)$ </tex-math></inline-formula>.
References
[1]
V. B. Afanassiev and A. A. Davydov, “Weight spectrum of quasi-perfect binary codes with distance 4,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Aachen, Germany, Jun. 2017, pp. 2193–2197.
[2]
S. A. Aly, A. Klappenecker, and P. K. Sarvepalli, “On quantum and classical BCH codes,” IEEE Trans. Inf. Theory, vol. 53, no. 3, pp. 1183–1188, Mar. 2007.
[3]
T. Baicheva, I. Bouyukliev, S. Dodunekov, and V. Fack, “Binary and ternary linear quasi-perfect codes with small dimensions,” IEEE Trans. Inf. Theory, vol. 54, no. 9, pp. 4335–4339, Sep. 2008.
[4]
R. C. Bose and D. K. Ray-Chaudhuri, “On a class of error correcting binary group codes,” Inf. Control, vol. 3, no. 1, pp. 68–79, 1960.
[5]
R. C. Bose and D. K. Ray-Chaudhuri, “Further results on error correcting binary group codes,” Inf. Control, vol. 3, no. 3, pp. 279–290, Sep. 1960.
[6]
H. Chen, S. Ling, and C. Xing, “Asymptotically good quantum codes exceeding the Ashikhmin–Litsyn–Tsfasman bound,” IEEE Trans. Inf. Theory, vol. 47, no. 5, pp. 2055–2058, Jul. 2001.
[7]
E. Z. Chen, “New quasi-cyclic codes from simplex codes,” IEEE Trans. Inf. Theory, vol. 53, no. 3, pp. 1193–1196, Mar. 2007.
[8]
Online Database of Quasi-Twisted Codes. Accessed: Mar. 24, 2024. [Online]. Available: https://databases.cs.hkr.se/qtcodes/
[9]
E. Z. Chen, “An explicit construction of 2-generator quasi-twisted codes,” IEEE Trans. Inf. Theory, vol. 54, no. 12, pp. 5770–5773, Dec. 2008.
[10]
T. Chen, C. Ding, C. Li, and Z. Sun, “Four infinite families of ternary cyclic codes with a square-root-like lower bound,” Finite Fields Their Appl., vol. 92, Dec. 2023, Art. no.
[11]
A. A. Davydov and L. M. Tombak, “Quasiperfect linear binary codes with distance 4 and complete caps in projective geometry,” Probl. Inf. Trans., vol. 25, no. 4, pp. 265–275, Oct. 1989.
[12]
C. Ding and T. Helleseth, “Optimal ternary cyclic codes from monomials,” IEEE Trans. Inf. Theory, vol. 59, no. 9, pp. 5898–5904, Sep. 2013.
[13]
C. Ding and J. Yang, “Hamming weights in irreducible cyclic codes,” Discrete Math., vol. 313, pp. 434–446, Feb. 2013.
[14]
C. Ding, “Parameters of several classes of BCH codes,” IEEE Trans. Inf. Theory, vol. 61, no. 10, pp. 5322–5330, Oct. 2015.
[15]
C. Ding and C. Li, “BCH cyclic codes,” Discrete Math., vol. 347, no. 5, May 2024, Art. no.
[16]
S. T. Dougherty, Algebraic Coding Theory Over Finite Commutative Rings. Cham, Switzerland: Springer, 2017.
[17]
M. Esmaeili, T. A. Gulliver, N. P. Secord, and S. A. Mahmoud, “A link between quasi-cyclic codes and convolutional codes,” IEEE Trans. Inf. Theory, vol. 44, no. 1, pp. 431–435, Jan. 1998.
[18]
T. Etzion and B. Mounits, “Quasi-perfect codes with small distance,” IEEE Trans. Inf. Theory, vol. 51, no. 11, pp. 3938–3946, Nov. 2005.
[19]
G. D. Forney, Concatenated Codes. Cambridge, MA, USA: MIT Press, 1996.
[20]
E. M. Gabidulin, A. A. Davydov, and L. M. Tombak, “Linear codes with covering radius 2 and other new covering codes,” IEEE Trans. Inf. Theory, vol. 37, no. 1, pp. 219–224, Jan. 1991.
[21]
I. B. Gashkov and V. M. Sidel’nikov, “Linear ternary quasi-perfect codes correcting double errors,” Problemy Peredachi Informatsii, vol. 22, no. 4, pp. 284–288, 1986.
[22]
T. A. Gulliver and V. K. Bhargava, “Some best rate 1/p and rate (p-1)/p systematic quasi-cyclic codes,” IEEE Trans. Inf. Theory, vol. 37, no. 3, pp. 552–555, May 1991.
[23]
M. Giulietti and F. Pasticci, “Quasi-perfect linear codes with minimum distance 4,” IEEE Trans. Inf. Theory, vol. 53, no. 5, pp. 1928–1935, May 2007.
[24]
M. Grassl. Code Tables: Bounds on the Parameters of Various Types of Codes. Accessed: Mar. 24, 2024. [Online]. Available: https://www.codetables.de
[25]
Z. Heng, C. Ding, and W. Wang, “Optimal binary linear codes from maximal arcs,” IEEE Trans. Inf. Theory, vol. 66, no. 9, pp. 5387–5394, Sep. 2020.
[26]
Z. Heng, Q. Wang, and C. Ding, “Two families of optimal linear codes and their subfield codes,” IEEE Trans. Inf. Theory, vol. 66, no. 11, pp. 6872–6883, Nov. 2020.
[27]
F. Hernando and D. Ruano, “New linear codes from matrix-product codes with polynomial units,” Adv. Math. Commun., vol. 4, no. 3, pp. 363–367, 2010.
[28]
A. Hocquenghem, “Codes correcteurs d’erreurs,” Chiffres, vol. 2, pp. 147–156, Sep. 1959.
[29]
W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes. Cambridge, U.K.: Cambridge Univ. Press, 2003.
[30]
J. Justesen, “Class of constructive asymptotically good algebraic codes,” IEEE Trans. Inf. Theory, vol. IT-18, no. 5, pp. 652–656, Sep. 1972.
[31]
T. Kasami, “A Gilbert–Varshamov bound for quasi-cycle codes of rate 1/2 (Corresp.),” IEEE Trans. Inf. Theory, vol. IT-20, no. 5, p. 679, Sep. 1974.
[32]
N. Li, C. Li, T. Helleseth, C. Ding, and X. Tang, “Optimal ternary cyclic codes with minimum distance four and five,” Finite Fields Their Appl., vol. 30, pp. 100–120, Nov. 2014.
[33]
S. Ling and P. Sole, “Good self-dual quasi-cyclic codes exist,” IEEE Trans. Inf. Theory, vol. 49, no. 4, pp. 1052–1053, Apr. 2003.
[34]
J. H. van Lint, Introduction to Coding Theory, vol. 86. Berlin, Germany: Springer, 1999.
[35]
Y. Liu and X. Cao, “Four classes of optimal quinary cyclic codes,” IEEE Commun. Lett., vol. 24, no. 7, pp. 1387–1390, Jul. 2020.
[36]
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes (North-Holland Mathematical Library), vol. 16, 3rd ed., Amsterdam, The Netherlands: North Holland, 1977.
[37]
C. Martinez-Perez and W. Wille, “Is the class of cyclic codes asymptotically good?,” IEEE Trans. Inf. Theory, vol. 52, no. 2, pp. 696–700, Feb. 2006.
[38]
S. Noguchi, X.-N. Lu, M. Jimbo, and Y. Miao, “BCH codes with minimum distance proportional to code length,” SIAM J. Discrete Math., vol. 35, no. 1, pp. 179–193, Feb. 2021.
[39]
E. Prange, Cyclic Error-Correcting Codes in Two Symbols. Cambridge, MA, USA: Air Force Cambridge Research Labs, 1957.
[40]
A. M. Romanov, “On the number of q-ary quasi-perfect codes with covering radius 2,” Des., Codes Cryptogr., vol. 90, no. 8, pp. 1713–1719, Jun. 2022.
[41]
I. Siap, N. Aydin, and D. K. Ray-Chaudhuri, “New ternary quasi-cyclic codes with better minimum distances,” IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 1554–1558, Jul. 2000.
[42]
Z. Sun, C. Li, and C. Ding, “An infinite family of binary cyclic codes with best parameters,” IEEE Trans. Inf. Theory, vol. 70, no. 4, pp. 2411–2418, Apr. 2024.
[43]
Z. Sun and C. Ding, “Several families of ternary negacyclic codes and their duals,” IEEE Trans. Inf. Theory, vol. 70, no. 5, pp. 3226–3241, May 2024.
[44]
C. Tang and C. Ding, “Binary [n, n + 1/2] cyclic codes with good minimum distances,” IEEE Trans. Inf. Theory, vol. 68, no. 12, pp. 7842–7849, Dec. 2022.
[45]
T. J. Wagner, “A search technique for quasi-perfect codes,” Inf. Control, vol. 9, no. 1, pp. 94–99, Feb. 1966.
[46]
X. Wang, D. Zheng, and C. Ding, “Some punctured codes of several families of binary linear codes,” IEEE Trans. Inf. Theory, vol. 67, no. 8, pp. 5133–5148, Aug. 2021.
[47]
C. Xie, H. Chen, C. Ding, and Z. Sun, “Self-dual negacyclic codes with variable lengths and square-root-like lower bounds on the minimum distances,” IEEE Trans. Inf. Theory, vol. 70, no. 7, pp. 4879–4888, Jul. 2024.
[48]
A. Zeh and S. Ling, “Decoding of quasi-cyclic codes up to a new lower bound on the minimum distance,” in Proc. IEEE Int. Symp. Inf. Theory, Honolulu, HI, USA, Jul. 2014, pp. 2584–2588.
Index Terms
- Explicit Cyclic and Quasi-Cyclic Codes With Optimal, Best Known Parameters, and Large Relative Minimum Distances
Index terms have been assigned to the content through auto-classification.
Recommendations
Cyclic and Negacyclic Codes With Optimal and Best Known Minimum Distances
In this paper, we construct infinitely many families of distance-optimal binary BCH codes with the minimum distance 6 and an infinite family of distance-optimal quaternary BCH codes with the minimum distance 4. We also construct several infinite families ...
Another Infinite Family of Binary Cyclic Codes With Best Parameters Known
Cyclic codes are important in theory, as they are closely related to a number of areas of mathematics. Cyclic codes are also important in practice, as they have efficient encoding and decoding algorithms. An infinite family of cyclic codes over <inline-...
An Infinite Family of Binary Cyclic Codes With Best Parameters
Binary cyclic codes with parameters <inline-formula> <tex-math notation="LaTeX">$[n,(n+1)/2, d\geq \sqrt {n}]$ </tex-math></inline-formula> are very interesting, as their minimum distances have a square-root bound. The binary quadratic residue codes and ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
0018-9448 © 2024 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
Publisher
IEEE Press
Publication History
Published: 08 October 2024
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 11 Dec 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in