海明码和CRC.doc

一、海明码校验法1.海明码 海明码是采用多位校验码的方式，在信息数据中合理加入校验位，将码距均匀拉大，校验中的每一位都对不同的信息数据位进行奇偶校验。 海明码是利用在信息位为K位，增加r位冗余位，构成一个n=k+r的码字，然后用r个监督关系式产生r 个校正因子来区分区无错和在码字中的n个不同位置的一位错，它必需满足关系式：2r=n+1或2r=k+r+11#10#1#1101#2.海明码的生成与接收方法一：1)海明码的生成。例1.已知：信息码为：0010 a2 a1 a0。海明码的监督关系式为：S2=a2+a4+a5+a6= 1= a2S1=a1+a3+a5+a6= 0= a1S0=a0+a3+a4+a6= 1= a0求：海明码码字。解：1)由监督关系式知冗余码为a2a1a0。2)冗余码与信息码合成的海明码是：0010a2a1a0。设S2=S1=S0=0,由监督关系式得：a2=a4+a5+a6=1a1=a3+a5+a6=0a0=a3+a4+a6=1因此，海明码码字为：00101012)海明码的接收。例2.已知：海明码的监督关系式为：S2=a2+a4+a5+a6S1=a1+a3+a5+a6S0=a0+a3+a4+a6接收码字为：0011101(n=7)求：发送端的信息码。解：1)由海明码的监督关系式计算得S2S1S0=011。2)由监督关系式可构造出下面错码位置关系表： S2S1S0000001010100011101110111错码位置无错a0a1a2a3a4a5a63)由S2S1S0=011查表得知错码位置是a3。4)纠错-对码字的a3位取反得正确码字：0 0 1 0 1 0 15)把冗余码a2a1a0删除得发送端的信息码：0010例3.若海明码的监督关系为：S0=a0+a3+a4+a6 ；S1=a1+a3+a5+a6 ；S2=a2+a4+a5+a6 。若需发送的信息为1101，则信道中传输的码字为 （ ） 。A1101001 B1101011 C1101010 D1101111 要正确的传输数据不出错，则在监督关系式中的S0，S1，S2的值就要为0，这样的话，将监督关系式化为：a0=a3+a4+a6 ；a1=a3+a5+a6 ；a2=a4+a5+a6。若要发送的信息为1101，则接受端的码字格式应该为：a6a5a4a3a2a1a0=1101XXX，这样就能求出a0，a1,a2的值（把a6，a5，a4，a3带入上面所化的关系式中）。这就是答案C了二、CRC校验法1、循环校验码（CRC码）：是数据通信领域中最常用的一种差错校验码，其特征是信息字段和校验字段的长度可以任意选定。2、生成CRC码的基本原理：任意一个由二进制位串组成的代码都可以和一个系数仅为0和1取值的多项式一一对应。例如：代码1010111对应的多项式为x6+x4+x2+x+1，而多项式为x5+x3+x2+x+1对应的代码101111。3、CRC码集选择的原则：若设码字长度为N，信息字段为K位，校验字段为R位(N=K+R)，则对于CRC码集中的任一码字，存在且仅存在一个R次多项式g(x)，使得V(x)=A(x)g(x)=xRm(x)+r(x);其中: m(x)为K次信息多项式， r(x)为R-1次校验多项式， g(x)称为生成多项式：g(x)=g0+g1x+ g2x2+.+g(R-1)x(R-1)+gRxR发送方通过指定的g(x)产生CRC码字，接收方则通过该g(x)来验证收到的CRC码字。 4、CRC校验码软件生成方法： 借助于多项式除法，其余数为校验字段。例如：信息字段代码为: 1011001；对应m(x)=x6+x4+x3+1 假设生成多项式为：g(x)=x4+x3+1；则对应g(x)的代码为: 11001 x4m(x)=x10+x8+x7+x4 对应的代码记为：10110010000；采用多项式除法: 得余数为: 1010 (即校验字段为：1010）发送方：发出的传输字段为: 1 0 1 1 0 0 1 1 0 10 信息字段 校验字段接收方：使用相同的生成码进行校验:接收到的字段/生成码（二进制除法） 如果能够除尽，则正确，例4.已知信息位为1100，生成多项式G(x) = x3+x+1，求CRC码。 M(x) = 1100 M(x)*x3 = 1100000 G(x)