## Description

Cyclic binary code of odd length \(n\) whose zeroes are consecutive powers of a primitive \(n\)th root of unity \(\alpha\) (see Cyclic-to-polynomial correspondence). 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=2^r-1\) for some \(r\geq 2\).

The code dimension is related to the multiplicative order of \(2\) modulo \(n\), i.e., the smallest integer \(m\) such that \(n\) divides \(2^m-1\). The dimension of a BCH code with \(\delta=2t+1\) is at least \(n-mt\). The field \(GF(2^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

## Decoding

## Realizations

## Notes

## Parents

## Children

- Golay code — The Golay code is equivalent to a BCH code with Bose distance 5 ([17], Ch. 20).
- \([2^r-1,2^r-r-1,3]\) Hamming code — Binary Hamming codes are binary primitive narrow-sense BCH codes [19; Corr. 5.1.5]. Binary Hamming codes are cyclic [22; Thm. 12.22].

## Cousins

- Quasi-perfect code — Only double error-correcting BCH codes \([2^m-1,n-2m,5]\) are quasi-perfect [23,24] (see also Ref. [17], Ch. 9).
- Griesmer code — The \([15,5,7]\) BCH code extended with a parity check saturates the Griesmer bound ([25], pg. 157).
- Preparata code — Preparata codes contain twice as many code words as the double-error-correcting BCH codes of the same length, which is the largest number of code words possible for given length and distance [26].
- Reed-Muller (RM) code — RM\(^*(r,m)\) codes are equivalent to subcodes of BCH codes of designed distance \(2^{m-r}-1\) while RM\((r,m)\) are subcodes of extended BCH codes of the same designed distance [17; Ch. 13].
- Error-correcting output code (ECOC) — BCH codes can be used as ECOCs [27].
- \(q\)-ary Hamming code — Some narrow sense BCH codes of length \(n=(q^r-1)/(q-1)\) such that \(\text{gcd}(r,q-1)=1\) are \(q\)-ary Hamming codes ([19], Thm. 5.1.4).
- Quantum data-syndrome (QDS) code — Primitive narrow-sense BCH codes can be used as the syndrome measurement codes of a QDS code [28]. This construction requires fewer measurements than a previous general construction [29].
- Qubit BCH code — Binary BCH codes are used to construct a subset of qubit BCH codes via the CSS construction.

## References

- [1]
- R. C. Bose and D. K. Ray-Chaudhuri, “On a class of error correcting binary group codes”, Information and Control 3, 68 (1960) DOI
- [2]
- R. C. Bose and D. K. Ray-Chaudhuri, “Further results on error correcting binary group codes”, Information and Control 3, 279 (1960) DOI
- [3]
- A. Hocquenghem, Codes correcteurs d'Erreurs, Chiffres (Paris), vol.2, pp.147-156, 1959.
- [4]
- W. Peterson, “Encoding and error-correction procedures for the Bose-Chaudhuri codes”, IEEE Transactions on Information Theory 6, 459 (1960) DOI
- [5]
- S. Arimoto, "Encoding and decoding of p-ary group codes and the correction system," Information Processing in Japan (in Japanese), vol. 2, pp. 320-325, Nov. 1961.
- [6]
- R.E. Blahut, Theory and practice of error-control codes, Addison-Wesley 1983.
- [7]
- J. Massey, “Shift-register synthesis and BCH decoding”, IEEE Transactions on Information Theory 15, 122 (1969) DOI
- [8]
- E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, 1968
- [9]
- H. Burton, “Inversionless decoding of binary BCH codes”, IEEE Transactions on Information Theory 17, 464 (1971) DOI
- [10]
- W. W. Peterson and E. J. Weldon, Error-correcting codes. MIT press 1972.
- [11]
- R. Gallager, Information Theory and Reliable Communication (Springer Vienna, 1972) DOI
- [12]
- Y. Sugiyama et al., “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]
- V. Guruswami and M. Sudan, “Improved decoding of Reed-Solomon and algebraic-geometry codes”, IEEE Transactions on Information Theory 45, 1757 (1999) DOI
- [15]
- 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
- [16]
- Cheung, K-M., and F. Pollara. "Phobos lander coding system: Software and analysis." The Telecommunications and Data Acquisition Report (1988).
- [17]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [18]
- S. Lin and D. J. Costello, Error Control Coding, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2004.
- [19]
- W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
- [20]
- 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.
- [21]
- 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
- [22]
- R. Hill. A First Course In Coding Theory. Oxford University Press, 1988.
- [23]
- D. Gorenstein, W. W. Peterson, and N. Zierler, “Two-error correcting Bose-Chaudhuri codes are quasi-perfect”, Information and Control 3, 291 (1960) DOI
- [24]
- T. Helleseth, “No primitive binary&lt;tex&gt;t&lt;/tex&gt;-error-correcting BCH code with&lt;tex&gt;t &gt; 2&lt;/tex&gt;is quasi-perfect (Corresp.)”, IEEE Transactions on Information Theory 25, 361 (1979) DOI
- [25]
- J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016) DOI
- [26]
- F. P. Preparata, “A class of optimum nonlinear double-error-correcting codes”, Information and Control 13, 378 (1968) DOI
- [27]
- T. G. Dietterich and G. Bakiri, “Solving Multiclass Learning Problems via Error-Correcting Output Codes”, (1995) arXiv:cs/9501101
- [28]
- E. Guttentag, A. Nemec, and K. R. Brown, “Robust Syndrome Extraction via BCH Encoding”, (2023) arXiv:2311.16044
- [29]
- Y. Fujiwara, “Ability of stabilizer quantum error correction to protect itself from its own imperfection”, Physical Review A 90, (2014) arXiv:1409.2559 DOI

## Page edit log

- Victor V. Albert (2022-08-04) — most recent
- Muhammad Junaid Aftab (2022-04-21)
- Nolan Coble (2021-12-15)
- Victor V. Albert (2021-12-15)
- Manasi Shingane (2021-12-05)

## Cite as:

“Binary BCH code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/bch

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/cyclic/bch.yml.