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 ([16], Ch. 20).
- Hamming code — Binary Hamming codes are binary primitive narrow-sense BCH codes ([18], Corr. 5.1.5). Binary Hamming codes are cyclic ([21], Thm. 12.22).
- Reed-Muller (RM) code — RM\((r,m)\) codes are subcodes of BCH codes of designed distance \(2^{m-r}-1\) ([16], Ch. 13).
Cousins
- Quasi-perfect code — Only double error-correcting BCH codes \([2^m-1,n-2m,5]\) are quasi-perfect [22][23] (see also Ref. [16], Ch. 9).
- Griesmer code — The \([15,5,7]\) BCH code extended with a parity check saturates the Griesmer bound ([24], pg. 157).
- \(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 ([18], Thm. 5.1.4).
- 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-geometric codes”, Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280) DOI
- [15]
- Cheung, K-M., and F. Pollara. "Phobos lander coding system: Software and analysis." The Telecommunications and Data Acquisition Report (1988).
- [16]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [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]
- R. Hill. A First Course In Coding Theory. Oxford University Press, 1988.
- [22]
- D. Gorenstein, W. W. Peterson, and N. Zierler, “Two-error correcting Bose-Chaudhuri codes are quasi-perfect”, Information and Control 3, 291 (1960) DOI
- [23]
- T. Helleseth, “No primitive binary<tex>t</tex>-error-correcting BCH code with<tex>t > 2</tex>is quasi-perfect (Corresp.)”, IEEE Transactions on Information Theory 25, 361 (1979) DOI
- [24]
- J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016) 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/tree/main/codes/classical/bits/cyclic/bch.yml.