CRC校验原理及推导过程
- 格式：docx
- 大小：158.76 KB
- 文档页数：10
1.1 伽罗华域 (2 )
在伽罗华域 (2 )中的元素由 (2)上的本原多项式构造，域中的元素两两运算之后
例如当 = 4,本原多项式为： ( ) = + + 1， (2 )中的元素集合 CRC 校验原理及推导过程
1 代数引论
参考文献[1]对伽罗华域、线性码、循环码、缩短循环码进行了很好的论述。
的结果依然是该域中的元素，域中运算是基于模 2 的。
4 4
{0,1, , 2, 3,⋯, 14}，转换为十六进制数依次对应为{0,1,2,4,8,3,6, , ,5, ,7, , , ,9}，转换为
多项式依次对应为 {0,1, , 2, 3, + 1, 2 + , 3 + 2, 3 + + 1, 2 + 1, 3 + , 2 + + 1, 3 + 2 + , 3 + 。
于是： 15 = ∙ 14 = ∙ (1 + 3) = + 4 = + 1 + = 1 7 + 5 = ( 2 + ) + ( 3 + + 1) = 3 + 2 + 1 = 13
1.2 模运算法则
模运算与基本四则运算有些相似，但是除法例外。其规则如下
(a+b) % p = (a % p + b % p) % p （1-1）
(a-b) % p = (a % p - b % p) % p （1-2）
(a × b) % p = ((a % p) × (b % p))% p （1-3）
ab % p = ((a % p)b) %p （1-4）
结合率：
((a+b) % p+c) % p = (a+(b+c) % p) % p （1-5）
((a × b) % p × c)% p = (a × (b × c) % p) % p （1-6）
交换率：
(a+b) % p = (b+a) % p （1-7）
(a × b) % p = (b × a) % p （1-8）
分配率：
((a +b)% p × c) % p = ((a × c) % p + (b × c) % p) % p （1-9） 一个长度为 ，有2 个码字的分组码，当且仅当其2 个码字构成 (2)域上 1.3 线性分组码和循环码
所有 维向量组成的向量空间的一个 维子空间是被称为( , )线性码。
线性码的码字由 位消息部分和( ‒ )位冗余校验部分组成。
循环码事线性分组码的一个重要的子类，其有两个引入注目的原因：一是
通过带反馈连接的移位寄存器（一般称为线性时序电路），其编码和校正计算
能够很容易的实现；二是由于其具有固有的代数机构，都能找到很多种实用的
方法进行译码。
一个( , ) 线性码 C，如果每个码字的循环移位后的数仍是 C 的码字，则成
为其为循环码。
给定一个( , )循环码的生成多项式
g(x) = ‒ ‒ + ‒ ‒ 1
‒
‒ 1 + ⋯ 1 + 1，假设待编码的消息为
u = ( ‒ 1, ‒ 2,⋯ 1,u0)，则相应的消息多项式为：
u( ) = ‒ 1 ‒ 1 + ‒ 2 ‒ 2 + ⋯ + 1 + u0 （1-10）
用 ‒ 乘以u( )，得到次数不大于( ‒ 1)的多项式为： ‒ u( ) = ‒ 1 ‒ 1 + ‒ 2 ‒ 2 + ⋯ + 1 ‒ ‒ 1 + u0 ‒
11）
用生成多项式g(x)除 ‒ u( )得到： （1-
‒ u( ) = ( ) ( ) + v( ) （1-12）
其中， ( )和v( )分别为商式和余式。由于g(x)的最高次数为( ‒ )，则
( )的次数必不大于( ‒ - 1)。从而有 ( ) = ‒ ‒ 1 ‒ ‒ 1 + ⋯ + 1 + 0
整理得到次数不大于( ‒ 1)的多项式：
‒ u( ) + ( ) （1-13）
= ( ) ( ) = ‒ 1 ‒ 1 + ‒ 2 ‒ 2 + ⋯ + 1 ‒ ‒ 1 + u0 ‒
+ ‒ ‒ 1 ‒ ‒ 1 + ⋯ + 1 + 0 （1-14）
该多项式能被多项式g(x)整除。
相应的完整码字为：( ‒ 1, ‒ 2,⋯ 1,u0, ‒ ‒ 1,⋯ 1, )
（1- 15）
1.4 缩短的循环码
在系统设计中，如不能找到一个具有合适的自然长度的或者信息位数目的 码字，缩短码是一种有效的解决方案。
对一个( , ) 循环码 ，其中信息位的高 位均为零的码字共有2 ‒ 个，构成
了 的线性子码。若从这些码字中删除这 个零信息位，将得到2 ‒ 个长度为
n ‒ 的向量，这些向量组成了 ( ‒ , ‒ ) 线性码。这种码被称为缩短循环码，
但不是循环码。缩短循环码的纠错能力与差错检测能力至少与原码相同。
1.5 冗余码
所用符号数或信号码元数比表示信息所必需的数目多的代码叫冗余码。
1.6 循环冗余检验
循环冗余检验英文名称为 Cyclical Redundancy Check，简称 CRC。它是利
用多项式除法及余数的原理来做错误检测的。它将要发送的数据比特序列当作
一个信息多项式u( )的系数，发送时去除以约定的生成多项式g(x)，得到一个
余数多项式v( )，将余数多项式加到信息多项式之后发送到接收端，接收端同
样用g(x)去除接收到的接收多项式r( )，进行计算，然后把计算结果与由生成
多项式g(x)决定的固定序列比较，来检测传输错误。由此可以看出其同时具有
循环码和冗余码的特征，所以这种错误检测方法叫循环冗余校验，编码叫循环
冗余校验码，即如式 1-15 所示。
理论上可以证明循环冗余校验码的检错能力有以下特点：
(1)可检测出所有奇数位错。
(2)可检测出所有双比特的错。
(3)可检测出所有小于、等于校验位长度的突发错。
2 CRC 码编码
在 1.3 节《线性分组码和循环码》中得到算式 1-15 的计算过程就是循环冗
余校验码的编码步骤，归纳起来有以下三步骤：
第 1 步 预先用 ‒ 乘以信息多项式u( )，得到 ‒ u( )；
第 2 步 用生成多项式g(x)去除 ‒ u( )，获得余式v( )；
第 3 步 整合余式v( )和 ‒ u( )，获得码多项式 ‒ u( ) + ( )。
对于一个( , )循环码，生成多项式
g(x) =
‒ + ‒ ‒ 1
‒
‒ 1 + ⋯ + 1 1 + 1，编码电路有两种方式：
一，信息位由高位到低位的顺序从循环移位寄存器体左侧依次输入，信息
位完全进入循环体后继续输入n ‒ ‒ 1个 0，最后循环体中寄存器的值就是余式
码字；0
0
以 CRC4 为例，其生成多项式为：g(x) = + + 1，当信息多项式
g0 g1 gnk1
Din + D + D1 + + Dnk1
图 1 左侧串行输入循环移位寄存器体
二，信息位由高位到低位的顺序从循环移位寄存器体右侧依次输入，信息
位完全进入循环体后寄存器的值就是余式码字。
g0 g1 gnk1
D + D1 + + Dnk1 +
Din
图 2 右侧串行输入循环移位寄存器体
注：1，移位寄存器循环体中余式码字低位在左侧，高位在右侧。
4
u = (101011)时用两种方法计算得到得余式码字是一样的： = (0100)，编码
后完整地码字为：(1010110100)。图三所示的两种计算余式码字的方法对应于
数字电路中 D 触发器、加法器、乘法器的组成的循环体结构分别为图 1、图 2
所示。 10011
1010110000
其中 = u( ), 方法一 方法二
0
10
1
101 0
1010 1
10101 10011
0110 1
01101 0
11010
10011
01001 0
10010
10011
0001
0 10011 10000
10011
0011 00000 00110 10000
11100 10011
01111 00000
11110
10011
01101 10000
01010 10000
0100 1
0
1
0
1
1
00010 0 0100
图 3 信息位为单比特两种方法比较
3 CRC 码校验
3.1 CRC 码校验的基本原理
所有的 CRC 校验都是基于以下这个等式：
( + ) = 0 (3-1)
u( ) = ‒ ‒ 1
‒ ‒ 1
+ ⋯ + 1 + u0,
= ‒ ,
