计算机通信技术第3.3章常用差错控制编码方法.ppt

1,3.3 常用差错控制编码方法,3.3.1 奇偶校验编码 3.3.2 方阵校验码 3.3.3 恒比码 3.3.4 正反码 3.3.5 循环冗余校验编码（CRC） 3.3.6 卷积码,2,差错控制的核心就是抗干扰编码，为了提高通信系统的检错和纠错能力，人们创造出许多差错控制编码，比较常用的有奇偶校验编码、循环冗余校验编码、卷积码等。,3,3.3.1 奇偶校验编码,又称奇偶监督编码，或垂直冗余校验（VRC，Vertical Redundancy Check），在计算机数据传输中应用广泛。 编码规则： 发送端，将所要传输的数据码元分组，在分组数据后面加一位监督码（校验位），使得该组码连同监督码在内的码组中“1”的个数为奇数（奇校验）或偶数（偶校验）。 接收端，按照编码规则检查如果发现不符，就说明产生差错，但不能明确差错的具体位置即不能纠错。,4,公式表示：设码组长度为n，表示为（an-1,an-2,a1,c0）其中前n-1位为信息位，第n位c0为监督位 奇校验：an-1an-2a1c0=1即c0= an-1an-2a11 偶校验：an-1an-2a1c0=0 即c0= an-1an-2a1,奇偶校验编码,5,特点： 无论信息位为多少位，监督位只有一位。 只能检测信息码组中奇数个错误，对偶数个错误无能为力；,奇偶校验编码,6,实例,写出下列二进制序列的偶校验码： 1001110 0101111 ,写出下列二进制序列的奇校验码： 1100101 0110010 ,10011100,01011111,11001011,01100100,7,水平奇偶校验,避免简单奇偶校验不能检测突发错误的缺点。 编码规则：经过奇偶监督编码的码元序列按行排成方阵，每一行为一组奇偶监督码(见实例)。发送端在发送时则按列的顺序传输：11101 11001 10000 01010 00111 而接受端仍将码元排成发送时方阵形式，然后按行进行奇偶校验水平奇偶监督码。,8,实例,9,特点 ：发送端是按列发送码元，而不是按码组（行）发送码元，因此可把本来可能集中发生在一码组中的突发错误分散到方阵中的各个码组，同时又作为整个方阵的行监督； 可以发现某一行上所有奇数个错误及长度不大于方阵行数的突发错误。,10,3.3.2 方阵校验码,又称行列监督码，矩阵码，纵向冗余校验码（LRC，Lognitudinal Redundancy Check），它的码元受到行和列两个方向奇偶监督，又称二维奇偶校验码。 编码规则：使的每个码元受到纵向（列）和横向两次监督；将欲发送的信息码按行排成一个矩阵，矩阵中每一行为一码组，每行的最后加上一个奇偶监督码元；矩阵中的每一列是由不同码组相同位置的码元组成，在每列最后也加上一个监督码元，进行奇偶校验；最后按行或列码组的顺序发送。,11,X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X,方阵校验码结构,12,实例,发送端在发送时则按列(或行）的顺序传输：111010 110011 100001 010100 001111 接收端仍将码元排成发送时方阵形式，然后按行、列进行奇偶校验,13,特点： 可以检测出某行某列上的奇数个错误和长度不大于行（列）数的突发错误。 可以检测出某行或某列上偶数个错误 不能纠正差错数正好是4的倍数且位置在行列矩阵/子矩阵的4个顶点上的差错,方阵校验码,14,失效！,15,3.3.3 恒比码(定比码),编码规则 ：恒比码中每码组中“1”和“0”个数保持恒定比例，接收端在检测接收到的码组中“1”的数目是否对就知道是否出错。 实例： 我国电传机传输汉字时使用数字代表汉字，采用的所谓“保护电码”就是一种“3：2”或“5中取3”的恒比码。 C52=10个许用码组 英文电报采用“7中取3”或“4：3”恒比码，共有C73=35个许用码组,16,3.3.4 正反码_能简单纠错的编码,多用于10单位电码的前向自动纠错设备中，能纠正一位差错，发现大部分两位错，差错编码和差错控制结合起来控制。以10单位电码为例： n=k+r 且 k=r=5 1.编码规则： (1)当信息码中“1”的个数为奇数时，监督码与信息码相同（正码）10101 10101 (2)当信息码中“1”的个数为偶数时，监督码与信息码相反（反码）10100 01011,17,2.解码方法： (1)将接收到信息码与监督码按相应的码位模2加（异或），得到一个新的5位码组。 (2)根据接收到的信息码中“1”的个数： if“1”的个数为奇数，则取新5位码组为校验码组 if“1”的个数为偶数，则取新5位码组的反码为校验码组,正反码,18,正反码判决表,（3），最后可按下表，根据检验码组中“1”的个数进行判断及纠正可能发现的错码,19,实例：,已知信息码11010使用正反码差错控制方式，试问下列接收端收到的数据是否有错？能否纠正？ 11010 11010 10010 11010 11010 01010 10000 11010,20,（1） 编码：11010（信息码）11010（监督码）11010 11010（正反码） （2） 解码： 接收端11010 11010 接收端10010 11010 接收端11010 01010 接收端10000 11010 判断：,21,11010 + 11010 00000 结果为0，正确。,22,10010 + 11010 01000 由于接收信息码中为偶数个1，所以检验码取反，10111，信息码中有一位出错，根据判决2，出错位置就是检验码组中0所对应的位置，纠正后为11010,23,11010 + 01010 10000 由于接收信息码中为奇数个1，所以检验码不变，根据判决3，监督码码中有一位出错，出错位置就是检验码组中1所对应的位置，纠正后为11010,24,10000 + 01010 01010 检验码中1的个数1，根据判决4，无法判断和纠错,25,3.3.5 循环冗余校验编码（CRC）,Cyclic Redundancy checking (CRC)循环冗余校验，又称多项式码。 在循环冗余校验中，不是通过将各比特位相加来得到期望的校验，而是通过在数据单元末尾加一串冗余比特，称作循环冗余校验码或循环冗余校验余数，使得整个数据单元可以被另一个预定的二进制数所整除。,26,CRC校验基本思想,CRC校验的基本思想是： 根据欲发送的k位信息位构成的报文，发送器生成一个r比特的序列，称为帧校验序列FCS（Frame checking Series），将r位FCS（即CRC码）附加到k位信息序列之后作为实际发送的数据帧（k+r位），这个帧所对应二进制序列恰好能够被某个预先确定的数（生成多项式）整除。接收器用相同的数去除传来的帧。如果无余数，则认为无差错；如果余数不为0，刚认为传输出错。,27,奇偶校验对一个字符校验一次，适合异步通讯；而CRC对一个数据块（frame）校验一次，适合同步通讯。在串行同步通信中，几乎都使用这种校验方法。如磁盘信息的读/写等。,CRC校验常用场合,28,CRC码生成和校验基本分为三步： 第一步：在数据单元(k位）的末尾加上r个0。r是一个比预定除数的比特位数(r十1)少1的数。 第二步：采用二进制除法将新的加长的数据单元（k+r位)除以除数。由此除法产生的余数就是循环冗余码校验码。,CRC码的生成,29,第三步：用从第二步得到的r个比特的CRC码替换数据单元末尾附加的r个0。如果余数位数小于r，最左的缺省位数为0。如果除法过程根本未产生余数（也就是说，原始的数据单元本身就可以被除数整除）那么以r个0作为CRC码替换余数所在的位置。产生的比特模式正好能被除数整除。,CRC码的生成,30,CRC码校验： 到达接收方的数据单元首先到达的是数据，然后是CRC校验码。接收方将整个数据串当作一个整体去除以用来产生循环冗余校验余数的同一个除数。 如果数据串无差错地到达接收方，循环冗余校验器将产生余数0。因此数据单元将通过检验。如果在传输中数据单元被改变，除法将产生非零余数，因此数据单元将通不过检验。,CRC码的校验,31,循环冗余码生成器采用模2除法。下图显示了这一过程。 CRC校验器的功能完全像发生器一样，当收到附加了CRC码的数据后，做同样的模2 除法。如果余数是全0，则将CRC码丢弃，接受数据。否则，丢弃收到的数据。,CRC码生成器和校验器,32,0,G(X),33,111010100011010 CRC校验码 信息码 CRC冗余校验码,34,CRC校验码的生成器和校验器,发送方,接收方,35,任何一个二进制数序列可以和一个只含有0和1两个系数的代数多项式建立起一一对应的关系。因此，用来求CRC码的那个除数通常用多项式来表示。原因如下： 代数多项式很短 可以通过多项式来进行概念的数学证明。,多项式,36,多项式,任何一个n位的二进制数都可以用一个n-1 次的多项式来表示,这种多项式叫码多项式（又叫信息多项式） 。 码多项式与二进制序列之间的一一对应关系： （an-1 an-2a1a0）N A (x)= an-1Xn-1+an-2Xn-2 +a1X+a0X0,码多项式,37,多项式 二进制序列实例,以n=3位二进制数为例 二进制数 对应多项式 000 001 010 011 100 101 111,0,1,x,x+1,x2,x2+1,x2+ x+1,1011011 x6+x4+x3+x+1 x5+x4+x2+x 110110,38,码多项式运算法则: 二进制码多项式的加减运算为模2加运算，即两个码多项式相加时，对应项系数进行模2加减。 乘除运算与普通多项式类似； 模2加减：即各位做不带进位、借位的按位加减。这种加减运算实际上就是逻辑上的异或运算。即加法和减法等价。,码多项式,39,生成多项式G(x): 求CRC码时所用的“除数”所对应的多项式叫生成多项式。 在串行通信中通常使用下列三种生成多项式G（X）来产生CRC码。 CRC-16：G(x)=X16+X15+X2+1，美国二进制同步系统中采用。 CRC-CCITT：G(x)=X16+X12+X5+1，CCITT推荐。 CRC-32：G(x)=X32+X26+X23+X22+ X16+X12+ X11+X10+X8+1X7+ X5+X4+X2+X+ 1,码多项式,40,CRC码性能,CRC码是很有效的差错校验方法。除了正好数据块的比特值是按除数值变化的错误外，循环冗余校验(CRC)将检测出其他所有错误。而且，常用的CRC除数通常有13、17，或是33个比特，使得不可检测的错误可能降低到几乎近于零。 CRC接收电路再配上适当的硬件电路不仅可以检错，而且可以纠错，纠错能力很强特别适合检测突发性错误，在数据通信中得到较广泛的应用。,41,检错性能,能检测出全部单个错误 能检测出全部随机二位错误 能检测出全部奇数个错误 能检测出全部长度小于k位的突发错误 能以1-（1/2）k-1概率检测出长度为（k+1）位的突发性错误,42,3.3.6 卷积码,1.概述 2.编码器 3.解码器,43,1.概述,前面介绍的编码方法都是线性分组码，即监督码只负责监督检验本码组中的信息码元。 如果每组的监督码元不但与本组码的信息码元有关，而且还与前面若干组信息码元有关，即不是分组校验而是每个监督码元对它的前后码元都实行监督，前后相连，具有连环监督的作用；因此我们称为连环码，即卷积码。 卷积码由 P.Elias于1955年最先提出，整个编解码过程一环扣一环，连锁地进行下去。,44,2.编码器,aiai-1a2a1a0,b 0= a 0 b 1= a 0a 1 b 2= a 1a 2 b 3= a 2a 3 b i= a i-1a i,45,2.编码器,（1） 编码器输出过程 第一次， 前半拍开关接到a输出a0 ，后半拍开关倒向b输出b0=a00=a0 第二次， 前半拍开关接到a输出a1，后半拍开关倒向b输出 b1=a1a0 第i次，前半拍开关接到a输出ai，后半拍开关倒向b输出bi=aiai-1,46,2.编码器,（2） 连环码结构： 信息码: an-1an-2aia1a0 连环码输出序列 bn-1an-1biaib2a2b1a1b0a0 监督码bn-1bn-2bib1b0 即“信息码 监督码 信息码”，一个信息码与一个校验码构成一组但每个校验码bi=aiai-1除了与本组码有关还与前一组信息码有关，故称为卷积码。,47,48,3.解码器,a b,接收到的监督码,计算出的监督码,判决电路,1,2,3,解码输出,解码输入,Si,Si-1,连环码入口,49,解码器,解码思路： 移位寄存器R1、R2及模2加法器1构成与发送端一样的编码器，用来计算监督码和解码输出。 用模2加法器2将计算出的监督码与接收到的监督码进行比较，即先对ai编码产生新的监督码bi，再与bi异或 if结果为0 then正确 else出错。 根据第2步的输出进行判决，由判决电路完成 由判决结果通过加法器3输出结果,50,解码器,设接收的码序列b3a3b2a2b1a1b0a0其解码过程为： （1） 第零拍， 前半拍电子开关倒向a, 移位寄存器R1移出a0,R2移出0，故加法器1结果生成一个a00= a0。 后半拍电子开关倒向b结果,接收到b0，生成S0 =b0（= a0）a0 ，R3为0故与门输出0 又R2输出为0，所以加法器3输出为0,51,解码器,（2）第一拍 前半拍电子开关倒向a ，R1移出工a1,R2移出a0加法器1输出a1 a0 后半拍电子开关倒向b，加法器2输入b1 ,加法器2输出 S1 = b1 （ a1 a0） 在第一拍后半期当b1 出现在输入端时，就可对a0做判断。,52,解码器,（3）第二拍 前半拍电子开关倒向a ，R1移出工a2,R2移出a1，加法器1输出a2 a1 后半拍电子开关倒向b，加法器2输入b2加法器2输出 S2 = b2 （ a2 a1） 在第二拍后半期当b2 出现在输入端时，就可对a1做判断。 （4 ）依次类推，当b3出现在输入端时，就可对a2做判断规则如P69。,53,解码方程,模2加法器2的输出对我们判决正确性至关重要。,54,解码器,判决规则： 当Si及Si+1都为“0”时， ai正确 当Si及Si+1都为“1”时，必定是ai出错 当Si为“1”而 Si1为“0”时，必定是ai-1 、bi中有一个出错，故判