第6章 信道编码
噪声信道中的编码
前言
- 平均互信息（信息传输率）为$I(X;Y)=H(X)-H(X|Y)$
- 信道容量为$C=\max I(X;Y)$
通过调整信源的概率分布，使得信息传输率尽量接近信道容量，也就是让信息传输率尽可能大，这一过程称为信源和信道匹配
- 信源编码的目的：增加信源熵$H(X)$，理解为信源发出的所有符号中每个符号带有的平均信息量，实现符号匹配，压缩冗余
- 信道编码的目的：减少损失熵$H(X|Y)$，提高传输信号的抗干扰能力
- 避免少量差错信号对信息内容的影响：使用纠错编码（纠错、检错）
- 信道编码的研究对象：信息序列（即码元间彼此无关且等概率出现）
- 基本思路：在传输的信息码中按照一定规律产生一些附加码元，经过信道传输，在传输中若码字出现错误，接收端则利用编码规律发现码的内在相关性被破坏，从而按照一定的译码规则自动纠正或发现错误，降低误码率
基本方法
前向纠错(FEC)
- 纠错过程在接收端独立进行，没有反馈，信息一直朝着前面的方向传播，因此叫前向
- 译码设备复杂，适用于实时性高容错能力强的场合
反馈重发(ARQ)
- 在接收端判断收到的序列是否符合编码规则，如果不符合就通知重发
- 如循环冗余校验码(CRC)
混合纠错(HEC)
- 结合前向纠错和反馈重发的纠错方法，兼有检错和纠错的能力
- 检错后在能力范围内直接纠错，如果超过该范围就通知重发
差错描述与控制
- 纠错码的传送形式是有形的，承载信息比特的基本单位为码元或符号，大的符号畸变会引起符号差错，使得其携带的信息比特也发生差错
信号差错和信息差错分别用差错符号和差错比特来描述，有区别也有联系
- 差错符号：符号出错的概率（误码概率），即信号差错概率
- 差错比特：误比特率，信息差错概率
- 对于二进制系统来说，因为一个符号承载的信息量就是$\log_22=1$，因此符号差错数值上等于比特差错，但对于多进制系统而言，一个符号差错对应的比特差错根据不同的编码方式而有所区别
反射二进制码（格雷码/循环二进制码）
- 编码特点：任意两个相邻代码中只有一位是不同的，且最大编码和最小编码间也仅有一位不同
- 举例（三位格雷码）：$000、001、011、010、110、111、101、100$
- 转换方法：递归法、异或转换、卡诺图等
- 优点：差错比特小，对于一般高斯信道来说，最可能的符号差错是畸变一个量级，此时格雷码明显优于自然二进制码
差错图样(Error Pattern)
定义：差错图样=发码-收码
$$ E=C-R $$
- 举例：8进制码，发$C=(0,2,5,4,7,5,2)$，收$R=(0,1,5,4,7,5,4)$，则$E=C-R=(0,1,0,0,0,0,6)$
- 特别地，对于二进制码来说，若发$C=(0,1,1,0,1,0,1)$，收$R=(0,1,0,0,1,0,1)$，则$E=C-R=(0,0,1,0,0,0,0)$，可以等效为模2相加，此时差错图样中的1既表示符号差错，又表示比特差错
- 差错的个数称为汉明距离(Hamming Distance)
- 从通信角度来看，收码是可测得的一直量，如果要从收码获知发码，那就要设法找到差错图样，就能通过反变换得到发码
禁用码组和许用码组
- 将信源发出的信息序列按照一定的编码规则，在n重矢量中编出的一组可用码字称为许用码组，剩下的矢量称为禁用码组
- 在信道编码过程中应当在许用码组中尽量寻找差异化最大的码组，以降低误码率
信道编码的分类
类别
- 检错码：能否发现错误的码
- 纠错码：能够发现并纠正错误的码
- 纠删码：能够纠正删除错误的码
纠错码
线性与非线性码
- 区别在于原始信息元是否为线性组合，乘法、非运算等为非线性运算，出现这些运算的组合式即为非线性组合
- 非分组码举例（出现了乘法运算）：输出码字为$(C_3,C_2,C_1,C_0)$时，按规则$C1=C_2+C_2C_3;C_0=1+C_2C_3$编出得码为非分组码
- 分组码举例（都是线性运算）：输出码字为$(C_3,C_2,C_1,C_0)$时，按规则$C_0=m_1;C_1=m_2;C_2=m_1\oplus m_2;C_3=m_1$编出的码为分组码
卷积码与分组码
区别
- 码字的关联性仅存在于码字内部还是码字和码字之间，只有码字内部有关联而码字间无关联的称卷积码，码字间存在关联性的为分组码
- 码字是否有记忆，在编码时是否要使用寄存器
移位循环码
- 定义：将码字内部的码元依次循环摆放组成的编码，如将码字的第一位移到最后一位变成一个新的码字
- 举例：$\{011101,111010,110101,101011,010111,101110\}$
系统码
- 定义：码字的前$k$位与信息序列相同，后面$n-k$位校验元则根据前面的信息元得到
信道译码和译码规则
信道传输模式分析
- 发端具有$2^k$个许用码组，接收端的矢量空间中共有$2^n$个码组，其中包含$2^k$个许用码组和$2^n-2^k$个禁用码组
以发端发出第$C_i$个码字为例
- 正确传输：收端也正确接收到$C_i$
- 不可检出错误传输：收端收到的是$n$维矢量空间中许用码组部分的非$C_i$的其他码字
- 可检出错误传输：收端收到的禁用码组中的码字
- 核心问题：收端要怎样对收到的码进行合适的“翻译”，或者说分类，如接收到码A应该分到哪个类，有什么样的规则
译码规则
- 将输入的接受矢量转换成一个输出码字的规则，核心是根据译码准则来构建译码规则表
- 译码准则：制定译码规则的原则
常见的译码准测
- 最小错误准则(MEPD)
- 最大后验概率准则(MPPD)
- 最大联合概率准则(MJPD)
- 最大似然译码准则(MLD)
有噪信道编码定理（香农第二定理）
定义
- 设某离散无记忆信道有$r$个输入，$s$个输出，信道容量为$C$，在输入$r^n$个符号中选出$M$个码字组成一组码，设$\epsilon$是任意小的正数
- 若$M\leqslant 2^{(n(C-\epsilon))}$，则存在这样的码和相应的译码规则，在当$n$足够大时，使信道输出的错误概率$P_e$任意小
- 若$M=2^{(n(C+\epsilon))}$，则无论$n$多大，也找不到这样一种编码使得译码错误概率任意小
其他表述
也可以写作
$$ M\leqslant2^{n(C-\epsilon)}\to R=\frac {\log M} n \leqslant C-\epsilon $$
- 解释：若信息传输率$R$不大于信道容量$C$，则存在一种编码，当码长$n$足够大时，它可以使信道输出端的错误概率任意小的同时信息传输率无限接近于$C$，但如果$R$大于$C$，则不可能找到这样一种编码使得错误概率任意小
讨论
- 香农第二定理纠正了“可靠性和有效性是一对不可调和的矛盾”的传统观点，为信道编码理论和技术的研究指明了方向
- 但是该定理只给出了编码的存在性，并没有给出编码的具体方法
- 定理指出，$R<C$是可靠传输的必要条件，进一步证明了$R=C$时，任意小的差错概率也是有可能达到的
线性分组码的基本概念
定义
- 分组码：编码中的约束性仅局限于码字内部，而不同码字之间没有关系
- 线性：编码生成的码元满足线性叠加原理
- 从信息序列到码字，是一个线性映射的过程
- 如果一个$(n,k)$分组码的编码规则可以用线性方程组表示，则称该码为线性分组码
判断标准
满足该式关系的编码称为线性分组码
$$ f(\alpha M+\beta M')=\alpha f(M)+\beta f(M') $$
- 该式表明，任意两个信息组的线性组合映射得到的码字都应是两个信息组对应码字的线性组合
共性
- 都有全零码：所有码字中一定含有全零的码
- 满足封闭性：任意两个码相加还是其中一个可能地码字
讨论
码的重量：一个码字中非零码元的个数称为该码字的（汉明）重量，如$01011$的重量为$3$
- 码集中非零码字的汉明重量的最小值称为该码字的最小汉明重量
码的距离：两个长度相同的码字中，对应位置码元不同的码元数目称为两码字之间的汉明距离，简称码距，如$01011$和$01000$之间的汉明距离为$2$
- 码集中码字间汉明距离的最小值称为该码的最小汉明距离
- 一个$(n,k)$分组码中非零码字的最小重量等于码的最小距离
生成矩阵
设码字可以写作
$$ \overrightarrow C=m_{k-1}\overrightarrow g_{k-1}+m_{k-2}\overrightarrow g_{k-2}+\cdots+m_{1}\overrightarrow g_{1}+m_{0}\overrightarrow g_{0} $$
用矩阵乘法的形式可以表示为
$$ (C_{n-1},\cdots,C_0)=(m_{k-1},m_{k-2},\cdots,m_1,m_0) \begin {bmatrix} \overrightarrow g_{k-1}\\ \overrightarrow g_{k-2}\\ \cdots \\ \overrightarrow g_{1}\\ \overrightarrow g_{0}\\ \end {bmatrix} $$
生成矩阵是一个$k$行$n$列的矩阵，表示生成的码字长度为$n$，信源序列长度为$k$，生成矩阵并不是唯一的，可写作如下形式
$$ G=\begin {bmatrix} \overrightarrow g_{k-1}\\ \overrightarrow g_{k-2}\\ \cdots \\ \overrightarrow g_{1}\\ \overrightarrow g_{0}\\ \end {bmatrix}= \begin {bmatrix} g_{k-1,0}&\cdots&g_{k-1,n-1}\\ \vdots &\ddots & \vdots\\ g_{0,0}&\cdots&g_{0,n-1} \end {bmatrix} $$
举例
若一个编码的生成规则为
$$ \left \{ \begin {align} &C_4=m_1\\ &C_3=m_0\\ &C_2=m_1\\ &C_1=m_0\\ &C_0=m_1\oplus m_0 \end {align} \right. $$
- 将其对应的生成矩阵为生成方程的系数矩阵再转置即可得到生成矩阵
$$ G=\begin {bmatrix} 1 & 0\\ 0 & 1\\ 1 & 0\\ 0 & 1\\ 1 & 1 \end {bmatrix}^T =\begin {bmatrix} 1 & 0 & 1 & 0 & 1\\ 0 & 1 & 0 & 1 & 1 \end {bmatrix} $$
讨论
- 生成矩阵的行表示基本码字（一组基底）
- 生成矩阵的列表示了某位码元的编码方式
一致校验矩阵
- 根据校验规则可列出一致校验方程组（判断是否出错的规则），该方程组的系数矩阵即一致校验矩阵
举例
若某编码的一致校验方程为
$$ \left \{ \begin {align} &C_2+C_4=0\\ &C_1+C_3=0\\ &C_0+C_4+C_3=0 \end {align} \right. $$
- 一致校验矩阵即
$$ \begin {bmatrix} 1 & 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 1 & 0\\ 1 & 1 & 0 & 0 &1 \end {bmatrix} $$
