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, 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,n-2m,5]\) are quasi-perfect [24,25] (see also [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].
Primary Hierarchy
Parents
Binary BCH code
Children
The Golay code is equivalent to a BCH code with Bose distance 5 [18; Ch. 20].
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. (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
- 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.