BCH code (Bose–Chaudhuri–Hocquenghem code) is a class of cyclic error-correcting codes that are among the most widely studied and deployed families of algebraic codes in coding theory. BCH codes were discovered independently by Alexis Hocquenghem in 1959 and by Raj Chandra Bose and Dwijendra Kumar Ray-Chaudhuri in 1960.
Overview
BCH codes are cyclic linear block codes constructed over finite fields (Galois fields). They are notable for their ability to correct multiple random errors and for the fact that efficient algebraic decoding algorithms exist for them. The codes are defined by specifying a set of consecutive powers of a primitive element in a finite field as roots of the generator polynomial.
Mathematical Definition
A BCH code of length $n$ and designed distance $\delta$ is a cyclic code whose generator polynomial $g(x)$ has as its roots ${\alpha^b, \alpha^{b+1}, \ldots, \alpha^{b+\delta-2}}$, where $\alpha$ is a primitive $n$th root of unity in some extension field $\mathbb{F}_{2^m}$. The parameter $b$ is typically chosen as 1 (narrow-sense BCH codes). When $n = 2^m - 1$, the code is called a primitive BCH code.
The BCH bound guarantees that the minimum Hamming distance $d$ of the code satisfies $d \geq \delta$. The designed distance $\delta = 2t + 1$ ensures that the code can correct at least $t$ bit errors per codeword.
Key Properties
- Flexibility: BCH codes can be designed to correct a specified number of errors $t$.
- Efficient decoding: Several polynomial-time decoding algorithms exist, including the Peterson decoder ($O(n^3)$), the Berlekamp–Massey algorithm ($O(n^2)$), and the Sugiyama extended Euclidean algorithm.
- Asymptotic behavior: Primitive binary BCH codes are asymptotically bad in the sense that their rate goes to zero as block length increases while maintaining a fixed error-correction capability.
- Special cases: Binary Hamming codes are equivalent to primitive narrow-sense BCH codes with designed distance $\delta = 3$. The binary $[23, 12, 7]$ Golay code is equivalent to a BCH code with Bose distance 5.
Variants
- Narrow-sense BCH codes: $b = 1$.
- Primitive BCH codes: $n = 2^m - 1$.
- Non-binary BCH codes: The most important non-binary case is the Reed–Solomon code, which is a BCH code over $\mathbb{F}_q$ with $n = q - 1$.
Decoding Algorithms
- Peterson decoder: Solves a system of linear equations to find the error locator polynomial. Complexity $O(n^3)$.
- Berlekamp–Massey algorithm: Iteratively finds the shortest linear feedback shift register that generates the syndrome sequence. Complexity $O(n^2)$.
- Sugiyama (extended Euclidean) algorithm: Uses the extended Euclidean algorithm on the syndrome polynomial and $x^{2t}$ to find the error locator polynomial.
- Guruswami–Sudan list decoder: A more recent algorithm that allows list decoding beyond half the minimum distance.
Applications
- Satellite communication (e.g., the Phobos lander coding system)
- Data storage systems
- QR codes (Reed–Solomon codes, a non-binary subclass, are used)
- Error-correcting output codes (ECOCs) in machine learning
- Quantum error correction: Binary BCH codes are used in constructing qubit BCH codes via the CSS construction and quantum synchronizable codes.
History
- 1959: Alexis Hocquenghem published "Codes correcteur d'erreurs" in Chiffres (Paris).
- 1960: Bose and Ray-Chaudhuri independently published "On a class of error correcting binary group codes" and "Further results on error correcting binary group codes" in Information and Control.
- 1960: W. Peterson published the first general decoding algorithm for BCH codes.
- 1968: E. R. Berlekamp published Algebraic Coding Theory, introducing the Berlekamp algorithm.
- 1969: J. Massey connected the decoding problem to shift-register synthesis (Berlekamp–Massey algorithm).
