差错控制基本方法和编码要求课件

1、差错控制基本方法和编码要求为什么要进行差错控制差错控制的基本方法差错控制编码的基本概念常用的简单编码常用的线性分组码（1）差错产生的原因数据通信系统的基本任务是高效率而无差错地传送数据。数据信号在通信线路中传输时，难免受到来自信道内部和外部的干扰，从而引起信号的失真，导致数据传输错误。传输出错的原因：一是信道的加性噪声；二是由于传输总特性（包括收、发滤波器和信道的特性）不理想引起的码间串扰。噪声是影响数据传输质量的主要因素。根据产生的原因可以将噪声分为四类：热噪声、交调噪声、串音和脉冲噪声四类。（2）噪声的类型热噪声是由带电粒子在导电介质中的布朗运动引起的，它存在于任何工作在绝对零度以上的电路

2、或系统中。热噪声属于高斯白噪声，其概率密度函数满足正态分布统计特性，同时它的功率谱密度函数是均匀分布的（常数）。热噪声的特点是：时刻存在、不可排除、幅度较小、强度与频率无关，但频谱很宽，是一类随机的噪声。噪声的类型交调噪声是一种附加的频率干扰。由于通信系统的非线性，将导致进入通信系统的不同频率的信号在系统的输出端产生这些频率之间的差频信号或倍频信号及其组合，这就是交调噪声。对于交调噪声可以通过适当的调制技术，人为地校正系统的非线性部分得到补偿。噪声的类型串音是一个通路的信号在相邻的另一个通路引起的干扰现象。这是由于信号线路之间的电磁感应引起的有害耦合。为了消除线路之间的有害耦合，可以将每一对线

3、拧成一定扭绞节距的线缆。噪声的类型脉冲噪声是由于电火花或其他原因造成的突发振幅很大、持续时间比间隔时间短得多的离散脉冲耦合到信号通路中的干扰。脉冲噪声也称为冲击噪声，它将引起一连串的数据比特出错，它是数据传输差错的主要根源。脉冲噪声产生的干扰很难消除，只能采用差错控制的方法来实现可靠传输。（3）差错的类型随机差错指数据单元中的单比特差错。它通常由传输信道的热噪声引起。突发差错指数据单元中的两个或两个以上的比特发生成串密集性的差错，第一个错误比特到最后一个错误比特之间的位数称为突发长度。冲击噪声持续的时间通常大于数据传输中每比特的发送时间，因而会引起相邻的多个数据位出错，从而导致突发差错。有差错

4、的信道类型按照噪声或干扰的变化规律，可把信道分为三类：随机信道：恒参高斯白噪声信道是典型的随机信道，其中差错的出现是随机的，而且错误之间是统计独立的。突发信道：具有脉冲干扰的信道，是典型的突发信道。错误是成串成群出现的，即在短时间内出现大量错误。混合信道：短波信道和对流层散射信道是混合信道的典型例子，随机差错和成串的突发差错都占有相当比例。（4）如何解决传输差错问题提高物理信道的质量，尽量避免和减少差错：采用电缆屏蔽措施和适当的调制解调方法设置中继设备对信号进行整理再生和放大加大发射功率，降低接收设备本身的噪声，以提高信噪比提高数据的健壮性，有效地进行检错和纠错：采用信道编码技术，为数据信息增

5、加冗余编码，形成抗干扰编码，使接收方能进行检错或纠错配合适当的差错控制方法进行检错或纠错。第十章 差错控制为什么要进行差错控制差错控制的基本方法差错控制编码的基本概念常用的简单编码常用的线性分组码差错控制的基本工作方式自动反馈重发方式ARQ发端发送检错码，收端收到信码后能够检查出错误。前向纠错方式FEC发端发送能够纠正错误的码，收端收到信码后自动地纠正传输中的错误。混合纠错方式HEC是FEC和ARQ方式的结合。信息反馈方式IF是不用编码的差错控制方式。（1）自动反馈重发ARQ 自动反馈重发记作ARQ (Automatic Repeat Request )，又称自动请求重传方式。发方按照一定的编

6、码规则处理待发信息，构成具有检错能力的编码，发往传输信道；收方判决传输中无错误产生，并通过反向信道把判决结果反馈给发方；发方根据反馈的结果决定是否执行重传动作，如果接收方未正确接收，则重传信息(出错重传)在规定的时间内，发方若未能收到应答信号(称为超时)，则可以认为传输出现差错，进而执行重传动作(超时重传)。主要的反馈重传方式 反馈重传方式的特点是译码设备简单，对突发错误和信道干扰较严重时有效；但实时性差，主要在计算机数据通信系统中得到应用。 常用的反馈重传方式有：发送-等待ARQ（停等协议）连续发送ARQ（滑动窗口协议）选择重传ARQ发送方接收方抗干扰编码应答信号（2）前向纠错法FEC前向纠

7、错方式记作FEC(Forword Error Correction)。发送方按照一定的编码规则处理待发信息，构成具有纠正错误能力的代码(纠错码)发往传输信道；接收方根据编码规则，检查传输差错，并自动加以纠正。其特点是单向传输，实时性好，但译码设备较复杂。 （3）混合纠错法混合纠错方式记作HEC(Hybrid Error Correction)是FEC和ARQ方式的结合。发方发送具有一定纠错能力同时又具有检错能力的编码。收方收到编码后，检查差错情况，如果错误在编码的纠错能力范围以内，则自动纠错，否则经过反馈信道请求发方重发。（4）信息反馈法信息反馈法记作IRQ (Information Repe

8、at Request )接收方把收到的信息代码全部送回发送方，由发送方进行差错检验。发送方若发现传输差错，则重发信息代码，直至不再发现差错为止。几种差错控制方法比较自动反馈重传法： 使用的编/解码设施比较简单，如果信道的质量差或干扰严重，则可能经常进入重发状态而影响通信效率。 前向纠错法：编/解码相对复杂，且编码的效率很低，但是无需专门的反馈信道。主要应用于没有反馈信道的场合，或用于线路传播时间很长、要求重发在经济上不切实际的的场合。由于形成纠错码要求较多的冗余信息，当信道质量较好时，也影响了传输的效率。混合纠错法：编/解码相当复杂、且编码的效率很低，很少被采用。信息反馈法：反馈信息量太大，传

9、输效率很低，很少被采用。第十章 差错控制为什么要进行差错控制差错控制的基本方法差错控制编码的基本概念常用的简单编码常用的线性分组码差错控制编码的基本原理差错控制的核心技术是信道编码技术，即采用适当的差错控制编码来传输信息。差错控制编码的基本思想是在被传输信息中增加一些冗余码，利用附加码元和信息码元之间的约束关系加以校验，以检测和纠正错误，增加的冗余码元就称为监督码元（校验码元）。信道编码技术对于n位的二进制码有N=2n种组合。如果这N种组合都用来传输信息，这样构成的编码并不具备抗干扰能力。因为不管哪一位发生错误，都会使传输信息出错。但是，若这N种组合并未完全使用，情况将会怎样呢？差错控制编码的

10、抗干扰机理【例】考虑n=3的情形，3位二进制码有8种组合：000、001、010、011、100、101、110、111若只用以下四个码组表示四个字母，其余的作为禁用码组：000 A011B101C110D则只要发生一位错误，准用码组就将变成禁用码组，接收端就能知道出错，但是不能纠错。若只用两个码组作为有用码组000 A、111B，并将8个码组分为两个子集：000、001、010、100和011、101、110、111，前者对应码组000，后者对应码组111。则接收端可以检测两位及以下的差错，或纠正一位的差错。【结论】增加监督码元的个数可提高纠检错能力。抗干扰编码的理论依据香农定理在有噪声干扰

11、的信道中，若信道容量为C，只要发送端以低于C的速率R发送信息（R为输入信道编码器的二进制码元速率），则一定存在一种编码方式，使数据的误码率随着码长n的增长将按指数下降到任一值。结论如码长及发送速率一定，可以通过增大信道容量，使误码率下降。如信道容量及发送信息速率一定，可以通过增加码长，使误码率下降。码长、码重、码距编码码组中的码元总位数称为码组的长度，简称码长。一个码组中，“1”码元的数目称为码组的重量，简称码重。两个等长码组之间对应码位上码元不同的数目称为这两个码组的海明(Hamming)距离，简称码距。一个码组集中任意两个码组之间距离的最小值称为码的最小距离。最小码距是抗干扰编码的一个重要

12、参数，它是衡量编码检错、纠错能力的依据。【例】在前述例子中，码组集000、011、101、110的最小码距为2，而码组集000、111的最小码距为3。编码的检错和纠错能力理论证明，编码的抗干扰能力与最小码距密切相关：为检查出e个错误，要求最小码距为dmine+1为纠正t个错误，要求最小码距为dmin2t+1为纠正e个错误，同时检查出t个错误，要求最小码距为dmine+t+1(et)编码效率用差错控制编码提高通信系统的的可靠性，是以降低有效性为代价换来的。定义编码效率R来衡量有效性：R=d/(d+r) 其中，d是信息码元的个数，r为校验码元个数 。校验码元越长，编码的检错能力越强，编码/解码越复

13、杂；附加的冗余信息在整个编码中所占的比例越大，传输的有效成分越低，传输的效率下降。对纠、检错码的基本要求对纠、检错码的基本要求是: 检错和纠错能力尽量强、编码效率尽量高、编码规律尽量简单。 实际中要根据具体指标要求，保证有一定的纠、检错能力和编码效率，并且易于实现。差错控制编码的分类按照信息码元和监督码元之间的函数关系分为：线性码和非线性码。前者码元之间能满足一组线性方程组，后者则不然。按照对信息元的处理方式分为：分组码和卷积码。前者的各码元仅与本组的信息元有关；后者的码元不仅与本组的信息元有关，而且还与前面若干组的信息元有关。按照差错控制编码的用途分为：检错码和纠错码。前者以检错为目的，不一

14、定能纠错；而后者以纠错为目的，一定能检错。按照码组中信息码元在编码前后是否相同分为：系统码和非系统码。分组码分组码一般用(n,k)表示。其中，k是每组二进制信息码元的数目，n是编码码组的码长。n-k=r为每个码组中的监督码元数目。简单地说，分组码是对每段k位长的信息组以一定的规则增加r个监督元，组成码长为n的码字。在二进制情况下，共有2k个不同的信息组，相应地可得到2k个不同的码字，称为许用码组。其余 2n-2k个码字未被选用，称为禁用码组。分组码= k个信息码元+ r个监督码元（校验码元）线性分组码线性分组码是指信息码元与监督码元之间的关系可以用一组线性方程来表示的分组码。在(n,k)分组码

15、中，每一个监督码元都是码组中某些信息码元按模2和而得到的，线性分组码是一类重要的检/纠错码，应用很广。本章介绍的差错控制编码均为线性分组码。第十章 差错控制为什么要进行差错控制差错控制的基本方法差错控制编码的基本概念常用的简单编码常用的线性分组码常用的简单编码奇偶校验码水平奇偶校验（行校验）垂直奇偶校验（列校验）水平垂直奇偶校验（方阵码）定比码（恒比码）奇偶校验码 奇偶校验码是在原信息码元后面附加一个监督码元，使得码组中“1”的个数为奇数或偶数。因此，奇偶校验码是含一个监督码元，码重为奇数或偶数的（n,n-1）系统分组码。奇偶监督码又分为奇监督码和偶监督码。奇偶校验码的特点 设有n-1位信息码

16、元为Cn-1，Cn-2，C1， 校验码为C0对于偶校验，有对于奇校验，有奇偶校验码只能检测出代码序列中的奇数个错误。没有纠错能力最小码距为dmin=2编码效率为R=（n-1）/n34行、列监督码奇偶校验码不能发现偶数个错误。为了改善这种情况，引入行、列监督码。这类编码不仅对水平(行)方向的码元，而且对垂直(列)方向的码元实施奇偶校验。既可以逐行传输，也可以逐列传输。这类编码具有较强的检测能力，适于检测突发错误，还有一定的纠错能力。水平奇偶校验（HRC） 属于水平方向冗余校验：把要传输的数据以适当的长度划分成若干个小组，每个小组由若干个码字组成。把码字按顺序一列一列地排列起来，然后对水平方向的码

17、元进行奇偶校验，得到一列校验码字，附加在其它各列之后，最后按列的顺序进行传输。水平奇偶校验之例 水平奇偶校验能发现水平方向奇数个错误，以及所有突发长度=n（n为码字长度）的突发性错误。 字符位ABCDEFGHI偶校验位11010101011201100110003000111100040000000110500000000006000000000071111111111垂直奇偶校验（VRC） 属于垂直方向冗余校验码：把要传输的数据以适当的长度划分成若干个小组，每个小组由若干个码字组成。把码字按顺序一列一列地排列起来。然后对垂直方向的码元进行奇偶校验，得到一行校验位字，附加在其它各列之后，最后按

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

19、之例 字符位ABCDEFGHI偶校验位11010101011201100110003000111100040000000110500000000006000000000071111111111奇校验位1101001101定比码定比码的码字中1的数目与0的数目保持恒定比例，也称为恒比码。由于恒比码中，每个码组均含有相同数目的1和0，因此恒比码又称等重码，定1码。这种码在检测时，只要计算接收码元中1的数目是否正确，就可判断有无差错。定比码应用举例我国电传通信中普遍采用32码，又称“5中取3”的定比码，即每个码组的长度为5，其中3个“1”。这时可能编成的不同码组数目等于从5中取3的组合数10，这10

20、个许用码组恰好可表示10个阿拉伯数字。而每个汉字又是以四位十进制数来代表的。国际通用的ARQ电报通信系统采用“7中取3”的定比码。“7中取3”码可以检出所有的单比特差错和奇数个差错，但只能检出部分偶数位差错。第十章 差错控制为什么要进行差错控制差错控制的基本方法差错控制编码的基本概念常用的简单编码常用的线性分组码循环冗余码（CRC）循环码是一类重要的线性分组码，它除了具有线性码的一般性质外，还具有循环性，即循环码组中任一码组循环移位所得的码组仍为该循环码中的一许用码组。循环冗余码（CRC码）是数据通信领域中最常用的一种差错检验码，其特征是信息码元和校验码元的长度可以任意选定。CRC码的原理假定

21、我们构成(n=7,k=3)这样的线性分组码，若已知三个信息码元为C6、C5和C4，而校验码元C3、C2、C1和C0是未知的。校验码元与信息码元间的关系是根据以下四个线性关系式确立的。 CRC码的原理按上页编出的线性码为：信息码元码 组C6C5C4C6C5C4C3C2C1C000000000000010011101010010011101101110101001001110101101001111011010011111110100当我们从表中任意挑选出两个码组时，将对应比特按模2相加，所得到的新码组仍然是表中的某一码组。这说明由8个码字组成的线性码具有封闭性。封闭性是线性码的一个重要特性。循环

22、冗余码的基本思想 把要传输的数据信息当作一个报文码多项式f(x)的系数，发送时用一个标准的生成多项式G(x)来除f(x) ，将所除得余式R(x)的系数附加在报文码之后发出；接收时用同一生成多项式G(x)来除收到的码字多项式，能除尽说明传输正确，否则说明有错。实现：用简单的移位寄存器电路即可。码多项式 从数学角度来看，所有的X进制数都可以用一个以X为基的多项式来表示。对于二进制数，基X=2，多项式的系数只取0、1。对于长度为n的任一二进制码字，可以用一个x的n-1次多项式来表示。码字中每个码元的值就是该多项式中的相应的系数。此多项式就成为码多项式。如： Cn-1Cn-2C1 C0的码多项式为：

23、Cn-1 xn-1 + Cn-2 xn-2+ C1 x1 + C0 x0 又如：码字对应的多项式为x6+x4+x2+x+1，而多项式为x5+x3+x2+x+1对应的码字为101111。循环冗余码（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-2 xk-2+ Cn-k x0 R(x)=Cr-1 xr-1 + Cr-2 xr-2+ C0 x0 Cn-1，Cn-2，Cn-k，Cr-1，C0循环冗余编码工作原理 发送方

24、接收方发送数据 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)CRC校验码软件生成方法设：信息代码M为，生成多项式为G(x)=x4+x3+1，则：k=7，r=4，CRC码字长度为n=11 对应 f(x)=x6+x4+x3+1，G(x)的代码为x4f(x)=x10+x8+x7+x4 对应的代码记为：10110010000；采用多项式除

25、法， 得余数为 1010 (即校验字段为1010)发送方发出的传输编码为: 1 0 1 1 0 0 1 1 0 10 信息字段 校验字段接收方使用相同的生成码进行校验，将接收到的字段除以生成码（二进制除法），如果能够除尽，则正确，否则出错。简化算法 1 1 11 1 1 0 11 0 1 0 0 0 0 1 1 1 0 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1将信息码字左移n-k位，后面补上n-k个0；用所得的码字除以生成多项式G(x)的系数；将所得的n-k位余数接在信息码字之后，即可得到CRC编码。例：设(7,3)码的信息码字为101， 生成

26、多项式为： G(x)=x4+x3+x2+1求CRC编码的码字的过程如右图所示。余数为0011， CRC编码为。例1设信息代码 M = 1010001101，r = 5,G = 110101。模 2 运算的结果是： 商 Q = 1101010110， 余数R = 01110。将余数 R 作为冗余码添加在信息 M 的后面发送出去，即发送的数据是101000110101110，或 2rM + R。例1的计算过程 1101010110 Q 商 除数 P 110101 101000110100000 2rM 被除数 110101 111011 110101 111010 110101 111110 11

27、0101 101100 110101 110010 110101 01110 R 余数 例21 1 0 0 1 1 1 0 0 11 1 0 0 1 1 1 0 0 11 1 0 0 11 1 0 0 101 0 0 0 0 11 1 0 0 1 1 0 0 0 01 1 0 0 1G(x) 1 1 0 0 11 0 0 0 01 1 0 0 11 0 0 1R(x)1 0 0 0 0 1Q(x)f(x).xr1 1 0 0 1 1发送数据比特序列CRC校验码比特序列1 0 0 1带CRC校验码的发送数据比特序列例3原始数据M=1101011011G(x)=x4+x+1 的系数=1001111

28、 0 10 11 0 11 0 0 0 010 0 1110 0 111 0 0 111 0 0 111 0 1 101 0 0 111 01 0 01 0 0 1111 1 0 1100001010余数 传输码元=原始数据（左移位后）+余数 11010110111110标准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 + x

29、2+x+1 循环码的检错能力 理论证明，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年才会有一个错误。海明码Hamming于1950年在美国贝尔实验室提出了海明码，是第一个用来纠错的线性分组码，被广泛地应用在数据通信和数据存储系统的