线性码

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

二元重复码 $\{000,111\}$ 是 $[3,1,3{]}_2$ 线性码。任意非线性码没有生成矩阵意义。矩阵 $G$ 需满行秩才能使消息维数为 $k$；不同生成矩阵可表示同一码。能检测至多 $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]$ 只是方便形式，不是定义要求。综合相同的多个高重量错误会落入同一陪集，最近邻译码超出保证半径后可能选错。

线性码用于通信和存储，并使编码、综合译码、对偶码和代数构造可高效实现。向量空间公理库向量空间Vector space标量域作用下满足线性公理的加法阿贝尔群。提供线性结构，Hamming 距离公理库Hamming 距离Hamming distance两个等长字在对应位置不同的坐标数。给出最小距离，综合译码公理库综合译码Syndrome decoding用校验矩阵计算接收向量综合并选择相应陪集首领纠错的译码方法。利用校验矩阵。参数上，线性 Singleton 界公理库Singleton 界Singleton bound通过删去最小距离减一个坐标，给出码字数、块长与距离之间的普适上界。要求 $k\le n-d+1$，而线性 Varshamov 版本公理库Gilbert–Varshamov 界Gilbert–Varshamov bound · GV bound由极大码的覆盖性质证明具有给定最小距离的大码存在，并导出渐近可达率下界。给出满足相应计数条件的码存在；前者约束所有线性码，后者不承诺显式高效构造。Reed–Solomon、BCH、LDPC 等码都在不同域和稀疏结构上发展这一框架。

全局线性结构不等于局部访问。局部可测试码公理库局部可测试码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$ 直接读出。