吉林大学通信工程学院 赵蓉 Zr_jlu@sina.com 数据通信原理 吉林大学通信工程学院 赵蓉 Zr_jlu@sina.com

第3章 差错控制

本章主要内容 差错控制的基本概念与原理 1 简单的差错控制编码 2 汉明码及线性分组码 3 循环码 4 卷积码 5

2.差错控制的基本思路 发送端：将被传送的信息码（无规律）按照一定的规则加入监督码元后进行传输，加入的监督码元与信息码元存在某种确定的约束关系。 接收端：检验信息码元与监督码元之间的既定的约束关系，如关系被破坏，则传输中有错。 差错控制也称纠错编码(或信道编码)。 信息码(k)+监督码(r)=码组(n)

3.差错控制方式 （1）检错重发（ARQ）（自动请求重发） ARQ有3种重发方式，即停发等候重发，返回重发和选择重发。 优缺点 ——所需的监督码位数少，编码效率比较高； ——译码设备较简单； ——接收端检测到差错后，要通过反向信道发回NAK，要求发端重发， 所以需要反向信道，实时性差 ARQ有3种重发方式，即停发等候重发，返回重发和选择重发。

a）停发等候重发 b）返回重发 c）选择重发

（2）前向纠错（FEC） 缺点：译码设备复杂；且纠错能力有限。 （当差错数大于纠错能力时，无能为力） 优点：不需要反向信道，自动纠错，不要求重发，因而实时性好； 缺点：译码设备复杂；且纠错能力有限。 （当差错数大于纠错能力时，无能为力）

（3）混合纠错检错（HEC） 是ARQ和FEC方式的折衷方案 优缺点 介于ARQ和FEC之间，设备不很复杂，实时性较好； 但需要反向信道。

（4）信息反馈（IRQ） 优点是不需要纠错、检错，设备简单； 缺点是需要和前向信道相同的反向信道，实时性差，且发送端需要一定容量的存储器。 数据信息 （d） 信息反馈 优缺点 优点是不需要纠错、检错，设备简单； 缺点是需要和前向信道相同的反向信道，实时性差，且发送端需要一定容量的存储器。

2. 汉明距离与检错和纠错能力的关系 码距：d0 = 4 dmin dmin = 1 （1）几个概念 码长：码组或码字中编码的总位数为码组的长度。 码重：码组中非零码元的数目为码组的重量。 例如“11010”的码长为5，码重为3。 码距：两个等长码组中对应码位上具有不同二进制码的数目 称为码距。 例如：码组1 11010 码组2 01101 码距：d0 = 4 汉明距离（最小码距） ： dmin 在一种编码中，任意两个许用码组间距离的最小值。 000 001 010 100 111 011 101 110 dmin = 1

（2）汉明距离和检错和纠错能力的关系 a)为了检测e位错码，要求最小码距 b)为了纠正t位错码，要求最小码距 c)为了纠正t位错码，同时检测e(e>t)位错码，要求最小码距

3. 纠错编码的分类 (1)按码组的功能分，有检错码和纠错码两类。 (2)按码组中监督码元与信息码元之间的关系分，有线性码和 非线性码两类。 (3)按照信息码元与监督码元的约束关系，可分为分组码和卷积码。 分组码的表示方式： （n, k）码 (4)按照信息码元在编码前后是否保持原来的形式不变， 可分为系统码和非系统码。 (5)按纠正差错的类型可分为纠正随机错误的码和纠正突发 错误的码。 (6)按照每个码元取值来分，可分为二进制码与多进制码。

3.2.2 水平奇偶监督码 思想方法：将信息码序列按行排成方阵，每行后面加一个奇或偶监督码，即每行为一个奇（偶）监督码组，但发送时则按列的顺序传输：111011100110000…10101，接收端仍将码元排成与发送端一样的方阵形式，然后按行进行奇偶校验。 信 息 码 元 监督码元 1 1 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 1 1 1 0 1 1 1 水平偶监督码 可以检出奇数位错误和长度不大于方阵中行数的突发错误。

例 解 首先确定采用的是奇校验还是偶校验。 偶校验 1

（7,4）汉明码的许用码组 信息码 a6 a5 a4 a3 码组A a6 a5 a4 a3 a2 a1 a0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 1 0 0 1 1 1 1 0 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 1 1 0 0 1 1 0 1 1 1 0 0 0 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 1 1 1 0 0 0 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 1 1 1 1 1 1 1 ——假设发送端的码字是A15=1111111， ——传输过程中第4位a3出现了错误，即接收的码字是B=1110111 不是许用码组。 有错

2.生成矩阵 用途：由信息位和生成矩阵可得出整个码组。 生成矩阵： 以（7,4）汉明码为例 生成矩阵

如（7,4）汉明码表中的信息位为0010， 求整个码组 注意：生成矩阵G各行本身就是一个码组。

4.线性分组码的主要性质 (1)封闭性 是指一种线性分组码中的任意两个码组之逐位模2和仍为这种 码中的另一个许用码组。 (2) 码的最小距离等于非零码的最小重量。 因为线性分组码具有封闭性，因而两个码组之间的距离必是 另一码组的重量。（全“0”码除外）

解： 2.生成多项式的另一种求法 （n,k）循环码的生成多项式是 的一个（n-k）次因式。 例 求（7,3）循环码的生成多项式。 生成多项式有两个： 生成多项式不同，产生出的循环码码组也不同。

通过线性变换可将非典型的生成矩阵转换为典型的生成矩阵 3.生成矩阵G 单位方阵 典型的生成矩阵 通过线性变换可将非典型的生成矩阵转换为典型的生成矩阵

得循环码的码组 1100101 编码器的构成：

判别方法 3.4.4 循环码的解码方法 如果信道中错码的个数超过了这种编码的检错能力，恰好使有错码的接收码组被g(x)整除，则不能检出。 1.检错的实现 无差错 发送码组 接收码组 若码组无错 判别方法 若码组有错，则 检测到差错 解码器的核心：除法器 如果信道中错码的个数超过了这种编码的检错能力，恰好使有错码的接收码组被g(x)整除，则不能检出。

2.纠错的实现 概念：错误图样 发送码组 接收码组 错误码组 错误码组的各种不同的 具体采样称错误图样 纠错的步骤： 得原发送码组。

国际上常用的CRC校验的生成多项式有： 用于美国二进制同步系统 用于HDLC,X.25,7号信令等。 用于以太网等。

3.5 卷积码 卷积码是线性码，非分组码。没有严格的代数结构 适用于前向纠错（FEC） 3.5.1 卷积码的基本概念 1.卷积码的概念 监督位不仅与当前输入的信息位有关，还与更前面的信息位有关。

3.5.2 卷积码编码器 (n, k, N)卷积码 编码器结构 卷积码的监督位不仅取决于这段时间的k个信息位，还取决于前N-1段规定时间内的信息位。 即卷积码的监督位不仅对本码组起监督作用，对前N-1个码组也起监督作用。 这N段时间内的码元数目Nk称为约束长度。

3.6 简单差错控制协议 3.6.1 停止等待协议 ARQ有3种重发方式，即停发等候重发，返回重发和选择重发。 1.停止等待协议的概念 停止等待协议规定：发送端每发送一个数据帧（对应一个码组）就暂停下来，等待接收端的应答。接收端收到数据帧进行差错检测，若数据帧没错，就向发送端返回一个确认帧ACK，发送端再发送下一个数据帧；若接收端检验出数据帧有错，就向发送端返回一个否认帧NAK，发送端重发刚才所发数据帧，直到没错为止。

2.停止等待协议的算法 （1）数据帧在实际链路上传输的4种情况 （2）停止等待协议算法 发送端算法 接收端算法

3.6.2 自动重发请求协议 1.自动重发请求(ARQ)协议的概念 2.连续ARQ协议 发送端在连续发送数据帧的同时，接收对方的应答帧。 若收到确认帧，继续发送数据帧； 若收到否认帧，将出错的数据帧或出错的数据帧及以后的各帧重发。 2.连续ARQ协议 将出错的数据帧及以后的各帧重发。

3.选择重发ARQ协议 发送端只重发出错的数据帧。

3.6.3 滑动窗口协议 1.发送窗口 发送窗口用来对发送端进行流量控制。 发送窗口尺寸 WT ：表示在没有收到对方确认的条件下，发送端最多可以发送数据帧的个数。 发送窗口尺寸： （n为编号的比特数）

2.接收窗口 接收窗口用来控制接收数据帧。只有当接收到数据帧的发送序号落在接收窗口内，才允许将该数据帧收下；否则，一律丢弃。 设接收窗口尺寸 WR 在连续ARQ协议中，在接收窗口向前“滑动”后， 发送窗口才能向前“滑动”。

本章小结 1.差错控制的基本概念和原理 主要内容：检错和纠错的概念； 2.几种简单的差错控制编码 奇偶监督码； 3.汉明码 4.循环码 检错纠错的实现方式：加监督位。 2.几种简单的差错控制编码 奇偶监督码； 水平奇偶监督码； 二维奇偶监督码。 3.汉明码 4.循环码 5.卷积码（基本概念）

Thank You ! 通信理论教研室 518