research-article

BCH Codes with Minimum Distance Proportional to Code Length

Authors:

Satoshi Noguchi,

Masakazu Jimbo,

Ying MiaoAuthors Info & Claims

SIAM Journal on Discrete Mathematics, Volume 35, Issue 1

Pages 179 - 193

https://doi.org/10.1137/19M1260876

Published: 01 January 2021 Publication History

Abstract

BCH codes are among the best practical cyclic codes widely used in consumer electronics, communication systems, and storage devices. However, not much is known about BCH codes with large minimum distance. In this paper, we consider narrow-sense BCH codes of length $n = \frac{q^m-1}{N}$ with designed distance $\delta = \frac{s}{q-1}n$ proportional to $n$, where $N$ divides $\frac{q^m-1}{q-1}$ and $1 \le s \le q-1$. We determine both their dimensions and minimum distances. In particular, when $N=1$, the codes are primitive, with minimum distance $d=\frac{s}{q-1}(q^m-1)$ and dimension $k = (q-s)^m$. The general result on code dimensions is achieved by applying generating functions and inverse discrete Fourier transforms to an enumeration problem.

References

[1]

S. A. Aly, A. Klappenecker, and P. K. Sarvepalli, On quantum and classical BCH codes, IEEE Trans. Inform. Theory, 53 (2007), pp. 1183--1188.

[2]

D. Augot, P. Charpin, and N. Sendrier, Studying the locator polynomials of minimum weight codewords of BCH codes, IEEE Trans. Inform. Theory, 38 (1992), pp. 960--973.

[3]

D. Augot and N. Sendrier, Idempotents and the BCH bound, IEEE Trans. Inform. Theory, 40 (1994), pp. 204--207.

[4]

E. R. Berlekamp, The enumeration of information symbols in BCH codes, Bell Syst. Tech. J., 46 (1967), pp. 1861--1880.

[5]

E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, New York, 1968.

[6]

A. Betten, M. Braun, H. Fripertinger, A. Kerber, A. Kohnert, and A. Wassermann, Error-Correcting Linear Codes: Classification by Isometry and Applications, Springer-Verlag, Berlin, 2006.

[7]

R. C. Bose and D. K. Ray-Chaudhuri, Further results on error correcting binary group codes, Inform. and Control, 3 (1960), pp. 279--290.

[8]

R. C. Bose and D. K. Ray-Chaudhuri, On a class of error correcting binary group codes, Inform. and Control, 3 (1960), pp. 68--79.

[9]

P. Charpin, On a class of primitive BCH-codes, IEEE Trans. Inform. Theory, 36 (1990), pp. 222--228.

[10]

P. Charpin, Weight distributions of cosets of two-error-correcting binary BCH codes, extended or not, IEEE Trans. Inform. Theory, 40 (1994), pp. 1425--1442.

[11]

P. Charpin, Open Problems on Cyclic Codes, in Handbook of Coding Theory, Vol. 1, V. S. Pless and W. C. Huffman, eds., North-Holland, Amsterdam, 1998, pp. 963--1063.

[12]

Y. Desaki, T. Fujiwara, and T. Kasami, The weight distributions of extended binary primitive BCH codes of length 128, IEEE Trans. Inform. Theory, 43 (1997), pp. 1364--1371.

[13]

C. Ding, Codes from Difference Sets, World Scientific, Singapore, 2015.

[14]

C. Ding, Parameters of several classes of BCH codes, IEEE Trans. Inform. Theory, 61 (2015), pp. 5322--5330.

[15]

C. Ding, X. Du, and Z. Zhou, The Bose and minimum distance of a class of BCH codes, IEEE Trans. Inform. Theory, 61 (2015), pp. 2351--2356.

[16]

C. Ding, C. Fan, and Z. Zhou, The dimension and minimum distance of two classes of primitive BCH codes, Finite Fields Appl., 45 (2017), pp. 237--263.

[17]

D. Gorenstein and N. Zierler, A class of error-correcting codes in $p^m$ symbols, J. Soc. Ind. Appl. Math., 9 (1961), pp. 207--214.

[18]

M. Grassl, Bounds on the Minimum Distance of Linear Codes and Quantum Codes, available online at http://www.codetables.de, 2007 (accessed on 2020-10-06).

[19]

K. Guenda, Dimension and minimum distance of a class of BCH codes, Ann. Sci. Math. Québec, 32 (2008), pp. 57--62.

[20]

A. Hocquenghem, Codes correcteurs d'erreurs, Chiffres, 2 (1959), pp. 147--156.

[21]

W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge University Press, Cambridge, UK, 2003.

[22]

T. Kasami and S. Lin, Some results on the minimum weight of primitive BCH codes (corresp.), IEEE Trans. Inform. Theory, 18 (1972), pp. 824--825.

[23]

T. Kasami and N. Tokura, Some remarks on BCH bounds and minimum weights of binary primitive BCH codes, IEEE Trans. Inform. Theory, 15 (1969), pp. 408--413.

[24]

C. Li, C. Ding, and S. Li, LCD cyclic codes over finite fields, IEEE Trans. Inform. Theory, 63 (2017), pp. 4344--4356.

[25]

C. Li, P. Wu, and F. Liu, On two classes of primitive BCH codes and some related codes, IEEE Trans. Inform. Theory, 65 (2019), pp. 3830--3840.

[26]

S. Li, The minimum distance of some narrow-sense primitive BCH codes, SIAM J. Discrete Math., 31 (2017), pp. 2530--2569, https://doi.org/10.1137/16M1108431.

[27]

S. Li, C. Ding, M. Xiong, and G. Ge, Narrow-sense BCH codes over GF($q$) with length $n=\frac{q^m-1}{q-1}$, IEEE Trans. Inform. Theory, 63 (2017), pp. 7219--7236.

[28]

S. Li, C. Li, C. Ding, and H. Liu, Two families of LCD BCH codes, IEEE Trans. Inform. Theory, 63 (2017), pp. 5699--5717.

[29]

X. Ling, S. Mesnager, Y. Qi, and C. Tang, A class of narrow-sense BCH codes over $\mathbb{F}_q$ of length $\frac{q^m-1}{2}$, Des. Codes, Cryptogr., 88 (2020), pp. 413--427, https://doi.org/10.1007/s10623-019-00691-0.

[30]

H. Liu, C. Ding, and C. Li, Dimensions of three types of BCH codes over GF$(q)$, Discrete Math., 340 (2017), pp. 1910--1927.

[31]

Y. Liu, R. Li, Q. Fu, L. Lu, and Y. Rao, Some binary BCH codes with length $n= 2^m+ 1$, Finite Fields Appl., 55 (2019), pp. 109--133.

[32]

Y. Liu, R. Li, G. Guo, and J. Wang, Some nonprimitive BCH codes and related quantum codes, IEEE Trans. Inform. Theory, 65 (2019), pp. 7829--7839.

[33]

Y. Liu, R. Li, L. Guo, and H. Song, Dimensions of Nonbinary Antiprimitive BCH Codes and Some Conjectures, preprint, https://arxiv.org/abs/1712.06842, 2018.

[34]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977.

[35]

H. B. Mann, On the number of information symbols in Bose-Chaudhuri codes, Inform. and Control, 5 (1962), pp. 153--162.

[36]

W. W. Peterson, Some new results on finite fields with applications to BCH codes, in Combinatorial Mathematics and Its Applications, R. C. Bose and T. A. Dowling, eds., University of North Carolina Press, Chapel Hill, NC, 1969, Chap. 9.

[37]

V. Pless, Introduction to the Theory of Error-Correcting Codes, 3rd ed., John Wiley & Sons, New York, 1998.

[38]

N. J. A. Sloane, On Single-deletion-correcting Codes, in Codes and Designs, K. T. Arasu and A. Seress, eds., Walter de Gruyter, Berlin, 2002, pp. 273--291.

[39]

P. Wu, C. Li, and W. Peng, On some cyclic codes of length $\frac{q^{2m}- 1}{q+ 1}$, Finite Fields Appl., 60 (2019), p. 101581.

[40]

F. Yan, A Construction for $q$-ary Cyclic Codes with Large Minimum Distance, Master's thesis, Graduate School of Information Science, Nagoya University, 2012.

[41]

H. Yan, A class of primitive BCH codes and their weight distribution, Appl. Algebra Engrg. Comm. Comput., 29 (2018), pp. 1--11.

[42]

H. Yan, H. Liu, C. Li, and S. Yang, Parameters of LCD BCH codes with two lengths, Adv. Math. Commun., 12 (2018), pp. 579--594.

[43]

D. Yue and G. Feng, Minimum cyclotomic coset representatives and their applications to BCH codes and Goppa codes, IEEE Trans. Inform. Theory, 46 (2000), pp. 2625--2628.

[44]

D. Yue and Z. Hu, On the dimension and minimum distance of BCH codes over GF$(q)$, J. Electronics (China), 13 (1996), pp. 216--221.

[45]

D. Yue and H. Zhu, On the minimum distance of composite-length BCH codes, IEEE Commun. Lett., 3 (1999), pp. 269--271.

[46]

S. Zhu, Z. Sun, and X. Kai, A class of narrow-sense BCH codes, IEEE Trans. Inform. Theory, 65 (2019), pp. 4699--4714.

Cited By

Sun ZLi CDing C(2024)An Infinite Family of Binary Cyclic Codes With Best ParametersIEEE Transactions on Information Theory10.1109/TIT.2023.330773270:4(2411-2418)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1109/TIT.2023.3307732
Fan MLi CDing C(2023)The Hermitian Dual Codes of Several Classes of BCH CodesIEEE Transactions on Information Theory10.1109/TIT.2023.325712369:7(4484-4497)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1109/TIT.2023.3257123
Dong SLi CMesnager SQian H(2023)Parameters of Squares of Primitive Narrow-Sense BCH Codes and Their ComplementsIEEE Transactions on Information Theory10.1109/TIT.2023.325589969:8(5017-5031)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/TIT.2023.3255899

Recommendations

The Minimum Distance of Some Narrow-Sense Primitive BCH Codes

Due to wide applications of BCH codes, the determination of their minimum distance is of great interest. However, this is a very challenging problem for which few theoretical results have been reported in the last four decades. Even for the narrow-sense ...
Dimensions of nonbinary antiprimitive BCH codes and some conjectures
Abstract
Bose-Chaudhuri-Hocquenghem (BCH) codes have been intensively investigated. Even so, there is only a little known about primitive BCH codes, let alone non-primitive ones. In this paper, let q > 2 be a prime power, the dimension of a ...
Two families of BCH codes and new quantum codes

In this paper, two families of non-narrow-sense (NNS) BCH codes of lengths $$n=\frac{q^{2m}-1}{q^2-1}$$n=q2m-1q2-1 and $$n=\frac{q^{2m}-1}{q+1}$$n=q2m-1q+1 ($$m\ge 3)$$m?3) over the finite field $$\mathbf {F}_{q^2}$$Fq2 are studied. The maximum designed ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Discrete Mathematics

SIAM Journal on Discrete Mathematics Volume 35, Issue 1

DOI:10.1137/sjdmec.35.1

Issue’s Table of Contents

© 2021, Society for Industrial and Applied Mathematics.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 2021

Author Tags

Author Tag

94B15

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sun ZLi CDing C(2024)An Infinite Family of Binary Cyclic Codes With Best ParametersIEEE Transactions on Information Theory10.1109/TIT.2023.330773270:4(2411-2418)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1109/TIT.2023.3307732
Fan MLi CDing C(2023)The Hermitian Dual Codes of Several Classes of BCH CodesIEEE Transactions on Information Theory10.1109/TIT.2023.325712369:7(4484-4497)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1109/TIT.2023.3257123
Dong SLi CMesnager SQian H(2023)Parameters of Squares of Primitive Narrow-Sense BCH Codes and Their ComplementsIEEE Transactions on Information Theory10.1109/TIT.2023.325589969:8(5017-5031)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/TIT.2023.3255899
Gong BDing CLi C(2022)The Dual Codes of Several Classes of BCH CodesIEEE Transactions on Information Theory10.1109/TIT.2021.312593368:2(953-964)Online publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1109/TIT.2021.3125933

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.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents