BCH 码

BCH 码由 Bose、Ray-Chaudhuri（1960）与 Hocquenghem（1959）独立提出，是第一个"先指定纠错能力、再倒推构造"的系统方法：在循环码的框架里，让生成多项式取一串连续的根，最小距离便被压在设计距离之上。它的证明核心是一条 Vandermonde 型论证，维数则由分圆陪集计数精确给出。Steane 1996 年的量子码表直接用长度 31 的 BCH 码做经典原料，CRSS 的 GF(4) 循环码是同一思想的量子化。

循环码：多项式商环中的理想

循环码（cyclic code）是线性码的子类：循环移位后仍是码字，$(c_0,\dots ,c_{n-1})\in \mathcal{C}\Rightarrow (c_{n-1},c_0,\dots ,c_{n-2})\in \mathcal{C}$。把码字写成多项式 $c(x)={\sum }_i{c}_i{x}^i$，循环移位就是乘 $x$ 再模 $x^n-1$；线性性与循环性合起来说明 $\mathcal{C}$ 是商环 ${\mathbb{F}}_2[x]/(x^n-1)$ 的理想。${\mathbb{F}}_2[x]$ 是主理想环，故

$\mathcal{C}=(g(x)),g(x)\mid x^n-1,k=n-\mathrm{deg}g,$

$g(x)$ 称为生成多项式，一切由它的根决定：编码即 $c(x)=m(x)g(x)$Bose & Ray-Chaudhuri 1960 (Information and Control)。

BCH 界：连续根与 Vandermonde 论证

取 $n\mid 2^m-1$，$\alpha$ 为 ${\mathbb{F}}_{2^m}$ 中的 $n$ 次本原单位根。设计距离为 $\delta$ 的 BCH 码：$g(x)$ 以连续 $\delta -1$ 个根 ${\alpha }^c,{\alpha }^{c+1},\dots ,{\alpha }^{c+\delta -2}$ 为根（窄意义取 $c=1$）。

定理（BCH 界）：$d\ge \delta$。

证明：设码字 $c(x)\ne 0$，其系数支撑 $S=\{i:c_i\ne 0\}$，$|S|=w$。每个根给出一个线性方程：对 $j=c,\dots ,c+\delta -2$，

$c\left({\alpha }^j\right)={\sum }_{i\in S}{c}_i{\alpha }^{ij}=0.$

假设 $w\le \delta -1$，取其中 $w$ 个方程（$j=c,\dots ,c+w-1$），系数矩阵为 $[{\alpha }^{ij}{]}_{j,i\in S}$。对第 $i$ 列提取公因子 ${\alpha }^{ic}$，矩阵化为 $[{\alpha }^{i(j-c)}]$，这是以互异的 ${\alpha }^i$（$i\in S$）为节点的 Vandermonde 矩阵，非奇异；方程组只有零解，与 $c_i\ne 0$（$i\in S$）矛盾。故 $w\ge \delta$。∎

注意论证是纯线代的：连续根恰好凑出足够多的 Vandermonde 方程，“距离下界”完全由根的排布买来——这就是”指定纠错能力再构造”的含义。Bose & Ray-Chaudhuri 1960 (Information and Control)。

共轭根与分圆陪集：维数怎么算

${\mathbb{F}}_2$ 上 ${\alpha }^j$ 的最小多项式连带包含其共轭 ${\alpha }^{2j},{\alpha }^{4j},\dots$（见galois-fields），故取”连续根”时 $g(x)$ 实际取到的是各根所在分圆陪集的并，维数由陪集大小决定：

$\mathrm{deg}g={\sum }_{\text{取到的陪集 }C}|C|,k=n-\mathrm{deg}g.$

GF(16) 实算（$n=15$，纠 2 错即 $\delta =5$，根 $\alpha ,{\alpha }^2,{\alpha }^3,{\alpha }^4$）：陪集 $C_1=\{1,2,4,8\}$ 与 $C_3=\{3,6,12,9\}$ 各 4 元，$\mathrm{deg}g=8$，得 $[15,7,5]$——设计距离 5 精确达到。同法在 $n=31$（GF(32)）：$C_1,C_3$ 各 5 元，$\mathrm{deg}g=10$，得 $[31,21,5]$。距离再往上取 $\delta =7$（根 $\alpha ..{\alpha }^6$，$C_5=\{5,10,20,9,18\}$ 加入）时 $\mathrm{deg}g=15$，得 $[31,16]$ 码（Steane 记其参数为 $[31,16,5]$，对偶距离 12）。

译码与渐近地位

BCH 译码与 RS 码共用同一套机件：Berlekamp–Massey 求错误定位多项式、Chien 搜索找根、Forney 公式给错误值，硬件成熟，长期服务于卫星信道与闪存控制器。渐近地位则有限：固定设计距离 $\delta$ 时 $k/n\to 1$ 而相对距离 $\delta /n\to 0$，二元 BCH 族只覆盖 GV 界的一部分区域（见classical-bounds），长码场景通常与 RS 一样以级联补足（见concatenated-classical）。

量子侧：Steane 码表与 CRSS

Steane 在 1996 年的量子码构造中把”对偶包含 ${\mathcal{C}}^{\perp }\subseteq \mathcal{C}$ 的经典码”作为原料：汉明/BCH 这类对偶距离可控的循环码恰好合格，其码表给出 $[[2^r-1,2^r-1-4r,5]]$ 型 BCH 量子码族（$r>4$，如 $[[31,11,5]]$）Steane 1996 (Phys. Rev. A)。CRSS 随后把整个循环码框架搬到 GF(4) 上，得到量子码的系统构造（见perfect-quantum-codes）；循环结构的现代延续是环 ${\mathbb{Z}}_2[x,y]/(x^{\ell }-1,y^m-1)$ 上的准循环 qLDPC 码——双变量自行车码（见bivariate-bicycle）。

延伸阅读

• galois-fields
• reed-solomon
• linear-codes
• steane-code
• bivariate-bicycle