线性码的编码理论基础

【线性码的基本定义】

长度为 $n$ 且维度为 $k$ 的线性码（Linear Code）是定义在 $n$ 维有限域 $\mathbb{F}_q^n$ 中维度为 $k$ 的线性子空间 $C$，其中 $\mathbb{F}_q$ 是具有 $q$ 个元素的有限域，通常称为 q 元码

如果 $q=2$ 或 $q=3$，则分别称为二进制线性码、三进制线性码，线性子空间 $C$ 中的向量称为码字（Codeword），线性码的大小是码字的数量，即 $q^k$

码字的权重（Weight）通常用 Hamming 重量衡量，即码字中非零元素的个数；两个码字之间的距离（Distances）通常用 Hamming 距离衡量，即它们之间不同的元素个数。线性码的距离 $d$，是非零码字的最小权重，其等价于不同码字间的最小距离

长度为 $n$、维度为 $k$、距离为 $d$ 的线性码，通常记为：

$$[n,k,d]_q$$

对于 $\mathbb{F}_q^{n}$，整个线性码组 $C$ 可以表示为一组长度为 $k$ 的码字的线性组合，这些基码字通常被整理成生成矩阵 $G$ 的行。那么，对于二进制线性码，其可以由一个 $k\times n$ 的二进制生成矩阵表示，该矩阵满足如下性质：任意非空行子集的模 $2$ 向量和中，至少有 $d$ 个位置为 $1$，即任意非零码字的 Hamming 距离至少为 $d$

【线性码的唯一纠错能力】

设一条长度为 $k$ 的原始比特消息编码后得到码字 $\mathbf{c}$，传输过程中有一些位置被翻转，接收方收到的内容是 $\mathbf{r}$。如果错误位置数为 $t$，那么有：

$$\Delta(\mathbf{r},\mathbf{c})=t$$

其中，$\Delta(\cdot,\cdot)$ 表示 Hamming 距离

如果存在另一个码字 $\mathbf{c}’$ 也可能解释为原始码字，且它距离接收向量 $\mathbf{r}$ 也不超过 $t$，那么根据三角不等式，有：

$$\Delta(\mathbf{c},\mathbf{c}')\leq \Delta(\mathbf{c},\mathbf{r}) + \Delta(\mathbf{c}',\mathbf{r}) \leq 2t$$

但由于线性码的最小距离是 $d$，即任意两个不同码字间的距离至少是：

$$\Delta(\mathbf{c},\mathbf{c}')\geq d$$

所以，如果 $2t<d$，就不可能同时存在两个不同的码字 $\mathbf{c}$ 与 $\mathbf{c}’$ 都距离 $\mathbf{c}$ 很近。也就是说，接收方只能找到唯一一个最接近的码字，即原始码字

因此，线性码纠错的上界是 $t<\frac{d}{2}$，即最多能够纠正的错误数是：

$$t_{\max}=\lfloor \frac{d-1}{2} \rfloor$$

也就是说，只要被翻转的位置数不超过 $\left\lfloor \frac{d-1}{2}\right\rfloor$，接收方就可以唯一确定原始码字，并进一步恢复出原始消息

【Hamming 球与球体积】

Hamming 球堆积上界（Hamming Sphere-Packing Bound）刻画的是在给定纠错能力的情况下，一个码的是码率最多能有多大

Hamming 球

对于长度为 $n$ 的 $q$ 元向量构成的空间 $\mathbb{F}_q^n$，其大小为 $q^n$。对于某个向量 $\mathbf{u}\in \mathbb{F}_q^n$，以 $\mathbf{u}$ 为中心、半径为 $r$ 的 Hamming 球（Hamming Ball） 定义为：

$$B_q(\mathbf{u},r)=\{\mathbf{v}\in \mathbb{F}_q^n:\Delta(\mathbf{u},\mathbf{v})\leq r\}$$

其中，$\Delta(\mathbf{u},\mathbf{v})$ 表示 $\mathbf{u}$ 与 $\mathbf{v}$ 的 Hamming 距离

Hamming 球体积

如果一个向量与中心 $\mathbf{u}$ 的距离恰好为 $i$，就需要从 $n$ 个位置中选出 $i$ 个出错位置，再在每个位置上选择一个不同于原符号的值。每个位置有 $q-1$ 种选择，所以距离恰好为 $i$ 的向量数量为 $\binom{n}{i}(q-1)^i$，将 $i=0$ 到 $t$ 的情况加起来，就得到半径为 $t$ 的 Hamming 球体积，即：

$$V_q(n,r)=\sum_{i=0}^{r}\binom{n}{i}(q-1)^i$$

对于二进制情形，$q=2$，故有：

$$V_2(n,r)=\sum_{i=0}^{r}\binom{n}{i}$$

二进制线性码的 Hamming 球体积渐近估计

对于二进制 Hamming 球，考虑 $t$ 和 $n$ 成比例增长时的情况，令 $t\approx\alpha n,0<\alpha<\frac{1}{2}$，此时 Hamming 球体积可以写为近似形式，即：

$$V_2(n,t)=\sum_{i=0}^{t}\binom{n}{i} \approx \sum_{i=0}^{\alpha n}\binom{n}{i}$$

在这个求和式中，最大的二项式系数出现在 $i=\alpha n$ 附近，记 $H_2(\cdot)$ 为二进制熵，则根据二项式系数的经典熵估计，有：

$$\binom{n}{i} \approx 2^{nH_2(\alpha)}$$

由于整个求和在指数阶上由最大的二项式系数控制，因此：

$$\sum_{i=0}^{\alpha n}\binom{n}{i} \approx 2^{nH_2(\alpha)}$$

也就是说，当 Hamming 球半径 $t$ 占码长比例约为 $\alpha$ 时，二进制 Hamming 球体积的指数阶近似为：

$$V_2(n,\alpha n)\approx 2^{nH_2(\alpha)}$$

进一步，若二进制线性码的相对距离为 $\delta=\frac{d}{n}$，则最小距离为 $d=\delta n$，对应的唯一纠错半径为：

$$t=\lfloor \frac{d-1}{2} \rfloor \approx \frac{d}{2}=\frac{\delta n}{2}$$

因此，有：

$$\alpha = \frac{t}{n}\approx \frac{\delta}{2}$$

将其代入 Hamming 球体积估计，可得：

$$V_2(n,t)\approx 2^{n H_2(\frac{\delta }{2})}$$

【Hamming 球体积堆积上界】

球体积堆积

对于 $[n,k,d]_q$ 线性码，其有 $q^k$ 个码字，若以每个码字为中心，画一个半径为 $t$ 的 Hamming 球，那么这些球就不能相交。因为如果两个球相交，就会存在一个接收向量 $\mathbf{r}$ 同时距离两个不同码字都不超过 $t$，接收方就无法唯一判断原始码字

因此，所有这些 Hamming 球的总体积不能超过整个空间大小，即：

$$q^k \cdot V_q(n,t) \leq q^n$$

化简可得：

$$V_q(n,t)\leq q^{n-k}$$

该不等式说明，如果希望纠错能力更强，也就是 $t$ 更大，那么每个码字周围的 Hamming 球体积就会增大。在总空间 $q^n$ 固定的情况下，能放下的互不相交的 Hamming 球就越少，码字数量和码字就都受到限制

对于二进制情形，$q=2$，故有：

$$V_2(n,t)\leq 2^{n-k}$$

二进制线性码的码率上界

对于二进制线性码，Hamming 球堆积上界为：

$$V_2(n,t)\leq 2^{n-k}$$

将 Hamming 球体积渐近估计 $V_2(n,t)\approx 2^{n H_2(\frac{\delta }{2})}$ 代入，有：

$$2^k\cdot 2^{nH_2(\frac{\delta}{2})}\lesssim 2^n$$

两边同时取 $\log_2$，并除以 $n$ 可得：

$$\frac{k}{n}+H_2\left(\frac{\delta}{2}\right)\lesssim 1$$

由于码率定义为：

$$R=\frac{1}{n}\log_2 2^k=\frac{k}{n}$$

因此可以得到 Hamming 球堆积上界对应的渐近码率限制：

$$R\leq 1-H_2\left(\frac{\delta}{2}\right)$$

这说明，当相对距离 $\delta$ 增大时，纠错半径约为 $\frac{\delta n}{2}$，每个码字周围的 Hamming 球体积也会增大，由于整个空间大小固定为 $2^n$，能够容纳的码字数量就必须减少，因此码率 $R$ 会受到上界限制

【Gilbert–Varshamov 下界】

Hamming 球堆积上界说明，如果要保证最小距离，那么码字不能太多。Gilbert–Varshamov 下界（Gilbert–Varshamov Bound）则从另一个方向说明：在给定线性码长度和距离的情况下，至少存在码字数量足够多、最小距离足够大的码

简单来说，Hamming 球堆积上界给出限制，而 GV 下界给出存在性保证

最大码数

记 $A_q(n,d)$ 表示在 $q$ 元空间 $\mathbb{F}_q^n$ 中，所有最小距离至少为 $d$ 的码里，最多能够拥有的码字数量。也就是说，$A_q(n,d)$ 是满足以下条件的码的最大规模：

$$\forall \mathbf{c}\neq \mathbf{c}' \notin \mathcal{C}\subseteq \mathbb{F}_{q}^{n},\quad \Delta(\mathbf{c},\mathbf{c}')\geq d$$

因此， $A_q(n,d)$ 是在长度为 $n$、任意两个码字间至少相差 $d$ 个位置的条件下，最多能够拥有的码字数量

最大码的覆盖性质

下面考虑一个已经达到最大规模的码 $\mathcal{C}$，即：

$$|\mathcal{C}|=A_q(n,d)$$

假设存在某个向量 $\mathbf{u}\in \mathbb{F}_q^n$，并且它到 $\mathcal{C}$ 中所有码字的距离都至少为 $d$，即：

$$\Delta(\mathbf{u},\mathbf{c})\geq d,\quad \forall c\in\mathcal{C}$$

那么，把 $\mathbf{u}$ 加入 $\mathcal{C}$ 后，新的码：

$$\mathcal{C}'=\mathcal{C}\cup\{\mathbf{u}\}$$

仍然满足任意两个码字之间距离至少为 $d$，这说明 $\mathcal{C}’$ 也是一个最小距离至少为 $d$ 的码，但它的码字数量比 $\mathcal{C}$ 多一个

而已经达到最大规模的码 $\mathcal{C}$ 已经不能再加入新的码字了，否则就会超出最大规模，这就与 $\mathcal{C}$ 已经是最大码矛盾。因此，对于最大码 $\mathcal{C}$，不可能存在这样的 $\mathbf{u}$

换句话说，对任意向量 $\mathbf{u}\in\mathbb{F}_q^n$，它都必须距离某个码字 $\mathbf{c}\in\mathcal{C}$ 至多为 $d-1$，即：

$$\exists \mathbf{c}\in\mathcal{C},\quad \Delta(\mathbf{u},\mathbf{c})\leq d-1$$

其几何含义是：以 $\mathcal{C}$ 中每个码字为中心，画半径为 $d-1$ 的 Hamming 球，这些球必须覆盖整个空间 $\mathbb{F}_q^n$

GV 下界的基本形式

对于半径为 $d-1$ 的 Hamming 球，球体积为：

$$V_q(n,d-1)=\sum_{i=0}^{d-1}\binom{n}{i}(q-1)^i$$

由于最大码 $\mathcal{C}$ 中有 $A_q(n,d)$ 个码字，所以一共有 $A_q(n,d)$ 个这样的 Hamming 球。这些球必须覆盖空间大小为 $q^n$ 的整个空间 $\mathbb{F}_q^n$，即这些球之间可以重叠，但总体积一定不能小于整个空间大小，所以有：

$$A_q(n,d)\cdot V_q(n,d-1)\geq q^n$$

于是得到：

$$A_q(n,d)\geq \frac{q^n}{V_q(n,d-1)}$$

这就是 Gilbert–Varshamov 下界的基本形式，其说明存在一个长度为 $n$、最小距离至少为 $d$ 的 $q$ 元码，其码字数量至少为

$$\frac{q^n}{V_q(n,d-1)}$$

二进制情形下的 GV 下界

考虑二进制情形，即 $q=2$。此时，整个空间大小为 $2^n$，半径为 $d-1$ 的 Hamming 球体积为：

$$V_2(n,d-1)=\sum_{i=0}^{d-1}\binom{n}{i}$$

因此 GV 下界写为：

$$A_2(n,d)\geq \frac{2^n}{V_2(n,d-1)}$$

设相对距离为 $\delta=\frac{d}{n}$，即 $d=\delta n$，在渐近分析中 $d-1$ 与 $d$ 的差别可以忽略，因此有：

$$\frac{d-1}{n}\approx \delta$$

当 $0<\delta<\frac12$ 时，二进制 Hamming 球体积可以用二元熵函数估计：

$$V_2(n,d-1) = \sum_{i=0}^{d-1}\binom{n}{i} \lesssim 2^{nH_2(\delta)}$$

将其代入 GV 下界，有：

$$A_2(n,d) \gtrsim \frac{2^n}{2^{nH_2(\delta)}}$$

即：

$$A_2(n,d) \gtrsim 2^{n(1-H_2(\delta))}$$

这说明在长度为 $n$、相对距离为 $\delta$ 的二进制线性码中，至少存在一个码，其码字数量可以达到指数规模：

$$2^{n(1-H_2(\delta))}$$

二进制线性码的存在性条件

二进制下的 GV 下界说明，在长度为 $n$、相对距离为 $\delta$ 的条件下，至少存在码字数量达到 $2^{n(1-H_2(\delta))}$ 的二进制线性码

因此，若目标二进制线性码 $[n,k,d]_2$ 的码字数量 $2^k$ 不超过这一可保证存在的规模，就可以保证存在具有相应参数的二进制线性码，即有：

$$2^k \lesssim 2^{n(1-H_2(\delta))}$$

将上述不等式取 $\log_2$ 并除以 $n$，有：

$$\frac{k}{n}\lesssim 1-H_2(\delta)$$

因此，在二进制渐近意义下，GV 下界通常写为存在性条件：

$$\frac{k}{n}<1-H_2\left(\frac{d}{n}\right)$$

【随机线性码的生成】

对于二进制线性码 $[n,k,d]_2$，GV 下界保证，只要码率 $\frac{k}{n}$ 低于 GV 下界给出的阈值，就存在长度为 $n$、维度为 $k$、最小距离至少为 $d$ 的二进制线性码，即：

$$\frac{k}{n}<1-H_2\left(\frac{d}{n}\right)$$

进一步地，如果存在某个 $\varepsilon>0$，使得：

$$\frac{k}{n}<1-H_2\left(\frac{(1+\varepsilon)d}{n}\right)$$

那么这一条件不仅保证这样的线性码存在，而且可以保证几乎所有随机选取的 $k\times n$ 二进制生成矩阵，都会构成 $[n,k,d]_2$ 码

直观上说，码率留出的余量越大，生成矩阵中的冗余越充分，随机矩阵生成好线性码的概率就越高。因此，当取常数 $\kappa,\delta,\varepsilon>0$，并满足：

$$\kappa<1-H_2((1+\varepsilon)\delta)$$

时，随机选取一个 $\kappa n\times n$ 的二进制矩阵 $C$，它就大概率生成一个最小距离至少为 $\delta n$ 的线性码