[Jump to code hierarchy]

Binary BCH code [1–3]

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 narrow-sense BCH code with \(\delta=2t+1\) is at least \(n-mt\). The field \(\mathbb{F}_{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

By the BCH bound, a BCH code with designed distance \(\delta\) has true 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 [4; Thm. 2.6.3].

Decoding

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

Realizations

Satellite communication [17]

Notes

See books [18–20][21; Sec. 1.14][4; Secs. 2.6-2.6.3] for expositions on BCH codes and code tables.See Kaiserslautern database [22] for explicit codes.See corresponding MinT database entry [23].

Cousins

  • Quasi-perfect code— Only double error-correcting BCH codes \([2^m-1,2^m-1-2m,5]\) are quasi-perfect [24,25] (see also [18; Ch. 9]).
  • Preparata code— Preparata codes contain twice as many codewords as the extended double-error-correcting BCH codes of the same length and minimum distance, and have the greatest possible number of codewords for this minimum distance [26][18; pg. 475].
  • 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 [18; Ch. 13].
  • \([16,5,8]\) first-order RM code— Extending the \([15,5,7]\) BCH code by a parity check yields the \([16,5,8]\) first-order RM code [18; Ch. 13, Thm. 11].
  • Error-correcting output code (ECOC)— BCH codes can be used as ECOCs [27].
  • \([[15,4,3]]\) quantum Hamming subcode— The \(X\)-type stabilizers of the \([[15,4,3]]\) code are generated by the \([15,7,5]\) BCH code.
  • Qubit BCH code— Binary BCH codes are used to construct a subset of qubit BCH codes via the CSS construction.
  • Quantum synchronizable code— BCH codes can be used to construct quantum synchronizable codes via the CSS construction [28,29].
  • Generalized bicycle (GB) code— There exist examples of GB codes whose syndromes are protected by small BCH codes [30].

Member of code lists

Primary Hierarchy

Classical Domain
Binary Kingdom
Binary codeECC
Binary group-orbit codeECC
Linear binary codeLinear \(q\)-ary Linear code over \(\mathbb{Z}_q\) ECC
Cyclic linear binary codeLinear \(q\)-ary Cyclic Constacyclic Skew-cyclic ECC
Parents
Cyclic linear binary code
Bose–Chaudhuri–Hocquenghem (BCH) codeLinear \(q\)-ary Cyclic Constacyclic Skew-cyclic ECC
Binary BCH code
Children
\([23, 12, 7]\) Golay code
The Golay code is equivalent to a BCH code with Bose distance 5 [18; Ch. 20].
\([2^m-1,m,2^{m-1}]\) simplex code
Binary simplex codes are BCH codes with \(b=0\) and designed distance \(2^{m-1}\), i.e., with zeros \(\alpha^0,\ldots,\alpha^{2^{m-1}-2}\) for a suitable primitive element \(\alpha\) [18; Ch. 7, Thm. 8 and Prob. 23].
\([2^r-1,2^r-r-1,3]\) Hamming code
Binary Hamming codes are binary primitive narrow-sense BCH codes [20; Corr. 5.1.5]. Binary Hamming codes can be written in cyclic form [31; Thm. 12.22].

References

  1. [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. [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. [3]

    A. Hocquenghem, Codes correcteurs d’Erreurs, Chiffres (Paris), vol.2, pp.147-156, 1959

  4. [4]

    C. Ding, “Cyclic Codes over Finite Fields”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 45-60 DOI

  5. [5]

    W. Peterson, “Encoding and error-correction procedures for the Bose-Chaudhuri codes”, IEEE Transactions on Information Theory 6, 459 (1960) DOI

  6. [6]

    S. Arimoto, “Encoding and decoding of p-ary group codes and the correction system”, Information Processing in Japan (in Japanese) 2, 320-325 (1961)

  7. [7]

    R. E. Blahut, Theory and Practice of Error-Control Codes (Addison-Wesley, 1983)

  8. [8]

    J. Massey, “Shift-register synthesis and BCH decoding”, IEEE Transactions on Information Theory 15, 122 (1969) DOI

  9. [9]

    E. R. Berlekamp, Algebraic Coding Theory (McGraw-Hill, 1968)

  10. [10]

    H. Burton, “Inversionless decoding of binary BCH codes”, IEEE Transactions on Information Theory 17, 464 (1971) DOI

  11. [11]

    W. W. Peterson and E. J. Weldon, Error-Correcting Codes (MIT Press, 1972)

  12. [12]

    R. Gallager, Information Theory and Reliable Communication (Springer Vienna, 1972) DOI

  13. [13]

    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

  14. [14]

    R. McEliece, The Theory of Information and Coding (Cambridge University Press, 2002) DOI

  15. [15]

    V. Guruswami and M. Sudan, “Improved decoding of Reed-Solomon and algebraic-geometry codes”, IEEE Transactions on Information Theory 45, 1757 (1999) DOI

  16. [16]

    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) 28 DOI

  17. [17]

    K.-M. Cheung and F. Pollara, “Phobos lander coding system: Software and analysis”, The Telecommunications and Data Acquisition Report (1988)

  18. [18]

    F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes (Elsevier, 1977)

  19. [19]

    S. Lin and D. J. Costello, Error Control Coding, 2nd ed. (Prentice-Hall, 2004)

  20. [20]

    W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI

  21. [21]

    W. C. Huffman, J.-L. Kim, and P. Solé, “Basics of coding theory”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 3-44 DOI

  22. [22]

    M. Helmling, S. Scholl, F. Gensheimer, T. Dietz, K. Kraft, S. Ruzika, and N. Wehn, Database of Channel Codes and ML Simulation Results, 2022 URL

  23. [23]

    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 URL

  24. [24]

    D. Gorenstein, W. W. Peterson, and N. Zierler, “Two-error correcting Bose-Chaudhuri codes are quasi-perfect”, Information and Control 3, 291 (1960) DOI

  25. [25]

    T. Helleseth, “No primitive binaryt-error-correcting BCH code witht > 2is quasi-perfect (Corresp.)”, IEEE Transactions on Information Theory 25, 361 (1979) DOI

  26. [26]

    F. P. Preparata, “A class of optimum nonlinear double-error-correcting codes”, Information and Control 13, 378 (1968) DOI

  27. [27]

    T. G. Dietterich and G. Bakiri, “Solving Multiclass Learning Problems via Error-Correcting Output Codes”, (1995) arXiv:cs/9501101

  28. [28]

    Y. Fujiwara, “Block synchronization for quantum information”, Physical Review A 87, (2013) arXiv:1206.0260 DOI

  29. [29]

    Y. Fujiwara, V. D. Tonchev, and T. W. H. Wong, “Algebraic techniques in designing quantum synchronizable codes”, Physical Review A 88, (2013) arXiv:1304.0502 DOI

  30. [30]

    P. Panteleev and G. Kalachev, “Degenerate Quantum LDPC Codes With Good Finite Length Performance”, Quantum 5, 585 (2021) arXiv:1904.02703 DOI

  31. [31]

    R. Hill, A First Course in Coding Theory (Oxford University Press, 1988)

Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

— see instructions

Zoo Code ID: bch

Cite as:
“Binary BCH code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/bch, arXiv:2606.11484
BibTeX:
@incollection{eczoo_bch,
title={Binary BCH code},
booktitle={The Error Correction Zoo},
year={2026},
editor={Albert, Victor V. and Faist, Philippe},
eprint={2606.11484},
doi={10.48550/arXiv.2606.11484},
url={https://errorcorrectionzoo.org/c/bch}
}
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/bch

Cite as:

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

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