说明
一、CRC介绍
循环冗馀校验(Cyclic Redundancy Check,CRC )是一种基于网络数据包和计算机文件等数据生成短固定位数校验码的散列函数,主要用于检测数据传输和存储后可能出现的错误利用除法和馀数的原理检测错误。
在数据传输期间,不管传输系统的设计多么完美,错误总是存在,并且这样的错误导致链路上传输的一个或多个帧被破坏(出现比特错误,0等于1,1等于0 ),从而导致接收方错误的数据为了尽可能提高接收方接收数据的准确性,接收方必须在接收数据之前对数据进行错误检测,并且只有在检测结果正确时接收方才真正接收数据。 检查的方式有很多种,常见的有奇偶校验、网络校验和循环冗馀校验等。
二、CRC硬件计算流程
1 .设置CRC寄存器,分配ffff(HEX )。
2 .将数据的前8位字符与16位CRC寄存器的后8位进行异或,并将结果存储在CRC寄存器中。
3 .将CRC寄存器右移1位,MSB补零,移动LSB进行检查。
4 .如果LSB为0,则重复步骤3如果LSB为1,则CRC寄存器是否与多项式代码不同。
注:在此步骤中,验证LSB是否为向右移动之前的LSB,即步骤3之前的LSB。
5 .重复步骤3和4,直到所有8次班次都完成。 此时,一个8位数据的处理完成。
6 .重复步骤2到5,直到处理完所有数据。 7 .最终CRC寄存器的内容是CRC值。
三.循环冗馀校验码(CRC )的基本原理
如果在k位的信息代码之后连接r位的校验码,则由于整体的代码长度为n位,所以将该代码也称为“n,k”代码。 对于给定的(n,k )码,可以证明存在N-K=R的最高次幂的多项式g ) x )。 可以从g(x )生成k位信息的校验码,g(x )称为此CRC码的生成多项式。
关于校验码的具体生成过程,假设发送信息由信息多项式c(x )表示,如果将c ) x )向左偏移r比特,则能够表示为c ) x ) 2r,由此在c ) x )的右边空出r比特成为校验码的位置c(x ) 2r除以生成多项式g ) x所得的馀数为校验码。
原理思维导图总结:
四.通信和网络中常用的CRC
在数据通信和网络中,通常k相当大,以1,000至几千个数据比特组成一帧,之后使用CRC码生成r比特的奇偶校验比特。 它只能检测错误,不能纠正错误。 一般取r=16,标准的16位生成多项式为CRC-16=x16 x15 x2 1和CRC-CCITT=x16 x15 x2 1。
一般而言,由r比特生成多项式生成的CRC码能够检测所有双重错误、奇数位错和突发长度为r以下的突发错误、以及(1-2-r () r-1 ) )的突发长度大于r 1的突发错误例如,如果上述r=16,则可以检测所有突发长度为16以下的突发错误、99.997%的突发长度为17的突发错误、99.998%的突发长度大于17的突发错误。 所以CRC码的检错能力还是很强的。 这里,突发错误是几乎连续发生的一系列错误,突发长度是从错误的第一位到最后一位的长度(但是,在中途并不是所有位都错了)。
【例1】将使用某个循环冗馀码(CRC )的生成多项式g ) x )=x3 x2 1 )生成多项式的冗馀比特与信息比特相加,形成CRC码。 在发送信息比特1111和1100的情况下,其CRC码分别为_A_和_B_。 出于某些原因,接收端接收能够被以某种规律判断为错误的CRC码,例如码字_C_、_D_、_E_。 (1998年问题11 )。
选择答案:
a )lll l00111101111101111111
b :1100100110010111001101100111
(c ) e )000000000011000010111) 1000110100111) 10100011011000
解:
a:g(x )=1101,c ) x )=1101 ) x ) 23g ) x )=11110001101=1011余111
得到的CRC码为1111111
b:g(x )=1101,c (x )=1101 (x ) ) g ) x )=11000001101=1001余101
得到的CRC代码为1100101
c至e :
分别除以g(x )=1101比~作型2 ) 00000001101余000 11111011101余001
00101111101余000 00110101101余000 10001101101余000
10011111101余100 10100011101余000 10110001101余100
因此_C_、_D_、_E_的答案为、、
【例2】计算机常用的错误检测码之一是CRC,即_A_码。 编码中请使用_B_运算。 使用的生成多项式为g(x )
)=X4+X3+X+1, 原始报文为11001010101,则编码后的报文为 _C_ 。CRC码 _D_ 的说法是正确的。在无线电通信中常采用它规定码字长为7位.并且其中总有且仅有3个“1”。这种码的编码效率为_E_。
供选择的答案:
A:① 水平垂直奇偶校验 ② 循环求和 ③ 循环冗余 ④正比率
B:① 模2除法 ②定点二进制除法 ③二-十进制除法 ④循环移位法
C:① 1100101010111 ② 110010101010011 ③ 110010101011100 ④ 110010101010101
D:① 可纠正一位差错 ②可检测所有偶数位错
③ 可检测所有小于校验位长度的突发错 ④可检测所有小于、等于校验位长度的突发错
E:① 3/7 ② 4/7 ③ log23/log27 ④ (log235)/7
解:从前面有关CRC的论述中可得出: A:③ 循环冗余 B:① 模2除法
C:G(x)=11011,C(x)=11001010101,C(x)*24÷G(x)=110010101010000÷11011 余0011
得到的CRC码为② 110010101010011
D:从前面有关通信与网络中常用的CRC的论述中可得出:④ 可检测所有小于、等于校验位长度的突发错
E:定比码又叫定重码,是奇偶校验的推广。在定比码中,奇数或偶数的性质保持不变,然而附加一种限制,每个字中1的总数是固定的。随用途之不同,定比码要求的附加校验位可能多于一个,但较之单一的奇偶校验将增加更多的检错能力。
所谓7中取3定比码,就是整个码字长度为7位,其中1的位数固定为3。所有128个7位代码(0000000~1111111)中只有1的位数固定为3的才是其合法码字。可以用求组合的公式求出其合法码字数为:C73=7!/(3!*(7-3)!)=7*6*5/(1*2*3)=35
编码效率=合法码字所需位数/码字总位数=(log235)/7
而对于CRC的实现有两种方式,分别为多项式和查表法。
打开APP阅读更多精彩内容
点击阅读全文