[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 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, 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,n-2m,5]\) are quasi-perfect [24,25] (see also Ref. [18], Ch. 9).
  • Griesmer code— The \([15,5,7]\) BCH code extended with a parity check saturates the Griesmer bound ([26], pg. 157).
  • Combinatorial design— A family of BCH codes supports an infinite family of combinatorial 4-designs [27,28].
  • 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 [29][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].
  • Error-correcting output code (ECOC)— BCH codes can be used as ECOCs [30].
  • 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 [31].
  • Generalized bicycle (GB) code— There exist examples of GB codes whose syndromes are protected by small BCH codes [32].

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 codeCyclic Linear \(q\)-ary Constacyclic Skew-cyclic ECC
Parents
Cyclic linear binary code
Bose–Chaudhuri–Hocquenghem (BCH) codeCyclic Linear \(q\)-ary 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^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 [33; Thm. 12.22].

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]
C. Ding, “Cyclic Codes over Finite Fields.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[5]
W. Peterson, “Encoding and error-correction procedures for the Bose-Chaudhuri codes”, IEEE Transactions on Information Theory 6, 459 (1960) DOI
[6]
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.
[7]
R. E. Blahut, Theory and practice of error-control codes, Addison-Wesley 1983.
[8]
J. Massey, “Shift-register synthesis and BCH decoding”, IEEE Transactions on Information Theory 15, 122 (1969) DOI
[9]
E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, 1968
[10]
H. Burton, “Inversionless decoding of binary BCH codes”, IEEE Transactions on Information Theory 17, 464 (1971) DOI
[11]
W. W. Peterson and E. J. Weldon, Error-correcting codes. MIT press 1972.
[12]
R. Gallager, Information Theory and Reliable Communication (Springer Vienna, 1972) DOI
[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]
R. McEliece, The Theory of Information and Coding (Cambridge University Press, 2002) DOI
[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]
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]
K.-M. Cheung and F. Pollara, “Phobos lander coding system: Software and analysis.” The Telecommunications and Data Acquisition Report (1988).
[18]
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[19]
S. Lin and D. J. Costello, Error Control Coding, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2004.
[20]
W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
[21]
W. C. Huffman, J.-L. Kim, and P. Solé, “Basics of coding theory.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[22]
M. Helmling, S. Scholl, F. Gensheimer, T. Dietz, K. Kraft, S. Ruzika, and N. Wehn. Database of Channel Codes and ML Simulation Results. URL, 2022.
[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. https://web.archive.org/web/20240420202309/https://mint.sbg.ac.at/desc_CCyclic-BCHBound.html.
[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]
T. Helleseth, “No primitive binaryt-error-correcting BCH code witht > 2is quasi-perfect (Corresp.)”, IEEE Transactions on Information Theory 25, 361 (1979) DOI
[26]
J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016) DOI
[27]
C. Ding and C. Tang, “Infinite families of near MDS codes holding \(t\)-designs”, (2019) arXiv:1910.08265
[28]
C. Tang and C. Ding, “An infinite family of linear codes supporting 4-designs”, (2020) arXiv:2001.00158
[29]
F. P. Preparata, “A class of optimum nonlinear double-error-correcting codes”, Information and Control 13, 378 (1968) DOI
[30]
T. G. Dietterich and G. Bakiri, “Solving Multiclass Learning Problems via Error-Correcting Output Codes”, (1995) arXiv:cs/9501101
[31]
Y. Fujiwara, “Block synchronization for quantum information”, Physical Review A 87, (2013) arXiv:1206.0260 DOI
[32]
P. Panteleev and G. Kalachev, “Degenerate Quantum LDPC Codes With Good Finite Length Performance”, Quantum 5, 585 (2021) arXiv:1904.02703 DOI
[33]
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

edit on this site

Zoo Code ID: bch

Cite as:
“Binary BCH code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/bch
BibTeX:
@incollection{eczoo_bch, title={Binary BCH code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, 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.), 2022. https://errorcorrectionzoo.org/c/bch

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