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

## Description

Cyclic \(q\)-ary code, with \(n\) and \(q\) relatively coprime, 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\).

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

## Rate

## Decoding

## Realizations

## Notes

## Parents

- Cyclic linear \(q\)-ary code
- Generalized RS (GRS) code — BCH codes are subfield subcodes of GRS codes.
- Twisted BCH code — Twisted BCH codes are obtained from \(q\)-ary BCH codes via various lengthening and extension procedures.

## Child

## Cousins

- Classical Goppa code — Narrow-sense BCH codes are Goppa codes with \(L=\{1,\alpha^{-1},\cdots,\alpha^{1-n}\}\) and \(G(x)=x^{\delta-1}\) ([18], pg. 522).
- \(q\)-ary linear LTC — Duals of BCH codes are locally testable [21].
- Justesen code — Using more general BCH codes instead of RS codes can improve the parameters of the Justesen codes [22].
- Reed-Solomon (RS) code — Narrow-sense RS codes are BCH codes [23; Remark 15.3.21][18; Thms. 5.2.1 and 5.2.3]. Their minimal distance is equal to their designed distance [24; pg. 81]. Moreover, an RS code can be represented as a union of cosets, with each coset being an interleaver of several binary BCH codes [25].
- 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 [26; Exam. 1].
- Galois-qudit BCH code

## 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 et al., “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]
- V. Guruswami and M. Sudan, “Improved decoding of Reed-Solomon and algebraic-geometry codes”, IEEE Transactions on Information Theory 45, 1757 (1999) DOI
- [14]
- V. Guruswami and M. Sudan, “Improved decoding of Reed-Solomon and algebraic-geometric codes”, Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280) DOI
- [15]
- R. Koetter and A. Vardy, “Algebraic soft-decision decoding of reed-solomon codes”, IEEE Transactions on Information Theory 49, 2809 (2003) DOI
- [16]
- S. Zhu, Z. Sun, and X. Kai, “A Class of Narrow-Sense BCH Codes”, IEEE Transactions on Information Theory 65, 4699 (2019) DOI
- [17]
- S. Lin and D. J. Costello, Error Control Coding, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2004.
- [18]
- W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
- [19]
- 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.
- [20]
- 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. http://mint.sbg.ac.at/desc_CCyclic-BCHBound.html
- [21]
- T. Kaufman and S. Litsyn, “Almost Orthogonal Linear Codes are Locally Testable”, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05) DOI
- [22]
- E. J. Weldon, “Justesen’s construction--The low-rate case (Corresp.)”, IEEE Transactions on Information Theory 19, 711 (1973) DOI
- [23]
- A. Couvreur, H. Randriambololona, "Algebraic Geometry Codes and Some Applications." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [24]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [25]
- A. Vardy and Y. Be’ery, “Bit-level soft-decision decoding of Reed-Solomon codes”, IEEE Transactions on Communications 39, 440 (1991) DOI
- [26]
- S. A. Aly, A. Klappenecker, and P. K. Sarvepalli, “Subsystem Codes”, (2006) arXiv:quant-ph/0610153

## 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