数据通信原理3课件

第三章差错控制本章首先讨论差错控制的基本概念及原理，介绍简单的差错控制协议，然后详细介绍几种简单的差错控制编码、汉明码、循环码，并具体分析了线性分组码的一般特性，最后探讨了卷积码的相关内容。第三章差错控制本章首先讨论差错控制3.1差错控制的基本概念及原理3.1.1差错控制的基本概念1.差错分类:随机差错、突发差错随机差错又称独立差错，它是指那些独立地、稀疏地和互不相关地发生的差错。突发差错是指一串串，甚至是成片出现的差错，差错之间有相关性，差错出现是密集的。例：数据序列1

01100011101

××××××××这一串为突发差错（中间可能有不错的码）3.1差错控制的基本概念及原理3.1.1差错控制的基本概例1发送数据序列：10010111001接收数据序列：11111001110差错序列：01101110111“0”表示没错；“1”表示有错例1发送数据序列：10010112.差错控制的基本思路差错控制的基本思路是：在发送端被传送的信息码序列（本身无规律）的基础上，按照一定的规则加入若干监督码元后进行传输，这些加入的码元与原来的信息码序列之间存在着某种确定的约束关系。在接收数据时，检验信息码元与监督码元之间的既定的约束关系，如该关系遭到破坏，则收端可以发现传输中的错误，乃至纠正错误。此过程叫信息码+监督码=码组r+k=n差错控制编码或纠错编码或信道编码2.差错控制的基本思路差错控制的基本思路是：在发送端被传送的3.差错控制方式检错重发ARQ前向纠错FEC混合纠错检错HEC信息反馈IRQ3.差错控制方式检错重发ARQ（1）检错重发(ARQ)（自动重发请求）①ARQ的思路ARQ是在发送端对数据序列进行分组编码，加入一定监督码元使之具有一定的检错能力，成为能够发现错误的码组。接收端收到码组后，按一定规则对其进行有无错误的判别，并把判决结果(应答信号)通过反向信道送回发送端。如有错误，发送端把前面发出的信息重新传送一次，直到接收端认为已正确接收到信息为止。②ARQ的重发方式ARQ有3种重发方式，即停发等候重发，返回重发和选择重发。（1）检错重发(ARQ)（自动重发请求）三种重发方式a.停止等待协议当重发方式采用停发等候重发时，应该遵循停止等待协议。停止等待协议规定：发送端每发送一个数据帧（对应一个码组）就暂停下来，等待接收端的应答。接收端收到数据帧进行差错检测，若数据帧没错，就向发送端返回一个确认帧ACK，发送端再发送下一个数据帧；若接收端检验出数据帧有错，就向发送端返回一个否认帧NAK，发送端重发刚才所发数据帧，直到没错为止。b.连续ARQ协议连续ARQ协议的重发方式是返回重发，即发送端从出错数据帧及以后的各帧都要重发。c.选择重发ARQ协议选择重发ARQ协议的重发方式是选择重发，即发送端只重发出错数据帧。三种重发方式a.停止等待协议停止等待(协议算法)重发

数据帧在实际链路上传输有四种情况，如图所示。停止等待(协议算法)重发

数据帧在实际链路上传输有四种情况，数据通信原理3课件③ARQ的优缺点需反向信道，实时性差编码效率较高译码设备较简单③ARQ的优缺点需反向信道，实时性差（2）前向纠错（FEC）（自动纠错）①FEC的思路前向纠错系统中，发送端的信道编码器将输入数据序列变换成能够纠正错误的码，接收端的译码器根据编码规律检验出错误的位置并自动纠正。②FEC的优缺点●不需要反向信道，实时性好。●缺点是所选择的纠错码必须与信道的错码特性密切配合，否则很难达到降低错码率的要求；●译码设备复杂；而要求附加的监督码也较多，传输效率就低。（2）前向纠错（FEC）（自动纠错）(3)混合纠错检错（HEC）①HEC的思路混合纠错检错方式是前向纠错方式和检错重发方式的结合。在这种系统中，发送端发出同时具有检错和纠错能力的码，接收端收到码后，检查错误情况，如果错误少于纠错能力，则自行纠正；如果干扰严重，错误很多，超出纠正能力，但能检测出来，则经反向信道要求发端重发。

②HEC的优缺点混合纠错检错方式在实时性和译码复杂性方面是前向纠错和检错重发方式的折衷，因而近年来，在数据通信系统中采用较多。(3)混合纠错检错（HEC）(4)信息反馈（IRQ）①IRQ的思路信息反馈方式(IRQ)在发送端不进行纠错编码，接收端把收到的数据序列全部由反向信道送回发端，发端自己比较发送的数据序列与送回的数据序列，从而发现是否有错误，并把认为错误的数据序列的原数据再次传送，直到发端没有发现错误为止。②IRQ的优缺点●这种方式的优点是不需要纠错、检错的编译器，设备简单。●缺点是需要和前向信道相同的反向信道，实时性差。●发送端需要一定容量的存储器以存储发送码组，环路时延越大，数据速率越高，所需存储容量越大。(4)信息反馈（IRQ）练习差错控制方式中不需反向信道的是实时性最好的是不需信道编译码器的是用得最多的是前向纠错FEC前向纠错FEC信息反馈IRQ混合纠错检错HEC练习差错控制方式中3.1.2差错控制的基本原理

1.差错控制的原理传两个消息（1）发1位码

1→00→1无纠检错能力（2）发2位码

11→1000→01可检错1位3.1.2差错控制的基本原理

1.差错控制的原理传两个消息（3）发3位码

111000可纠错1位可检错2位收发两端约定，当收到两个以上的1时，认为发的是111；当收到两个以上的0时，认为发的是000。

111→110

000→001若无以上约定，111000→110（3）发3位码可纠错1位可检错2位收发两端约定，1纠错编码之所以具有检错和纠错能力，是因为在信息码之外附加了监督码，即码的检错和纠错能力是用信息量的冗余度来换取的。加入监督码越多，码的检错、纠错能力越强，但信息传输效率下降也越多。在纠错编码中将信息传输效率也称为编码效率，定义为（3-1）纠错编码之所以具有检错和纠错能力，是因为在信息2.汉明距离与检错和纠错能力的关系

（1）几个概念码组的重量——码组中非零码元的数目为码组的重量，简称码重。码距——把两个码组中对应码位上具有不同二进制码元的个数定义为两码组的距离，简称码距。例：1101010001码距是3汉明距离——在一种编码中，任意两个许用码组间距离的最小值，称为这一编码的汉明距离，以表示。2.汉明距离与检错和纠错能力的关系

（1）几个概念码组的重量例：一码组集合10111110010001011010333422例：一码组集合101113334223.纠错编码的分类(1)按码组的功能分，有检错码和纠错码两类。(2)按码组中监督码元与信息码元之间的关系分，有线性码和非线性码两类。(3)按照信息码元与监督码元的约束关系，又可分为分组码和卷积码两类。(4)按照信息码元在编码前后是否保持原来的形式不变，可划分为系统码和非系统码。(5)按纠正差错的类型可分为纠正随机错误的码和纠正突发错误的码。(6)按照每个码元取值来分，可分为二进制码与多进制码。3.纠错编码的分类3.2简单的差错控制编码

3.2.1奇偶监督码(编码规则)设码组长度为n，表示为()，其中前n-1位为信息码元，第n位为监督位a0。3.2简单的差错控制编码

3.2.1奇偶监督码(编码规则2、监督方程偶检验的监督关系（偶监督方程）在奇校验的监督关系（奇监督方程）1、概念偶监督码---信息码与监督码合在一起“1”的个数是偶数奇监督码---信息码与监督码合在一起“1”的个数是奇数2、监督方程偶检验的监督关系（偶监督方程）只能发现单个或奇数个错误，不能检测出偶数个错误只能发现单个或奇数个错误，3.2.1水平奇偶监督码水平奇偶监督码的构成思路是：将信息码序列按行排成方阵，每行后面加一个奇或偶监督编码，即每行为一个奇偶监督码组(见表3-2，以偶监督为例)，但发送时则按列的顺序传输：111011100110000…10101，接收端仍将码元排成与发送端一样的方阵形式，然后按行进行奇偶校验。表3-2水平偶监督码信息码元监督码元

11100110001101001101100001110100010000101100111011

10101*******3.2.1水平奇偶监督码信检错能力（1）可发现某一行上所有奇数个错误（2）能检测出所有长度不大于方阵中行数的突发错误讨论：

水平奇偶监督码是检错码，属于线性分组码。

检错能力（1）可发现某一行上所有奇数个错误讨论：

水平奇偶监3.2.2二维奇偶监督码二维奇偶监督码是将水平奇偶监督码推广而得，又称水平垂直奇偶监督码、行列监督码和方阵码。它的方法是在水平监督基础上对表3-2方阵中每一列再进行奇偶校验，就可得表3-3（以偶监督为例）所示的方阵。发送是按列或按行的顺序传输。接收端重新将码元排成发送时方阵形式，然后每行、每列都进行奇偶校验。表3-3二维偶监督码信息码元监督码元

11100110001101001101100001110100010000101100111011

监督码元

1010101101100011*******3.2.2二维奇偶监督码二维奇偶监检错能力（1）可发现某行或某列上奇数个错误。（2）能检测出所有长度不大于方阵中行数（或列数）的突发错误（3）能检测出偶数个错误。但若偶数个错误恰好分布在矩阵的四个顶点上时，这样的偶数个错误是检测不出来的。（4）可以纠正某些错误，当某行某列均不满足监督关系，可判定该行该列交叉位置的码元有错，从而纠正这一位上的错误。讨论：二维奇偶监督码是检错码或纠错码，属于线性分组码。检错能力（1）可发现某行或某列上奇数个错误。讨论：二维奇偶监3.3汉明码及线性分组码

3.3.1汉明码1、（n,k）汉明码r与n的关系为3.3汉明码及线性分组码1、（n,k）汉明码数据通信原理3课件例题例题（2）纠检错

方法------接收端收到（7，4）汉明码，由下述方程计算校正子，然后查表3-4可知此码组是否有错以及差错的确切位置（2）纠检错

方法------接收端收到（7，4）汉明码，由

s1s2s3错码位置

000无错

001

a0

010a1

100a2

011a3

101a4

110a5

111a6表3-4较正子与错码位置**s1s2s3例：接收端收到某（7，4）汉明码为1001010，此（7，4）汉明码是否有错？错码位置如何？例：接收端收到某（7，4）汉明码为1001010，此（7，4讨论①汉明距离

②编码效率讨论①汉明距离

②编码效率数据通信原理3课件3.3.2线性分组码2.线性分组码的主要性质

(1)封闭性所谓封闭性，是指一种线性分组码中的任意两个码组之逐位模2和仍为这种码中的另一个许用码组。线性码是指信息位和监督位满足一组线性方程的码，分组码是监督码仅对本码组起监督作用，既是线性码又是分组码称为线性分组码。3.3.2线性分组码2.线性分组码的主要性质(2)码的最小距离等于非零码的最小重量（除了全0码组之外）因为线性分组码具有封闭性，因而两个码组之间的距离必是另一码组的重量。(2)码的最小距离等于非零码的最小重量（除了循环码是线性分组码中一类重要的码。

3.4.1循环码的循环特性循环码的循环性是指循环码中任一许用码组经过循环移位后(将最右端的码元移至左端，或反之)所得到的码组仍为它的一个许用码组。表3-6给出一种(7，3)循环码的全部码组，由此表可直观看出这种码的循环性。例如，表中的第2码组向右循环移一位即得到第5码组，第2码组向左循环移一位即得到第3码组。3.4循环码循环码是线性分组码中一类重要的码。

3.4.1循环码的循表3-6（7，3）循环码的码组

码组编号信息位监督位

码组编号信息位监督位

1234

000001010011

0000011111101001

5678

100101110111

1011110001010010表3-6（7，3）循环码的码组信息位数据通信原理3课件1.码的多项式若码组

，则相应的多项式表示为

3.4.2循环码的生成多项式和生成矩阵3.4.2循环码的生成多项式和生成矩阵例1：A=1011011例2：已知，写出对应的码组(n=7)。解：A=1101001例1：A=1011011例2：已知循环码的2k个码组中，有一个码组前k-1位码元均为0，第k位码元为1，第n位（最后一位）码元为1，此码组对应的多项式。例：求表3-6（7，3）循环码的生成多项式。表3-6（7，3）循环码对应生成多项式的码组为第3个码组0010111，生成多项式为2、循环码的生成多项式循环码的2k个码组中，有一个码组前k-1位码元例3.生成矩阵G由循环码的生成多项式g(x)可得到生成矩阵G(x)，为转换后，典型的生成矩阵为3.生成矩阵G转换后，典型的生成矩阵为生成矩阵可以通过线性变换将非典型的生成矩阵转换为典型的生成矩阵，具体方法是：任意几行模二加取代某一行。生成矩阵可以通过线性变换将非典型的生成矩阵转换为典型的生成矩例例将三位信息码（000、001、010、011…111）与典型的生成矩阵G相乘便可得到全部码组，即表3-6所示。将三位信息码（00数据通信原理3课件

信息字段为K位，校验字段为R位，码字长度为N(N=K+R)位

V(x)=xRm(x)+r(x)m(x)为K次信息多项式，

r(x)为R次校验多项式例如：信息字段代码为:1011001对应m(x)=x6+x4+x3+1g(x)=x4+x3+1为生成多项式g(x)的代码为:11001校验码生成的另一种方法信息字段为K位，校验字段为R位，码字长度为N(N=K+R

信息字段移位：

x4m(x)=x10+x8+x7+x4—10110010000校验字段形成：（二进制除）取余数

1100110110010000得：1010传输字段：10110011010校验：接收字段/相同的生成码（二进制除），除尽（正确），否则（错）信息字段移位：BinaryDivisionBinaryDivision常用的CRC生成多项式g(x)为:CRC16=x16+x15+x2+1R=16，IBM专用

CRC16=x16+x12+x5+1R=16，CCITT专用

CRC32=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1R=32,LAN中常用数据通信原理3课件3.5卷积码1.卷积码的概念在分组码中，任何一段规定时间内编码器产生的n个码元的一个码组，其监督位完全决定于这段时间中输入的k个信息位，这个码组中的n-k个监督位仅对本码组起监督作用。卷积码则不然，编码器在任何一段规定时间内产生的n个码元，其监督位不仅取决于这段时间中的k个信息位，而且还取决于前N-1段规定时间内的信息位。换句话说，监督位不仅对本码组起监督作用，还对前N-1个码组也起监督作用。这段N时间内的码元数目nN称为这种卷积码的约束长度。通常把卷积码记作(n,k,N)，其编码效率3.5卷积码1.卷积码的概念卷积码的基本概念卷积码的基本概念数据通信原理3课件2卷积码的编码简单例子：由2个移位寄存器和1个模2加电路构成（2，1，2）卷积码编码器D1D2+m1m2m3m4m5m6tm1c1m2c2m3c3m4c4m5c5m6c6tmcmi.m1.0.m2.m1.m3.m2.mi-1ci+1

=mi+m(i+1)2卷积码的编码简单例子：由2个移位寄存器和1个模2加电路构2卷积码的解码D1D2+++D3与门.m1’.c1’0S0.mi+1’0.m2’.c2’.m1’.S1S0.m3’.m2’.c3’.S2S1.mi’.ci+1’SiSi-1S0=0+m1’+c1’S1=m1’+m2’+c2’S2=m2’+m3’+c3’S3=m3’+m4’+c4’校正子Si=mi’+m(i+1)’+ci+1’此为门限解码，属于代数解码，适于约束长度较短的卷积码；另一类为概率解码2卷积码的解码D1D2+++D3与.m1’.c1’0S（2，1，3）卷积码编码器m1m2m3++.c1c2C1=m1+m2+m3C2=m1+m3输入比特状态比特输入序列输出序列（2，1，3）卷积码编码器m1m2m3++.c1.m2m3=00(左)输入m1=000移位后10001001110010(左)输入m1=101110010011100100111001001110010011100100111卷积码的树状图.m2m3=00(左)输入00移位后100010011100（2，1，3）卷积码的树状图.a(m3m2)(左)输入m1=0a.c1c2=00babcdab(左)输入m1=1cdabcdabcdabcdabcdabcd0000001111111111101010010111000110当输入序列为11010…时，输出码元序列？1101010010…（2，1，3）卷积码的树状图.a(m3m2)(左)输入a.c输入为0110…时，输出码元序列？000111101011输入为000111101（2，1，3）卷积码的网格图（篱笆图）abcd（2，1，3）卷积码的网格图（篱笆图）abcd（2，1，3）卷积码的状态图0，实线；1，虚线00=a01=b10=c11=d00=a01=b10=c11=d0011111001100100（2，1，3）卷积码的状态图0，实线；1，虚线00=a01卷积码的译码方法代数译码利用编码本身得代数结构进行解码，并不考虑信道的统计特性。其主要特点是算法简单，易于实现，但是它的误码性能要比概率译码差。其译码方法是从线性码的监督子出发，找到一组特殊的能够检查信息位置是否发生错误的方程组，从而实现纠错译码。概率译码的基本思想是：把已经接收到的序列与所有可能的发送序列相比较，选择其中汉明距离最小的一个序列作为发送序列。维特比译码是目前用得较多的一种译码方法。卷积码的译码方法代数译码利用编码本身得代数结构进行解码，并不

举例说明维特比译码工作原理维特比提出了一种算法：译码器不是在篱笆图上一次就计算和比较2Lk条路径，而是接收一段，就计算、比较一段，从而在每个状态时，选择进入该状态的最可能的分支。维特比译码的基本思想：将接收序列R与篱笆图上的路径逐分支地比较，比较的长度一般取(5~6)mn，然后留下与R距离最小的路径，称为幸存路径，而去掉其余可能的路径，并将这些幸存路径逐分支地延长并存储起来。幸存路径的数目等于状态数：2km以(2,1,2)非系统码为例说明维特比译码的基本思想：设发送序列C为全0；接收序列R=[10,00,01,00,00,00,00,…]

维特比译码的基本原理举例说明维特比译码工作原理维特比译码的基本原理假设译码器的初始状态为全0；第0个时刻：接收序列的第0个分支R0=10进入译码器。从S0状态有两个分支，它们是00和11，R0与这两个分支比较，比较的结果和到达的状态如表9.2所示：每个状态/节点都有两个存储器：路径存储器：存储该状态的部分路径；路径值存储器：存储达到该状态的部分路径值(累加距离)。

维特比译码的基本原理假设译码器的初始状态为全0；维特比译码的基本原理第一个时刻：进入译码器的接收码组R1=00和此时刻出发的四条分支比较，比较结果和达到状态如表9.3所示：从第一个时刻到第二个时刻：共有四条路径，到达S0,S1,S2和S3。在第二个时刻以前译码器不做任何选择和判决。每个状态的路径存储器存储下此时刻的幸存路径：0000,0011,1110,1101；每个状态的路径值存储器存储了此时刻到达该状态的幸存路径累加值(累加距离)。

维特比译码的基本原理第一个时刻：进入译码器的接收码组R1=00和此时刻出发的从第二个时刻起：第二个接收码组R2=01进入译码器，从篱笆图上可见，从第二个时刻到第三个时刻，进入每个状态的分支有两个（或者说在第三个时刻，进入每个状态的路径有两条）。译码器将接收码组R2与进入每个状态的两个分支进行比较和判决，选择一个累加距离（部分路径值）最小的路径作为进入该状态的幸存路径。这样的幸存路径共四条，比较和判决的过程如下：

维特比译码的基本原理从第二个时刻起：第二个接收码组R2=01进入译码器，从篱经过比较后选择：部分路径

000000为到达S0

状态的幸存路径；部分路径000011为到达

S1状态的幸存路径；部分路径110101为到达S2状态的幸存路径；部分路径001101为到达S3

状态的幸存路径。按照上述方法，接收序列的诸码组依次进入译码器，每个时刻进入一个码组，沿着篱笆图对每个状态按部分路径值（累加距离）的大小，选择一条幸存路径。在每个状态上进行判决时，可能出现进入这一状态的两条路径的距离值相同，这时可以任选其一，因为对以后的判决而言，无论选择那一条路径，累加距离是相同的。经过比较后选择：对本例而言，按上述算法进行到第十一个分支后，四条路径的前面分支都合并在一起。所以，只要译码深度足够，就可达到较低的错误概率。一般，约为(5~6)mn，所以，维特比译码的延时可达(5~6)m个单位时刻（每个单位时刻为n个码元长度）就可以对第0个接收码组的信息元进行判决。依此类推，对接收序列中的诸码组进行译码。维特比译码的一次运算：计算每个输入分支的度量值（分支距离、累加距离）；比较各部分路径的度量值，选择一条作为幸存路径。篱笆图中共有2km个状态，因此，维特比译码的计算量与编码存储m成指数关系变化，所以采用维特比算法译码的卷积码，其m不能选的太大。

维特比译码的基本原理对本例而言，按上述算法进行到第十一个分支后，四条路维特比译

维特比译码的基本原理维特比译码的基本原理

维特比译码的基本原理维特比译码的基本原理7.6维特比译码的基本原理7.6维特比译码的基本原理7.6维特比译码的基本原理7.6维特比译码的基本原理

维特比译码的基本原理维特比译码的基本原理

总结维特比算法的步骤在第j(j=m)个时刻以前，译码器计算所有的长为m个分支的部分路径值，对进入2km个状态的每一条部分路径都保留。第m个时刻开始，对进入每一个状态的部分路径进行计算，这样的路径有2k条，挑选具有最大部分路径值的部分路径为幸存路径，删去进入该状态的其它路径，然后，幸存路径向前延长一个分支。重复第二步的计算、比较和判决过程。若输入接收序列长为(L+m)k，其中，后m段是人为加入的全0段，则译码一直进行到(L+m)个时刻为止。若进入某个状态的部分路径中，有两条的部分路径值相等，则可任选其一作为幸存路径。

维特比译码的基本原理总结维特比算法的步骤维特比译码的基本原理小结小结R=k/nR=k/n第三节简单的差错控制编码

奇偶监督码、水平奇偶监督码、二维奇偶监督码的构成思路、检错能力

第四节汉明码及线性分组码

1汉明码r与n的关系

（7，4）汉明码（监督方程、纠检错方法、几个要点）

2线性分组码的概念、主要性质

第三节简单的差错控制编码

奇偶监督码、水平奇偶监督码、二第五节循环码

码组A码的多项式

循环特性

生成多项式（最高幂次）概念、求法

生成矩阵

第六节卷积码

基本概念、约束长度、编码效率

第五节循环码

码组A作业P1291，3，4，5，7，8，9，12，13，15,16（除15题外写在书上）作业P129第三章差错控制本章首先讨论差错控制的基本概念及原理，介绍简单的差错控制协议，然后详细介绍几种简单的差错控制编码、汉明码、循环码，并具体分析了线性分组码的一般特性，最后探讨了卷积码的相关内容。第三章差错控制本章首先讨论差错控制3.1差错控制的基本概念及原理3.1.1差错控制的基本概念1.差错分类:随机差错、突发差错随机差错又称独立差错，它是指那些独立地、稀疏地和互不相关地发生的差错。突发差错是指一串串，甚至是成片出现的差错，差错之间有相关性，差错出现是密集的。例：数据序列1

01100011101

××××××××这一串为突发差错（中间可能有不错的码）3.1差错控制的基本概念及原理3.1.1差错控制的基本概例1发送数据序列：10010111001接收数据序列：11111001110差错序列：01101110111“0”表示没错；“1”表示有错例1发送数据序列：10010112.差错控制的基本思路差错控制的基本思路是：在发送端被传送的信息码序列（本身无规律）的基础上，按照一定的规则加入若干监督码元后进行传输，这些加入的码元与原来的信息码序列之间存在着某种确定的约束关系。在接收数据时，检验信息码元与监督码元之间的既定的约束关系，如该关系遭到破坏，则收端可以发现传输中的错误，乃至纠正错误。此过程叫信息码+监督码=码组r+k=n差错控制编码或纠错编码或信道编码2.差错控制的基本思路差错控制的基本思路是：在发送端被传送的3.差错控制方式检错重发ARQ前向纠错FEC混合纠错检错HEC信息反馈IRQ3.差错控制方式检错重发ARQ（1）检错重发(ARQ)（自动重发请求）①ARQ的思路ARQ是在发送端对数据序列进行分组编码，加入一定监督码元使之具有一定的检错能力，成为能够发现错误的码组。接收端收到码组后，按一定规则对其进行有无错误的判别，并把判决结果(应答信号)通过反向信道送回发送端。如有错误，发送端把前面发出的信息重新传送一次，直到接收端认为已正确接收到信息为止。②ARQ的重发方式ARQ有3种重发方式，即停发等候重发，返回重发和选择重发。（1）检错重发(ARQ)（自动重发请求）三种重发方式a.停止等待协议当重发方式采用停发等候重发时，应该遵循停止等待协议。停止等待协议规定：发送端每发送一个数据帧（对应一个码组）就暂停下来，等待接收端的应答。接收端收到数据帧进行差错检测，若数据帧没错，就向发送端返回一个确认帧ACK，发送端再发送下一个数据帧；若接收端检验出数据帧有错，就向发送端返回一个否认帧NAK，发送端重发刚才所发数据帧，直到没错为止。b.连续ARQ协议连续ARQ协议的重发方式是返回重发，即发送端从出错数据帧及以后的各帧都要重发。c.选择重发ARQ协议选择重发ARQ协议的重发方式是选择重发，即发送端只重发出错数据帧。三种重发方式a.停止等待协议停止等待(协议算法)重发

数据帧在实际链路上传输有四种情况，如图所示。停止等待(协议算法)重发

数据帧在实际链路上传输有四种情况，数据通信原理3课件③ARQ的优缺点需反向信道，实时性差编码效率较高译码设备较简单③ARQ的优缺点需反向信道，实时性差（2）前向纠错（FEC）（自动纠错）①FEC的思路前向纠错系统中，发送端的信道编码器将输入数据序列变换成能够纠正错误的码，接收端的译码器根据编码规律检验出错误的位置并自动纠正。②FEC的优缺点●不需要反向信道，实时性好。●缺点是所选择的纠错码必须与信道的错码特性密切配合，否则很难达到降低错码率的要求；●译码设备复杂；而要求附加的监督码也较多，传输效率就低。（2）前向纠错（FEC）（自动纠错）(3)混合纠错检错（HEC）①HEC的思路混合纠错检错方式是前向纠错方式和检错重发方式的结合。在这种系统中，发送端发出同时具有检错和纠错能力的码，接收端收到码后，检查错误情况，如果错误少于纠错能力，则自行纠正；如果干扰严重，错误很多，超出纠正能力，但能检测出来，则经反向信道要求发端重发。

②HEC的优缺点混合纠错检错方式在实时性和译码复杂性方面是前向纠错和检错重发方式的折衷，因而近年来，在数据通信系统中采用较多。(3)混合纠错检错（HEC）(4)信息反馈（IRQ）①IRQ的思路信息反馈方式(IRQ)在发送端不进行纠错编码，接收端把收到的数据序列全部由反向信道送回发端，发端自己比较发送的数据序列与送回的数据序列，从而发现是否有错误，并把认为错误的数据序列的原数据再次传送，直到发端没有发现错误为止。②IRQ的优缺点●这种方式的优点是不需要纠错、检错的编译器，设备简单。●缺点是需要和前向信道相同的反向信道，实时性差。●发送端需要一定容量的存储器以存储发送码组，环路时延越大，数据速率越高，所需存储容量越大。(4)信息反馈（IRQ）练习差错控制方式中不需反向信道的是实时性最好的是不需信道编译码器的是用得最多的是前向纠错FEC前向纠错FEC信息反馈IRQ混合纠错检错HEC练习差错控制方式中3.1.2差错控制的基本原理

1.差错控制的原理传两个消息（1）发1位码

1→00→1无纠检错能力（2）发2位码

11→1000→01可检错1位3.1.2差错控制的基本原理

1.差错控制的原理传两个消息（3）发3位码

111000可纠错1位可检错2位收发两端约定，当收到两个以上的1时，认为发的是111；当收到两个以上的0时，认为发的是000。

111→110

000→001若无以上约定，111000→110（3）发3位码可纠错1位可检错2位收发两端约定，1纠错编码之所以具有检错和纠错能力，是因为在信息码之外附加了监督码，即码的检错和纠错能力是用信息量的冗余度来换取的。加入监督码越多，码的检错、纠错能力越强，但信息传输效率下降也越多。在纠错编码中将信息传输效率也称为编码效率，定义为（3-1）纠错编码之所以具有检错和纠错能力，是因为在信息2.汉明距离与检错和纠错能力的关系

（1）几个概念码组的重量——码组中非零码元的数目为码组的重量，简称码重。码距——把两个码组中对应码位上具有不同二进制码元的个数定义为两码组的距离，简称码距。例：1101010001码距是3汉明距离——在一种编码中，任意两个许用码组间距离的最小值，称为这一编码的汉明距离，以表示。2.汉明距离与检错和纠错能力的关系

（1）几个概念码组的重量例：一码组集合10111110010001011010333422例：一码组集合101113334223.纠错编码的分类(1)按码组的功能分，有检错码和纠错码两类。(2)按码组中监督码元与信息码元之间的关系分，有线性码和非线性码两类。(3)按照信息码元与监督码元的约束关系，又可分为分组码和卷积码两类。(4)按照信息码元在编码前后是否保持原来的形式不变，可划分为系统码和非系统码。(5)按纠正差错的类型可分为纠正随机错误的码和纠正突发错误的码。(6)按照每个码元取值来分，可分为二进制码与多进制码。3.纠错编码的分类3.2简单的差错控制编码

3.2.1奇偶监督码(编码规则)设码组长度为n，表示为()，其中前n-1位为信息码元，第n位为监督位a0。3.2简单的差错控制编码

3.2.1奇偶监督码(编码规则2、监督方程偶检验的监督关系（偶监督方程）在奇校验的监督关系（奇监督方程）1、概念偶监督码---信息码与监督码合在一起“1”的个数是偶数奇监督码---信息码与监督码合在一起“1”的个数是奇数2、监督方程偶检验的监督关系（偶监督方程）只能发现单个或奇数个错误，不能检测出偶数个错误只能发现单个或奇数个错误，3.2.1水平奇偶监督码水平奇偶监督码的构成思路是：将信息码序列按行排成方阵，每行后面加一个奇或偶监督编码，即每行为一个奇偶监督码组(见表3-2，以偶监督为例)，但发送时则按列的顺序传输：111011100110000…10101，接收端仍将码元排成与发送端一样的方阵形式，然后按行进行奇偶校验。表3-2水平偶监督码信息码元监督码元

11100110001101001101100001110100010000101100111011

10101*******3.2.1水平奇偶监督码信检错能力（1）可发现某一行上所有奇数个错误（2）能检测出所有长度不大于方阵中行数的突发错误讨论：

水平奇偶监督码是检错码，属于线性分组码。

检错能力（1）可发现某一行上所有奇数个错误讨论：

水平奇偶监3.2.2二维奇偶监督码二维奇偶监督码是将水平奇偶监督码推广而得，又称水平垂直奇偶监督码、行列监督码和方阵码。它的方法是在水平监督基础上对表3-2方阵中每一列再进行奇偶校验，就可得表3-3（以偶监督为例）所示的方阵。发送是按列或按行的顺序传输。接收端重新将码元排成发送时方阵形式，然后每行、每列都进行奇偶校验。表3-3二维偶监督码信息码元监督码元

11100110001101001101100001110100010000101100111011

监督码元

1010101101100011*******3.2.2二维奇偶监督码二维奇偶监检错能力（1）可发现某行或某列上奇数个错误。（2）能检测出所有长度不大于方阵中行数（或列数）的突发错误（3）能检测出偶数个错误。但若偶数个错误恰好分布在矩阵的四个顶点上时，这样的偶数个错误是检测不出来的。（4）可以纠正某些错误，当某行某列均不满足监督关系，可判定该行该列交叉位置的码元有错，从而纠正这一位上的错误。讨论：二维奇偶监督码是检错码或纠错码，属于线性分组码。检错能力（1）可发现某行或某列上奇数个错误。讨论：二维奇偶监3.3汉明码及线性分组码

3.3.1汉明码1、（n,k）汉明码r与n的关系为3.3汉明码及线性分组码1、（n,k）汉明码数据通信原理3课件例题例题（2）纠检错

方法------接收端收到（7，4）汉明码，由下述方程计算校正子，然后查表3-4可知此码组是否有错以及差错的确切位置（2）纠检错

方法------接收端收到（7，4）汉明码，由

s1s2s3错码位置

000无错

001

a0

010a1

100a2

011a3

101a4

110a5

111a6表3-4较正子与错码位置**s1s2s3例：接收端收到某（7，4）汉明码为1001010，此（7，4）汉明码是否有错？错码位置如何？例：接收端收到某（7，4）汉明码为1001010，此（7，4讨论①汉明距离

②编码效率讨论①汉明距离

②编码效率数据通信原理3课件3.3.2线性分组码2.线性分组码的主要性质

(1)封闭性所谓封闭性，是指一种线性分组码中的任意两个码组之逐位模2和仍为这种码中的另一个许用码组。线性码是指信息位和监督位满足一组线性方程的码，分组码是监督码仅对本码组起监督作用，既是线性码又是分组码称为线性分组码。3.3.2线性分组码2.线性分组码的主要性质(2)码的最小距离等于非零码的最小重量（除了全0码组之外）因为线性分组码具有封闭性，因而两个码组之间的距离必是另一码组的重量。(2)码的最小距离等于非零码的最小重量（除了循环码是线性分组码中一类重要的码。

3.4.1循环码的循环特性循环码的循环性是指循环码中任一许用码组经过循环移位后(将最右端的码元移至左端，或反之)所得到的码组仍为它的一个许用码组。表3-6给出一种(7，3)循环码的全部码组，由此表可直观看出这种码的循环性。例如，表中的第2码组向右循环移一位即得到第5码组，第2码组向左循环移一位即得到第3码组。3.4循环码循环码是线性分组码中一类重要的码。

3.4.1循环码的循表3-6（7，3）循环码的码组

码组编号信息位监督位

码组编号信息位监督位

1234

000001010011

0000011111101001

5678

100101110111

1011110001010010表3-6（7，3）循环码的码组信息位数据通信原理3课件1.码的多项式若码组

，则相应的多项式表示为

3.4.2循环码的生成多项式和生成矩阵3.4.2循环码的生成多项式和生成矩阵例1：A=1011011例2：已知，写出对应的码组(n=7)。解：A=1101001例1：A=1011011例2：已知循环码的2k个码组中，有一个码组前k-1位码元均为0，第k位码元为1，第n位（最后一位）码元为1，此码组对应的多项式。例：求表3-6（7，3）循环码的生成多项式。表3-6（7，3）循环码对应生成多项式的码组为第3个码组0010111，生成多项式为2、循环码的生成多项式循环码的2k个码组中，有一个码组前k-1位码元例3.生成矩阵G由循环码的生成多项式g(x)可得到生成矩阵G(x)，为转换后，典型的生成矩阵为3.生成矩阵G转换后，典型的生成矩阵为生成矩阵可以通过线性变换将非典型的生成矩阵转换为典型的生成矩阵，具体方法是：任意几行模二加取代某一行。生成矩阵可以通过线性变换将非典型的生成矩阵转换为典型的生成矩例例将三位信息码（000、001、010、011…111）与典型的生成矩阵G相乘便可得到全部码组，即表3-6所示。将三位信息码（00数据通信原理3课件

信息字段为K位，校验字段为R位，码字长度为N(N=K+R)位

V(x)=xRm(x)+r(x)m(x)为K次信息多项式，

r(x)为R次校验多项式例如：信息字段代码为:1011001对应m(x)=x6+x4+x3+1g(x)=x4+x3+1为生成多项式g(x)的代码为:11001校验码生成的另一种方法信息字段为K位，校验字段为R位，码字长度为N(N=K+R

信息字段移位：

x4m(x)=x10+x8+x7+x4—10110010000校验字段形成：（二进制除）取余数

1100110110010000得：1010传输字段：10110011010校验：接收字段/相同的生成码（二进制除），除尽（正确），否则（错）信息字段移位：BinaryDivisionBinaryDivision常用的CRC生成多项式g(x)为:CRC16=x16+x15+x2+1R=16，IBM专用

CRC16=x16+x12+x5+1R=16，CCITT专用

CRC32=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1R=32,LAN中常用数据通信原理3课件3.5卷积码1.卷积码的概念在分组码中，任何一段规定时间内编码器产生的n个码元的一个码组，其监督位完全决定于这段时间中输入的k个信息位，这个码组中的n-k个监督位仅对本码组起监督作用。卷积码则不然，编码器在任何一段规定时间内产生的n个码元，其监督位不仅取决于这段时间中的k个信息位，而且还取决于前N-1段规定时间内的信息位。换句话说，监督位不仅对本码组起监督作用，还对前N-1个码组也起监督作用。这段N时间内的码元数目nN称为这种卷积码的约束长度。通常把卷积码记作(n,k,N)，其编码效率3.5卷积码1.卷积码的概念卷积码的基本概念卷积码的基本概念数据通信原理3课件2卷积码的编码简单例子：由2个移位寄存器和1个模2加电路构成（2，1，2）卷积码编码器D1D2+m1m2m3m4m5m6tm1c1m2c2m3c3m4c4m5c5m6c6tmcmi.m1.0.m2.m1.m3.m2.mi-1ci+1

=mi+m(i+1)2卷积码的编码简单例子：由2个移位寄存器和1个模2加电路构2卷积码的解码D1D2+++D3与门.m1’.c1’0S0.mi+1’0.m2’.c2’.m1’.S1S0.m3’.m2’.c3’.S2S1.mi’.ci+1’SiSi-1S0=0+m1’+c1’S1=m1’+m2’+c2’S2=m2’+m3’+c3’S3=m3’+m4’+c4’校正子Si=mi’+m(i+1)’+ci+1’此为门限解码，属于代数解码，适于约束长度较短的卷积码；另一类为概率解码2卷积码的解码D1D2+++D3与.m1’.c1’0S（2，1，3）卷积码编码器m1m2m3++.c1c2C1=m1+m2+m3C2=m1+m3输入比特状态比特输入序列输出序列（2，1，3）卷积码编码器m1m2m3++.c1.m2m3=00(左)输入m1=000移位后10001001110010(左)输入m1=101110010011100100111001001110010011100100111卷积码的树状图.m2m3=00(左)输入00移位后100010011100（2，1，3）卷积码的树状图.a(m3m2)(左)输入m1=0a.c1c2=00babcdab(左)输入m1=1cdabcdabcdabcdabcdabcd0000001111111111101010010111000110当输入序列为11010…时，输出码元序列？1101010010…（2，1，3）卷积码的树状图.a(m3m2)(左)输入a.c输入为0110…时，输出码元序列？000111101011输入为000111101（2，1，3）卷积码的网格图（篱笆图）abcd（2，1，3）卷积码的网格图（篱笆图）abcd（2，1，3）卷积码的状态图0，实线；1，虚线00=a01=b10=c11=d00=a01=b10=c11=d0011111001100100（2，1，3）卷积码的状态图0，实线；1，虚线00=a01卷积码的译码方法代数译码利用编码本身得代数结构进行解码，并不考虑信道的统计特性。其主要特点是算法简单，易于实现，但是它的误码性能要比概率译码差。其译码方法