Bose–Chaudhuri–Hocquenghem (BCH) code

Bose–Chaudhuri–Hocquenghem (BCH) code[1]

Description

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 are powers of the form \(\{b,b+s,b+2s,\cdots,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 \(GF(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, 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; pg. 269].

Decoding

Berlekamp-Massey decoder with runtime of order \(O(n^2)\) [3–5] and modification by Burton [6]; see also [7,8].Gorenstein-Peterson-Zierler decoder with runtime of order \(O(n^3)\) [1,9] (see exposition in Ref. [10]).Sugiyama et al. modification of the extended Euclidean algorithm [11,12].

Realizations

DVDs, disk drives, and two-dimensional bar codes [13].

Notes

See books [2,14,15] for expositions on BCH codes and code tables.See Kaiserslautern database [16] for explicit codes.See corresponding MinT database entry [17].

Cousins

\(q\)-ary linear LTC— Duals of BCH codes are locally testable [18].
Justesen code— Using more general BCH codes instead of RS codes can improve the parameters of the Justesen codes [19].
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 [20]. BCH codes are subfield subcodes of RS codes.
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 [21; Exam. 1].
Galois-qudit BCH code

Member of code lists

Primary Hierarchy

Classical Domain

Galois-field Kingdom

\(q\)-ary codeECC

Additive \(q\)-ary codeECC

Linear \(q\)-ary codeECC

Alternant code

Chien-Choy generalized BCH (GBCH) code

Parents

Chien-Choy generalized BCH (GBCH) code

\(q\)-ary BCH codes are a special case of GBCH codes [2; Ch. 12].

Cyclic linear \(q\)-ary codeLinear \(q\)-ary Cyclic Constacyclic Skew-cyclic ECC

Twisted BCH codeECC

Twisted BCH codes are obtained from \(q\)-ary BCH codes via various lengthening and extension procedures.

Bose–Chaudhuri–Hocquenghem (BCH) code

Children

Binary BCH code

Narrow-sense RS code

Narrow-sense RS codes are \(q\)-ary BCH codes [22; Remark 15.3.21][15; Thms. 5.2.1 and 5.2.3]. Their minimal distance is equal to their designed distance [23; pg. 81].

Primitive narrow-sense BCH code

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]: F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[3]: E. Berlekamp, “Nonbinary BCH decoding (Abstr.)”, IEEE Transactions on Information Theory 14, 242 (1968) DOI
[4]: J. Massey, “Shift-register synthesis and BCH decoding”, IEEE Transactions on Information Theory 15, 122 (1969) DOI
[5]: E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, 1968
[6]: H. Burton, “Inversionless decoding of binary BCH codes”, IEEE Transactions on Information Theory 17, 464 (1971) DOI
[7]: W. W. Peterson and E. J. Weldon, Error-correcting codes. MIT press 1972.
[8]: R. Gallager, Information Theory and Reliable Communication (Springer Vienna, 1972) DOI
[9]: W. Peterson, “Encoding and error-correction procedures for the Bose-Chaudhuri codes”, IEEE Transactions on Information Theory 6, 459 (1960) DOI
[10]: R.E. Blahut, Theory and practice of error-control codes, Addison-Wesley 1983.
[11]: 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
[12]: R. McEliece, The Theory of Information and Coding (Cambridge University Press, 2002) DOI
[13]: S. Zhu, Z. Sun, and X. Kai, “A Class of Narrow-Sense BCH Codes”, IEEE Transactions on Information Theory 65, 4699 (2019) DOI
[14]: S. Lin and D. J. Costello, Error Control Coding, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2004.
[15]: W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
[16]: Michael Helmling, Stefan Scholl, Florian Gensheimer, Tobias Dietz, Kira Kraft, Stefan Ruzika, and Norbert Wehn. Database of Channel Codes and ML Simulation Results. URL, 2022.
[17]: Rudolf Schürer and Wolfgang Ch. Schmid. “Cyclic Codes (BCH-Bound).” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2015-09-03. https://mint.sbg.ac.at/desc_CCyclic-BCHBound.html
[18]: 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
[19]: E. J. Weldon, “Justesen’s construction--The low-rate case (Corresp.)”, IEEE Transactions on Information Theory 19, 711 (1973) DOI
[20]: A. Vardy and Y. Be’ery, “Bit-level soft-decision decoding of Reed-Solomon codes”, IEEE Transactions on Communications 39, 440 (1991) DOI
[21]: S. A. Aly, A. Klappenecker, and P. K. Sarvepalli, “Subsystem Codes”, (2006) arXiv:quant-ph/0610153
[22]: A. Couvreur, H. Randriambololona, "Algebraic Geometry Codes and Some Applications." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[23]: 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

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/q-ary_digits/alternant/bch/q-ary_bch.yml.