信息论及其应用

TBD: 目前这篇文章只是基于我的笔记做了中文翻译，后序修复格式和表述问题。

信息论（information theory）研究的核心问题是消息在不确定性意义上带来了多少信息。如果一个事件本来几乎必然发生，那么它发生时不会带来多少新信息；如果一个事件本来极不可能发生，那么它一旦发生，就显著减少了我们对世界的无知。围绕这个直觉，信息论建立了一套用概率刻画信息、压缩、加密与通信可靠性的体系。本文对信息论的基本概念、压缩与信道编码、线性分组码、有限域、BCH 码与 Reed–Solomon 码进行总结。

信息量、熵与互信息

信息量

信息论的起点是一个很朴素的问题：一个事件发生之后，我们到底获得了多少信息？直觉上，一个概率很大的事件发生时，信息量很小；一个概率很小的事件发生时，信息量很大。因此，一个事件 $X=x$ 的自信息量（self-information）定义为

$$h(x)=\log_2 \frac{1}{p(x)}.$$

这里使用 $\log_2$ 是因为信息量通常以 bit 为单位。这个定义满足几个自然要求：概率越小，信息量越大；独立事件同时发生时，信息量可以相加，因为

$$\log_2 \frac{1}{p(x,y)}=\log_2 \frac{1}{p(x)p(y)}=\log_2 \frac{1}{p(x)}+\log_2 \frac{1}{p(y)}.$$

熵：随机变量的平均不确定性

单个事件的信息量只描述一次观测带来的信息。如果我们关心一个随机变量整体上有多不确定，就需要对所有可能事件的信息量取期望，这就是熵（entropy）：

$$H(X)=\mathbb{E}[h(X)] = \sum_{i=1}^{N_x} p(x_i)\log_2\frac{1}{p(x_i)}.$$

熵可以理解为观察 $X$ 之前平均缺少多少信息。如果 $X$ 几乎总是取同一个值，那么观察它之前其实没什么悬念，熵很小；如果 $X$ 在很多状态之间均匀分布，那么每次观测都可能带来较多信息，熵更大。

当 $X$ 有 $N_x$ 个可能取值时，熵的上界是

$$H(X)\leq \log_2 N_x,$$

并且当所有状态等概率，即 $p(x_i)=1/N_x$ 时取等号。这说明在状态数量固定的情况下，最不确定的分布是均匀分布。

联合熵与条件熵

当我们同时观察两个随机变量 $X,Y$ 时，需要描述它们作为整体的不确定性，这就是联合熵（joint entropy）：

$$H(X,Y)=\sum_{i=1}^{N_x}\sum_{j=1}^{N_y}p(x_i,y_j)\log_2\frac{1}{p(x_i,y_j)}.$$

联合熵描述的是同时确定 $X$ 和 $Y$ 所需要的信息量。另一方面，如果我们已经知道 $Y$，那么 $X$ 的剩余不确定性通常会减少。这个剩余不确定性由条件熵（conditional entropy）刻画：

$$H(X\mid Y)=\sum_{i=1}^{N_x}\sum_{j=1}^{N_y}p(x_i,y_j)\log_2\frac{1}{p(x_i\mid y_j)}.$$

条件熵的本质是：知道 $Y$ 之后，$X$ 还剩多少不确定性。如果 $Y$ 完全决定 $X$，则 $H(X\mid Y)=0$；如果 $Y$ 和 $X$ 独立，则知道 $Y$ 并不会帮助预测 $X$，因此 $H(X\mid Y)=H(X)$。

联合熵与条件熵之间有一个非常重要的链式关系：

$$H(X,Y)=H(X)+H(Y\mid X)=H(Y)+H(X\mid Y).$$

这个公式的含义很直接：要同时描述 $X$ 和 $Y$，可以先描述 $X$，再描述知道 $X$ 后 $Y$ 还剩下的不确定性。

互信息：一个变量告诉了另一个变量多少信息

如果条件熵描述“知道 $Y$ 后 $X$ 还剩多少不确定性”，那么 $H(X)-H(X\mid Y)$ 就描述知道 $Y$ 使 $X$ 的不确定性减少了多少。这就是互信息（mutual information）：

$$I(X;Y)=H(X)-H(X\mid Y)=H(Y)-H(Y\mid X).$$

它也可以写成概率分布之间的形式：

$$I(X;Y)=\sum_{i=1}^{N_x}\sum_{j=1}^{N_y}p(x_i,y_j)\log_2\frac{p(x_i,y_j)}{p(x_i)p(y_j)}.$$

从这个表达式可以看到，互信息衡量的是联合分布 $p(x,y)$ 与独立假设下的乘积分布 $p(x)p(y)$ 的偏离程度。如果 $X$ 和 $Y$ 独立，则 $p(x,y)=p(x)p(y)$，互信息为 $0$；反之，互信息越大，说明 $Y$ 对预测 $X$ 越有帮助。

互信息满足

$$I(X;Y)=I(Y;X),\qquad I(X;Y)\geq 0.$$

它和熵之间的常用关系包括

$$I(X;Y)=H(X)+H(Y)-H(X,Y),$$

以及

$$H(X,Y)=H(X)+H(Y)-I(X;Y).$$

这些关系给出一个很清楚的图像：两个变量各自的不确定性之和中，有一部分是重复的、共享的，这一部分正是互信息。

KL 散度：两个分布之间的差异

在信息论中，经常需要比较两个概率分布 $p$ 和 $q$ 的差异。KL 散度（Kullback–Leibler divergence）定义为

$$D_{\mathrm{KL}}(p|q)=\mathbb{E}_{X\sim p}\left[\log_2\frac{p(X)}{q(X)}\right] =\sum_i p(x_i)\log_2\frac{p(x_i)}{q(x_i)}.$$

对于连续情形，则写成

$$D_{\mathrm{KL}}(p|q)=\int p(x)\log_2\frac{p(x)}{q(x)},dx.$$

KL 散度满足 $D_{\mathrm{KL}}(p|q)\geq 0$，且当 $p=q$ 时为 $0$。不过它不是严格意义上的距离，因为一般有

$$D_{\mathrm{KL}}(p|q)\neq D_{\mathrm{KL}}(q|p).$$

从信息论角度看，KL 散度可以理解为：如果真实分布是 $p$，但我们用 $q$ 来编码或解释数据，平均会多付出多少信息代价。

连续随机变量中的差分熵

对于连续随机变量，熵的形式变成差分熵（differential entropy）：

$$h(X)=-\int p(x)\log_2 p(x),dx.$$

联合差分熵和条件差分熵分别为

$$h(X,Y)=-\int\int p(x,y)\log_2 p(x,y),dx,dy,$$ $$h(X\mid Y)=-\int\int p(x,y)\log_2 p(x\mid y),dx,dy.$$

连续变量的互信息仍然保持类似形式：

$$I(X;Y)=\int\int p(x,y)\log_2\frac{p(x,y)}{p(x)p(y)},dx,dy.$$

需要注意的是，差分熵不像离散熵那样总是非负，也不再能简单解释为“平均编码长度”。但互信息和 KL 散度在连续情形下仍然具有稳定的信息论意义。

信息论应用

信息论的基本概念一旦建立，就会自然导向三个重要应用。第一个是安全：密文到底泄露了多少明文信息？第二个是压缩：一段消息最短可以压到多短？第三个是通信：如果信道会出错，怎样用冗余换可靠性？这三件事看似不同，本质上都在处理“不确定性”和“冗余”。

完美保密

在密码系统中，设明文为 $X$，密文为 $C$，密钥为 $K$。加密的目标是让攻击者即使观察到密文，也无法获得关于明文的额外信息。

完美保密（perfect secrecy）可以用条件熵表达为

$$H(X\mid C)=H(X).$$

这句话的意思是：观察密文 $C$ 之后，明文 $X$ 的不确定性没有减少。等价地，

$$I(X;C)=0.$$

也就是说，密文和明文在信息论意义上相互独立。经典的一次一密（one-time pad）正是完美保密的例子：密钥完全随机、长度不短于明文、只使用一次，则密文不会泄露明文信息。

信息论还可以解释距离唯一性（unicity distance）。它描述攻击者至少需要多少密文长度，才可能从语言冗余中唯一确定一个合理明文。若密钥熵为 $H(K)$，语言每个字符的冗余为

$$r=H_{\max}-\overline{h}_X=\log_2 N_x-\frac{H(X)}{n},$$

则距离唯一性通常写作

$$d_u=\frac{H(K)}{r}.$$

这个公式背后的直觉是：自然语言不是均匀随机的，它有结构、有语法、有高频词，因此有冗余。密文越长，攻击者越能利用这些冗余排除不合理明文。当累积的语言冗余足以抵消密钥的不确定性时，密钥和明文就可能被唯一确定。

信息论与压缩：去掉冗余

压缩的目标是用尽可能短的码字表示消息，同时仍然能够无歧义解码。若某个符号出现概率高，就应该分配短码；若出现概率低，则可以分配长码。这一思想正是熵与编码长度之间关系的来源。

一个二进制码如果每个码字都不是另一个码字的前缀，就称为即时码或前缀码（instantaneous code / prefix code）。即时码可以边读边解码，不需要等待后续比特。

Kraft–McMillan 定理给出了前缀码长度是否可行的判据。若码字长度 $l_1, \dots,l_M$ 满足

$$\sum_{i=1}^M 2^{-l_i}\leq 1,$$

则存在一个二进制前缀码，其码字长度正好为这些 $l_i$。这个定理的重要性在于，它把“是否存在一个可解码编码”的问题转化成了一个关于长度的代数不等式。

对于源符号集合 $S$，若符号 $c$ 的概率为 $p(c)$，码长为 $l(c)$，则平均码长为

$$L=\sum_{c\in S}p(c)l(c).$$

任何唯一可译码的平均长度都满足下界

$$L\geq H(S).$$

这就是无损压缩的基本极限：熵给出了平均编码长度的理论下界。你可以更聪明地编码，但无法在长期平均意义上突破熵。

Shannon–Fano 码与 Huffman 码

Shannon–Fano 编码的基本做法是，对于概率为 $p_i$ 的符号，给它分配长度

$$l_i=\left\lceil \log_2\frac{1}{p_i}\right\rceil.$$

这符合“概率越大，码字越短”的原则。由于取了上整，Shannon–Fano 码的平均长度通常满足接近熵的上界：它不会比理论最优差太多，但也不一定达到最优。

Huffman 编码则进一步给出一种构造最优前缀码的方法。它每次合并概率最小的两个符号，构造一棵二叉树，最后由树上的路径得到码字。Huffman 编码在给定符号概率的前缀码集合中达到最小平均码长。

压缩理论最深刻的结论来自Shannon 第一编码定理，也称信源编码定理（source coding theorem）。对于平稳信源，若考虑由 $n$ 个符号组成的扩展信源，则随着 $n\to\infty$，每个符号所需的平均编码长度可以逼近信源的熵率：

$$\lim_{n\to\infty}\frac{L(n)}{n}=\widehat{H}(S).$$

这里的熵率可以写为

$$\widehat{H}(S)=\lim_{n\to\infty}H(S_n\mid S_1,\dots,S_{n-1}).$$

它表示在知道过去所有符号后，下一个符号还剩多少平均不确定性。这个定义很贴近真实语言：一个字符或单词本身也许有很大不确定性，但在上下文给定后，不确定性会显著降低。

信道编码：主动加入冗余

压缩是去掉冗余，信道编码则是主动加入冗余。二者方向相反，但都由信息论统一解释。压缩希望用更少比特表达同样的信息；信道编码希望在信息中加入可控冗余，使接收端能够发现甚至纠正传输错误。

在信道编码中，编码器（encoder）把原始消息映射为更长的码字，引入冗余；解码器（decoder）根据接收到的序列判断它是否满足编码规则，并在可能时恢复原始码字。

若接收词为 $\underline r$，码字集合为 $C$，一种自然的解码方法是最大似然解码（maximum likelihood decoding）。在二元对称信道中，最大似然解码等价于选择与接收词 Hamming 距离最小的码字：

$$\underline c_{\min}=\arg\min_{\underline c\in C}d(\underline r,\underline c),$$

其中 Hamming 距离定义为

$$d(\underline x,\underline y)=|{i:x_i\neq y_i}|.$$

如果一个码的最小距离为 $d_{\min}$，也就是任意两个不同码字之间的最小 Hamming 距离，那么它可以检测最多 $d_{\min}-1$ 个错误，并且可以纠正最多 $\left\lfloor\frac{d_{\min}-1}{2}\right\rfloor$

个错误。原因很直观：检测错误只需要接收词偏离合法码字；而纠错必须保证接收词仍然离原码字最近，不会落入另一个码字的判决区域。

信道容量（channel capacity）描述的是一个信道在可靠通信意义下最多能传输多少信息。若输入为 $X$，输出为 $Y$，信道容量定义为

$$C=\max_{p(x)} I(X;Y).$$

它表示通过选择最优输入分布，输入与输出之间能够共享的最大互信息。

线性分组码

信道编码的关键是构造一组彼此足够“远”的码字。如果码字之间距离足够大，那么少量错误不会让一个码字看起来像另一个码字。问题是：如何系统地构造这样的码字集合，并高效完成检测与纠错？线性分组码的思想是把码字集合设计成一个向量空间。

线性码与生成矩阵

设字母表 $A$ 是一个有限域，例如二元域 $\mathbb{Z}/2\mathbb{Z}$。一个长度为 $n$、维数为 $k$ 的线性分组码（linear block code）是 $A^n$ 的一个 $k$ 维子空间。也就是说，码字集合 $C\subset A^n$ 对加法和数乘封闭。

若 $C$ 由 $k$ 个线性无关的生成向量

$$\underline g_1,\dots,\underline g_k$$

张成，则任意码字都可以写成

$$\underline c=\sum_{i=1}^k a_i\underline g_i, \qquad a_i\in A.$$

把这些生成向量作为行排列，就得到生成矩阵（generator matrix）：

$$G=\begin{pmatrix} \underline g_1\ \vdots\ \underline g_k \end{pmatrix}\in A^{k\times n}.$$

于是编码可以写成非常简洁的矩阵形式：

$$\underline c=\underline aG,$$

其中 $\underline a\in A^k$ 是待编码的信息向量。这个表达式的好处是，编码不再是任意查表，而是线性映射。

码重、最小距离与纠错能力

对于一个 $n$ 元向量 $\underline r$，其重量（weight）$w(\underline r)$ 是非零坐标的个数。在二元码中，它就是向量中 $1$ 的个数。

对于线性码，有一个非常重要的性质：码的最小距离等于非零码字的最小重量：

$$d_{\min}=w_{\min}=\min{w(\underline c):\underline c\in C,\underline c\neq 0}.$$

原因是任意两个码字之差仍然是码字，而两个码字之间的距离等于它们差向量的重量。这个性质极大简化了最小距离的分析：我们不需要枚举所有码字对，只需要看非零码字的最小重量。

校验矩阵与 syndrome

线性码不仅可以通过生成矩阵描述，也可以通过正交空间描述。设 $C^\perp$ 是所有与 $C$ 中码字正交的向量组成的空间。若用 $C^\perp$ 的一组基作为行向量，就得到校验矩阵（parity-check matrix）：

$$H\in A^{(n-k)\times n}.$$

一个向量 $\underline c$ 是合法码字，当且仅当

$$\underline cH^T=0.$$

因此，当接收端收到 $\underline r$ 时，可以计算伴随式或综合征（syndrome）：

$$\underline s=\underline rH^T.$$

如果 $\underline s\neq 0$，则说明检测到了错误；如果 $\underline s=0$，则 $\underline r$ 是一个合法码字。不过需要注意，$\underline s=0$ 不一定意味着没有错误，因为错误也可能把一个合法码字变成另一个合法码字。

如果发送码字为 $\underline c$，错误向量为 $\underline e$，接收词为

$$\underline r=\underline c+\underline e,$$

则 syndrome 满足

$$\underline rH^T=(\underline c+\underline e)H^T=\underline cH^T+\underline eH^T=\underline eH^T.$$

这说明 syndrome 本质上只依赖错误模式，而与原始码字无关。这正是 syndrome 解码能够工作的根本原因。

Hamming 码：一种典型的一错纠正码

Hamming 码是线性码中最经典的例子。若冗余位数为 $R=n-k$，并且长度满足

$$n=2^R-1,$$

则可以构造一个二元 Hamming 码。其校验矩阵 $H$ 由所有非零的 $R$ 维二元列向量组成。例如当 $R=3$ 时，$n=7,k=4$，校验矩阵的列可以取

$$100,010,001,110,101,011,111.$$

由于每个单比特错误都会对应 $H$ 的某一列，而这些列互不相同，所以 syndrome 可以直接指出错误位置。因此 Hamming 码可以纠正一个错误，检测两个错误。

系统形式编码

一个编码如果把原始信息直接保留在码字的某些位置中，就称为系统形式（systematic form）。典型形式是

$$(a_1,\dots,a_k)\mapsto(c_1,\dots,c_n),$$

并且

$$c_1=a_1,\dots,c_k=a_k.$$

系统形式的生成矩阵可以写为

$$G=(I_k; P),$$

其中 $I_k$ 是单位矩阵，$P$ 是冗余部分对应的矩阵。对应的校验矩阵可写为

$$H=(P^T; -I_{n-k}).$$

在二元域中，因为 $-1=1$，所以也常写为

$$H=(P^T; I_{n-k}).$$

系统形式的好处是编码结果中可以直接读出原始信息位，而冗余位只承担校验作用。任意线性码都等价于某个系统形式的线性码，这里的等价通常指码字坐标经过重排等变换后，距离分布保持不变。

syndrome 解码与陪集领导元

对于二元线性码，所有长度为 $n$ 的向量可以按照码 $C$ 的陪集划分：

$$\underline l+C={\underline l+\underline c:\underline c\in C}.$$

每个陪集选取一个重量最小的代表，称为陪集领导元（coset leader）。解码时，如果接收词为 $\underline r$，先计算 syndrome：

$$\underline s=\underline rH^T.$$

然后在 syndrome 表中找到对应的陪集领导元 $\underline l$，将它视为最可能的错误模式，最终输出

$$\underline c_{\mathrm{emis}}=\underline r-\underline l.$$

这套方法很清楚，但缺点也明显：对于二元 $[n,k]$ 码，陪集数量为

$$2^{n-k},$$

因此完整 syndrome 表的规模随冗余位数指数增长。于是我们需要更强的结构来避免暴力查表，这就引向了代数纠错码。

从线性码到代数码：为什么需要有限域

线性分组码已经把纠错问题变成线性代数问题，但如果只停留在线性代数层面，复杂度仍然可能很高。代数码进一步引入有限域和多项式，把码字、校验、错误位置都表示成代数对象。这样一来，错误定位就可以通过求解多项式方程完成。

从群、环到域

为了理解有限域，需要先区分几个代数结构。

阿贝尔群（abelian group）是带有一个加法运算的集合 $(G,+)$，其中加法满足结合律、交换律，存在零元，并且每个元素都有加法逆元。

环（ring）是在加法群的基础上加入乘法运算的结构。乘法满足结合律，并且对加法满足分配律。

域（field）则进一步要求非零元素都存在乘法逆元。因此，在域中可以自由做加、减、乘、除。常见例子包括有理数域、实数域，以及当 $p$ 是素数时的有限域

$$\mathbb{Z}/p\mathbb{Z}.$$

而 $\mathbb{Z}/n\mathbb{Z}$ 对任意 $n$ 都是环，但只有当 $n$ 为素数时才是域。这一点很关键：纠错码中的除法、求逆、解方程，都要求我们工作在一个域上。

多项式与模不可约多项式

在一个域 $K$ 上，可以考虑多项式环 $K[X]$。其中多项式可以写为

$$P(X)=a_0+a_1X+\cdots+a_nX^n.$$

多项式环中有类似整数的欧几里得除法：对任意 $A(X),B(X)$，且 $B(X)\neq 0$，存在唯一的商 $Q(X)$ 和余数 $R(X)$，使得

$$A(X)=B(X)Q(X)+R(X),\qquad \deg R<\deg B.$$

如果 $P(a)=0$，则 $a$ 是 $P$ 的根，并且 $P(X)$ 可以被 $X-a$ 整除。

一个多项式如果不能分解为更低次数多项式的乘积，就称为不可约多项式（irreducible polynomial）。不可约多项式在多项式环中的地位类似整数中的素数。

构造有限域 $GF(16)$

有限域的一个核心构造是：从二元域 $GF(2)$ 出发，对多项式模一个不可约多项式。若选择四次不可约多项式

$$\Pi(\alpha)=1+\alpha+\alpha^4,$$

并规定

$$\Pi(\alpha)=0,$$

则有

$$\alpha^4=1+\alpha.$$

这样，每个元素都可以表示为次数小于 $4$ 的多项式：

$$a_0+a_1\alpha+a_2\alpha^2+a_3\alpha^3, \qquad a_i\in GF(2).$$

因此它和四位二元向量一一对应：

$$(a_0,a_1,a_2,a_3)\leftrightarrow a_0+a_1\alpha+a_2\alpha^2+a_3\alpha^3.$$

因为每个 $a_i$ 有两个选择，所以共有 $2^4=16$ 个元素，这就是 $GF(16)$。

加法很简单：对应系数按位模 $2$ 相加。乘法则先按普通多项式相乘，再用关系 $\alpha^4=1+\alpha$ 把高次项化简回次数小于 $4$ 的形式。除法则通过求乘法逆元完成。

在实际计算中，经常使用两种表示：加法时用多项式表示更方便，乘法时用 $\alpha$ 的幂表示更方便。若 $\alpha$ 是本原元，则非零元素构成一个循环群：

$$GF(16)^*={1,\alpha,\alpha^2,\dots,\alpha^{14}}, \qquad \alpha^{15}=1.$$

这就是有限域在纠错码中如此有用的原因：它既是向量空间，又有良好的乘法循环结构。

用有限域定位两个错误

有限域可以把“错误发生在哪些位置”转化为“某个多项式的根是什么”。例如在长度为 $15$ 的二元码中，可以把位置和 $GF(16)^*$ 中的幂次对应起来：第 $p+1$ 个位置对应 $\alpha^p$。

如果收到的词为 $\underline r$，错误发生在位置 $I,J$，那么 syndrome 可以写成某些有限域元素的组合。例如构造校验矩阵时使用两行函数

$$H=\begin{pmatrix} 1^T&\alpha^T&\cdots&\alpha^{14T}\ f(1)^T&f(\alpha)^T&\cdots&f(\alpha^{14})^T \end{pmatrix},$$

其中 $f$ 可以取非线性函数，例如 $f:x\mapsto x^3$。若有两个错误，syndrome 的两个分量可以写成

$$S_1=I+J, \qquad S_3=f(I)+f(J).$$

通过 $S_1,S_3$ 可以进一步推出 $IJ$，于是构造错误定位多项式

$$P(X)=(X-I)(X-J)=X^2-S_1X+IJ.$$

接下来只需要在有限域中寻找形如 $\alpha^p$ 的根。如果根是 $\alpha^{p_1},\alpha^{p_2}$，那么错误位置就是

$$p_1+1,\quad p_2+1.$$

这就是代数纠错的核心思路：不再枚举所有错误模式，而是从 syndrome 构造定位多项式，再通过求根定位错误。

Galois 域：有限域的结构

代数纠错码离不开有限域。更一般地，设 $p$ 是素数，$GF(p)$ 是含 $p$ 个元素的有限域。考虑多项式环 $GF(p)[X]$，并固定一个次数为 $r$ 的多项式 $F(X)$。模 $F$ 的多项式商结构记作

$$GF(p)[X]/(F).$$

其中两个多项式 $P_1,P_2$ 如果相差 $F$ 的倍数，就称为模 $F$ 等价：

$$P_1\equiv P_2\pmod F \iff \exists Q(X),; P_1=P_2+FQ.$$

每个等价类都可以用一个次数小于 $r$ 的多项式表示。因此该结构共有 $p^r$ 个元素，并且可以看作 $GF(p)$ 上的 $r$ 维向量空间。

当且仅当 $F(X)$ 是不可约多项式时，$GF(p)[X]/(F)$ 才是一个域，记作

$$GF(p^r).$$

这一定义揭示了有限域的本质：$GF(p^r)$ 不是“整数模 $p^r$”，而是“在 $GF(p)$ 上取一个 $r$ 维代数扩张”。

乘法群与本原元

有限域 $GF(p^r)$ 中的非零元素构成乘法群，记作

$$GF(p^r)^*.$$

它有 $p^r-1$ 个元素。任意非零元素 $\gamma$ 都满足

$$\gamma^{p^r-1}=1.$$

这可以看作有限域版本的 Fermat 小定理。元素 $\gamma$ 的阶（order）定义为最小正整数 $s$，使得

$$\gamma^s=1.$$

并且 $\mathrm{ord}(\gamma)$ 一定整除 $p^r-1$。如果某个元素 $\lambda$ 的阶正好是 $p^r-1$，则它称为本原元（primitive element）。本原元可以生成所有非零元素：

$$GF(p^r)^*={1,\lambda,\lambda^2,\dots,\lambda^{p^r-2}}.$$

这个循环结构是 BCH 码和 Reed–Solomon 码能够用“连续根”构造的基础。

共轭与最小多项式

在有限域扩张中，一个元素 $\beta\in GF(p^r)$ 的共轭由 Frobenius 映射给出：

$$\beta,\beta^p,\beta^{p^2},\dots,\beta^{p^{r-1}}.$$

这是因为在特征为 $p$ 的域中，有

$$(\alpha+\beta)^{p^n}=\alpha^{p^n}+\beta^{p^n}.$$

如果一个系数在 $GF(p)$ 中的多项式以 $\beta$ 为根，那么它也会以 $\beta^p,\beta^{p^2},\dots$ 为根。这说明有限域中的根不是孤立出现的，而是以共轭类的形式出现。

最小多项式（minimal polynomial）是以 $\beta$ 为根的最低次数不可约多项式。设最小的 $e$ 满足

$$\beta^{p^e}=\beta,$$

则 $\beta$ 的最小多项式可以写为

$$\Phi_\beta(X)=\prod_{i=0}^{e-1}(X-\beta^{p^i}).$$

这个多项式的系数落在 $GF(p)$ 中，并且任何以 $\beta$ 为根的 $GF(p)$ 系数多项式都被它整除。这个结论在分解 $X^n-1$ 时非常重要。

循环码：用多项式表示码字

什么是循环码

循环码（cyclic code）是一类特殊的线性分组码：如果一个码字属于码，那么它的循环移位也属于码。例如二元码

$${000,110,011,101}$$

就是循环码，因为每个非零码字循环移位后仍然在集合中。

循环码之所以重要，是因为循环移位可以用多项式乘以 $X$ 来表达。给定长度为 $n$ 的向量

$$(b_0,b_1,\dots,b_{n-1}),$$

把它表示为多项式

$$b(X)=b_0+b_1X+\cdots+b_{n-1}X^{n-1}.$$

在模 $X^n-1$ 的意义下，乘以 $X$ 正好对应循环移位。于是，循环码可以转化为多项式环

$$K[X]/(X^n-1)$$

中的理想结构。

生成多项式

循环码的核心定理是：任意长度为 $n$ 的循环码都由 $X^n-1$ 的某个因子生成。也就是说，存在唯一的首一多项式 $g(X)$，称为生成多项式（generator polynomial），使得

$$g(X)\mid X^n-1,$$

并且码中所有多项式都是 $g(X)$ 的倍数模 $X^n-1$：

$$C=\langle g(X)\rangle ={a(X)g(X)\bmod (X^n-1):a(X)\in K[X]}.$$

若 $\deg g=r$，则码的维数为

$$k=n-r.$$

对应的生成矩阵可以由

$$g(X),Xg(X),\dots,X^{k-1}g(X)$$

这些多项式的系数向量组成。

如果

$$X^n-1=g(X)h(X),$$

那么 $h(X)$ 与校验矩阵密切相关。循环码的校验条件可以用生成多项式和校验多项式共同描述。

循环码的系统编码

循环码也可以做系统形式编码。设信息向量为

$$\underline i=(i_0,\dots,i_{k-1}),$$

对应信息多项式

$$i(X)=i_0+i_1X+\cdots+i_{k-1}X^{k-1}.$$

为了给信息后面加上 $n-k$ 个校验位，先计算

$$X^{n-k}i(X).$$

这相当于把信息多项式整体左移，为校验位预留位置。然后用生成多项式 $g(X)$ 做除法，得到余数

$$r(X)=X^{n-k}i(X)\bmod g(X), \qquad \deg r<n-k.$$

最后令

$$c(X)=X^{n-k}i(X)+r(X).$$

因为 $r(X)$ 正好抵消了除以 $g(X)$ 的余数，所以 $c(X)$ 能被 $g(X)$ 整除，是合法码字。同时，信息部分仍然保留在码字中，因此这是系统编码。

例如对于 $(n,k)=(7,4)$，若

$$g(X)=X^3+X+1,$$

信息为 $1011$，即

$$i(X)=1+X^2+X^3,$$

则计算

$$X^3i(X)\bmod g(X)=1.$$

因此得到系统码字

$$1001011.$$

分解 $X^n-1$

为了构造循环码，需要知道 $X^n-1$ 在基础域上的不可约因子分解。设要构造 $GF(p)$ 上长度为 $n$ 的循环码，并且 $\gcd(n,p)=1$。选择最小的整数 $l$，使得

$$n\mid p^l-1.$$

那么 $GF(p^l)$ 中包含所有 $n$ 次单位根。若 $\alpha$ 是 $GF(p^l)$ 的本原元，设

$$p^l-1=nq_0, \qquad \beta=\alpha^{q_0},$$

则 $\beta$ 是一个 $n$ 次单位根，并且

$$X^n-1=\prod_{i=0}^{n-1}(X-\beta^i)$$

在扩域 $GF(p^l)$ 上完全分解。

但我们通常希望得到的是 $GF(p)$ 上的不可约因子。因此需要把根 $\beta^i$ 按共轭类分组，每个共轭类对应一个最小多项式。最后，$X^n-1$ 在 $GF(p)$ 上可以分解为这些最小多项式的乘积。

这个过程是 BCH 码构造的代数基础：我们通过选择若干个根，再取它们最小多项式的最小公倍数，得到生成多项式。

BCH 码：用连续根保证纠错能力

BCH 码的构造思想

BCH 码是一类重要的循环码。它的核心设计思想是：如果生成多项式 $g(X)$ 拥有若干个连续的根，那么这个码就具有可保证的最小距离，从而能够纠正一定数量的错误。

设 $\alpha$ 是 $GF(2^l)$ 的本原元。若我们希望构造能够纠正 $t$ 个错误的二元 BCH 码，可以选择生成多项式

$$g(X)=\mathrm{lcm}(f_1(X),f_2(X),\dots,f_{2t}(X)),$$

其中 $f_i(X)$ 是 $\alpha^i$ 在 $GF(2)$ 上的最小多项式。于是 $g(X)$ 至少以

$$\alpha,\alpha^2,\dots,\alpha^{2t}$$

为根。

BCH 码的关键定理是：如果生成多项式包含 $2t$ 个连续根，那么该码至少可以纠正 $t$ 个错误。

BCH 码的校验矩阵与 syndrome

BCH 码的校验矩阵可以在扩域中写成 Vandermonde 形式：

$$H_0= \begin{pmatrix} 1&\alpha&\alpha^2&\cdots&\alpha^{n-1}\\ 1&\alpha^2&(\alpha^2)^2&\cdots&(\alpha^2)^{n-1}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&\alpha^{2t}&(\alpha^{2t})^2&\cdots&(\alpha^{2t})^{n-1} \end{pmatrix}.$$

如果接收多项式为

$$R(X)=r_0+r_1X+\cdots+r_{n-1}X^{n-1},$$

则 syndrome 的第 $i$ 个分量为

$$s_i=R(\alpha^i)=\sum_{j=0}^{n-1}r_j\alpha^{ij}.$$

因为合法码字 $C(X)$ 满足 $C(\alpha^i)=0$，所以

$$s_i=R(\alpha^i)=C(\alpha^i)+E(\alpha^i)=E(\alpha^i).$$

也就是说，syndrome 只反映错误多项式 $E(X)$。

对于二元 BCH 码，还可以利用关系

$$s_{2i}=s_i^2,$$

因此实际计算中常常只保留奇数行 syndrome。

错误定位多项式

假设实际发生了 $\nu$ 个错误，错误位置为

$$j_1,\dots,j_\nu.$$

令

$$\beta_l=\alpha^{j_l}.$$

错误多项式为

$$E(X)=X^{j_1}+\cdots+X^{j_\nu},$$

因此 syndrome 满足

$$s_i=\beta_1^i+\beta_2^i+\cdots+\beta_\nu^i, \qquad i=1,\dots,2t.$$

我们希望从这些 power sums 中恢复 $\beta_l$。为此构造错误定位多项式（error locator polynomial）：

$$\sigma(X)=\prod_{l=1}^{\nu}(X-\beta_l) =X^\nu+\sigma_1X^{\nu-1}+\cdots+\sigma_\nu.$$

由于每个 $\beta_l$ 都是根，有

$$\sigma(\beta_l)=0.$$

利用这一点可以建立关于 $\sigma_1,\dots,\sigma_\nu$ 的线性方程组：

$$\begin{cases} s_{\nu+1}+\sigma_1s_\nu+\cdots+\sigma_\nu s_1=0,\ \vdots\ s_{2\nu}+\sigma_1s_{2\nu-1}+\cdots+\sigma_\nu s_\nu=0. \end{cases}$$

求出错误定位多项式后，只需要逐个测试 $X=\alpha^i$，找到使 $\sigma(\alpha^i)=0$ 的位置，就得到错误位置 $i$。这一步本质上是在有限域中求根。

因此 BCH 解码可以概括为两步：先由 syndrome 求错误定位多项式，再由定位多项式求错误位置。

Reed–Solomon 码：按符号纠错

Reed–Solomon 码可以看作一种非二元 BCH 码。它的码字符号直接取自有限域 $GF(2^m)$，长度通常为

$$n=2^m-1.$$

与二元 BCH 码不同，Reed–Solomon 码不是逐 bit 工作，而是逐符号工作。每个符号包含 $m$ 个 bit。因此，它特别擅长纠正突发错误：如果一段连续 bit 出错，只要这些错误集中在少数几个符号中，就可以被纠正。

一个能够纠正 $t$ 个符号错误的 Reed–Solomon 码，其生成多项式拥有 $2t$ 个连续根。编码方法与循环码类似，只是多项式系数现在位于 $GF(2^m)$ 中，而不是二元域中。

在解码中，首先像 BCH 码一样计算 syndrome，并构造错误定位多项式。得到错误位置后，还需要计算每个错误位置上的错误值。设错误位置对应

$$\beta_1,\dots,\beta_\nu,$$

错误值为

$$Y_1,\dots,Y_\nu.$$

则 syndrome 满足线性系统：

$$\begin{cases} Y_1\beta_1+Y_2\beta_2+\cdots+Y_\nu\beta_\nu=s_1, \\ Y_1\beta_1^2+Y_2\beta_2^2+\cdots+Y_\nu\beta_\nu^2=s_2,\\ \vdots\\ Y_1\beta_1^\nu+Y_2\beta_2^\nu+\cdots+Y_\nu\beta_\nu^\nu=s_\nu. \end{cases}$$

求解这个系统即可得到错误幅值，从而构造错误多项式并完成纠正。

Reed–Solomon 码的关键优势在于，它纠正的是符号错误，而不是单独的 bit 错误。因此，长度为若干 bit 的突发错误只要落在少量符号内，就可以被视作少数符号错误处理。这也是它广泛用于存储系统、二维码、光盘、通信系统中的原因。