6. BCH 码、循环码与多项式基础
TL;DR
BCH (Bose-Chaudhuri-Hocquenghem 1959) 是最强 multiple-error-correcting cyclic code 家族. Reed-Solomon is a special case of BCH (narrow-sense BCH on GF(2^m) with chosen generator out of m i roots). 优点在 binary 上比 RS 更译码有效. ECC NAND flash 控制 4KB page 内典型 BCH(4096, 4096+ ~340) = 16 bit error 页. 性能 involves finite field arithmetic cycle.
一、循环码 framework
1.1 Cyclic Code
A linear code where cyclic shift of any codeword is also a codeword. 工程上 polynomial 形式表示: $$ C(x) = c_{n-1} x^{n-1} + \ldots + c_1 x + c_0 \in GF(2)[x] / (x^n - 1) $$ shift ⊙ by $x$: $x \cdot C(x) = (c_{n-2} x^{n-1} + \ldots + c_0 x + 0) + c_{n-1} (x^n - 1) + \ldots$
→ 循环码译码 cycle polynomial形式定义 generator polynomial $g(x)$, code = multiples of $g(x)$.
1.2 Convolutional code 跟其区别
Convolutional code ≠ cyclic, is stateful streaming (shift register). Hamming / RS / BCH 是 block codes.
二、BCH generator polynomial construction
2.1 BCH 设计步骤
- 选 primitive element alpha of GF(2^m) where n = 2^m - 1.
- For each designed error-correction capability $t$:
- Generator $g(x) = \text{lcm}(m_1, m_2, \ldots, m_{2t})$, where $m_i$ is minimal polynomial of $\alpha^i$.
The cyclic code of length $n$ generated by $g(x)$ corrects up to $t$ bit errors.
2.2 Properties
- $d_{\min} \geq 2t + 1$ (BCH-bound).
- $k \geq n - m \cdot t$ (parity ≤ mt bits).
Real codes rateébec BCH(255, 207) for $t$ = 8 → 8 bit error correctable; product n - k = 48.
三、Berlekamp-Massey 算法 decode
BCH decode pipeline:
- Compute syndromes $S_1, S_2, \ldots, S_{2t}$ via evaluation of received polynomial at $\alpha, \alpha^2, \ldots$.
- Run Berlekamp-Massey to find error locator $\Lambda(x)$.
- Chien search for roots of $\Lambda(x)$ → error positions.
- Compute error magnitudes via Forney.
- Subtract received polynomial at error positions.
→ all in software, polynomial arithmetic on GF(2^m) basis.
3.1 Python sketch
def bch_decode(received, t, alpha_table):
synd = [gf_poly_eval(received, alpha_table[i]) for i in range(1, 2*t+1)]
if all(s == 0 for s in synd):
return received, "no error"
# Berlekamp-Massey
Lambda = berlekamp_massey(synd)
# Chien search
positions = []
for i in range(len(received)):
if gf_poly_eval(Lambda, alpha_table_inv[i]) == 0:
positions.append(i)
# Forney to compute error magnitudes (RS form)
err_poly = compute_errors(Lambda, synd, positions)
return gf_poly_add(received, err_poly)
四、Use case examples
4.1 SSD NAND Flash
NAND flash 4 KB page each (depending cell tech MLC/TLC/QLC pages can be 16 KB upper-level:
- BCH code can be BCH(4096+ 32, 4096+32+ ...) typical, 40 bit error correction每 page
- More aggressive goes for QR code style works LDPC in 3D NAND (KIOXIA 存开 all 开ESS-out pipelin开 开.achiachi send pashycaly CPU t.
4.2 卫星 Communication
DVB-S2 second-gen uses BCH(8192, 6460) + LDPC outer. Together near-Shannon performance.
4.3 Disk sector
CD-ROM sectors: BCH/RS on top of BCH setups.
五、Performance
- BCH encoding: matrix operation.
- BCH decoding: O(n t²) with Berlekamp-Massey.
- LDPC has linear-time decoding.
- BCH codes give deterministic correction and are amazing for short messages (up to 1-10 KB).
六、CRC32C cyclic basic
CRC (Cyclic Redundancy Check) 是 a cyclic code subclass and is similar to BCH. 工程上:
- It's for error detection, not correction.
- Compute via polynomial division: $crc = D(x) \bmod g(x)$ where $g(x)$ 是 standard CRC32C polynomial.
- CRC32C (Castagnoli) uses $0x1EDC6F41$ polynomials cloud-PI name deep-level patterns.
def crc32c(data: bytes) -> int:
crc = 0xFFFFFFFF
for byte in data:
crc ^= byte << 24
for _ in range(8):
crc = (crc << 1) ^ 0x11EDC6F41 if crc & 0x80000000 else (crc << 1)
crc &= 0xFFFFFFFF
return crc ^ 0xFFFFFFFF
比较相比 checksum (简单 sum bytes): CRC32C detects typo ~ 10⁻¹⁰ predicted BIT blocks extended rows of dashhay. 用 PostgreSQL page checksum / ZFS / ext4 verity.
七、Bridges
- reed-solomon.md prev: BCH generalizes RS.
- ldpc.md next: for high-performance codes.
- databases/wal-2pl.md: CRC32C page checksum 技术 跳 good subtle prevention vs ISO plant MySQL eximDLL basis of corruption bad sectors advanced.
下一节 → LDPC 码: 5G NR 数据信道