数字通信基础-ch3(2)PPT课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,.,*,3.3 常用差错控制编码方法,3.3.1 奇偶校验编码,3.3.2 方阵校验码,3,.,3.3 恒比码,3,.,3.4 正反码,3,.,3.5 循环冗余校验编码（CRC）,3.3.6 卷积码,.,差错控制的核心就是抗干扰编码，为了提高通信系统的检错和纠错能力，人们创造出许多差错控制编码，比较常用的有,奇偶校验编码、循环冗余校验编码、卷积码,等。,.,3.3.1 奇偶校验编码,又称奇偶监督编码，或,垂直冗余校验（,VRC,，Vertical Redundancy Check），,在计算机数据传输中应用广泛。,编码规则,：,发送端，,将所要传输的数据码元分组，在分组数据后面加,一位,监督码（校验位），使得该组码连同监督码在内的码组中“1”的个数为,奇数（奇校验）或偶数（偶校验）,。,接收端，,按照编码规则检查如果发现不符，就说明产生差错，但不能明确差错的具体位置即不能纠错。,.,公式表示,：设码组长度为n，表示为（a,n-1,a,n-2,a,1,c,0,）其中前n-1位为信息位，第n位c,0,为监督位,奇校验：,a,n-1,a,n-2,a,1,c,0,=,1,即c,0,=a,n-1,a,n-2,a,1,1,偶校验,：,a,n-1,a,n-2,a,1,c,0,=0 即,c,0,=a,n-1,a,n-2,a,1,奇偶校验编码,.,特点：,无论信息位为多少位，监督位只有一位。,只能检测信息码组中奇数个错误，对,偶数,个错误无能为力；,奇偶校验编码,.,实例,写出下列二进制序列的偶校验码：,1001110,0101111,写出下列二进制序列的奇校验码：,1100101,0110010,1001110,0,0101111,1,1100101,1,0110010,0,.,水平奇偶校验,避免简单奇偶校验不能检测突发错误的缺点。,编码规则：,经过奇偶监督编码的码元序列按行排成方阵，每一行为一组奇偶监督码,(见实例),。发送端在,发送时则按,列,的顺序,传输：,11101,11001,10000,01010,00111,而接受端仍将码元排成发送时方阵形式，然后按行进行奇偶校验,水平奇偶监督码。,.,实例,信息码元,监督码元（偶）,1,1,1,0,0,1,0,0,1,1,0,1,0,0,1,0,1,0,0,0,0,1,1,1,0,0,0,1,0,0,0,1,1,1,0,0,1,1,1,1,.,特点,：,发送端是,按列发送码元,，而不是按码组（行）发送码元，因此可把本来可能集中发生在一码组中的突发错误分散到方阵中的各个码组，同时又作为整个方阵的行监督；,可以发现某一行上所有奇数个错误及长度不大于方阵行数的突发错误。,.,3.3.2 方阵校验码,又称,行列监督码,，,矩阵码,，纵向冗余校验码（,LRC,，Lognitudinal Redundancy Check），它的码元受到行和列两个方向奇偶监督，又称,二维奇偶校验码,。,编码规则,：,使的每个码元受到,纵向（列）和横向,两次监督；将欲发送的信息码按行排成一个矩阵，矩阵中每一行为一码组，每行的最后加上一个奇偶监督码元；矩阵中的每一列是由不同码组相同位置的码元组成，在每列最后也加上一个监督码元，进行奇偶校验；最后按,行或列,码组的顺序发送,。,.,XXXXXXXX,X,XXXXXXXXXXXX X X X,XXXXXXXX,X XXXXXXX,方阵校验码结构,.,实例,信息码元,监督码元（偶）,1,1,1,0,0,1,0,0,1,1,0,1,0,0,1,0,1,0,0,0,0,1,1,1,0,0,0,1,0,0,0,1,1,1,0,0,1,1,1,1,0,1,1,0,1,1,1,1,发送端,在,发送时则按列,(,或行）的顺序,传输：,11101,0,11001,1,10000,1,01010,0,00111,1,接收端,仍将码元排成发送时方阵形式，然后按行、列进行奇偶校验,.,特点：,可以检测出某行某列上的奇数个错误和长度不大于行（列）数的突发错误。,可以检测出,某行或某列,上偶数个错误,不能纠正差错数正好是4的倍数且位置在,行列矩阵/子矩阵,的4个顶点上的差错,方阵校验码,.,失效！,信息码元,监督码元（偶）,1,1,1,0,0,1,0,0,1,1,0,1,0,0,1,0,1,0,0,0,0,1,1,1,0,0,0,1,0,0,0,1,1,1,0,0,1,1,1,1,0,1,1,0,1,1,1,1,.,3.3.3 恒比码(定比码),编码规则：,恒比码中每码组中“1”和“0”个数保持恒定比例，接收端在检测接收到的码组中“1”的数目是否对就知道是否出错。,实例：,我国电传机传输汉字时使用数字代表汉字，采用的所谓“保护电码”就是一种“3：2”或“5中取3”的恒比码。C,5,2,=10个许用码组,英文电报采用“7中取3”或“4：3”恒比码，共有C,7,3,=35个许用码组,.,3.3.4 正反码_能简单纠错的编码,多用于10单位电码的前向自动纠错设备中，能,纠正一位差错，,发现大部分两位错，差错编码和差错控制结合起来控制。以10单位电码为例：,n=k+r 且 k=r=5,1.编码规则,：,(1)当信息码中“1”的个数为奇数时，监督码与信息码相同（正码）,10101,10101,(2)当信息码中“1”的个数为偶数时，监督码与信息码相反（反码）,10100,01011,.,2.解码方法,：,(1)将接收到信息码与监督码按相应的码位模2加（异或），得到一个新的5位码组。,(2)根据接收到的,信息码,中“1”的个数：,if“1”的个数为奇数，则取新5位码组为校验码组,if“1”的个数为偶数，则取新5位码组的反码为校验码组,正反码,.,正反码判决表,校验码组的组成,判决差错情况,1,全“0”,无错,2,4个“1”一个“0”,信息码中有一位出错，出错位置就是检验码组中0所对应的位置,3,4个“0”一个“1”,监督码中有一位出错，出错位置就是检验码组中1所对应的位置,4,其他,差错个数1个,（3,），最后可按下表，根据检验码组中“,1”,的个数进行判断及纠正可能发现的错码,.,实例：,已知信息码11010使用正反码差错控制方式，试问下列接收端收到的数据是否有错？能否纠正？,11010 11010,10010 11010,11010 01010,10000 11010,.,（1）编码：11010（信息码）11010（监督码）11010 11010（正反码）,（2）解码：,接收端11010 11010,接收端10010 11010,接收端11010 01010,接收端10000 11010,判断：,.,11010,+11010,00000,结果为0，正确。,.,10010,+11010,01000,由于接收信息码中为偶数个1，所以检验码取反，10111，信息码中有一位出错，根据判决2，出错位置就是检验码组中0所对应的位置，纠正后为1,1,010,.,11010,+01010,10000,由于接收信息码中为奇数个1，所以检验码不变，根据判决3，监督码码中有一位出错，出错位置就是检验码组中1所对应的位置，纠正后为,1,1010,.,10000,+01010,01010,检验码中1的个数1，根据判决4，无法判断和纠错,.,3.3.5 循环冗余校验编码（CRC）,Cyclic Redundancy checking(,CRC,)循环冗余校验，又称多项式码。,在循环冗余校验中，不是通过将各比特位相加来得到期望的校验，而是通过在数据单元末尾加一串冗余比特，称作,循环冗余校验码,或,循环冗余校验余数,，使得整个数据单元可以被另一个预定的二进制数所整除。,.,CRC,校验基本思想,CRC校验的基本思想是：,根据欲发送的,k,位信息位构成的报文，发送器生成一个,r,比特的序列，称为帧校验序列,FCS,（,Frame checking Series,），将r位FCS（即CRC码）附加到k位信息序列之后作为实际发送的数据帧（k+r位），,这个帧所对应二进制序列恰好能够被某个预先确定的数（生成多项式）整除。,接收器用相同的数去除传来的帧。如果无余数，则认为无差错；如果余数不为0，刚认为传输出错。,.,奇偶校验对一个字符校验一次，适合异步通讯；而CRC对一个数据块（frame）校验一次，适合同步通讯。在串行同步通信中，几乎都使用这种校验方法。如磁盘信息的读/写等。,CRC,校验常用场合,.,CRC码生成和校验基本分为三步,：,第一步：在数据单元(k位）的末尾加上r个0。r是一个比预定除数的比特位数(r十1)少1的数。,第二步：采用二进制除法将新的加长的数据单元（k+r位)除以,除数,。由此除法产生的,余数,就是循环冗余码校验码。,CRC,码的生成,.,第三步：用从第二步得到,的,r,个比特的,CRC,码替换数据单元末尾附加的,r,个0,。如果余数位数小于,r，,最左的缺省位数为,0。,如果除法过程根本未产生余数（也就是说，原始的数据单元本身就可以被除数整除）那么以,r,个0,作为,CRC,码替换余数所在的位置。产生的比特模式正好能被除数整除。,CRC,码的生成,.,CRC码校验,：,到达接收方的数据单元首先到达的是数据，然后是CRC校验码。接收方将整个数据串当作一个整体去除以用来产生循环冗余校验余数的同一个除数。,如果数据串无差错地到达接收方，循环冗余校验器将产生余数0。因此数据单元将通过检验。如果在传输中数据单元被改变，除法将产生非零余数，因此数据单元将通不过检验。,CRC,码的校验,.,循环冗余码生成器采用模2除法。下图显示了这一过程。,CRC校验器的功能完全像发生器一样，当收到附加了CRC码的数据后，做同样的模2 除法。如果余数是全0，则将CRC码丢弃，接受数据。否则，丢弃收到的数据。,CRC,码生成器和校验器,.,0,G(X),.,11101010001,1010,CRC校验码,信息码,CRC冗余校验码,.,CRC校验码的生成器和校验器,r个比特0数据,g(x),CRC校验码,r+1,r,余数,先发数据位,后发校验位,g(x),余数,r+1,r,数据,0接收，非0拒绝,数据,发送方,接收方,.,任何一个二进制数序列可以和一个只含有0和1两个系数的代数多项式建立起一一对应的关系。因此，用来求CRC码的那个除数通常用多项式来表示。原因如下：,代数多项式很短,可以通过多项式来进行概念的数学证明。,多项式,.,多项式,任何一个n位的二进制数都可以用一个n-1 次的多项式来表示,这种多项式叫,码多项式,（又叫信息多项式）,。,码多项式与二进制序列之间的一一对应关系：,（a,n-1,a,n-2,a,1,a,0,）,N,A,(x)=,a,n-1,X,n-1,+a,n-2,X,n-2,+a,1,X+a,0,X,0,码多项式,.,多项式 二进制序列实例,以n=3位二进制数为例,二进制数 对应多项式,000,001,010,011,100,101,111,0,1,x,x+1,x,2,x,2,+1,x,2,+x+1,1011011,x6+x4+x3+x+1,x5+x4+x2+x,110110,.,码多项式运算法则:,二进制码多项式的加减运算为模2加运算，即两个码多项式相加时，对应项系数进行模2加减。,乘除运算与普通多项式类似；,模2加减：即各位做不带进位、借位的按位加减。这种加减运算实际上就是逻辑上的异或运算。即加法和减法等价。,码多项式,.,生成多项式G(x):,求CRC码时所用的“除数”所对应的多项式叫,生成多项式,。,在串行通信中通常使用下列三种生成多项式G（X）来产生CRC码。,CRC-16：G(x)=X,16,+X,15,+X,2,+1，美国二进制同步系统中采用。,CRC-CCITT：G(x)=X,16,+X,12,+X,5,+1，CCITT推荐。,CRC-32：G(x)=X,32,+X,26,+X,23,+X,22,+X,16,+X,12,+X,11,+X,10,+X,8,+1X,7,+X,5,+X,4,+X,2,+X+1,码多项式,.,CRC,码性能,CRC码是很有效的差错校验方法。,除了正好数据块的比特值是按除数值变化的错误外，循环冗余校验(CRC)将检测出其他所有错误。而且，常用的CRC除数通常有13、17，或是33个比特，使得不可检测的错误可能降低到几乎近于零。,CRC接收电路再配上适当的硬件电路不仅可以检错，而且可以纠错，纠错能力很强特别适合检测突发性错误，在数据通信中得到较广泛的应用。,.,检错性能,能检测出全部单个错误,能检测出全部随机二位错误,能检测出全部奇数个错误,能检测出全部长度小于k位的突发错误,能以1-（1/2）,k-1,概率检测出长度为（k+1）位的突发性错误,.,3.3.6 卷积码,1.概述,2.编码器,3.解码器,.,1.概述,前面介绍的编码方法都是,线性分组码,，即监督码只负责监督检验本码组中的信息码元。,如果每组的监督码元不但与本组码的信息码元有关，而且还与前面若干组信息码元有关，即不是分组校验而是,每个监督码元对它的前后码元都实行监督，前后相连，具有连环监督的作用,；因此我们称为,连环码,，即,卷积码,。,卷积码由 P.Elias于1955年最先提出，整个编解码过程一环扣一环，连锁地进行下去。,.,2.编码器,a,i,a,i-1,a,2,a,1,a,0,R2,R1,信息入口,连环码输出,模2加法器,a,b,b,3,a,3,b,2,a,2,b,1,a,1,b,0,a,0,移位寄存器,移位寄存器,b,0,=,a,0,b,1,=,a,0,a,1,b,2,=,a,1,a,2,b,3,=,a,2,a,3,b,i,=,a,i-1,a,i,.,2.编码器,（1）编码器输出过程,第一次，前半拍开关接到a输出a0，后半拍开关倒向b输出b0=a00=a0,第二次，前半拍开关接到a输出a1，后半拍开关倒向b输出 b1=a1a0,第i次，前半拍开关接到a输出a,i,，后半拍开关倒向b输出b,i,=a,i,a,i-1,.,2.编码器,（2）连环码结构：,信息码:,a,n-1,a,n-2,a,i,a,1,a,0,连环码输出序列,b,n-1,a,n-1,b,i,a,i,b,2,a,2,b,1,a,1,b,0,a,0,监督码b,n-1,b,n-2,b,i,b,1,b,0,即“,信息码 监督码 信息码,”，一个信息码与一个校验码构成一组但每个校验码,b,i,=a,i,a,i-1,除了与本组码有关还与前一组信息码有关，故称为卷积码。,.,.,3.解码器,R1,R2,R3,&,a,b,接收到的监督码,计算出的监督码,判决电路,1,2,3,解码输出,解码输入,S,i,S,i-1,连环码入口,.,解码器,解码思路：,移位寄存器R1、R2及模2加法器1,构成与发送端一样的编码器，用来计算监督码和解码输出。,用,模2加法器2,将计算出的监督码与接收到的监督码进行比较，即先对a,i,编码产生新的监督码b,i,，再与b,i,异或 if结果为0 then正确 else出错。,根据第2步的输出进行判决，由判决电路完成,由判决结果通过,加法器3,输出结果,.,解码器,设接收的码序列,b,3,a,3,b,2,a,2,b,1,a,1,b,0,a,0,其解码过程为：,（1）,第零,拍,，,前半拍电子开关倒向a,移位寄存器R1移出a,0,R2移出0，故加法器1结果生成一个a,0,0=a,0,。,后半拍电子开关倒向b结果,接收到b,0,，生成,S,0,=b,0,（=a,0,）a,0,，R,3,为0故与门输出0,又R,2,输出为0，所以加法器3输出为0,.,解码器,（2）,第一,拍,前半拍电子开关倒向a，R1移出工,a,1,R2移出,a,0,加法器1输出,a,1,a,0,后半拍电子开关倒向b，加法器2输入,b,1,加法器2输出,S,1,=,b,1,（,a,1,a,0,）,在第一拍后半期当,b,1,出现在输入端时，就可对,a,0,做判断。,.,解码器,（3）,第二,拍,前半拍电子开关倒向a，R1移出工,a,2,R2移出,a,1,，加法器1输出,a,2,a,1,后半拍电子开关倒向b，加法器2输入,b,2,加法器2输出,S,2,=,b,2,（,a,2,a,1,）,在第二拍后半期当,b,2,出现在输入端时，就可对,a,1,做判断。,（4）依次类推，,当,b,3,出现在输入端时，就可对,a,2,做判断,规则如P69。,.,解码方程,模2加法器2的输出对我们判决正确性至关重要。,.,解码器,判决规则：,当S,i,及S,i+1,都为“0”时，a,i,正确,当S,i,及S,i+1,都为“1”时，必定是a,i,出错,当S,i,为“1”而 S,i1,为“0”时，必定是a,i-1,、b,i,中有一个出错，故判决a,i,无错,当S,i1,为“1”时，而 S,i,为“0”时，必定是a,i+1,、b,i+1,中有一个出错，故判决a,i,无错,.,寄存器：,是能够寄存一组二进制信息的逻辑部件。,由D型触发器组成的4位寄存器,补充：寄存器,.,触发器,能寄存一位二进制信息的单元电路称为,触发器,。触发器有两个输出端：,“1”端和“0”端,（见下页图）。,两个输出端的极性总是相反,（,“1”端为高电平，“0”端就为低电平；“1”端为低电平，“0”端就为高电平）,触发器有两种稳定状态,。一种是：“1”端为高电平，“0”端为低电平，另一种是：“1”端为低电平，“0”端为高电平。约定触发器为前一种状态时处于“1”状态，存的信息是“1”；为后一种状态时触发器处于“0”状态，存的信息是“0”。,没有外界作用，触发器状态保持不变，即所存的信息不变。,在一定的外界作用下，触发器能从一种状态变到另一种状态并保持住,。,.,触发器的输出端,D型触发器,.,D触发器,在SET端（置“1”端）加一负脉冲，触发器变为“1”状态。在CLR端（置“0”端）加一负脉冲，触发器变为“0”状态。平常，SET端和CLR端为高电平。,CP端为接收脉冲（或称打入脉冲）输入端。,当CP端没有接收脉冲时，即一直处于固定的电位时，触发器的状态保持不变。在CP端加一接收脉冲，在脉冲的上升沿（由低变高）时，,如果此刻代码输入端D为0，则触发器变为0，如果D为1，则触发器变为1。,也就是说，,接收的信息,（或说成打入到触发器中的信息）,取决于接收脉冲的,上升沿,时刻代码输入端的状态,。接收脉冲过后D型触发器的状态保持不变。,.,由D触发器构成4位移位寄存器,.,