Algebraic codes with guaranteed error correction — from finite field theory to flash memory
Hocquenghem, Bose & Ray-Chaudhuri — independent discovery
GF(2m), minimal polynomials, cyclotomic cosets
BCH bound, generator polynomial, designed distance
Systematic & non-systematic methods
PGZ, Berlekamp-Massey, Chien search
Flash memory, satellite, connection to RS codes
French mathematician at the Conservatoire National des Arts et Metiers in Paris.
Published the construction of a class of multiple-error-correcting codes in Comptes Rendus, September 1959.
His work was less well-known initially due to the French publication venue.
Raj Chandra Bose and Dwijendra Kumar Ray-Chaudhuri at the University of North Carolina.
Published independently in March 1960 in the Journal of Information and Control.
Provided a more detailed treatment with proofs of the BCH bound.
GF(2m) is constructed as GF(2)[x] / p(x), where p(x) is an irreducible polynomial of degree m over GF(2).
GF(2m) has 2m elements:
α is a root of p(x), called the primitive element.
α2m-1 = 1 (cyclic group of order 2m-1).
Every nonzero element is a power of α.
Addition: XOR of polynomial coefficients.
Multiplication: polynomial multiplication mod p(x).
| Power | Polynomial | Binary | Decimal |
|---|---|---|---|
| 0 | 0 | 0000 | 0 |
| α0 | 1 | 0001 | 1 |
| α1 | α | 0010 | 2 |
| α2 | α2 | 0100 | 4 |
| α3 | α3 | 1000 | 8 |
| α4 | α + 1 | 0011 | 3 |
| α5 | α2 + α | 0110 | 6 |
| α6 | α3 + α2 | 1100 | 12 |
| α7 | α3 + α + 1 | 1011 | 11 |
Table continues for α8 through α14. All 15 nonzero elements are distinct powers of α.
The minimal polynomial mi(x) of αi is the smallest degree polynomial over GF(2) that has αi as a root:
m1(x) = x4 + x + 1
Roots: α, α2, α4, α8
m3(x) = x4 + x3 + x2 + x + 1
Roots: α3, α6, α12, α9
m5(x) = x2 + x + 1
Roots: α5, α10
m7(x) = x4 + x3 + 1
Roots: α7, α14, α13, α11
The cyclotomic coset of i modulo 2m-1 is:
Elements in the same coset share the same minimal polynomial.
| Coset | Elements | Size | Minimal Polynomial |
|---|---|---|---|
| C0 | {0} | 1 | x + 1 |
| C1 | {1, 2, 4, 8} | 4 | x4 + x + 1 |
| C3 | {3, 6, 12, 9} | 4 | x4 + x3 + x2 + x + 1 |
| C5 | {5, 10} | 2 | x2 + x + 1 |
| C7 | {7, 14, 13, 11} | 4 | x4 + x3 + 1 |
The designed distance δ is a guaranteed lower bound on dmin. Often dmin = δ exactly, but sometimes dmin > δ.
If c(x) is a codeword and g(x)|c(x), then c(αi) = 0 for all roots of g(x). A codeword of weight < d would give a system of equations with a Vandermonde matrix that must have a nontrivial solution — but Vandermonde is always invertible for distinct roots! Contradiction.
Step 1: Choose designed distance δ = 2t + 1 (to correct t errors).
Step 2: The generator must have roots α, α2, ..., α2t.
Step 3: Compute g(x) = LCM(m1(x), m2(x), ..., m2t(x)).
Since conjugate roots share minimal polynomials, many mi's are redundant.
t = 2, need roots α, α2, α3, α4 in g(x).
n = 15, deg(g) = 8, so k = 15 - 8 = 7. BCH(15, 7, 5) code.
| m | n | t | k | dmin | Rate |
|---|---|---|---|---|---|
| 4 | 15 | 1 | 11 | 3 | 0.733 |
| 4 | 15 | 2 | 7 | 5 | 0.467 |
| 4 | 15 | 3 | 5 | 7 | 0.333 |
| 5 | 31 | 1 | 26 | 3 | 0.839 |
| 5 | 31 | 3 | 16 | 7 | 0.516 |
| 5 | 31 | 5 | 11 | 11 | 0.355 |
| 8 | 255 | 2 | 239 | 5 | 0.937 |
| 8 | 255 | 4 | 223 | 9 | 0.875 |
Note: The t=1 case for any m gives the Hamming code — BCH generalizes Hamming codes!
Simply multiply:
Message polynomial m(x) of degree < k produces codeword c(x) of degree < n.
Simple but message bits are not directly readable in the codeword.
Place message in high-order positions:
where r(x) = [xn-k·m(x)] mod g(x)
Codeword = [parity bits | message bits]
First k bits of the codeword are the original message — easy to extract after decoding!
g(x) = x8 + x7 + x6 + x4 + 1
Message: m = (1 0 1 1 0 0 1) → m(x) = x6 + x4 + x3 + 1
Step 1: Compute x8 · m(x) = x14 + x12 + x11 + x8
Step 2: Divide by g(x):
Step 3: r(x) = x7 + x6 + x4 + x3 + x2 + x (the remainder)
Step 4: c(x) = x8·m(x) + r(x)
Evaluate r(x) at the roots of g(x):
If all Sj = 0, no errors detected.
Find σ(x) = (1 + X1x)(1 + X2x)...(1 + Xvx)
Where Xi = αei marks error positions.
For a t-error-correcting BCH code, compute 2t syndromes:
If v errors occurred at positions e₁, e₂, ..., ev:
where Xi = αei are the error locators.
The error-locator polynomial σ(x) = 1 + σ1x + σ2x2 + ... + σvxv satisfies Newton's identities:
| S1 | S2 | ⋯ | Sv |
| S2 | S3 | ⋯ | Sv+1 |
| ⋮ | ⋮ | ⋱ | ⋮ |
| Sv | Sv+1 | ⋯ | S2v−1 |
| σv |
| σv−1 |
| ⋮ |
| σ1 |
| Sv+1 |
| Sv+2 |
| ⋮ |
| S2v |
Matrix inversion: O(t3) field operations.
Practical for small t, but Berlekamp-Massey is preferred for t > 3 due to O(t2) complexity.
The BM algorithm finds the shortest LFSR (Linear Feedback Shift Register) that generates the syndrome sequence S₁, S₂, ..., S₂ₜ.
Named after R.T. Chien (1964). An exhaustive search made efficient by exploiting the structure of finite fields.
If σ(α-i) = 0, then position i has an error.
Instead of recomputing from scratch each time, update incrementally:
Only v multiplications per step instead of evaluating the full polynomial.
Simpler decoding — no need for Forney's algorithm.
Needs Forney's algorithm to compute error magnitudes.
BCH codes are the standard ECC for NAND flash storage.
BCH preferred for its deterministic latency and low power.
DVB-S2 uses BCH outer code + LDPC inner code.
QR codes use RS (a BCH generalization) for error correction at multiple levels.
L: 7%, M: 15%, Q: 25%, H: 30% correction capability.
Hard drives use BCH/RS codes in the read channel alongside other signal processing.
Typical: t = 10-20 error correction.
def gf2_poly_mod(dividend, divisor):
"""Polynomial division over GF(2), return remainder."""
dividend = list(dividend) # copy
for i in range(len(dividend) - len(divisor) + 1):
if dividend[i] == 1:
for j in range(len(divisor)):
dividend[i + j] ^= divisor[j]
return dividend[-(len(divisor)-1):]
def gf2_poly_mult(a, b):
"""Polynomial multiplication over GF(2)."""
result = [0] * (len(a) + len(b) - 1)
for i, ai in enumerate(a):
if ai:
for j, bj in enumerate(b):
result[i + j] ^= bj
return result
class BCHCode:
def __init__(self, n, g_coeffs):
"""
n: code length (2^m - 1)
g_coeffs: generator polynomial as list [high...low]
"""
self.n = n
self.g = g_coeffs
self.n_minus_k = len(g_coeffs) - 1
self.k = n - self.n_minus_k
def encode_systematic(self, message):
"""Systematic BCH encoding."""
assert len(message) == self.k
# x^(n-k) * m(x)
shifted = message + [0] * self.n_minus_k
# Compute remainder
remainder = gf2_poly_mod(shifted, self.g)
# Codeword = message | parity
codeword = message + remainder
return codeword
def compute_syndrome(self, received, alpha_powers):
"""Compute syndromes by evaluating r(x) at roots."""
# This requires GF(2^m) arithmetic - simplified here
pass # Full implementation needs GF arithmetic# BCH(15, 7, 5) generator: x^8 + x^7 + x^6 + x^4 + 1
g = [1, 1, 1, 0, 1, 0, 0, 0, 1] # coefficients high to low
bch = BCHCode(15, g)
# Encode a message
message = [1, 0, 1, 1, 0, 0, 1]
codeword = bch.encode_systematic(message)
print(f"Message: {message}")
print(f"Codeword: {codeword}")
# Output: [1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0]
# |--- message ---| |--- parity ---|
# Verify: codeword should be divisible by g(x)
remainder = gf2_poly_mod(codeword, g)
print(f"Remainder (should be all zeros): {remainder}")
# [0, 0, 0, 0, 0, 0, 0, 0]
# Introduce 2 errors (max correctable)
received = codeword.copy()
received[3] ^= 1 # flip bit 3
received[10] ^= 1 # flip bit 10
print(f"Received: {received}")
# Check syndrome (non-zero = errors detected)
rem = gf2_poly_mod(received, g)
print(f"Syndrome check: {rem}")
print(f"Errors detected: {any(rem)}") # True
# Encode all 2^7 = 128 messages to verify code properties
min_weight = 15
for i in range(1, 128):
m = [(i >> j) & 1 for j in range(6, -1, -1)]
c = bch.encode_systematic(m)
w = sum(c)
min_weight = min(min_weight, w)
print(f"Minimum weight (= d_min): {min_weight}") # 5