线性码

线性码把码字集合选成有限域向量空间的子空间，用生成矩阵把消息线性映射成带冗余的向量，再由奇偶校验矩阵检验 $H{c}^T=0$。线性结构使码字之差仍是码字，从而把任意两码字的距离分析化为非零码字的最小重量，显著简化参数分析和综合译码。代价是码字集合受线性限制，不一定对所有信道和块长最优。

从矩阵走完一次纠错 ​

二元重复码 $\{000,111\}$ 是 $[3,1,3{]}_2$ 线性码，可以取

消息 $1$ 编为 $111$。第二位翻转后收到 $r=101$，综合 $H{r}^T=(1,1{)}^T$ 恰为 $H$ 的第二列，翻转该位置便恢复 $111$。所有运算都在 ${\mathbb{F}}_2$ 中；三个非零且不同的列使三个单比特错误具有不同综合。同样的两行校验在稳定子码理路稳定子码Stabilizer code · 稳定子量子码以对易 Pauli 的共同本征空间编码量子信息，构造综合测量与恢复信道，并证明三比特码对相干比特翻转的纠正范围。中成为 $ZZI$ 与 $IZZ$，但量子恢复还须保留 $\alpha |000⟩+\beta |111⟩$ 中的相干，且不能由经典距离 $3$ 推出可纠正任意单 qubit 错误。

然而错误 $e=101$ 与单比特错误 $010$ 都产生综合 $(1,1{)}^T$，按单错规则会误纠。距离 $d$ 只保证检测至多 $d-1$ 个非零错误，唯一纠正至多 $\lfloor (d-1)/2\rfloor$ 个错误。非线性码仍可用一般编码映射描述，但不能由一个矩阵的行空间完整表示。

二元 $(7,4)$ Hamming 码把 $4$ 个信息 bit 映为 $7$ bit 码字，最小距离 $3$，可纠正一位错误。接收词 $r=c+e$ 的综合为 $H{r}^T=H{e}^T$，单 bit 错误时对应 $H$ 的某一列，从而定位错误位置。

生成矩阵行必须线性独立才能达到声明维数；系统形 $[I|P]$ 只是方便形式，不是定义要求。综合相同的多个高重量错误会落入同一陪集，最近邻译码超出保证半径后可能选错。

线性结构支持高效编码、综合计算和对偶码构造：给定矩阵，$mG$ 与 $H{r}^T$ 都可直接计算，对偶的基也可由消元得到。但综合译码理路综合译码Syndrome decoding利用校验矩阵消去码字成分，以综合定位错误陪集并选择首领；区分合法输出、正确恢复与一般译码困难性。还要从 $H{e}^T=H{r}^T$ 的许多解中寻找低重量错误。这是额外的搜索问题，一般线性码并不因此拥有高效译码算法；Reed–Solomon、BCH 等特定码族要依靠各自的结构与算法，LDPC 的迭代译码也须另论成功条件。

向量空间理路向量空间Vector space标量域作用下满足线性公理的加法阿贝尔群。决定线性码的维数，Hamming 距离理路Hamming 距离Hamming distance等长字中不同坐标的数量；由逐位比较、三角不等式和 Hamming 球解释检错与唯一纠错半径。决定其检测与唯一纠错半径。参数上，线性 Singleton 界理路Singleton 界Singleton bound通过删去最小距离减一个坐标，给出码字数、块长与距离之间的普适上界。要求 $k\le n-d+1$；线性 Varshamov 版本理路Gilbert–Varshamov 界Gilbert–Varshamov bound · GV bound由极大码的覆盖性质证明具有给定最小距离的大码存在，并导出渐近可达率下界。则在相应计数条件下保证码存在。存在性、显式构造与高效译码是三个不同承诺，不能由其中一个自动推出另外两个。

全局线性结构不等于局部访问。局部可测试码理路局部可测试码Locally testable code · LTC通过少量码字符号查询区分合法码字与到整个码至少相距 ε 的接收词，并量化局部拒绝概率。要求只查询接收词少量坐标，就能区分码字与距码至少 $\epsilon$ 的词；局部译码与纠错理路局部译码与局部纠错Locally decodable code · Locally correctable code · Local decoding在接收词接近某个码字时，以少量坐标查询恢复指定消息符号或指定码字符号。则要从同样受损的 oracle 中恢复指定消息位或码字符号。前者是性质测试，后者是恢复任务，查询复杂度都必须连同噪声半径、成功概率和适应性声明。若码字经物理信道发送，成本是块长与码率；若两方用编码交换私有输入，通信复杂度理路两方通信模型Two-party communication model · Two-party communication complexity model两位参与者各自持有私有输入，只以交换消息协同计算函数或关系，并把通信位数作为核心资源。另按实际发送的 bit 计费，不能由维数 $k$ 或距离 $d$ 直接读出。

固定码本后，还要说明使用哪种距离 ​

有限域线性子空间可以同时配上不同距离。扩域秩度量理路秩度量码Rank-metric code · 秩距离码以错误矩阵的秩或扩域符号张成的底域维数衡量噪声，证明矩形Singleton界、秩一球计数及唯一纠错半径。把 $L^n$ 中的词展开为底域矩阵，按矩阵秩而非非零坐标数计费；若子空间在 $L={\mathbb{F}}_{q^m}$ 上维数为 $k$，其底域维数就是 $mk$。线性码的核与生成矩阵接口仍然有效，具体最小距离和纠错半径却需重新证明。

Gabidulin求值码理路Gabidulin码与Moore求值Gabidulin code · Gabidulin evaluation code在底域独立的求值点上评价低q次数线性化消息，构造达到秩Singleton界的线性码，并证明最小距离与任意k个坐标的擦除恢复。由底域独立的输入点及低 $q$ 次数消息给出满行秩Moore生成矩阵，达到 $d_R=n-k+1$。相应插值译码利用这一特殊结构，而不是给任意线性子空间自动配上一份高效最近邻算法。

群平移对称给最小重量的另一份证书 ​

若坐标由有限群 $G$ 标记，且非零码空间 $C\subseteq {\mathbb{F}}_q^G$ 在所有右平移下保持不变，平移支撑覆盖理路有限群的支撑与秩不确定性Finite-group support-rank uncertainty · Meshulam rank-support inequality用平移基的支撑覆盖证明任意域上的稀疏度与卷积秩乘积界，再给平移不变空间的擦除恢复保证和精确秩判据。给 $d\ge \lceil |G|/\dim C\rceil$。证明对任意非零词从其真实平移中取基，再用这些基的支撑覆盖全部群坐标，不要求域特征与群阶互素。

这给位置已知的擦除一项充分保证：$|E|\dim C<|G|$ 时，合法词由剩余坐标唯一确定。具体模式的精确条件仍是列基矩阵保留行满列秩，恢复前也要检查数据相容性。S3右陪集常值码可以恢复某些两处擦除，却不能恢复完整一个两元素陪集被删的情况；统一数量界不是每个模式的必要条件。