第一章 绪论
第二章 离散信源及信息测度
第三章 离散信道及其信道容量
第四章 连续信源和波形信道
第五章 无失真信源编码定理
第六章 有噪信道编码
第七章 限失真信源编码
第八章 无失真信源编码
第九章 纠错编码

第九章 纠错编码

9.1 基本概念

• 减小接收端码元错误概率的措施：

1. 选择合适的调制、解调方法
2. 增加信号的发送功率
3. 采用差错控制编码

• 纠错编码是提高传输可靠性的最主要的措施之一。

• 纠错编码的基本思路：

  根据一定的规律在待发送的信息码元中人为的加入一些冗余码元，这些冗余码元与信息码元之间以某种确定的规则相互关联（约束)。 在接收端按照既定的规则检验信息码元与监督码元之间的关系。如果传输过程出错，则信息码元与监督码元之间的关系将受到破坏，从而可以发现错误乃至纠正错误。

纠错的工作方式

1. 反馈重传（ARQ）

发送端经编码后发出能够发现错误的码，接收端收到后经检验，如果发现传输中有错误，则通过反馈系统把这一判断结果反馈回发端，然后发送端把前面发出的信息重新传送一次，直到接收端认为正确地收到信息为止。

1. 前向纠错（FEC）

发送端发出的是具有纠错能力的纠错码，接收端根据译码规则进行译码。当误码个数在码的纠错能力范围内时，译码器可以自动纠正错误。

• 特点：
  1. 前向纠错方式不需要反馈信道，特别适合于只能提供单向信道的场合。
  2. 由于能自动纠错，不要求检错重发，因而延时小，实时性好。
  3. 随着纠错能力的增强，译码设备也变得复杂。

1. 混合纠错

   对发送端进行适当的编码。当错误不严重，在码的纠错能力范围之内时，采用自动纠错；当产生的差错超出码的纠错能力范围时，通过反馈系统要求发端重发。

纠错码的分类

• 按功能分：
  1. 检错码：仅能检测误码
  2. 纠错码：可纠正误码
  3. 纠删码：兼纠错和检错能力
• 按信息码元与监督码元之间的检验关系分：
  1. 线性码：满足线性关系
  2. 非线性码：不存在线性关系
• 按信息码元与监督码元之间的约束方式不同分：
  1. 分组码：本码组的监督码元仅和本码组的信息元相关
  2. 卷积码：本码组的监督码元不仅和本码组的信息元相关，而且与前面码组的信息码元有关。
• 按信息码元在编码后是否保持原形式不变：
  1. 系统码：信息码元与监督码元在分组内有确定位置，编码后的信息码元保持不变；
  2. 非系统码：信息位打乱，与编码前不同。
• 按纠正差错的类型可分为：
  1. 纠随机错误码:差错的出现互不相关，彼此独立
  2. 纠突发错误码:错误之间存在相关性
  3. 纠随机和突发错误码

9.2 线性分组码

线性码的优点

• 分组码的表示方法：
  • 信息码组由k个信息码元组成，共有2^k个不同的信息码组；
  • 附加r个校验码元，每个校验码元是该信息码组的某些信息码元模2和；
  • 编码器输出长度为n=r+k的码字；
  • 码字的数目共有2^k；
  • 这2^k个码字的集合称为(n,k)分组码；
• 对二进制(n,k)线性分组码，合法码字数为2^k，可用编码空间的序列数为2^n个。
• 任一种2^k信息集合到二进制序列集合(2^n)的映射都是一种(n,k)码。因此总共可能的编码方案有C_{2n}^{2k}种。
• 译码运算量：如果直接用最大似然序列译码，对一般性的编码而言，正比于n\times2k。几乎是不可能译码。
• 线性分组码是最简单、实用一类码，比如汉明码、循环码、BCH码、RS码等。

校验矩阵和生成矩阵

• 校验矩阵：

  以(7,3)线性分组码为例，码字表示为：

  \mathbf C=[c_1,c_2,c_3,c_4,c_5,c_6,c_7]

  其中c_1,c_2,c_3为信息元，c_4,c_5,c_6,c_7为校验元。

  校验元可以由以下方程组得到：

  \begin{cases} c_4=c_1+c_3\\ c_5=c_1+c_2+c_3\\ c_6=c_1+c_2\\ c_7=c_2+c_3\\ \end{cases}\Rightarrow\begin{cases} c_1+c_3+c_4=0\\ c_1+c_2+c_3+c_5=0\\ c_1+c_2+c_6=0\\ c_2+c_3+c_7=0\\ \end{cases}

  用矩阵表示为：

  \begin{bmatrix} 1&0&1&1&0&0&0\\ 1&1&1&0&1&0&0\\ 1&1&0&0&0&1&0\\ 0&1&1&0&0&0&1\\ \end{bmatrix} \begin{bmatrix} c_1\\c_2\\c_3\\c_4\\c_5\\c_6\\c_7\\ \end{bmatrix}=\begin{bmatrix} 0\\0\\0\\0 \end{bmatrix}

  令

  \mathbf H=\left[\begin{array}{ccc:cccc} 1&0&1&1&0&0&0\\ 1&1&1&0&1&0&0\\ 1&1&0&0&0&1&0\\ 0&1&1&0&0&0&1\\ \end{array}\right]

  \mathbf C=\begin{bmatrix} c_1,c_2,c_3,c_4,c_5,c_6,c_7 \end{bmatrix}

  \mathbf 0=[0,0,0,0]

  则：

  \mathbf H\mathbf C^T=0^T\Leftrightarrow\mathbf C\mathbf H^T=0

  其中\mathbf H被称为校验矩阵。

  • 对于(n,k)的线性分组码，其校验矩阵为n\times(n-k)维矩阵。
  • 对于系统码，校验矩阵可以表示为\mathbf H=[\mathbf Q~~\mathbf I]。

• 生成矩阵

  由校验方程：

  \begin{cases}c_1=c_1\\ c_2=c_2\\ c_3=c_3\\ c_4=c_1+c_3\\ c_5=c_1+c_2+c_3\\ c_6=c_1+c_2\\ c_7=c_2+c_3\end{cases}

  令：

  \mathbf m=[c_1,c_2,c_3]

  \mathbf G=\left[\begin{array}{ccc:cccc} 1&0&0&1&1&1&0\\ 0&1&0&0&1&1&1\\ 0&0&1&1&1&0&1\\ \end{array}\right]=[\mathbf I~~\mathbf P]

  \Rightarrow\mathbf C=\mathbf m\mathbf G

  其中\mathbf G被称为校验矩阵。

  • 对于(n,k)线性分组码，生成矩阵为k\times n维矩阵。
  • 对于系统码，生成矩阵可以表示为\mathbf G=[\mathbf I~~\mathbf P]。

根据矩阵乘法：

\mathbf C=\mathbf m\mathbf G=\sum\limits^k_{i=1}m_i\mathbf G_i

其中\mathbf G_i为\mathbf G的每一行的行向量。

• 特别地：对于信息码组\mathbf m中仅有一个非零元素时，得到的码字即为生成矩阵中的某一行。

• 生成矩阵和校验矩阵的关系：

  \begin{gathered}\mathbf H=[\mathbf Q~~\mathbf I]\\\mathbf G=[\mathbf I~~\mathbf P]\end{gathered} \Leftrightarrow\mathbf Q=\mathbf P^T

• 线性分组码的封闭性：线性分组码中任意两个码字之和仍然是该码的码字。

线性分组码的检纠错能力

• 对于一个二进制对称信道，若输入为k个等可能的长码字，则最大后验概率译码准则应为最小汉明距离译码。

• 线性分组码的最小汉明距离等于非零码字的最小重量。

  说明：

  1. 线性分组码具有封闭性
  2. 码字的重量定义为非零码元的个数
  3. 两个码字的汉明距离等于这两个码字相加所得新码字的重量。

• 设d_{\min}为线性分组码的最小汉明距离：

  1. 该码具备纠正u个错误的充分必要条件是：

     d_{\min}=2u+1

     

  2. 该码检测出l和错误的充分必要条件是：

     d_{\min}=l+1

     

  3. 该码具备纠正t个错误，同时可以发现l(l>t)个错误的充分必要条件是：

     d_{\min}=t+l+1

     

校验矩阵和最小距离的关系

• 对于线性分组码，设其校验矩阵为\mathbf H

  若\mathbf H中的任意t列线性无关，而t+1列线性相关，则该码的最小汉明距离为t+1;反之，若码的最小汉明距离为t+1，则校验矩阵的任意t列线性无关，而t+1列线性相关。

线性分组码的伴随式

设发送的码字为\mathbf C，接受到的码元序列为\mathbf Y，令：

\mathbf S^T=\mathbf H\mathbf Y^T

其中\mathbf S称为线性分组码的伴随式。若\mathbf S=0，则\mathbf Y是一个码字；若\mathbf S\neq\mathbf 0，则\mathbf Y不是码字，在传输过程中出现了误码。

• 结论：
  1. 当传输过程中没有错误时，\mathbf S^T=0；
  2. 当传输过程中发生一位错误时，\mathbf S^T是校验矩阵中的某一位。
  3. 当传输过程中发生多个错误时，\mathbf S^T为校验矩阵对应列的模2加。

伴随式是n-k维向量，伴随式数目与可纠正错误数目的关系：

2^{n-k}\geq\sum_{i=0}^{u}C_n^i

其中u为该码最大的检错个数，等号成立表示该码为完备码，完备码就是伴随式个数和错误图样个数相同的码。

• 译码过程总结：
  1. 确定校验矩阵\mathbf H；
  2. 对于接受到的矩阵，求伴随式：\mathbf S^T=\mathbf H\mathbf Y^T；
  3. 判断出错码元的位置；
  4. 纠错。

9.3 汉明码

汉明码是一种能够纠正单个错误的线性分组码。最小码距d_{\min}=3；

汉明码是完备码，设监督码共有m位，汉明码是(2^m-1,2^m-m-1)线性分组码。

汉明码校验矩阵的构成

• 将m位的二进制数的自然顺序从左到右排列（不包括全0列）。
• 非标准形式的校验矩阵可通过列置换变成标准形式的监督矩阵，纠错能力不变

扩展的汉明码

如果给汉明码添加一位奇偶奇偶校验位，可得到扩展汉明码。

• 信息位保持不变，监督位增加一位；

• 最小码距d_{\min}=4，可纠正一位错误，同时发现两位错误。

• 扩展汉明码的校验矩阵为：

  \mathbf H'=\begin{bmatrix} &&&0\\ &H&&0\\ &&&\vdots\\ &&&0\\ 1&1&\cdots&1 \end{bmatrix}

9.4 循环码

循环码的特点

• 循环码是线性分组码的一个重要子集。

• 循环码有严密的代数学理论基础，检错和纠错能力较强，而且编码和解码设备都不太复杂。

• 循环码除了具有线性分组码的一般性质外，还具有循环性：循环码中任一许用码组经过循环移位后，所得到的码组仍然是许用码组。

• 并不是所有的码字都是由同一个码字移位得到， 全部码字可能是由几个码字移位得到。

• 生成多项式：g(x)=x^3+x^2+1

• 生成矩阵：

  \mathbf G=\left[\begin{array}{cccc:ccc} 1&0&0&0&1&1&0\\ 0&1&0&0&0&1&1\\ 0&0&1&0&1&1&1\\ 0&0&0&1&1&0&1\\ \end{array}\right]

码多项式

设循环码的码字为\mathbf C=[c_1,c_2,...,c_n]，用码多项式表示为：

C(x)=c_1x^{n-1}+c_2x^{n-2}+...+c_{n-1}x+c_n

• 对于二进制码，码多项式的每个系数不是0就是1。
• x仅是码元位置的标记，我们不关心x的取值。
• 在循环码中，若C(x)是一个长为n的许用码字的多项式，则x^iC(x)在模x^n+1运算下也是一个许用码字。

生成码的循环多项式和循环矩阵

• 在(n,k)循环码中，除了全0码字以外，其他码字的连0个数最多只有k-1个。
• 从码中取出一个前面是k-1为都是0的码字，定义这个码字的码多项式为生成多项式g(x)。
• 生成多项式的次数为n-k，且常数项为1。

为了保证构成的生成矩阵\mathbf G的各行线性不相关通常用g(x)来构造生成矩阵。

\textbf{G}(x)=\begin{bmatrix}x^{k-1}g(x)\\ x^{k-2}g(x)\\ \vdots\\ xg(x)\\ g(x)\end{bmatrix}

生成的矩阵不一定是标准形式的生成矩阵。

• 循环码的生成多项式是x^n+1的因式。

循环码的编码方法

由生成多项式构造的生成矩阵，对应的码不是系统码。系统循环码的编码方法如下：

1. 用x^{n-k}乘m(x)，实际上就是在信息码后面附加n-k个0。
2. 求r(x)（校验位）：用x^{n-k}m(x)除以g(x)得到商和余式。余式分子为r(x)。

循环码的译码方法

令

h(x)=\frac{x^n+1}{g(x)}=x^k+h_1x^{k-1}+\cdots+h_{k-1}x+1

h(x)为监督多项式，设h^*(x)：

h^*(x)=x^k+h_{k-1}x^{k-1}+\cdots+h_1x+1

h^*(x)为h(x)的逆多项式。

监督矩阵为：

H(x)=\begin{bmatrix}x^{n-k-1}h^_(x)\\ x^{n-k-2}h^_(x)\\ \vdots\\ xh^_(x)\\h^_(x) \end{bmatrix}

译码可分为三步：

1. 由接收到的码多项式B(x)计算校正子多项式S(x);
2. 由校正子S(x)确定错误图样E(x);
3. 将错误图样E(x)和H(x)相加，纠正错误。

其中校正子多项式S(x)就是用接受到的码多项式除以生成多项式g(x)所得的余式。

习题

判断对错：

1. 纠错编码的基本思路是在信息码元中加入冗余码元来实现纠错功能。
2. 纠错编码不需要反馈信道就能实现纠错功能。
3. 纠随机错误码与信息码元之间没有关联关系。
4. 线性分组码的最小汉明距离是指能够纠正的最大错误个数。
5. 纠错编码可以在传输过程中实时纠错和检测错误。
6. 纠错编码能够检测出所有错误码字。
7. 汉明码是一种能够纠正多个错误的线性分组码。
8. 汉明码的最小码距是3。
9. 扩展汉明码可以纠正两位错误。
10. 循环码是线性分组码的一部分。
11. 循环码的生成多项式的次数为n-k。
12. 在循环码中，任一许用码组经过循环移位后得到的码组仍然是许用码组。
13. 循环码的译码方法中，根据错误图样E(x)和校验位H(x)相加来纠正错误。
14. 循环码的生成矩阵一定是标准形式的生成矩阵。

• 答案

  1-对、2-对、3-对、4-错、5-对、6-错、7-错、8-对、9-错、10-对、11-对、12-对、13-对、14-错

---

已知(7,4)循环码的生成多项式为

g(x)=x^3+x^2+1

求生成矩阵和校验矩阵。当信息多项式为

m(x)=x^3+1

时，求码多项式。

• 答案

  

---

• 答案