信道码

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

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

在翻转概率 $p=0.1$ 的独立二元对称信道上，多数译码失败当且仅当至少两位翻转，故

与不编码的错误率 $0.1$ 比，可靠性提高，但传一 bit 需三次信道使用。若三位总是一起翻转，错误率仍为 $0.1$，所以距离保证与随机错误率不是同一指标。

平均错误转最大错误也可具体计算：若 ${\overline{P}}_e\le \epsilon$，错误率超过 $2\epsilon$ 的消息不可能占一半以上。保留其余至少 $M/2$ 个消息，最大错误不超过 $2\epsilon$，码率损失至多 $1/n$ bit/次使用。

删消息还要修改译码器：保留原译码器对保留消息的所有判决区；若原来输出已删消息，就改为任一固定的保留消息，再重新编号。这样输出仍属于新的消息集合，保留消息原本判对的事件不会丢失，条件错误不会增加。随机抽码允许重复码字；但若删码后最大错误小于 $1/2$，两条保留消息不可能共用码字，因为相同输出分布下两者的成功概率之和至多为 $1$。

这个删码论证针对单用户。两个发送者分别编码理路二用户多址信道容量区域Multiple-access channel capacity region · Two-user DM-MAC capacity · 多址信道容量两个无反馈的独立发送者共享一个接收端时，可靠速率由两条条件互信息界和一条总率界共同限制；时间共享、三类候选错误和整数加法信道给出完整可复算的容量区域。时，合法消息集合须保留笛卡尔积结构；从消息对中删去少数坏点，不保证剩下足够大的消息矩形。因此多用户的平均错误与最大错误必须分别指定。

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

信道码支撑数字通信、存储和网络传输，并把容量定义转化为可达码率问题。Hamming 距离理路Hamming 距离Hamming distance等长字中不同坐标的数量；由逐位比较、三角不等式和 Hamming 球解释检错与唯一纠错半径。提供码字几何，线性码理路线性码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通过少量码字符号查询区分合法码字与到整个码至少相距 ε 的接收词，并量化局部拒绝概率。只判断接收词是否属于码或远离码；后者的少量查询不会给出完整译码器。