二差错检测1差错检测的基本原理

二.差错检测1.差错检测的基本原理•纠错编码的检错、纠错原理差错控制的根本措施：采用抗干扰编码(即纠错编码)。码组：由n个码元(0,1)构成的每一组合。信息码：代表报文的0和1；监督码：插入的“0”和“1”A：0B：1即没有检错也纠错能力。假设要传送的消息为A和B二.差错检测1.差错检测的基本原理•纠错编码的检错、纠错原理信息码：代表消息的0和1；监督码：插入的“0”和“1”；A：00B：11具有了检出一位错码的能力；没有纠错能力。准用码组：{00，11}禁用码组：{01，10}二.差错检测1.差错检测的基本原理•纠错编码的检错、纠错原理信息码：代表信息的0和1;监督码：插入的“00”和“11”;A：000B：111具有检出两位及两位以下错码的能力；具有纠正一位错码的能力；准用码组＝{000，111}禁用码组＝{001,010,100,011,101,110}二.差错检测1.差错检测的基本原理•纠错编码的检错、纠错能力一般来说，监督码引入越多，检错纠错能力越强，但信道的传输效率下降也越快。(000)与(010)的码距为1(000)与(110)的码距为2(000)与(111)的码距为3码距：指两个码组对应码位码元不同的个数。汉明距离：在一个码组的集合中，任意两个码组间的最小码距。二.差错检测1.差错检测的基本原理•编码关系式为了检出e个错码，同时能纠正t个错码，则应满足为了检出e个错码，要求码集的汉明距离d≥e+1为纠正t个错码，要求码集的汉明距离d≥2t+1d≥e+t+1(et)二.差错检测1.差错检测的基本原理•例1ife=2,t=1,thend≥e+t+1=40001，0010，0100，10001110，1011，1101，01110011，0101，0110，1001，1010，1100肯定能检2位错肯定能纠1位错能检2个错码能纠1个错码A：0000B：1111d=4二.差错检测2.奇偶校验编码•编码规则先将所要传送的数据码元分组。在各组的数据后面附加一位校验位，使得该组码连校验位在内的码字中：“1”的个数为偶数—偶校验“1”的个数为奇数—奇校验垂直奇偶校验、水平奇偶校验、垂直水平奇偶校验、斜奇偶校验检错能力逐渐加强能检出码字中任意奇数个错误；随机错误十分有效;二.差错检测2.奇偶校验编码•垂直奇偶校验发送端在k位表示字符的信息位上，附加一个第k+1位的校验位；接收端根据收到的k位重新产生校验位，并与第k+1位作比较。如相同则无错，否则存在错误。设b1b2…bm-1是同一码组内的数据码元，bm为校验位偶校验：b1b2….bm-1bm=0bm=b1b2….bm-1奇校验：b1b2….bm-1bm=1bm=b1b2….bm-11二.差错检测2.奇偶校验编码b10101010101b20011000100b30000111100b41011000011b50110111111b60000110111b7111100100001001011101011010001字符位偶奇b8HQZK45T789编码效率：R=k/(k+1)k为码元的位数能发现奇数个差错无法发现偶数个差错二.差错检测2.奇偶校验编码•水平奇偶校验在传送数据时，常将若干个字符组成一组信息。当对一组内的各字符的同一位进行奇偶校验时，就称为～。可检测出组内各字符同一位上的奇数个错可检测出突发长度≤字符长度的所有突发错误编码效率：R=m/(m+1)m为参与校验的字符数b10101010101b20011000100b30000111100b41011000011b50110111111b60000110111b71111001000字符位偶奇10100110011010HQZK45T789二.差错检测2.奇偶校验编码•示例二.差错检测2.奇偶校验编码•垂直水平奇偶校验可检出3位或3位以下的全部错误可检出所有的奇数个错可检出大部分偶数个错可检出长度＜k+1的突发错误把垂直和水平两个方向的奇偶校验结合起来使用。编码效率：mk/[(m+1)(k+1)]k为码元的位数m为参与校验的字符数b10101010101b20011000100b30000111100b41011000011b50110111111b60000110111b7111100100001001011101011010001字符位偶奇b8110101110水平HQZK45T789二.差错检测2.奇偶校验编码二.差错检测3.循环冗余校验码(CRC，CyclicRedundancycheck)将要传送的信息分成码组M，然后按某一种约定的规律对每一个信息码组附加一些校验的码元R，形成新的码组C，使得C中的码元之间具有一定的相关性(即码组中“1”和“0”的出现彼此相关)，再传输到接收端；接收端根据这种相关性或规律性来校验码组C是否正确，还可对出错码组的错定位加以相应的纠正，最后将码组C还原成信息码组M。二.差错检测3.循环冗余校验码(CRC，CyclicRedundancycheck)•线性分组码与循环码分组码：码组内的码元之间的相关性只局限在本码组内线性分组码：码组结构规则或规律性可用线性方程来描述循环码：具有循环移位特性的线性分组码奇偶校验码循环码移位特性封闭性码集中任何码字向左/右移位得到的是码集中的另一个码子。码集中任何两个码子相加后仍然是该码集中的一个码子。二.差错检测3.循环冗余校验码(CRC，CyclicRedundancycheck)•码多项式及其算术运算假设循环码C=Cn-1Cn-2….C2C1C0长度为n例1：C=1100101C(x)=1x6+1x5+0x4+0x3+1x2+0x+1=x6+x5+x2+1码多项式的算术运算：模2加、模2减、模2乘、模2除C的码多项式（称为n-1次多项式）C(x)=Cn-1xn-1+Cn-2xn-2+….C2x2+C1x+C0二.差错检测3.循环冗余校验码(CRC，CyclicRedundancycheck)模2加，减，乘，除举例………在模2运算的基础上，xn+1总能够被x+1整除。奇数个项的多项式不能够被x+1整除。xj(xi-j+1)不能被g(x)整除的充分必要条件是。xi-j+1不能够被g(x)整除。二.差错检测3.循环冗余校验码(CRC，CyclicRedundancycheck)•循环码的编码对于一个码长为n，信息码元为k位的循环码(n，k),其构成形式为：12knk+1k+2n位每个码多项式的前面k项与待编码的信息多项式相同后面的r=n-k项与校验码元序列对应的校验多项式相同信息码元k位校验码元r位二.差错检测3.循环冗余校验码(CRC，CyclicRedundancycheck)m(x)=mk-1xk-1+mk-2xk-2+….+m1x+m0xn-k·m(x)+r(x)=q(x)·g(x)r(x)=rn-k-1xn-k-1+rn-k-2xn-k-2+….+r1x+r0g(x)是(n-k)次多项式q(x)是商式r(x)是余式且次数不高于n-k-1设要编码的k位信息元为：m=(mk-1,mk-2,….m1,m0)xn-k·m(x)=mk-1xn-1+mk-2xn-2+….+m1xn-k+1+m0xn-k=q(x)·g(x)+r(x)mk-1xn-1+mk-2xn-2+...+m1xn-k+1+m0xn-k+rn-k-1xn-k-1+rn-k-2xn-k-2+...+r1x+r0(mk-1,mk-2,….m1,m0,rn-k-1,rn-k-2,….,r1,r0)不加改变的k个信息位(n-k)个监督位二.差错检测3.循环冗余校验码(CRC，CyclicRedundancycheck)•校验码的产生C(x)=Cn-1xn-1+Cn-2xn-2+.+Cn-kxn-k+Cn-k-1xn-k-1+…C2x2+C1x+C0=Cn-1xn-1+Cn-2xn-2+…+Cn-kxn-k+Cr-1xr-1+Cr-2xr-2…C2x2+C1x+C0校验码信息码(1)设生成多项式g(x)的最高幂次为r=n-k(2)将待编码码元序列表示为m(x)，乘以xr，结果左移r位xr·m(x)(3)用g(x)去除xr·m(x)，求得商式q(x)和余式r(x)[xr·m(x)]/g(x)=q(x)+r(x)/g(x)xr·m(x)=q(x)·g(x)+r(x)xr·m(x)+r(x)=q(x)·g(x)校验多项式。其系数Cr-1，Cr-2，….C1，C0为校验码为除法运算后变成的循环多项式C(x)的表示式CRC-12=x12+x11+x3+x2+x+1CRC-16=x16+x15+x2+1CRC-CCITT=x16+x12+x5+1二.差错检测3.循环冗余校验码(CRC，CyclicRedundancycheck)•校验码的应用在接收端本来应该收到：c(x)=xr·m(x)+r(x)=q(x)·g(x)用协商好的生成多项式g(x)去除c(x),从余数来判断是否出错二.差错检测3.循环冗余校验码(CRC，CyclicRedundancycheck)•例2m(x)=x9+x8+x6+x4+x3+x+1,k=10(3)1101011011.000010011商数：1100001010余数：1110r(x)=x3+x2+x+0所需的循环编码C(x)为C(x)=xr·m(x)+r(x)=1101011011，1110设编码的信息码元为1101011011(1)假设g(x)=x4+x+1系数形成的位串为10011r=4——n=14r(x)的最高幂次为r-1=3(2)x4·m(x)=1101011011，0000二.差错检测3.循环冗余校验码(CRC，CyclicRedundancycheck)•多项式除法1101011011,0000100111001110011100111011010011101001001111101100001010商数被除数m(x)余数r(x)除数g(x)1101011011.000010011模2加=模2减模2乘模2除=乘的可逆运算二.差错检测3.循环冗余校验码(CRC，CyclicRedundancycheck)•循环码的检错能力假定在接收端实际收到c(x)+e(x)检查全部单个错（1位错）e(x)=xi检查全部离散的二位错（双错）e(x)=?检查全部的奇数个错（1，3，5，…个错）检查全部长度等于(n-k)或小于(n-k)的突发错e(x)=?以[1-2-(r-1)]的概率检查出长度为(r+1)的突发错以及以[1-2-r]的概率检查出多于(r+1)的突发错二.差错检测4.汉明纠错码•基本原理发送端计算监督位bm=b1b2….bm-1接收端计算S=b1b2….bm-1bm如果监督增加一位，变成2位，则增加一个监督关系式监督关系式校正子S=0：无错1：有错00011011表示1位错码的不同位置SS=表示无错一般地，r个监督关系式指示一位错码的(2r-1)种可能位置。2r–1n即2rk+r+1汉明不等式对(n,k)分组码，监督位数r=n-k；若希望用r个监督位构造出r个监督关系式用来指示一位错误的n种可能位置，则汉明码：码长为n=2r–1的线性分组码，即(2r–1,2r–1–r)码。二.差错检测4.汉明纠错码编码效率R=k/n=(n-r)/n=1-r/n二.差错检测4.汉明纠错码•描述(7，4)汉明码编码结构：m3m2m1m0r2r1r0mi为信息码元ri为监督码元假设：S1S2S3是三个监督关系式的校正子S1S2S3与错码位置的对应关系S1S2S3错码位置001r0010r1100r2011m0101m1110m2111m3000无错S1=m3m2m1r2S2=m3m2m0r1S3=m3m1m0r0四个码元构成偶数监督关系：二.差错检测4.汉明纠错码•发送端m3m2m1m0取决于输入信号；r2r1r0取决于m3m2m1m0的取值；从