Bose–Chaudhuri–Hocquenghem (BCH) code[1]
Description
A cyclic \(q\)-ary code, with \(n\) and \(q\) relatively prime, whose zeroes are consecutive powers of a primitive \(n\)th root of unity \(\alpha\).
More precisely, the generator polynomial of a BCH code of designed distance \(\delta\geq 1\) is the lowest-degree monic polynomial with zeroes \(\{\alpha^b,\alpha^{b+1},\cdots,\alpha^{b+\delta-2}\}\) for some \(b\geq 0\). BCH codes are called narrow-sense when \(b=1\), and are called primitive when \(n=q^r-1\) for some \(r\geq 2\). More general BCH codes can be defined for zeroes of the form \(\{\alpha^b,\alpha^{b+s},\alpha^{b+2s},\cdots,\alpha^{b+(\delta-2)s}\}\), where gcd\((s,n)=1\).
The code dimension is related to the multiplicative order of \(q\) modulo \(n\), i.e., the smallest integer \(m\) such that \(n\) divides \(q^m-1\). The dimension of a BCH code is at least \(n-m(\delta-1)\). The field \(\mathbb{F}_{q^m}\) is the smallest field containing the above root of unity \(\alpha\), and is the splitting field of the polynomial \(x^n-1\) (see Cyclic-to-polynomial correspondence).
Protection
By the BCH bound, a BCH code with designed distance \(\delta\) has true minimum distance \(d\geq\delta\). BCH codes with different designed distances may coincide, and the largest possible designed distance for a given code is the Bose distance; the true distance may still be larger than that.Rate
Primitive BCH codes are asymptotically bad [2; Thm. 2.6.3][3; pg. 269].Decoding
Berlekamp-Massey decoder with runtime of order \(O(n^2)\) [4–6] and modification by Burton [7]; see also [8,9].Gorenstein-Peterson-Zierler decoder with runtime of order \(O(n^3)\) [1,10] (see exposition in Ref. [11]).Sugiyama et al. modification of the extended Euclidean algorithm [12,13].Realizations
DVDs, disk drives, and two-dimensional bar codes [14].Notes
See books [3,15,16][2; Secs. 2.6-2.6.3] for expositions on BCH codes and code tables.See Kaiserslautern database [17] for explicit codes.See corresponding MinT database entry [18].Cousins
- Twisted BCH code— Twisted BCH codes are obtained from \(q\)-ary BCH codes via various lengthening and extension procedures.
- \(q\)-ary linear LTC— Duals of BCH codes are locally testable [19].
- Linear code over \(\mathbb{Z}_q\)— BCH codes for \(q=p\) prime field can also work as codes over the Lee metric [20].
- Justesen code— Using more general BCH codes instead of RS codes can improve the parameters of the Justesen codes [21].
- Skew-cyclic code— There exist skew-BCH codes, which are skew-cyclic versions of BCH codes [22].
- Reed-Solomon (RS) code— An RS code can be represented as a union of cosets, with each coset being an interleaver of several binary BCH codes [23]. BCH codes are subfield subcodes of RS codes, while primitive RS codes are primitive BCH codes [2; Sec. 2.6].
- \(q\)-ary Hamming code— When \(\gcd(r,q-1)=1\), \(q\)-ary Hamming codes are narrow-sense BCH codes [24; Exam. 16.4.10][16; Thm. 5.1.4], which are cyclic [3; pg. 194][2; Exam. 2.5.1].
- Qubit BCH code— BCH codes are used to construct qubit BCH codes via the CSS construction or the Hermitian construction.
- Subsystem qubit stabilizer code— BCH codes yield subsystem stabilizer codes via the subsystem extension of the Hermitian construction to subsystem codes [25; Exam. 1].
- Galois-qudit BCH code— Galois-qudit BCH codes are quantum analogues of q-ary BCH codes.
Primary Hierarchy
Parents
\(q\)-ary BCH codes are a special case of GBCH codes [3; Ch. 12].
Bose–Chaudhuri–Hocquenghem (BCH) code
Children
Narrow-sense RS codes are \(q\)-ary BCH codes [26; Remark 15.3.21][16; Thms. 5.2.1 and 5.2.3]. Their minimal distance is equal to their designed distance [27; pg. 81].
BCH codes are called narrow-sense when \(b=1\), and are called primitive when \(n=q^r-1\) for some \(r\geq 2\).
References
- [1]
- D. Gorenstein and N. Zierler, “A Class of Error-Correcting Codes in \(p^m \) Symbols”, Journal of the Society for Industrial and Applied Mathematics 9, 207 (1961) DOI
- [2]
- C. Ding, “Cyclic Codes over Finite Fields.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [3]
- F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes (Elsevier, 1977)
- [4]
- E. Berlekamp, “Nonbinary BCH decoding (Abstr.)”, IEEE Transactions on Information Theory 14, 242 (1968) DOI
- [5]
- J. Massey, “Shift-register synthesis and BCH decoding”, IEEE Transactions on Information Theory 15, 122 (1969) DOI
- [6]
- E. R. Berlekamp, Algebraic Coding Theory (McGraw-Hill, 1968)
- [7]
- H. Burton, “Inversionless decoding of binary BCH codes”, IEEE Transactions on Information Theory 17, 464 (1971) DOI
- [8]
- W. W. Peterson and E. J. Weldon, Error-Correcting Codes (MIT Press, 1972)
- [9]
- R. Gallager, Information Theory and Reliable Communication (Springer Vienna, 1972) DOI
- [10]
- W. Peterson, “Encoding and error-correction procedures for the Bose-Chaudhuri codes”, IEEE Transactions on Information Theory 6, 459 (1960) DOI
- [11]
- R. E. Blahut, Theory and Practice of Error-Control Codes (Addison-Wesley, 1983)
- [12]
- Y. Sugiyama, M. Kasahara, S. Hirasawa, and T. Namekawa, “A method for solving key equation for decoding goppa codes”, Information and Control 27, 87 (1975) DOI
- [13]
- R. McEliece, The Theory of Information and Coding (Cambridge University Press, 2002) DOI
- [14]
- S. Zhu, Z. Sun, and X. Kai, “A Class of Narrow-Sense BCH Codes”, IEEE Transactions on Information Theory 65, 4699 (2019) DOI
- [15]
- S. Lin and D. J. Costello, Error Control Coding, 2nd ed. (Prentice-Hall, 2004)
- [16]
- W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
- [17]
- M. Helmling, S. Scholl, F. Gensheimer, T. Dietz, K. Kraft, S. Ruzika, and N. Wehn. Database of Channel Codes and ML Simulation Results. URL, 2022
- [18]
- R. Schürer and W. Ch. Schmid. “Cyclic Codes (BCH-Bound).” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2015-09-03. https://web.archive.org/web/20240420202309/https://mint.sbg.ac.at/desc_CCyclic-BCHBound.html
- [19]
- T. Kaufman and S. Litsyn, “Almost Orthogonal Linear Codes are Locally Testable”, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05) 317 DOI
- [20]
- R. M. Roth and P. H. Siegel, “Lee-metric BCH codes and their application to constrained and partial-response channels”, IEEE Transactions on Information Theory 40, 1083 (1994) DOI
- [21]
- E. J. Weldon, “Justesen’s construction–The low-rate case (Corresp.)”, IEEE Transactions on Information Theory 19, 711 (1973) DOI
- [22]
- D. Boucher, W. Geiselmann, and F. Ulmer, “Skew-cyclic codes”, (2006) arXiv:math/0604603
- [23]
- A. Vardy and Y. Be’ery, “Bit-level soft-decision decoding of Reed-Solomon codes”, IEEE Transactions on Communications 39, 440 (1991) DOI
- [24]
- W. Willems, “Codes in Group Algebras.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [25]
- S. A. Aly, A. Klappenecker, and P. K. Sarvepalli, “Subsystem Codes”, (2006) arXiv:quant-ph/0610153
- [26]
- A. Couvreur, H. Randriambololona, “Algebraic Geometry Codes and Some Applications.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [27]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
Page edit log
- Victor V. Albert (2022-07-13) — most recent
- Muhammad Junaid Aftab (2022-04-21)
Cite as:
“Bose–Chaudhuri–Hocquenghem (BCH) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/q-ary_bch