Bose–Chaudhuri–Hocquenghem (BCH) code [1]
Description
A cyclic \(q\)-ary code, with \(n\) and \(q\) relatively prime, whose zeroes are consecutive powers of a primitive \(n\)th root of unity \(\alpha\).
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=q^r-1\) for some \(r\geq 2\). More general BCH codes can be defined for zeroes of the form \(\{\alpha^b,\alpha^{b+s},\alpha^{b+2s},\cdots,\alpha^{b+(\delta-2)s}\}\), where gcd\((s,n)=1\).
The code dimension is related to the multiplicative order of \(q\) modulo \(n\), i.e., the smallest integer \(m\) such that \(n\) divides \(q^m-1\). The dimension of a BCH code is at least \(n-m(\delta-1)\). The field \(\mathbb{F}_{q^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 minimum 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.Decoding
Berlekamp-Massey decoder with runtime of order \(O(n^2)\) [4–6] and modification by Burton [7]; see also [8,9].Gorenstein-Peterson-Zierler decoder with runtime of order \(O(n^3)\) [1,10] (see exposition in Ref. [11]).Sugiyama et al. modification of the extended Euclidean algorithm [12,13].Realizations
DVDs, disk drives, and two-dimensional bar codes [14].Notes
See books [3,15,16][2; Secs. 2.6-2.6.3] for expositions on BCH codes and code tables.See Kaiserslautern database [17] for explicit codes.See corresponding MinT database entry [18].Cousins
- Twisted BCH code— Twisted BCH codes are obtained from \(q\)-ary BCH codes via various lengthening and extension procedures.
- \(q\)-ary linear LTC— Duals of BCH codes are locally testable [19].
- Linear code over \(\mathbb{Z}_q\)— BCH codes over a prime field \(\mathbb{F}_p\) can also work as codes over the Lee metric [20].
- Combinatorial design— Narrow-sense BCH codes of length \(q+1\) over \(\mathbb{F}_q\) with designed distance four support an infinite family of combinatorial 4-designs for \(q=2^{2s+1}\) [21]. Such codes with designed distance three are near MDS and support infinite families of 3-designs for \(q=3^s\) and of 2-designs for \(q=2^{2s}\) [22].
- Justesen code— Using more general BCH codes instead of RS codes can improve the parameters of the Justesen codes [23].
- Skew-cyclic code— There exist skew-BCH codes, which are skew-cyclic versions of BCH codes [24].
- Reed-Solomon (RS) code— An RS code can be represented as a union of cosets, with each coset being an interleaver of several binary BCH codes [25]. BCH codes are subfield subcodes of RS codes, while primitive RS codes are primitive BCH codes [2; Sec. 2.6].
- \(q\)-ary Hamming code— When \(\gcd(r,q-1)=1\), \(q\)-ary Hamming codes are narrow-sense BCH codes [26; Exam. 16.4.10][16; Thm. 5.1.4], which are cyclic [3; pg. 194][2; Exam. 2.5.1].
- Qubit BCH code— BCH codes are used to construct qubit BCH codes via the CSS construction or the Hermitian construction.
- Subsystem qubit stabilizer code— BCH codes yield subsystem stabilizer codes via the subsystem extension of the Hermitian construction to subsystem codes [27; Exam. 1].
- Galois-qudit BCH code— Galois-qudit BCH codes are quantum analogues of q-ary BCH codes.
Primary Hierarchy
References
- [1]
D. Gorenstein and N. Zierler, “A Class of Error-Correcting Codes in \(p^m \) Symbols”, Journal of the Society for Industrial and Applied Mathematics 9, 207 (1961) DOI
- [2]
C. Ding, “Cyclic Codes over Finite Fields”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 45-60 DOI
- [3]
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes (Elsevier, 1977)
- [4]
E. Berlekamp, “Nonbinary BCH decoding (Abstr.)”, IEEE Transactions on Information Theory 14, 242 (1968) DOI
- [5]
J. Massey, “Shift-register synthesis and BCH decoding”, IEEE Transactions on Information Theory 15, 122 (1969) DOI
- [6]
E. R. Berlekamp, Algebraic Coding Theory (McGraw-Hill, 1968)
- [7]
H. Burton, “Inversionless decoding of binary BCH codes”, IEEE Transactions on Information Theory 17, 464 (1971) DOI
- [8]
W. W. Peterson and E. J. Weldon, Error-Correcting Codes (MIT Press, 1972)
- [9]
R. Gallager, Information Theory and Reliable Communication (Springer Vienna, 1972) DOI
- [10]
W. Peterson, “Encoding and error-correction procedures for the Bose-Chaudhuri codes”, IEEE Transactions on Information Theory 6, 459 (1960) DOI
- [11]
R. E. Blahut, Theory and Practice of Error-Control Codes (Addison-Wesley, 1983)
- [12]
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
- [13]
R. McEliece, The Theory of Information and Coding (Cambridge University Press, 2002) DOI
- [14]
S. Zhu, Z. Sun, and X. Kai, “A Class of Narrow-Sense BCH Codes”, IEEE Transactions on Information Theory 65, 4699 (2019) DOI
- [15]
S. Lin and D. J. Costello, Error Control Coding, 2nd ed. (Prentice-Hall, 2004)
- [16]
W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
- [17]
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
- [18]
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
- [19]
T. Kaufman and S. Litsyn, “Almost Orthogonal Linear Codes are Locally Testable”, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05) 317 DOI
- [20]
R. M. Roth and P. H. Siegel, “Lee-metric BCH codes and their application to constrained and partial-response channels”, IEEE Transactions on Information Theory 40, 1083 (1994) DOI
- [21]
C. Tang and C. Ding, “An infinite family of linear codes supporting 4-designs”, (2020) arXiv:2001.00158
- [22]
C. Ding and C. Tang, “Infinite families of near MDS codes holding \(t\)-designs”, (2019) arXiv:1910.08265
- [23]
E. J. Weldon, “Justesen’s construction–The low-rate case (Corresp.)”, IEEE Transactions on Information Theory 19, 711 (1973) DOI
- [24]
D. Boucher, W. Geiselmann, and F. Ulmer, “Skew-cyclic codes”, (2006) arXiv:math/0604603
- [25]
A. Vardy and Y. Be’ery, “Bit-level soft-decision decoding of Reed-Solomon codes”, IEEE Transactions on Communications 39, 440 (1991) DOI
- [26]
W. Willems, “Codes in Group Algebras”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 363-384 DOI
- [27]
S. A. Aly, A. Klappenecker, and P. K. Sarvepalli, “Subsystem Codes”, (2006) arXiv:quant-ph/0610153
- [28]
A. Couvreur, H. Randriambololona, “Algebraic Geometry Codes and Some Applications”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 311-362 DOI
- [29]
J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
Page edit log
- Victor V. Albert (2026-06-08) — most recent
- Victor V. Albert (2022-07-13)
- Muhammad Junaid Aftab (2022-04-21)
Cite as:
“Bose–Chaudhuri–Hocquenghem (BCH) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/q-ary_bch, arXiv:2606.11484