[2021年最新整理]循环冗余校验码(CRC)的基本原理(精品文档).docx

《[2021年最新整理]循环冗余校验码(CRC)的基本原理(精品文档).docx》由会员分享，可在线阅读，更多相关《[2021年最新整理]循环冗余校验码(CRC)的基本原理(精品文档).docx（9页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、精品word 可编辑资料 - - - - - - - - - - - - -循环冗余校验码（CRC ）的基本原理循环冗余校验码 （ CRC ）的基本原理是：在K 位信息码后再拼接R 位的校验码，整个编码长度为N 位，因此，这种编码又叫（N，K） 码；对于一个给定的（N，K）码，可以证明存在一个最高次幂为N-K=R的多项式G(x) ；依据 G(x) 可以生成K 位信息的校验码，而G(x) 叫做这个 CRC 码的生成多项式；校验码的详细生成过程为：假设发送信息用信息多项式f(X) 表示，将 f(x)左移 R 位（就可表示成 f(x)*X R ），这样 f(x) 的右边就会空出 R 位，这就是校验码

2、的位置；通过 f(x)* X R 除以生成多项式 G(x) 得到的余数就是校验码；几个基本概念1、多项式与二进制数码多项式和二进制数有直接对应关系：x的最高幂次对应二进制数的最高位，以下各位对应多项式的各幂次，有此幂次项对应1，无此幂次项对应0；可以看出： x 的最高幂次为R，转换成对应的二进制数有 R+1 位；多项式包括生成多项式G(x) 和信息多项式f(x)；如 生 成 多 项 式 为G(x)=X 4+X 3+X+1 ，可 转 换 为 二 进 制 数 码11011 ；而发送信息位1111 ，可转换为数据多项式为f(x)=X 3+X 2+X+1 ；第 1 页，共 9 页 - - - - -

3、- - - - -精品word 可编辑资料 - - - - - - - - - - - - -2、生成多项式是接受方和发送方的一个商定，也就是一个二进制数，在整个传输过程中，这个数始终保持不变；在发送方 ,利用生成多项式对信息多项式做模2 除生成校验码 ；在接受方利用生成多项式对收到的编码多项式做模2除检测和确定错误位置；应满意以下条件：a、生成多项式的最高位和最低位必需为1；b、当被传送信息（CRC 码）任何一位发生错误时，被生成多项式做模 2 除后应当使余数不为0；c、不同位发生错误时，应当使余数不同；d、对余数连续做模2 除，应使余数循环；将这些要求反映为数学关系是比较复杂的；但可以从有

4、关资料查到常用的对应于不同码制的生成多项式如图9 所示：NK码距 dG(x) 多项式G(x) 743x3+x+11011743x3 +x2+11101734x4 +x3+x2+1734x4+x2 +x+11110110111第 2 页，共 9 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -15113x4 +x+1100111575x8+x 7+x 6+x4 +111101000131263x5+x 2+110010131215x10 +x 9+x8+x 6+x5+x 3+11110110100163573x6 +x+110

5、0001163515x12 +x 10 +x5+x 4+x 2+1101000011010110411024x16 +x15 +x2 +111000000000000101图 9常用的生成多项式3、模 2 除（按位除）模 2 除做法与算术除法类似，但每一位除（减）的结果不影响其它位，即不向上一位借位；所以实际上就是异或；然后再移位做下一位的模 2 减；步骤如下：a、用除数对被除数最高几位做模2 减，没有借位；b、除数右移一位，如余数最高位为1，商为 1，并对余数做模2减；如余数最高位为0，商为0，除数连续右移一位； c、始终做到余数的位数小于除数时，该余数就是最终余数；第 3 页，共 9 页

6、- - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -【例】 1111000除 以 1101 ：1011 商1111000- 被除数1101 除数1000110110101101111 余数4、CRC 码的生成步骤（1）将 x 的最高幂次为R 的生成多项式G(x) 转换成对应的R+1位二进制数；（2）将信息码左移R 位得到多项式f(x)*X R；第 4 页，共 9 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -（3）用生成多项式（二进制数）对f(x)*X R 做模

7、 2 除，得到余数（即校验码）；（4）将余数多项式加到f(x)*X R 中，得到完整的CRC 码 ；【例】假设使用的生成多项式是G(x)=x 3+x+1 ；4位的原始报文为 1010 ，求编码后的报文；解：（1）将生成多项式G(x)=x 3 +x+1 转换成对应的二进制除数1011；（2）此题生成多项式有4 位（R+1 ），要把原始报文F(x)左移 3（ R）位变成1010000（3）用生成多项式对应的二进制数对左移4位后的原始报文进行模 2 除：1001- 商- 10100001011- 除数-10001011-第 5 页，共 9 页 - - - - - - - - - -精品word 可编

8、辑资料 - - - - - - - - - - - - -11- 余数（校验位）（ 4）编码后的报文（CRC 码 ）：1010000+11- 1010011CRC 码为 1010011 （和纠错）；在接收端收到了CRC 码后用生成多项式为G(x) 去做模2 除，如得到余数为0，就码字无误；如得到余数不为0，就接收的数据有错；5、通信与网络中常用的CRC在数据通信与网络中，通常k 相当大，由一千甚至数千数据位构成一帧，而后采纳CRC 码 产生r 位的校验位；它只能检测出错误，而不能订正错误；一般取r=16 ，标准的16 位生成多项式有CRC-16 x16 +x15 +x2 +1和CRC-CCIT

9、T x16 +x 15 +x2+1 ；【例 1】某循环冗余码（ CRC ）的生成多项式 G(x) x3+x2+1 ， 用此生成多项式产生的冗余位，加在信息位后形成 CRC 码；如发送信息位 1111 和 1100 就它的 CRC 码分别为 A和 B；由于某种缘由，使接收端收到了按某种规律可判定为出错的CRC 码，例如码字 C、 D、和 E；（ 1998 年试题 11 ）第 6 页，共 9 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -供挑选的答案A ： 1111100111110111111101111111B ： 110

10、0100110010111001101100111C E ： 00000000001100001011100110101011000100011010011111010001解：A： G(x) 1101 ， f(x) 1111 ， f(x)*x 3G(x) 11110001101 1011 余 111得到的 CRC 码为 1111111B： G(x) 1101 ， f(x) 1100 ， f(x)*x 3G(x) 11000001101 1001 余 101得到的 CRC 码为 1100101 C E：分别用 G(x) 1101 对作模 2 除:00000001101余 00011111011

11、101余 001第 7 页，共 9 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -00101111101余 00000110101101余 00010001101101余 00010011111101余 10010100011101余 00010110001101余 100所以 C、 D和 E的答案是、【例 2】运算机中常用的一种检错码是 CRC ，即 _A_ 码；在进行 编 码 过 程 中 要 使 用 _B_ 运 算 ； 假 设 使 用 的 生 成 多 项 式 是G(X)=X 4 +X3+X+1 ， 原始报文为 1100

12、1010101 ，就编码后的报文为_C_；CRC 码_D_的说法是正确的；供挑选的答案：A：水平垂直奇偶校验循环求和循环冗余正比率B：模 2 除法定点二进制除法二十进制除法循环移位法C：1100101010111110010101010011110010101011100110010101010101D：可订正一位差错可检测全部偶数位错可检测全部小于校验位长度的突发错可检测全部小于、等于校验位长度的突发错第 8 页，共 9 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -解：从前面有关CRC 的论述中可得出：A：循环冗余B：模 2 除 法C ： G(x) 11011 ， f(x) 11001010101， F(x)*24G(x) 11001010101000011011余 0011得 到 的 CRC 码为110010101010011D：从前面有关通信与网络中常用的CRC 的论述中可得出 ：可检测全部小于、等于校验位长度的突发错第 9 页，共 9 页 - - - - - - - - - -