ch常用差错控制编码方法实用

会计学1ch常用差错控制编码方法实用

差错控制的核心就是抗干扰编码，为了提高通信系统的检错和纠错能力，人们创造出许多差错控制编码，比较常用的有奇偶校验编码、循环冗余校验编码、卷积码等。

第1页/共63页3.3.1奇偶校验编码

又称奇偶监督编码，或垂直冗余校验（VRC，VerticalRedundancyCheck），在计算机数据传输中应用广泛。

编码规则：发送端，将所要传输的数据码元分组，在分组数据后面加一位监督码（校验位），使得该组码连同监督码在内的码组中“1”的个数为奇数（奇校验）或偶数（偶校验）。接收端，按照编码规则检查如果发现不符，就说明产生差错，但不能明确差错的具体位置即不能纠错。第2页/共63页公式表示：设码组长度为n，表示为（an-1,an-2……,a1,c0）其中前n-1位为信息位，第n位c0为监督位①奇校验：an-1⊕an-2⊕……⊕a1⊕c0=1即c0=an-1⊕an-2⊕……⊕a1⊕1②偶校验：an-1⊕an-2⊕……⊕a1⊕c0=0即c0=an-1⊕an-2⊕……⊕a1奇偶校验编码

第3页/共63页特点：无论信息位为多少位，监督位只有一位。只能检测信息码组中奇数个错误，对偶数个错误无能为力；信息位越长,效率越高.奇偶校验编码

第4页/共63页实例写出下列二进制序列的偶校验码：①1001110②0101111写出下列二进制序列的奇校验码：①1100101②011001010011100

010111111100101101100100第5页/共63页3.3.2方阵校验码又称行列监督码，矩阵码，纵向冗余校验码（LRC，LognitudinalRedundancyCheck），它的码元受到行和列两个方向奇偶监督，又称二维奇偶校验码。编码规则：使的每个码元受到纵向（列）和横向两次监督；将欲发送的信息码按行排成一个矩阵，矩阵中每一行为一码组，每行的最后加上一个奇偶监督码元；矩阵中的每一列是由不同码组相同位置的码元组成，在每列最后也加上一个监督码元，进行奇偶校验；最后按行或列码组的顺序发送。第6页/共63页

X X X X X X X X

X X X X X X X X X X X X X XX X X X X X X X X X X X X X X X X X

方阵校验码结构第7页/共63页实例

信息码元监督码元（偶）111001001101001010000111000100011100111101101111发送端在发送时则按列(或行）的顺序传输：111010

110011

100001

010100

……001111接收端仍将码元排成发送时方阵形式，然后按行、列进行奇偶校验第8页/共63页特点：可以检测出某行某列上的奇数个错误和长度不大于行（列）数的突发错误。可以检测出某行或某列上偶数个错误不能纠正差错数正好是4的倍数且位置在行列矩阵/子矩阵的4个顶点上的差错

方阵校验码第9页/共63页失效！！！

信息码元监督码元（偶）111001001101001010000111000100011100111101101111第10页/共63页3.3.3恒比码(定比码)编码规则：恒比码中每码组中“1”和“0”个数保持恒定比例，接收端在检测接收到的码组中“1”的数目是否对就知道是否出错。实例：我国电传机传输汉字时使用数字代表汉字，采用的所谓“保护电码”就是一种“3：2”或“5中取3”的恒比码。C52=10个许用码组英文电报采用“7中取3”或“4：3”恒比码，共有C73=35个许用码组第11页/共63页3.3.4正反码_能简单纠错的编码多用于10单位电码的前向自动纠错设备中，能纠正一位差错，发现大部分两位错，差错编码和差错控制结合起来控制。以10单位电码为例：n=k+r且k=r=51.编码规则：(1)当信息码中“1”的个数为奇数时，监督码与信息码相同（正码）1010110101(2)当信息码中“1”的个数为偶数时，监督码与信息码相反（反码）1010001011第12页/共63页2.解码方法：(1)将接收到信息码与监督码按相应的码位模2加（异或），得到一个新的5位码组。(2)根据接收到的信息码中“1”的个数：if“1”的个数为奇数，则取新5位码组为校验码组if“1”的个数为偶数，则取新5位码组的反码为校验码组正反码第13页/共63页正反码判决表校验码组的组成判决差错情况1全“0”无错24个“1”一个“0”信息码中有一位出错，出错位置就是检验码组中0所对应的位置34个“0”一个“1”监督码中有一位出错，出错位置就是检验码组中1所对应的位置4其他差错个数>1个（3），最后可按下表，根据检验码组中“1”的个数进行判断及纠正可能发现的错码第14页/共63页实例：已知信息码11010使用正反码差错控制方式，试问下列接收端收到的数据是否有错？能否纠正？①1101011010②1001011010③1101001010④1000011010第15页/共63页（1）编码：11010（信息码）11010（监督码）→1101011010（正反码）（2）解码：①接收端1101011010②接收端1001011010③接收端1101001010④接收端1000011010判断：第16页/共63页11010+1101000000

结果为0，正确。第17页/共63页10010+1101001000由于接收信息码中为偶数个1，所以检验码取反，10111，信息码中有一位出错，根据判决2，出错位置就是检验码组中0所对应的位置，纠正后为11010第18页/共63页11010+0101010000由于接收信息码中为奇数个1，所以检验码不变，根据判决3，监督码码中有一位出错，出错位置就是检验码组中1所对应的位置，纠正后为11010第19页/共63页10000+0101001010检验码中1的个数>1，根据判决4，无法判断和纠错第20页/共63页作业已知信息码10010使用正反码差错控制方式，试问下列接收端收到的数据是否有错？能否纠正？①1101001101②1001010010③1001001101④1001001001第21页/共63页11010+0110110111由于接收信息码中为奇数个1，所以检验码不变，根据判决2，信息码中有一位出错，出错位置就是检验码组中0所对应的位置，纠正后为10010。第22页/共63页10010+1101001000由于接收信息码中为偶数个1，所以检验码取反，10111，信息码中有一位出错，根据判决2，出错位置就是检验码组中0所对应的位置，纠正后为11010第23页/共63页10010+0110111111由于接收信息码中为偶数个1，所以检验码取反，11111,1的个数大于1,结果错误,不能纠正第24页/共63页10000+0101001010检验码中1的个数>1，根据判决4，无法判断和纠错第25页/共63页

3.3.5循环冗余校验编码（CRC）

CyclicRedundancychecking(CRC)循环冗余校验，又称多项式码。在循环冗余校验中，不是通过将各比特位相加来得到期望的校验，而是通过在数据单元末尾加一串冗余比特，称作循环冗余校验码或循环冗余校验余数，使得整个数据单元可以被另一个预定的二进制数所整除。第26页/共63页1.CRC校验基本思想

CRC校验的基本思想是：

(1)根据欲发的k位信息生成一个r比特的序列，称为帧校验序列FCS（FramecheckingSeries）。（2）求出实际发送的数据帧（k+r位），这个帧所对应二进制序列恰好能够被某个预先确定的数（生成多项式）整除。（3）接收器用相同的数（生成多项式）去除传来的帧。如果无余数，则认为无差错；如果余数不为0，刚认为传输出错。第27页/共63页奇偶校验对一个字符校验一次，适合异步通讯；而CRC对一个数据块（frame）校验一次，适合同步通讯。在串行同步通信中，几乎都使用这种校验方法。如磁盘信息的读/写等。2.CRC校验常用场合

第28页/共63页CRC码生成和校验基本分为三步：第一步：在数据单元(k位）的末尾加上r个0。r是一个比预定除数的比特位数(r十1)少1的数。第二步：采用二进制除法将新的加长的数据单元（k+r位)除以除数。由此除法产生的余数就是循环冗余码校验码。3.CRC码的生成

第29页/共63页第三步：求CRC循环冗余校验码(K+r)被除数+r(余数)如果余数位数小于r，最左的缺省位数为0。如果余数为0,则r=0。CRC码的生成

第30页/共63页CRC码校验：到达接收方的数据单去除以用来产生循环冗余校验余数的G（X）。如果余数0，将通过检验。如果余数非零，将通不过检验。4.CRC码的校验

第31页/共63页

任何一个二进制数序列可以和一个只含有0和1两个系数的代数多项式建立起一一对应的关系。因此，用来求CRC码的那个除数通常用多项式来表示。原因如下：代数多项式很短可以通过多项式来进行概念的数学证明。5.多项式第32页/共63页多项式

任何一个n位的二进制数都可以用一个n-1次的多项式来表示,这种多项式叫码多项式（又叫信息多项式）

。码多项式与二进制序列之间的一一对应关系：（an-1an-2……a1a0）N

A(x)=an-1Xn-1+an-2Xn-2+……+a1X+a0X0码多项式第33页/共63页多项式二进制序列实例以n=3位二进制数为例

二进制数对应多项式

000

001

010

011 100 101

111

01xx+1x2x2+1x2+x+11011011x6+x4+x3+x+1x5+x4+x2+x110110第34页/共63页码多项式运算法则:二进制码多项式的加减运算为⊕模2加运算，即两个码多项式相加时，对应项系数进行模2加减。乘除运算与普通多项式类似；模2加减：即各位做不带进位、借位的按位加减。这种加减运算实际上就是逻辑上的异或运算。即加法和减法等价。码多项式第35页/共63页生成多项式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码多项式第36页/共63页循环冗余码生成器采用模2除法。下图显示了这一过程。CRC校验器的功能完全像发生器一样，当收到附加了CRC码的数据后，做同样的模2除法。如果余数是全0，则将CRC码丢弃，接受数据。否则，丢弃收到的数据。6.CRC码生成器和校验器

第37页/共63页CRC校验码的生成器和校验器r个比特0数据g(x)CRC校验码r+1r余数先发数据位后发校验位g(x)余数r+1r数据0接收，非0拒绝数据发送方接收方第38页/共63页0G(X)第39页/共63页111010100011010CRC校验码信息码

CRC冗余校验码第40页/共63页7.CRC码性能

CRC码是很有效的差错校验方法。除了正好数据块的比特值是按除数值变化的错误外，循环冗余校验(CRC)将检测出其他所有错误。而且，常用的CRC除数通常有17，或是33个比特，使得不可检测的错误可能降低到几乎近于零。CRC接收电路再配上适当的硬件电路不仅可以检错，而且可以纠错，纠错能力很强特别适合检测突发性错误，在数据通信中得到较广泛的应用。第41页/共63页检错性能能检测出全部单个错误能检测出全部随机二位错误能检测出全部奇数个错误能检测出全部长度小于k位的突发错误能以[1-（1/2）k-1]概率检测出长度为（k+1）位的突发性错误第42页/共63页课堂练习题设某一循环码，其生成多项式为G（X）=X5+X2+1，试求出信息序列1101010101011的循环校验码CRC（要求写出计算步骤）。第43页/共63页设某一循环码，其生成多项式为G（X）=X5+X4+X2+1，试求出信息序列1010001100的CRC循环校验码（要求写出计算步骤）。第44页/共63页3.3.6卷积码1.概述2.编码器3.解码器第45页/共63页1.概述前面介绍的编码方法都是线性分组码，即监督码只负责监督检验本码组中的信息码元。如果每组的监督码元不但与本组码的信息码元有关，而且还与前面若干组信息码元有关，即不是分组校验而是每个监督码元对它的前后码元都实行监督，前后相连，具有连环监督的作用；因此我们称为连环码，即卷积码。卷积码由P.Elias于1955年最先提出，整个编解码过程一环扣一环，连锁地进行下去。第46页/共63页2.编码器aiai-1…a2a1a0R2R1信息入口连环码输出模2加法器ab…b3a3b2a2b1a1b0a0移位寄存器移位寄存器b0=a0b1=a0⊕a1b2=a1⊕a2

b3=a2⊕a3…bi=ai-1⊕ai第47页/共63页2.编码器（1）编码器输出过程第一次，前半拍开关接到a输出a0，后半拍开关倒向b输出b0=a0⊕0=a0第二次，前半拍开关接到a输出a1，后半拍开关倒向b输出b1=a1⊕a0……第i次，前半拍开关接到a输出ai，后半拍开关倒向b输出bi=ai⊕ai-1

第48页/共63页2.编码器（2）连环码结构：信息码: an-1an-2……ai……a1a0

监督码

bn-1bn-2……bi……b1b0连环码输出序列

bn-1an-1…biai…b2a2b1a1b0a0

即“信息码监督码信息码……”，一个信息码与一个校验码构成一组但每个校验码bi=ai⊕ai-1除了与本组码有关还与前一组信息码有关，故称为卷积码。第49页/共63页第50页/共63页3.解码器R1R2R3&a’b’接收到的监督码计算出的监督码判决电路123解码输出解码输入Si

Si-1连环码入口第51页/共63页解码器解码思路：移位寄存器R1、R2及模2加法器1构成与发送端一样的编码器，用来计算监督码和解码输出。用模2加法器2将计算出的监督码与接收到的监督码进行比较，即先对ai’编码产生新的监督码bi’’，再与bi’异或,if结果为0then正确else出错。根据第2步的输出进行判决，由判决电路完成由判决结果通过加法器3输出结果第52页/共63页

解码器设接收的码序列…b3’a3’b2’a2’b1’a1’b0’a0’其解码过程为：（1）第零拍，前半拍电子开关倒向a’,移位寄存器R1移出a0’,R2移出0，故加法器1结果生成一个a0’⊕0=a0’。后半拍电子开关倒向b’结果,接收到b0’，生成S0=b0’（=a0’）⊕a0’，R3为0故与门输出0又R2输出为0，所以加法器3输出为0第53页/共63页

解码器（2）第一拍前半拍电子开关倒向a’，R1移出工a1’,R2移出a0’加法器1输出a1’⊕a0’后半拍电子开关倒向b’，加法器2输入b1’,加法器2输出

S1=

b1

’⊕（a1’⊕a0’）在第一拍后半期当b1

’出现在输入端时，就可对a0’做判断。第54页/共63页解码器（3）第二拍前半拍电子开关倒向a’，R1移出工a2’,R2移出a1’，加法器1输出a2’⊕a1’后半拍电子开关倒向b’，加法器2输入b2’加法器2输出

S2=

b2

’⊕（a2’⊕a1’）在第二拍后半期当b2

’出现在输入端时，就可对a1’做判断。（4

）依次类推，当b3’出现在输入端时，就可对a2’做判断……规则如P69。第55页/共63页解码方程模2加法器2的输出对我们判决正确性至关重要。第56页/共63页解码器判决规则：当Si及Si+1都为“0”时，a