计算机网络通信原理概论课件

第十章差错控制为什么要进行差错控制差错控制的基本方法差错控制编码的基本概念常用的简单编码常用的线性分组码第十章差错控制为什么要进行差错控制1（1）差错产生的原因数据通信系统的基本任务是高效率而无差错地传送数据。数据信号在通信线路中传输时，难免受到来自信道内部和外部的干扰，从而引起信号的失真，导致数据传输错误。传输出错的原因：一是信道的加性噪声；二是由于传输总特性（包括收、发滤波器和信道的特性）不理想引起的码间串扰。噪声是影响数据传输质量的主要因素。根据产生的原因可以将噪声分为四类：热噪声、交调噪声、串音和脉冲噪声四类。（1）差错产生的原因数据通信系统的基本任务是高效率而无差错地2（2）噪声的类型热噪声是由带电粒子在导电介质中的布朗运动引起的，它存在于任何工作在绝对零度以上的电路或系统中。热噪声属于高斯白噪声，其概率密度函数满足正态分布统计特性，同时它的功率谱密度函数是均匀分布的（常数）。热噪声的特点是：时刻存在、不可排除、幅度较小、强度与频率无关，但频谱很宽，是一类随机的噪声。（2）噪声的类型热噪声3噪声的类型交调噪声是一种附加的频率干扰。由于通信系统的非线性，将导致进入通信系统的不同频率的信号在系统的输出端产生这些频率之间的差频信号或倍频信号及其组合，这就是交调噪声。对于交调噪声可以通过适当的调制技术，人为地校正系统的非线性部分得到补偿。噪声的类型交调噪声4噪声的类型串音是一个通路的信号在相邻的另一个通路引起的干扰现象。这是由于信号线路之间的电磁感应引起的有害耦合。为了消除线路之间的有害耦合，可以将每一对线拧成一定扭绞节距的线缆。噪声的类型串音5噪声的类型脉冲噪声是由于电火花或其他原因造成的突发振幅很大、持续时间比间隔时间短得多的离散脉冲耦合到信号通路中的干扰。脉冲噪声也称为冲击噪声，它将引起一连串的数据比特出错，它是数据传输差错的主要根源。脉冲噪声产生的干扰很难消除，只能采用差错控制的方法来实现可靠传输。噪声的类型脉冲噪声6（3）差错的类型随机差错指数据单元中的单比特差错。它通常由传输信道的热噪声引起。突发差错指数据单元中的两个或两个以上的比特发生成串密集性的差错，第一个错误比特到最后一个错误比特之间的位数称为突发长度。冲击噪声持续的时间通常大于数据传输中每比特的发送时间，因而会引起相邻的多个数据位出错，从而导致突发差错。（3）差错的类型随机差错7有差错的信道类型按照噪声或干扰的变化规律，可把信道分为三类：随机信道：

恒参高斯白噪声信道是典型的随机信道，其中差错的出现是随机的，而且错误之间是统计独立的。突发信道：

具有脉冲干扰的信道，是典型的突发信道。错误是成串成群出现的，即在短时间内出现大量错误。混合信道：

短波信道和对流层散射信道是混合信道的典型例子，随机差错和成串的突发差错都占有相当比例。有差错的信道类型按照噪声或干扰的变化规律，可把信道分为三类：8（4）如何解决传输差错问题提高物理信道的质量，尽量避免和减少差错：采用电缆屏蔽措施和适当的调制解调方法设置中继设备对信号进行整理再生和放大加大发射功率，降低接收设备本身的噪声，以提高信噪比提高数据的健壮性，有效地进行检错和纠错：采用信道编码技术，为数据信息增加冗余编码，形成抗干扰编码，使接收方能进行检错或纠错配合适当的差错控制方法进行检错或纠错。（4）如何解决传输差错问题提高物理信道的质量，尽量避免和减少9第十章差错控制为什么要进行差错控制差错控制的基本方法差错控制编码的基本概念常用的简单编码常用的线性分组码第十章差错控制为什么要进行差错控制10差错控制的基本工作方式自动反馈重发方式ARQ发端发送检错码，收端收到信码后能够检查出错误。前向纠错方式FEC发端发送能够纠正错误的码，收端收到信码后自动地纠正传输中的错误。混合纠错方式HEC是FEC和ARQ方式的结合。信息反馈方式IF是不用编码的差错控制方式。差错控制的基本工作方式自动反馈重发方式ARQ11（1）自动反馈重发ARQ

自动反馈重发记作ARQ(AutomaticRepeatRequest)，又称自动请求重传方式。发方按照一定的编码规则处理待发信息，构成具有检错能力的编码，发往传输信道；收方判决传输中无错误产生，并通过反向信道把判决结果反馈给发方；发方根据反馈的结果决定是否执行重传动作，如果接收方未正确接收，则重传信息(出错重传)在规定的时间内，发方若未能收到应答信号(称为超时)，则可以认为传输出现差错，进而执行重传动作(超时重传)。（1）自动反馈重发ARQ自动反馈重发记作ARQ(Auto12主要的反馈重传方式

反馈重传方式的特点是译码设备简单，对突发错误和信道干扰较严重时有效；但实时性差，主要在计算机数据通信系统中得到应用。常用的反馈重传方式有：发送-等待ARQ（停—等协议）连续发送ARQ（滑动窗口协议）选择重传ARQ发送方接收方抗干扰编码应答信号主要的反馈重传方式反馈重传方式的特点是译码设备简单，对突发13（2）前向纠错法FEC前向纠错方式记作FEC(ForwordErrorCorrection)。发送方按照一定的编码规则处理待发信息，构成具有纠正错误能力的代码(纠错码)发往传输信道；接收方根据编码规则，检查传输差错，并自动加以纠正。其特点是单向传输，实时性好，但译码设备较复杂。（2）前向纠错法FEC前向纠错方式记作FEC(Forword14（3）混合纠错法混合纠错方式记作HEC(HybridErrorCorrection)是FEC和ARQ方式的结合。发方发送具有一定纠错能力同时又具有检错能力的编码。收方收到编码后，检查差错情况，如果错误在编码的纠错能力范围以内，则自动纠错，否则经过反馈信道请求发方重发。（3）混合纠错法混合纠错方式记作HEC(HybridErr15（4）信息反馈法信息反馈法记作IRQ(InformationRepeatRequest)接收方把收到的信息代码全部送回发送方，由发送方进行差错检验。发送方若发现传输差错，则重发信息代码，直至不再发现差错为止。（4）信息反馈法信息反馈法记作IRQ(Informatio16几种差错控制方法比较自动反馈重传法：

使用的编/解码设施比较简单，如果信道的质量差或干扰严重，则可能经常进入重发状态而影响通信效率。前向纠错法：编/解码相对复杂，且编码的效率很低，但是无需专门的反馈信道。主要应用于没有反馈信道的场合，或用于线路传播时间很长、要求重发在经济上不切实际的的场合。由于形成纠错码要求较多的冗余信息，当信道质量较好时，也影响了传输的效率。混合纠错法：编/解码相当复杂、且编码的效率很低，很少被采用。信息反馈法：反馈信息量太大，传输效率很低，很少被采用。几种差错控制方法比较自动反馈重传法：17第十章差错控制为什么要进行差错控制差错控制的基本方法差错控制编码的基本概念常用的简单编码常用的线性分组码第十章差错控制为什么要进行差错控制18差错控制编码的基本原理差错控制的核心技术是信道编码技术，即采用适当的差错控制编码来传输信息。差错控制编码的基本思想是在被传输信息中增加一些冗余码，利用附加码元和信息码元之间的约束关系加以校验，以检测和纠正错误，增加的冗余码元就称为监督码元（校验码元）。差错控制编码的基本原理差错控制的核心技术是信道编码技术，即采19信道编码技术对于n位的二进制码有N=2n种组合。如果这N种组合都用来传输信息，这样构成的编码并不具备抗干扰能力。因为不管哪一位发生错误，都会使传输信息出错。但是，若这N种组合并未完全使用，情况将会怎样呢？信道编码技术对于n位的二进制码有N=2n种组合。20差错控制编码的抗干扰机理【例】考虑n=3的情形，3位二进制码有8种组合：

000、001、010、011、100、101、110、111若只用以下四个码组表示四个字母，其余的作为禁用码组：

000——A 011——B 101——C 110——D则只要发生一位错误，准用码组就将变成禁用码组，接收端就能知道出错，但是不能纠错。若只用两个码组作为有用码组000——A、111——B，并将8个码组分为两个子集：{000、001、010、100}和{011、101、110、111}，前者对应码组000，后者对应码组111。则接收端可以检测两位及以下的差错，或纠正一位的差错。【结论】增加监督码元的个数可提高纠检错能力。差错控制编码的抗干扰机理【例】考虑n=3的情形，3位二进制码21抗干扰编码的理论依据香农定理在有噪声干扰的信道中，若信道容量为C，只要发送端以低于C的速率R发送信息（R为输入信道编码器的二进制码元速率），则一定存在一种编码方式，使数据的误码率随着码长n的增长将按指数下降到任一值。结论如码长及发送速率一定，可以通过增大信道容量，使误码率下降。如信道容量及发送信息速率一定，可以通过增加码长，使误码率下降。抗干扰编码的理论依据香农定理22码长、码重、码距编码码组中的码元总位数称为码组的长度，简称码长。一个码组中，“1”码元的数目称为码组的重量，简称码重。两个等长码组之间对应码位上码元不同的数目称为这两个码组的海明(Hamming)距离，简称码距。一个码组集中任意两个码组之间距离的最小值称为码的最小距离。最小码距是抗干扰编码的一个重要参数，它是衡量编码检错、纠错能力的依据。【例】在前述例子中，码组集{000、011、101、110}的最小码距为2，而码组集{000、111}的最小码距为3。码长、码重、码距编码码组中的码元总位数称为码组的长度，简称码23编码的检错和纠错能力理论证明，编码的抗干扰能力与最小码距密切相关：为检查出e个错误，要求最小码距为dmin≥e+1为纠正t个错误，要求最小码距为dmin≥2t+1为纠正e个错误，同时检查出t个错误，要求最小码距为dmin≥e+t+1 (e>t)编码的检错和纠错能力理论证明，编码的抗干扰能力与最小码距密切24编码效率用差错控制编码提高通信系统的的可靠性，是以降低有效性为代价换来的。定义编码效率R来衡量有效性：R=d/(d+r)其中，d是信息码元的个数，r为校验码元个数

。校验码元越长，编码的检错能力越强，编码/解码越复杂；附加的冗余信息在整个编码中所占的比例越大，传输的有效成分越低，传输的效率下降。编码效率用差错控制编码提高通信系统的的可靠性，是以降低有效性25对纠、检错码的基本要求对纠、检错码的基本要求是:检错和纠错能力尽量强、编码效率尽量高、编码规律尽量简单。实际中要根据具体指标要求，保证有一定的纠、检错能力和编码效率，并且易于实现。对纠、检错码的基本要求26差错控制编码的分类按照信息码元和监督码元之间的函数关系分为：线性码和非线性码。前者码元之间能满足一组线性方程组，后者则不然。按照对信息元的处理方式分为：分组码和卷积码。前者的各码元仅与本组的信息元有关；后者的码元不仅与本组的信息元有关，而且还与前面若干组的信息元有关。按照差错控制编码的用途分为：检错码和纠错码。前者以检错为目的，不一定能纠错；而后者以纠错为目的，一定能检错。按照码组中信息码元在编码前后是否相同分为：系统码和非系统码。差错控制编码的分类按照信息码元和监督码元之间的函数关系分为：27分组码分组码一般用(n,k)表示。其中，k是每组二进制信息码元的数目，n是编码码组的码长。n-k=r为每个码组中的监督码元数目。简单地说，分组码是对每段k位长的信息组以一定的规则增加r个监督元，组成码长为n的码字。在二进制情况下，共有2k个不同的信息组，相应地可得到2k个不同的码字，称为许用码组。其余2n-2k个码字未被选用，称为禁用码组。分组码=k个信息码元+r个监督码元（校验码元）分组码分组码一般用(n,k)表示。其中，k是每组二进制信息码28线性分组码线性分组码是指信息码元与监督码元之间的关系可以用一组线性方程来表示的分组码。在(n,k)分组码中，每一个监督码元都是码组中某些信息码元按模2和而得到的，线性分组码是一类重要的检/纠错码，应用很广。本章介绍的差错控制编码均为线性分组码。线性分组码线性分组码是指信息码元与监督码元之间的关系可以用一29第十章差错控制为什么要进行差错控制差错控制的基本方法差错控制编码的基本概念常用的简单编码常用的线性分组码第十章差错控制为什么要进行差错控制30常用的简单编码奇偶校验码水平奇偶校验（行校验）垂直奇偶校验（列校验）水平垂直奇偶校验（方阵码）定比码（恒比码）常用的简单编码奇偶校验码31奇偶校验码

奇偶校验码是在原信息码元后面附加一个监督码元，使得码组中“1”的个数为奇数或偶数。因此，奇偶校验码是含一个监督码元，码重为奇数或偶数的（n,n-1）系统分组码。奇偶监督码又分为奇监督码和偶监督码。奇偶校验码奇偶校验码是在原信息码元后面附加一个监督码元，使32奇偶校验码的特点

设有n-1位信息码元为Cn-1，Cn-2，……，C1，校验码为C0对于偶校验，有 对于奇校验，有奇偶校验码只能检测出代码序列中的奇数个错误。没有纠错能力最小码距为dmin=2编码效率为R=（n-1）/n33奇偶校验码的特点设有n-1位信息码元为Cn-1，Cn-2，行、列监督码奇偶校验码不能发现偶数个错误。为了改善这种情况，引入行、列监督码。这类编码不仅对水平(行)方向的码元，而且对垂直(列)方向的码元实施奇偶校验。既可以逐行传输，也可以逐列传输。这类编码具有较强的检测能力，适于检测突发错误，还有一定的纠错能力。行、列监督码奇偶校验码不能发现偶数个错误。为了改善这种情况，34水平奇偶校验（HRC）

属于水平方向冗余校验：把要传输的数据以适当的长度划分成若干个小组，每个小组由若干个码字组成。把码字按顺序一列一列地排列起来，然后对水平方向的码元进行奇偶校验，得到一列校验码字，附加在其它各列之后，最后按列的顺序进行传输。水平奇偶校验（HRC）属于水平方向冗余校验：35水平奇偶校验之例

字符位ABCDEFGHI偶校验位11010101011201100110003000111100040000000110500000000006000000000071111111111水平奇偶校验能发现水平方向奇数个错误，以及所有突发长度<=n（n为码字长度）的突发性错误。水平奇偶校验之例字符ABCDEFGHI偶校验位36垂直奇偶校验（VRC）

属于垂直方向冗余校验码：把要传输的数据以适当的长度划分成若干个小组，每个小组由若干个码字组成。把码字按顺序一列一列地排列起来。然后对垂直方向的码元进行奇偶校验，得到一行校验位字，附加在其它各列之后，最后按列的顺序进行传输。垂直奇偶校验（VRC）属于垂直方向冗余校验码：37垂直奇偶校验之例

垂直奇偶校验能发现垂直方向奇数个错误，以及50%的突发性错误。字符位ABCDEFGHI1101010101201100110030001111004000000011500000000060000000007111111111奇校验位110100110垂直奇偶校验之例垂直奇偶校验能发现垂直方向奇数个错误，以及38水平垂直奇偶校验（LRC）

水平垂直奇偶校验码，也称为方阵校验码。它不仅对行进行奇偶校验，而且也对列进行奇偶校验。这种方法按列传输时能发现所有长度<=n+1（n为码字长度）的突发性错误和其它错误；按行传输时能发现所有长度<=m+1（m为码字个数）的突发性错误和其它错误；并且具有一定的纠错能力。水平垂直奇偶校验（LRC）水平垂直奇偶校验码，也称为方阵校39水平垂直奇偶校验之例

字符位ABCDEFGHI偶校验位11010101011201100110003000111100040000000110500000000006000000000071111111111奇校验位1101001101水平垂直奇偶校验之例字符ABCDEFGHI偶校40定比码定比码的码字中1的数目与0的数目保持恒定比例，也称为恒比码。由于恒比码中，每个码组均含有相同数目的1和0，因此恒比码又称等重码，定1码。这种码在检测时，只要计算接收码元中1的数目是否正确，就可判断有无差错。

定比码定比码的码字中1的数目与0的数目保持恒定比例，也称为恒41定比码应用举例我国电传通信中普遍采用3∶2码，又称“5中取3”的定比码，即每个码组的长度为5，其中3个“1”。这时可能编成的不同码组数目等于从5中取3的组合数10，这10个许用码组恰好可表示10个阿拉伯数字。而每个汉字又是以四位十进制数来代表的。国际通用的ARQ电报通信系统采用“7中取3”的定比码。“7中取3”码可以检出所有的单比特差错和奇数个差错，但只能检出部分偶数位差错。定比码应用举例我国电传通信中普遍采用3∶2码，又称“5中取342第十章差错控制为什么要进行差错控制差错控制的基本方法差错控制编码的基本概念常用的简单编码常用的线性分组码第十章差错控制为什么要进行差错控制43循环冗余码（CRC）循环码是一类重要的线性分组码，它除了具有线性码的一般性质外，还具有循环性，即循环码组中任一码组循环移位所得的码组仍为该循环码中的一许用码组。循环冗余码（CRC码）是数据通信领域中最常用的一种差错检验码，其特征是信息码元和校验码元的长度可以任意选定。循环冗余码（CRC）循环码是一类重要的线性分组码，它除了具有44CRC码的原理假定我们构成(n=7,k=3)这样的线性分组码，若已知三个信息码元为C6、C5和C4，而校验码元C3、C2、C1和C0是未知的。校验码元与信息码元间的关系是根据以下四个线性关系式确立的。 CRC码的原理假定我们构成(n=7,k=3)这样的线性分组码45CRC码的原理按上页编出的线性码为：信息码元码组C6C5C4C6C5C4C3C2C1C000000000000010011101010010011101101110101001001110101101001111011010011111110100当我们从表中任意挑选出两个码组时，将对应比特按模2相加，所得到的新码组仍然是表中的某一码组。这说明由8个码字组成的线性码具有封闭性。封闭性是线性码的一个重要特性。CRC码的原理按上页编出的线性码为：信息码元码组C646循环冗余码的基本思想把要传输的数据信息当作一个报文码多项式f(x)的系数，发送时用一个标准的生成多项式G(x)来除f(x)，将所除得余式R(x)的系数附加在报文码之后发出；接收时用同一生成多项式G(x)来除收到的码字多项式，能除尽说明传输正确，否则说明有错。实现：用简单的移位寄存器电路即可。循环冗余码的基本思想把要传输的数据信息当作一个报文码多项式47码多项式

从数学角度来看，所有的X进制数都可以用一个以X为基的多项式来表示。对于二进制数，基X=2，多项式的系数只取0、1。对于长度为n的任一二进制码字，可以用一个x的n-1次多项式来表示。码字中每个码元的值就是该多项式中的相应的系数。此多项式就成为码多项式。如：

Cn-1Cn-2……C1

C0的码多项式为：

Cn-1

xn-1+

Cn-2xn-2+……+

C1x1+

C0x0又如：码字1010111对应的多项式为x6+x4+x2+x+1，而多项式为x5+x3+x2+x+1对应的码字为101111。码多项式从数学角度来看，所有的X进制数都可以用一个以X为基48循环冗余码（CRC）

设：

k个信息码元Cn-1，Cn-2，……，Cn-k对应的码多项式为f(x)；r次的生成多项式为G(x)

（n=k+r）；用G(x)去除f(x)（模2运算）所得余式为R(x)；f(x)=Cn-1

xk-1+

Cn-2xk-2+……+

Cn-k

x0R(x)=Cr-1

xr-1+

Cr-2

xr-2+……+

C0x0Cn-1，Cn-2，……，Cn-k，Cr-1，……，C0循环冗余码（CRC）设：

k个信息码元Cn-1，Cn-2，49循环冗余编码工作原理

发送方接收方发送数据f(x)生成多项式G(x)f(x)xr.G(x)=Q(x)+R(x)G(x)实际发送:f(x)xr.+R(x)信息字段校验字段f(x)xr.R(x)接收数据f(x)+R(x)生成多项式G(x)R'(x)=R(x)接收正确R'(x)≠R(x)接收出错发送f(x)xr.G(x)=Q(x)+R'(x)G(x)循环冗余编码工作原理发送方接收方发送数据f(x)生成多项50CRC校验码软件生成方法设：信息代码M为1011001，生成多项式为G(x)=x4+x3+1，则：k=7，r=4，CRC码字长度为n=11对应f(x)=x6+x4+x3+1，G(x)的代码为1011001x4f(x)=x10+x8+x7+x4对应的代码记为：10110010000；采用多项式除法，得余数为1010

(即校验字段为1010)发送方发出的传输编码为:

1011001

1010

信息字段

校验字段接收方使用相同的生成码进行校验，将接收到的字段除以生成码（二进制除法），如果能够除尽，则正确，否则出错。CRC校验码软件生成方法设：信息代码M为1011001，生成51简化算法

11111101√1010000

1110110010

1110111110

1110111将信息码字左移n-k位，后面补上n-k个0；用所得的码字除以生成多项式G(x)的系数；将所得的n-k位余数接在信息码字之后，即可得到CRC编码。例：设(7,3)码的信息码字为101，生成多项式为：G(x)=x4+x3+x2+1求CRC编码的码字的过程如右图所示。余数为0011，CRC编码为1010011。简化算法将信息码字左移n-k位，后面补上n-k个0；52例1设信息代码M=1010001101，r=5,G=110101。模2运算的结果是：商Q=1101010110，余数R=01110。将余数R作为冗余码添加在信息M的后面发送出去，即发送的数据是101000110101110，或2rM+R。例1设信息代码M=1010001101，r=5,G53例1的计算过程

1101010110

←

Q

商

除数

P→

110101101000110100000

←

2rM被除数

110101

111011

110101

111010

110101

111110

110101

101100

110101

110010

110101

01110

←

R

余数例1的计算过程54

1100111001110011100111001110010100001110011000011001G(x)1100110000110011001R(x)100001Q(x)f(x).xr例2110011发送数据比特序列CRC校验码比特序列1001带CRC校验码的发送数据比特序列11001110011100155例3原始数据M=1101011011G(x)=x4+x+1的系数=1001111010110110000100111001110011100111011010011101001001111101100001010余数传输码元

=原始数据（左移位后）+余数

11010110111110例3原始数据M=11010110111101011056标准CRC生成多项式G(x)CRC-12：G（x）=x12+x11+x3+x2+x+1CRC-16：G（x）=x16+x15+x2+1CRC-CCITT：G（x）=x16+x12+x5+1CRC-32：G（x）=x32+x26+x23+x22+x16+x12+x11+x10+x8+

x7+x5+x4+

x2+x+1标准CRC生成多项式G(x)CRC-12：57循环码的检错能力

理论证明，CRC码能查出：全部的单个比特错误；所有的离散的双位错（不相邻）；全部≤n-k（冗余位数）的突发性错误；对于n-k+1位的突发性错误；检出率为1-2-(n-k-1)；对于多于n-k+1位的突发性错误；检出率为1-2-(n-k)；实验表明，如果使用16位冗余码可以检出所有奇数位的差错及所有双位错，和长度小于16位的突发错误，还能查出99.997%的17位和99.998%18位或更长位的突发性错误。传输速率为9600bps时，传输3000年才会有一个错误。循环码的检错能力理论证明，CRC码能查出：58海明码Hamming于1950年在美国贝尔实验室提出了海明码，是第一个用来纠错的线性分组码，被广泛地应用在数据通信和数据存储系统的差错控制中。所谓海明校验实质上是奇偶校验，是分组奇偶校验。它可以纠正一位差错。设海明码长为n，监督码元的个数为r，海明码它利用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的一位错。海明码Hamming于1950年在美国贝尔实验室提出了海明码59海明码的特点设码长为n，信息位为k位，监督码元的个数为r=n-k，海明码长满足n=2r-1，r≥2且为正整数。给定r之后，即可确定n和k。无论码长n为多少，海明码的最小码距为dmin=3。因此它只能纠正1位错码，通常用于前向纠错FEC的系统中海明码的编码效率为R=k/n=1-r/n，因此编码效率将随着码长增加而提高。

海明码的特点设码长为n，信息位为k位，监督码元的个数为r=n60海明码校验码的位权海明码是分组奇偶校验码，每组校验位P1，P2，P3，…，Pn的位权值为2n-1。即所有2的幂次方的数据位就是奇偶校验位(对应编号为1,2,4,8,16,32,64等的位置)其他数据位用于待编码数据.(编号为3,5,6,7,9,10,11,12,13,14,15,17等的位置)海明码校验码的位权海明码是分组奇偶校验码，每组校验位P1，P61海明码的构建每个奇偶校验位的值代表了码字中部分数据位的奇偶性，其所在位置决定了要校验和跳过的比特位顺序：位置1：每校验1位，跳过1位(1,3,5,7,9,11,13,15,…)位置2：每校验2位，跳过2位(2,3,6,7,10,11,14,15,…)位置4：每校验4位，跳过4位(4,5,6,7,12,13,14,15,20,21,22,23,…)位置8：每校验8位，跳过8位(8~15,24~31,40~47,…)……如果全部校验的位置中有奇数个1，把该奇偶校验位置为1；如果全部校验的位置中有偶数个1，把该奇偶校验位置为0.海明码的构建每个奇偶校验位的值代表了码字中部分数据位的奇偶性62海明校验码的生成示例设发送信息为1000101，把校验码P１，P2，P3，…，顺序插入信息码中，得海明码P１P21P3000P4101分组：组P1P21P3000P41011√√√√√√2√√√√√√3√√√√4√√√√编码，设发送与接收双方均采用奇校验，则P1=0，P2=1，P3=1，P4

=1发送端发送的比特流为01110001101海明校验码的生成示例设发送信息为1000101，把校验码P１63检错和纠错接收端对海明码检错的方法就是逐个验证每一个校验位。假如有错，就累加出错的检验码元的位权。得到的就是错误信息所在的位置。假定实际接收到的数据是01110011101，接收方验证每一个校验位验证，可以发现校验位P1、P2和P3的数据不正确。错误校验位的位权求和1+2+4=7,表明位置7的数据出错。检错和纠错接收端对海明码检错的方法就是逐个验证每一个校验位。64示例假定实际接收到的数据是01110011101组0P11P2111P30000101P41100111√√√√√√2√√√√√√3√√√√4√√√√示例假定实际接收到的数据是01110011101组0111065第十章差错控制为什么要进行差错控制差错控制的基本方法差错控制编码的基本概念常用的简单编码常用的线性分组码第十章差错控制为什么要进行差错控制66（1）差错产生的原因数据通信系统的基本任务是高效率而无差错地传送数据。数据信号在通信线路中传输时，难免受到来自信道内部和外部的干扰，从而引起信号的失真，导致数据传输错误。传输出错的原因：一是信道的加性噪声；二是由于传输总特性（包括收、发滤波器和信道的特性）不理想引起的码间串扰。噪声是影响数据传输质量的主要因素。根据产生的原因可以将噪声分为四类：热噪声、交调噪声、串音和脉冲噪声四类。（1）差错产生的原因数据通信系统的基本任务是高效率而无差错地67（2）噪声的类型热噪声是由带电粒子在导电介质中的布朗运动引起的，它存在于任何工作在绝对零度以上的电路或系统中。热噪声属于高斯白噪声，其概率密度函数满足正态分布统计特性，同时它的功率谱密度函数是均匀分布的（常数）。热噪声的特点是：时刻存在、不可排除、幅度较小、强度与频率无关，但频谱很宽，是一类随机的噪声。（2）噪声的类型热噪声68噪声的类型交调噪声是一种附加的频率干扰。由于通信系统的非线性，将导致进入通信系统的不同频率的信号在系统的输出端产生这些频率之间的差频信号或倍频信号及其组合，这就是交调噪声。对于交调噪声可以通过适当的调制技术，人为地校正系统的非线性部分得到补偿。噪声的类型交调噪声69噪声的类型串音是一个通路的信号在相邻的另一个通路引起的干扰现象。这是由于信号线路之间的电磁感应引起的有害耦合。为了消除线路之间的有害耦合，可以将每一对线拧成一定扭绞节距的线缆。噪声的类型串音70噪声的类型脉冲噪声是由于电火花或其他原因造成的突发振幅很大、持续时间比间隔时间短得多的离散脉冲耦合到信号通路中的干扰。脉冲噪声也称为冲击噪声，它将引起一连串的数据比特出错，它是数据传输差错的主要根源。脉冲噪声产生的干扰很难消除，只能采用差错控制的方法来实现可靠传输。噪声的类型脉冲噪声71（3）差错的类型随机差错指数据单元中的单比特差错。它通常由传输信道的热噪声引起。突发差错指数据单元中的两个或两个以上的比特发生成串密集性的差错，第一个错误比特到最后一个错误比特之间的位数称为突发长度。冲击噪声持续的时间通常大于数据传输中每比特的发送时间，因而会引起相邻的多个数据位出错，从而导致突发差错。（3）差错的类型随机差错72有差错的信道类型按照噪声或干扰的变化规律，可把信道分为三类：随机信道：

恒参高斯白噪声信道是典型的随机信道，其中差错的出现是随机的，而且错误之间是统计独立的。突发信道：

具有脉冲干扰的信道，是典型的突发信道。错误是成串成群出现的，即在短时间内出现大量错误。混合信道：

短波信道和对流层散射信道是混合信道的典型例子，随机差错和成串的突发差错都占有相当比例。有差错的信道类型按照噪声或干扰的变化规律，可把信道分为三类：73（4）如何解决传输差错问题提高物理信道的质量，尽量避免和减少差错：采用电缆屏蔽措施和适当的调制解调方法设置中继设备对信号进行整理再生和放大加大发射功率，降低接收设备本身的噪声，以提高信噪比提高数据的健壮性，有效地进行检错和纠错：采用信道编码技术，为数据信息增加冗余编码，形成抗干扰编码，使接收方能进行检错或纠错配合适当的差错控制方法进行检错或纠错。（4）如何解决传输差错问题提高物理信道的质量，尽量避免和减少74第十章差错控制为什么要进行差错控制差错控制的基本方法差错控制编码的基本概念常用的简单编码常用的线性分组码第十章差错控制为什么要进行差错控制75差错控制的基本工作方式自动反馈重发方式ARQ发端发送检错码，收端收到信码后能够检查出错误。前向纠错方式FEC发端发送能够纠正错误的码，收端收到信码后自动地纠正传输中的错误。混合纠错方式HEC是FEC和ARQ方式的结合。信息反馈方式IF是不用编码的差错控制方式。差错控制的基本工作方式自动反馈重发方式ARQ76（1）自动反馈重发ARQ

自动反馈重发记作ARQ(AutomaticRepeatRequest)，又称自动请求重传方式。发方按照一定的编码规则处理待发信息，构成具有检错能力的编码，发往传输信道；收方判决传输中无错误产生，并通过反向信道把判决结果反馈给发方；发方根据反馈的结果决定是否执行重传动作，如果接收方未正确接收，则重传信息(出错重传)在规定的时间内，发方若未能收到应答信号(称为超时)，则可以认为传输出现差错，进而执行重传动作(超时重传)。（1）自动反馈重发ARQ自动反馈重发记作ARQ(Auto77主要的反馈重传方式

反馈重传方式的特点是译码设备简单，对突发错误和信道干扰较严重时有效；但实时性差，主要在计算机数据通信系统中得到应用。常用的反馈重传方式有：发送-等待ARQ（停—等协议）连续发送ARQ（滑动窗口协议）选择重传ARQ发送方接收方抗干扰编码应答信号主要的反馈重传方式反馈重传方式的特点是译码设备简单，对突发78（2）前向纠错法FEC前向纠错方式记作FEC(ForwordErrorCorrection)。发送方按照一定的编码规则处理待发信息，构成具有纠正错误能力的代码(纠错码)发往传输信道；接收方根据编码规则，检查传输差错，并自动加以纠正。其特点是单向传输，实时性好，但译码设备较复杂。（2）前向纠错法FEC前向纠错方式记作FEC(Forword79（3）混合纠错法混合纠错方式记作HEC(HybridErrorCorrection)是FEC和ARQ方式的结合。发方发送具有一定纠错能力同时又具有检错能力的编码。收方收到编码后，检查差错情况，如果错误在编码的纠错能力范围以内，则自动纠错，否则经过反馈信道请求发方重发。（3）混合纠错法混合纠错方式记作HEC(HybridErr80（4）信息反馈法信息反馈法记作IRQ(InformationRepeatRequest)接收方把收到的信息代码全部送回发送方，由发送方进行差错检验。发送方若发现传输差错，则重发信息代码，直至不再发现差错为止。（4）信息反馈法信息反馈法记作IRQ(Informatio81几种差错控制方法比较自动反馈重传法：

使用的编/解码设施比较简单，如果信道的质量差或干扰严重，则可能经常进入重发状态而影响通信效率。前向纠错法：编/解码相对复杂，且编码的效率很低，但是无需专门的反馈信道。主要应用于没有反馈信道的场合，或用于线路传播时间很长、要求重发在经济上不切实际的的场合。由于形成纠错码要求较多的冗余信息，当信道质量较好时，也影响了传输的效率。混合纠错法：编/解码相当复杂、且编码的效率很低，很少被采用。信息反馈法：反馈信息量太大，传输效率很低，很少被采用。几种差错控制方法比较自动反馈重传法：82第十章差错控制为什么要进行差错控制差错控制的基本方法差错控制编码的基本概念常用的简单编码常用的线性分组码第十章差错控制为什么要进行差错控制83差错控制编码的基本原理差错控制的核心技术是信道编码技术，即采用适当的差错控制编码来传输信息。差错控制编码的基本思想是在被传输信息中增加一些冗余码，利用附加码元和信息码元之间的约束关系加以校验，以检测和纠正错误，增加的冗余码元就称为监督码元（校验码元）。差错控制编码的基本原理差错控制的核心技术是信道编码技术，即采84信道编码技术对于n位的二进制码有N=2n种组合。如果这N种组合都用来传输信息，这样构成的编码并不具备抗干扰能力。因为不管哪一位发生错误，都会使传输信息出错。但是，若这N种组合并未完全使用，情况将会怎样呢？信道编码技术对于n位的二进制码有N=2n种组合。85差错控制编码的抗干扰机理【例】考虑n=3的情形，3位二进制码有8种组合：

000、001、010、011、100、101、110、111若只用以下四个码组表示四个字母，其余的作为禁用码组：

000——A 011——B 101——C 110——D则只要发生一位错误，准用码组就将变成禁用码组，接收端就能知道出错，但是不能纠错。若只用两个码组作为有用码组000——A、111——B，并将8个码组分为两个子集：{000、001、010、100}和{011、101、110、111}，前者对应码组000，后者对应码组111。则接收端可以检测两位及以下的差错，或纠正一位的差错。【结论】增加监督码元的个数可提高纠检错能力。差错控制编码的抗干扰机理【例】考虑n=3的情形，3位二进制码86抗干扰编码的理论依据香农定理在有噪声干扰的信道中，若信道容量为C，只要发送端以低于C的速率R发送信息（R为输入信道编码器的二进制码元速率），则一定存在一种编码方式，使数据的误码率随着码长n的增长将按指数下降到任一值。结论如码长及发送速率一定，可以通过增大信道容量，使误码率下降。如信道容量及发送信息速率一定，可以通过增加码长，使误码率下降。抗干扰编码的理论依据香农定理87码长、码重、码距编码码组中的码元总位数称为码组的长度，简称码长。一个码组中，“1”码元的数目称为码组的重量，简称码重。两个等长码组之间对应码位上码元不同的数目称为这两个码组的海明(Hamming)距离，简称码距。一个码组集中任意两个码组之间距离的最小值称为码的最小距离。最小码距是抗干扰编码的一个重要参数，它是衡量编码检错、纠错能力的依据。【例】在前述例子中，码组集{000、011、101、110}的最小码距为2，而码组集{000、111}的最小码距为3。码长、码重、码距编码码组中的码元总位数称为码组的长度，简称码88编码的检错和纠错能力理论证明，编码的抗干扰能力与最小码距密切相关：为检查出e个错误，要求最小码距为dmin≥e+1为纠正t个错误，要求最小码距为dmin≥2t+1为纠正e个错误，同时检查出t个错误，要求最小码距为dmin≥e+t+1 (e>t)编码的检错和纠错能力理论证明，编码的抗干扰能力与最小码距密切89编码效率用差错控制编码提高通信系统的的可靠性，是以降低有效性为代价换来的。定义编码效率R来衡量有效性：R=d/(d+r)其中，d是信息码元的个数，r为校验码元个数

。校验码元越长，编码的检错能力越强，编码/解码越复杂；附加的冗余信息在整个编码中所占的比例越大，传输的有效成分越低，传输的效率下降。编码效率用差错控制编码提高通信系统的的可靠性，是以降低有效性90对纠、检错码的基本要求对纠、检错码的基本要求是:检错和纠错能力尽量强、编码效率尽量高、编码规律尽量简单。实际中要根据具体指标要求，保证有一定的纠、检错能力和编码效率，并且易于实现。对纠、检错码的基本要求91差错控制编码的分类按照信息码元和监督码元之间的函数关系分为：线性码和非线性码。前者码元之间能满足一组线性方程组，后者则不然。按照对信息元的处理方式分为：分组码和卷积码。前者的各码元仅与本组的信息元有关；后者的码元不仅与本组的信息元有关，而且还与前面若干组的信息元有关。按照差错控制编码的用途分为：检错码和纠错码。前者以检错为目的，不一定能纠错；而后者以纠错为目的，一定能检错。按照码组中信息码元在编码前后是否相同分为：系统码和非系统码。差错控制编码的分类按照信息码元和监督码元之间的函数关系分为：92分组码分组码一般用(n,k)表示。其中，k是每组二进制信息码元的数目，n是编码码组的码长。n-k=r为每个码组中的监督码元数目。简单地说，分组码是对每段k位长的信息组以一定的规则增加r个监督元，组成码长为n的码字。在二进制情况下，共有2k个不同的信息组，相应地可得到2k个不同的码字，称为许用码组。其余2n-2k个码字未被选用，称为禁用码组。分组码=k个信息码元+r个监督码元（校验码元）分组码分组码一般用(n,k)表示。其中，k是每组二进制信息码93线性分组码线性分组码是指信息码元与监督码元之间的关系可以用一组线性方程来表示的分组码。在(n,k)分组码中，每一个监督码元都是码组中某些信息码元按模2和而得到的，线性分组码是一类重要的检/纠错码，应用很广。本章介绍的差错控制编码均为线性分组码。线性分组码线性分组码是指信息码元与监督码元之间的关系可以用一94第十章差错控制为什么要进行差错控制差错控制的基本方法差错控制编码的基本概念常用的简单编码常用的线性分组码第十章差错控制为什么要进行差错控制95常用的简单编码奇偶校验码水平奇偶校验（行校验）垂直奇偶校验（列校验）水平垂直奇偶校验（方阵码）定比码（恒比码）常用的简单编码奇偶校验码96奇偶校验码

奇偶校验码是在原信息码元后面附加一个监督码元，使得码组中“1”的个数为奇数或偶数。因此，奇偶校验码是含一个监督码元，码重为奇数或偶数的（n,n-1）系统分组码。奇偶监督码又分为奇监督码和偶监督码。奇偶校验码奇偶校验码是在原信息码元后面附加一个监督码元，使97奇偶校验码的特点

设有n-1位信息码元为Cn-1，Cn-2，……，C1，校验码为C0对于偶校验，有 对于奇校验，有奇偶校验码只能检测出代码序列中的奇数个错误。没有纠错能力最小码距为dmin=2编码效率为R=（n-1）/n98奇偶校验码的特点设有n-1位信息码元为Cn-1，Cn-2，行、列监督码奇偶校验码不能发现偶数个错误。为了改善这种情况，引入行、列监督码。这类编码不仅对水平(行)方向的码元，而且对垂直(列)方向的码元实施奇偶校验。既可以逐行传输，也可以逐列传输。这类编码具有较强的检测能力，适于检测突发错误，还有一定的纠错能力。行、列监督码奇偶校验码不能发现偶数个错误。为了改善这种情况，99水平奇偶校验（HRC）

属于水平方向冗余校验：把要传输的数据以适当的长度划分成若干个小组，每个小组由若干个码字组成。把码字按顺序一列一列地排列起来，然后对水平方向的码元进行奇偶校验，得到一列校验码字，附加在其它各列之后，最后按列的顺序进行传输。水平奇偶校验（HRC）属于水平方向冗余校验：100水平奇偶校验之例

字符位ABCDEFGHI偶校验位11010101011201100110003000111100040000000110500000000006000000000071111111111水平奇偶校验能发现水平方向奇数个错误，以及所有突发长度<=n（n为码字长度）的突发性错误。水平奇偶校验之例字符ABCDEFGHI偶校验位101垂直奇偶校验（VRC）

属于垂直方向冗余校验码：把要传输的数据以适当的长度划分成若干个小组，每个小组由若干个码字组成。把码字按顺序一列一列地排列起来。然后对垂直方向的码元进行奇偶校验，得到一行校验位字，附加在其它各列之后，最后按列的顺序进行传输。垂直奇偶校验（VRC）属于垂直方向冗余校验码：102垂直奇偶校验之例

垂直奇偶校验能发现垂直方向奇数个错误，以及50%的突发性错误。字符位ABCDEFGHI1101010101201100110030001111004000000011500000000060000000007111111111奇校验位110100110垂直奇偶校验之例垂直奇偶校验能发现垂直方向奇数个错误，以及103水平垂直奇偶校验（LRC）

水平垂直奇偶校验码，也称为方阵校验码。它不仅对行进行奇偶校验，而且也对列进行奇偶校验。这种方法按列传输时能发现所有长度<=n+1（n为码字长度）的突发性错误和其它错误；按行传输时能发现所有长度<=m+1（m为码字个数）的突发性错误和其它错误；并且具有一定的纠错能力。水平垂直奇偶校验（LRC）水平垂直奇偶校验码，也称为方阵校104水平垂直奇偶校验之例

字符位ABCDEFGHI偶校验位11010101011201100110003000111100040000000110500000000006000000000071111111111奇校验位1101001101水平垂直奇偶校验之例字符ABCDEFGHI偶校105定比码定比码的码字中1的数目与0的数目保持恒定比例，也称为恒比码。由于恒比码中，每个码组均含有相同数目的1和0，因此恒比码又称等重码，定1码。这种码在检测时，只要计算接收码元中1的数目是否正确，就可判断有无差错。

定比码定比码的码字中1的数目与0的数目保持恒定比例，也称为恒106定比码应用举例我国电传通信中普遍采用3∶2码，又称“5中取3”的定比码，即每个码组的长度为5，其中3个“1”。这时可能编成的不同码组数目等于从5中取3的组合数10，这10个许用码组恰好可表示10个阿拉伯数字。而每个汉字又是以四位十进制数来代表的。国际通用的ARQ电报通信系统采用“7中取3”的定比码。“7中取3”码可以检出所有的单比特差错和奇数个差错，但只能检出部分偶数位差错。定比码应用举例我国电传通信中普遍采用3∶2码，又称“5中取3107第十章差错控制为什么要进行差错控制差错控制的基本方法差错控制编码的基本概念常用的简单编码常用的线性分组码第十章差错控制为什么要进行差错控制108循环冗余码（CRC）循环码是一类重要的线性分组码，它除了具有线性码的一般性质外，还具有循环性，即循环码组中任一码组循环移位所得的码组仍为该循环码中的一许用码组。循环冗余码（CRC码）是数据通信领域中最常用的一种差错检验码，其特征是信息码元和校验码元的长度可以任意选定。循环冗余码（CRC）循环码是一类重要的线性分组码，它除了具有109CRC码的原理假定我们构成(n=7,k=3)这样的线性分组码，若已知三个信息码元为C6、C5和C4，而校验码元C3、C2、C1和C0是未知的。校验码元与信息码元间的关系是根据以下四个线性关系式确立的。 CRC码的原理假定我们构成(n=7,k=3)这样的线性分组码110CRC码的原理按上页编出的线性码为：信息码元码组C6C5C4C6C5C4C3C2C1C000000000000010011101010010011101101110101001001110101101001111011010011111110100当我们从表中任意挑选出两个码组时，将对应比特按模2相加，所得到的新码组仍然是表中的某一码组。这说明由8个码字组成的线性码具有封闭性。封闭性是线性码的一个重要特性。CRC码的原理按上页编出的线性码为：信息码元码组C6111循环冗余码的基本思想把要传输的数据信息当作一个报文码多项式f(x)的系数，发送时用一个标准的生成多项式G(x)来除f(x)，将所除得余式R(x)的系数附加在报文码之后发出；接收时用同一生成多项式G(x)来除收到的码字多项式，能除尽说明传输正确，否则说明有错。实现：用简单的移位寄存器电路即可。循环冗余码的基本思想把要传输的数据信息当作一个报文码多项式112码多项式

从数学角度来看，所有的X进制数都可以用一个以X为基的多项式来表示。对于二进制数，基X=2，多项式的系数只取0、1。对于长度为n的任一二进制码字，可以用一个x的n-1次多项式来表示。码字中每个码元的值就是该多项式中的相应的系数。此多项式就成为码多项式。如：

Cn-1Cn-2……C1

C0的码多项式为：

Cn-1

xn-1+

Cn-2xn-2+……+

C1x1+

C0x0又如：码字1010111对应的多项式为x6+x4+x2+x+1，而多项式为x5+x3+x2+x+1对应的码字为101111。码多项式从数学角度来看，所有的X进制数都可以用一个以X为基113循环冗余码（CRC）

设：

k个信息码元Cn-1，Cn-2，……，Cn-k对应的码多项式为f(x)；r次的生成多项式为G(x)

（n=k+r）；用G(x)去除f(x)（模2运算）所得余式为R(x)；f(x)=Cn-1

xk-1+

Cn-2xk-2+……+

Cn-k

x0R(x)=Cr-1

xr-1+

Cr-2

xr-2+……+

C0x0Cn-1，Cn-2，……，Cn-k，Cr-1，……，C0循环冗余码（CRC）设：

k个信息码元Cn-1，Cn-2，114循环冗余编码工作原理

发送方接收方发送数据f(x)生成多项式G(x)f(x)xr.G(x)=Q(x)+R(x)G(x)实际发送:f(x)xr.+R(x)信息字段校验字段f(x)xr.R(x)接收数据f(x)+R(x)生成多项式G(x)R'(x)=R(x)接收正确R'(x)≠R(x)接收出错发送f(x)xr.G(x)=Q(x)+R'(x)G(x)循环冗余编码工作原理发送方接收方发送数据f(x)生成多项115CRC校验码软件生成方法设：信息代码M为1011001，生成多项式为G(x)=x4+x3+1，则：k=7，r=4，CRC码字长度为n=11对应f(x)=x6+x4+x3+1，G(x)的代码为1011001x4f(x)=x10+x8+x7+x4对应的代码记为：10110010000；采用多项式除法，得余数为1010

(即校验字段为1010)发送方发出的传输编码为:

1011001

1010

信息字段

校验字段接收方使用相同的生成码进行校验，将接收到的字段除以生成码（二进制除法），如果能够除尽，则正确，否则出错。CRC校验码软件生成方法设：信息代码M为1011001，生成116简化算法

11111101√1010000

1110110010

1110111110

1110111将信息码字左移n-k位，后面补上n-k个0；用所得的码字除以生成多项式G(x)的系数；将所得的n-k位余数接在信息码字之后，即可得到CRC编码。例：设(7,3)码的信息码字为101，生成多项式为：G(x)=x4+x3+x2+1求CRC编码的码字的过程如右图所示。余数为0011，CRC编码为1010011。简化算法将信息码字左移n-k位，后面补上n-k个0；117例1设信息代码M=1010001101，r=5,G=110101。模2运算的结果是：商Q=1101010110，余数R=01110。将余数R作为冗余码添加在信息M的后面发送出去，即发送的数据是101000110101110，或2rM+R。例1设信息代码M=1010001101，r=5,G118例1的计算过程

1101010110

←

Q

商

除数

P→

110101101000110100000

←

2rM被除数

110101

111011

110101

111010

110101

111110

110101

101100

110101

110010