信道码

信道码把消息映射为加入结构和冗余的更长码字，通过在码字集合中留出几何距离，使不同消息经过噪声后仍能在输出空间中分开。编码率衡量有效信息占用，最小距离决定可检测或纠正的错误数；冗余越多通常越稳健，却降低速率。解码根据接收词选择最可能或最近的码字，而信道模型决定“最近”的度量是否合适。

三重重复码把 bit $0,1$ 分别编码为 000,111，码率 $1/3$、最小 Hamming 距离 $3$，可纠正任意一位翻转。若收到 101，它与 111 的距离为 $1$、与 000 的距离为 $2$，所以最近邻解码为 $1$。随机码证明存在性不等于给出高效编码与译码；平均错误小也不自动保证每个消息的错误都小，通常可通过 expurgation 转换，但会损失少量码字。

最小距离 $d$ 只能保证唯一纠正至多 $\lfloor (d-1)/2\rfloor$ 个任意错误；列表译码公理库列表译码List decoding允许每个接收词对应一个受控候选列表，从而在组合意义上越过唯一译码半径。允许输出至多 $L$ 个候选，可以越过这个半径，但小列表与高效找到完整列表是两项不同要求。码率高并不单独代表好码，还需在给定信道和块长下考察错误概率、列表大小与译码复杂度。

信道码支撑数字通信、存储和网络传输，并把容量定义转化为可达码率问题。Hamming 距离公理库Hamming 距离Hamming distance两个等长字在对应位置不同的坐标数。提供码字几何，线性码公理库线性码Linear code有限域向量空间中的线性子空间作为码字集合的信道码。用子空间结构简化编码译码；Singleton 界公理库Singleton 界Singleton bound通过删去最小距离减一个坐标，给出码字数、块长与距离之间的普适上界。给出码大小的普适上界，Gilbert–Varshamov 界公理库Gilbert–Varshamov 界Gilbert–Varshamov bound · GV bound由极大码的覆盖性质证明具有给定最小距离的大码存在，并导出渐近可达率下界。则给出存在性下界，二者方向不能互换。信道编码定理公理库有噪信道编码定理Noisy-channel coding theorem · Channel coding theorem低于离散无记忆信道容量的速率可实现任意小错误概率，而高于容量的速率不能可靠传输。说明存在速率接近容量的码族，Reed–Solomon、LDPC、polar code 则实现不同错误模型和复杂度权衡。

“通信”在这里指码字经过带噪信道，码率按块长计算；通信复杂度公理库两方通信模型Two-party communication model · Two-party communication complexity model两位参与者各自持有私有输入，只以交换消息协同计算函数或关系，并把通信位数作为核心资源。则假设参与者各持私有输入、本地计算免费，并计算为求函数而交换的 bit。两者都研究可靠传递，却不能把信道容量直接当作函数通信复杂度。若接收者只读受损码字的少数坐标，问题又分成测试与恢复两个目标。局部译码/纠错公理库局部译码与局部纠错Locally decodable code · Locally correctable code · Local decoding在接收词接近某个码字时，以少量坐标查询恢复指定消息符号或指定码字符号。恢复指定消息位或码字符号，局部可测试码公理库局部可测试码Locally testable code · LTC通过少量码字符号查询区分合法码字与到整个码至少相距 ε 的接收词，并量化局部拒绝概率。只判断接收词是否属于码或远离码；后者的少量查询不会给出完整译码器。