CRC编码

项目1-2无线电传输技术鄢立抗衰落与多径干扰消除技术01多项式运算规则02循环冗余纠错码Contents目录03小结01Part多项式运算规则鄢立概述循环冗余校验码（CyclicRedundancyCheck），简称CRC码，是数据通信领域中最常用的一种差错校验码，具有数据传输检错功能。特点：信息字段和校验字段的长度可以任意选定。方法：对数据进行多项式计算，并将得到的结果附在帧的后面，接收设备也执行类似的算法，保证数据传输的正确性和完整性。多项式编码规则码多项式和二进制数对应关系：X的最高幂次对应二进制数的最高位，以下各位对应多项式的各幂次，有此幂次项对应1，无此幂次项对应0。可以看出：X的最高幂次为R，转换成对应的二进制数有R+1位。【例】5位二进制数字序列110101×24＋1×23＋0×22＋1×21＋0×20→11010多项式编码规则通常在编码中，以x表示系数只取0、1的多项式的基，则５位二进制序列11010可表示为1*x4＋1*x3＋0*x2＋1*x1＋0*x0=x4＋x3+x任意一个由二进制位串组成的代码都可以和一个系数仅为‘0’和‘1’取值的多项式一一对应。【例如】：代码1010111对应的多项式为：x6+x4+x2+x+1，而多项式为x5+x3+x2+x+1对应的代码：101111。多项式编码规则编码格式：长度为n的码可以用x的n-1次多项式表示。（以长度为3的二进制序列为例）长度为3的二进制序列对应的多项式00000101001110010111011101xx+1x2x2+1x2+xx2+x+1多项式运算规则模2加•两个多项式模2加时，同幂项应消掉。【例】已知：M(x)=x9+x5+x2+1N(x)=x8+x5+x3+1M(x)⊕N(x)=x9+x8+(x5+x5)+x3+x2+(1+1)=x9+x8+x3+x2乘法：与通常的算术运算相同，但遇到同幂项时应消掉【例：】已知F(x)=x2+x+1G(x)=x5+x4+x2+1F(x)×G(x)=(x2+x+1)(x5+x4+x2+1)=x2(x5+x4+x2+1)+x(x5+x4+x2+1)+(x5+x4+x2+1)=x7+x6+x4+x2+x6+x5+x3+x+x5+x4+x2+1=x7+x3+x+1多项式运算规则多项式运算规则除法【例】H(x)÷G(x)=(x14+x10+x7+x5)÷(x5+x4+x2+1)02PartCRC码基本原理鄢立CRC循环码循环码是一种系统码，通常前k位为信息码元，后r位为监督码元在K位信息码后拼接R位的校验码，整个编码长度为N位，因此，这种编码也叫（N，K）码。CRC循环码CRC的特点具有循环性，即当循环码中的任一码组循环移动一位以后，所得码组仍为该循环码的一个准用码组。CRC循环码--生成多项式G(x)对于一个给定的（N，K）码，可以证明存在一个最高次幂为N-K=R的多项式G(x)。根据G(x)可以生成K位信息的校验码，G(x)叫做这个CRC码的生成多项式。校验码的具体生成过程为：假设要发送的信息用多项式M(X)表示，将M(x)左移R位（可表示成M(x)*xR），这样M(x)的右边就会空出R位，这就是校验码的位置。用M(x)*xR除以生成多项式G(x)得到的余数就是校验码。校验码位数CRC校验码位数=生成多项式位数-1。注意有些生成多项式的简记式中将生成多项式的最高位1省略CRC循环码--生成多项式G(x)应用接受方和发送方的一个约定，是一个二进制数，在整个传输过程中，这个数始终保持不变。在发送方，利用生成多项式对信息多项式做模2除生成校验码。在接收方利用生成多项式对收到的编码多项式做模2除检测和确定错误位置。CRC循环码--生成多项式G(x)生成多项式G（x）应满足以下条件：生成多项式的最高位和最低位必须为1。当被传送信息（CRC码）任何一位发生错误时，被生成多项式做除后应该使余数不为0。不同位发生错误时，应该使余数不同。对余数继续做除，应使余数循环。CRC循环码生成原理发送端CRC编码的主要过程：a）将要传送的二进制序列看作是一个多项式M（x）的系数；b）用一个选取的多项式G（x）去除各数据位，得到Q（x）和余数R（x）；c）把余数R（x）用作检验位挂接在欲传递的M（x）之后，新形成的二进制序列U（x）即是传输给信道的实际二进制序列。注：G（x）——生成多项式，最高、最低项的系数必须为“1”。。【例】假设使用的生成多项式是G(X)=X3+X+1。4位的原始报文为1010，求编码后的报文。解：将生成多项式G(X)=X3+X+1转换成对应的二进制除数1011。此题生成多项式有4位（最高次幂值R+1）【备注：此处R=3】CRC循环码生成原理将信息码左移R位，相当于对应的信息多项式C(X)*2R。【注意】：根据CRC校验码位数=生成多项式位数-14位的生成多项式计算所得的校验码为3位，R为校验码位数，要把原始报文M(X)左移3（R）位变成1010000用生成多项式（二进制数1011）对信息码（1010000）做除，得到R位的余数将余数拼到信息码左移后空出的位置，得到完整的CRC码。本例题得到的余位011，所以最终编码为：1010011CRC循环码生成原理【小结】若设码字长度为N，信息字段为K位，校验字段为R位(N=K+R)，则对于CRC码集中的任一码字，存在且仅存在一个R次多项式g(x)，使得M(x)=U(x)g(x)其中:U(x)为K次原始的信息多项式g(x)称为生成多项式：发送方通过指定的g(x)产生CRC码字，接收方则通过该g(x)来验证收到的CRC码字。CRC循环码生成原理【例2】设欲传送的二进制数据序列M(x)为：1101011011；选取的生成多项式G(x)为：10011；【编码】设G(x)的阶r=4，将r个“0”附在M(x)的低端：11010110110000；令M(x)/G(x)得余数R(x)：1110将余数R(x)挂接在M(x)之后得到实际传送的二进制数据序列U(x)：11010110111110CRC循环码检错原理设接收端收到带有误码的二进制数据序列U(x)+E(x)，用G(x)相除时有：[U(x)+E(x)]/G(x)=U(x)/G(x)+E(x)/G(x)因为：U(x)/G(x)=0所以：[U(x)+E(x)]/G(x)=E(x)/G(x)E(x)/G(x)应该有余数，否则检不出错来。CRC循环码检错原理【解码】接收端U(x)/G(x)：余数为“0”，说明信道传输中无误码，否则有错。将U(x)去掉末尾的r个数据，即得到原来欲传输的M(x)。CRC循环码检错原理【练习】设发送的数据为1101011011，若收到的数据为1001001011，将两信号异或（模2加）则得到E(x)=0100010000E(x)/G(x)=010001000/10011必然有余数，所以可判定1001001011里面含有误码。结论：有r位校验位的多项式码将能检测所有≦r位的突发性误码，故只要k-1﹤r，就能检测出所有突发性误码CRC实现电路模型03Part小结及作业鄢立作业假设信息码字为(1011001)，即信息多项式和生成多项式求CRC校验码。如果例子中的发送码字(10110011010)经传输后受噪声的干扰，在接收端变成为(10110011100)。求差错图样，643()1mxxxx43()1gxxx谢谢观赏thankyou2.15