0×0＝0； 0×1＝0； 1×0＝0； 1×1＝1
多位二进制模2乘法类似于普通意义上的多位二进制乘法，不同之处在于后者累加中间结果（或称部分积）时采用带进位的加法，而模2乘法对中间结果的处理方式采用的是模2加法。 ④模2除法运算定义为：
0÷1＝0 1÷1＝1
多位二进制模2除法也类似于普通意义上的多位二进制除法，但是在如何确定商的问题上两者采用不同的规则。后者按带借位的二进制减法，根据余数减除数够减与否确定商1还是商0，若够减则商1，否则商0。多位模2除法采用模2减法，不带借位的二进制减法，因此考虑余数够减除数与否是没有意义的。实际上，在CRC运算中，总能保证除数的首位为1，则模2除法运算的商是由余数首位与除数首位的模2除法运算结果确定。因为除数首位总是1，按照模2除法运算法则，那么余数首位是1就商1，是0就商0。
2.3 CRC分类
在线性分组码中,有一种重要的码称为循环码(cyclic code)。循环码是建立在严密的代数学理论基础上之上的。这种码的检（纠）错能力较强,而且编码和解码设备都不太复杂。循环码除了具有线性码的一般性质外，还具有循环性。循环性是指任一码组循环移位以后，仍是该码中的一个码组。作为数据传输中差错控制的基本方法之一,循环冗余校验（Cyclic Redundant Check）已被广泛用于通信应用中。目前CRC的应用分为非标准和标准两种，已被国际标准化组织规定的标准生成多项式为标准,用户自定义的生成多项式为非标准，这也是目前广泛使用的几种。
- 7 -
2.3.1 标准的CRC
在通信协议中常见并被广泛使用的标准列于表中。
表2－2 标准CRC多项式
名称 CRC－4 CRC－16 CRC－CCITT 多项式 简记 0x13 0x8005 0x1201 x4?x?1 x16?x15?x2?1 应用 ITU G.704 IBM SDLC ISO HDLC,ITUX.25,SDLC,V.34/V.41/V.42,PPP-FCS ZIP,RAR,IEEE802LAN/FDDI,IEEE 1394,PPP-FCS x16?x12?x5?1 x32?x26?x23?x22?x16?x12?x10?x?x?x?x?x?187542CRC－32 0x104C11DB7 CRC－32C x32?x28?x27?x26?x25?x23?x22?x20?x19?x?x?x?x?x?x?x?x?118141311109840x11EDC6F41 SCTP 2.3.2 非标准的CRC
非标准的CRC一般是为了某种用途而采用不同于标准的生成多项式，而实际的操作原理是相同的，主要用于需要CRC而需要低成本的应用，或者为了减轻设计算机处理负担而又能够保证数据可靠性的折中办法，此外，部分的加密算法也是采用CRC来生成。
2.4 循环码理论基础
循环码属于分组码也记为(n,k),可分为线性循环码和非线性循环码两种。循环码仍是线性分组码，但另有循环移位不变特性。
循环码的码字和多项式： 设循环码的任一个码字为：
an?1an?2?ai?a1a0
在二元情况下，ai只取1或0，为了完整描述一个码字，需要知道ai的取值及其在码字中的位置。用多项式来描述码字是很方便的，于是an?1an?2?ai?a1a0表示的码字用n?1次多项式来表示，即：
8
an?1an?2?ai?a1a0?an?1xn?1?an?2xn?2??ai??a1x?a0
上式表示一个n位长的码字可以用一个xn?1次多项式来表示。可见多项式仅
是码字的一个数学描述工具，但不是码字本身，但两者有一一对应的关系。
aa?ai?a1a0改写为：an?2an?3?ai?a1a0an?1 如果n?1n?2则表示码字中码元循环左移一位，其对应的多项式相对于乘x：
n?1n?2ix?ax?ax??ax??a1x?a0?n?2i?n?1??an?1xn?an?2xn?1??aixi?1??a1x2?a0x?an?2xn?1?an?3xn?2??aixi?1??a0x?an?1
上式中采用了模多项式运算，表明码字的左移，相对于多项式乘x(升幂)后
ni取x?1的模剩余。同理左移i位相对于乘x。两多项式间一个常用的运算是加法，
应为同幂次项系数相加，在二元的情况下应做模2加，例如：
C1?x??x4?x3?1则：
C2?x??x3?x2?x?1
C1?x??C2?x??x4?x3?1?x3?x2?x?1?x4?x2?x其中的一对x和1由于模2加消掉了，也可以认为做了减法。 多项式另一个常用的运算是除法，可排竖式长除法。
C1?x??x7?x2?x?1已知多项式：
3
C2?x??x3?x?1列竖式做：
- 9 -
x4?x2?x?1x3?x?1x7?x2?x?1x7?x5?x4x5?x4?x2?x?1x5?x3?x2x4?x3?x?1x4?x2?xx3?x2?1x3?x?1x2?x
2C1?x?CxC(x)x?x。2可见不能除尽，故有余式如果将余式加到被除式1??即：
C1*?x??C1?x??x2?x?x7?x2?x?1?x2?x?x7?1x?x?x?1x3?x?1x7?1x7?x5?x4x5?x4?1x5?x3?x2x4?x3?x2?1 x4?x2?xx3?x?1x3?x?1042
2.5循环码编码方法
nGx在编码时,首先要根据给定的(n,k)值选定生成多项式??,即从（x?1）的
Gx因子中选一个（n-k）次多项式作为??。
TxGx所有码多项式??都可以被??整除。根据这条原则，就可以对给定的信
?n?k?M?x?Mxx息位进行编码：设为信息码多项式，其次数小于k。用乘??，得
?n?k?M?x?x?n?k?M?x?RxRxG?x?x到的次数必定小于n。用除，得到余式??，??n?k?Rx的次数必定小于G?x?的次数，即小于?。将此余式??加于信息位之后作为
?n?k?M?x?R?x?x监督位，即将和相加，得到的多项式必定是一个码多项式。因为
10
它必定能够被
G?x?整除，且商的次数不大于?k?1?。
根据上述原理，编码步骤如下：
?1? 用x?n?k?乘M?x?。 ?2?用G?x?除x?n?k?M?x?，得到商
Q?x?和余式
R?x?，即
x?n?k?M?x?R?x??Q?x??G?x?G?x??3?编出的码组T?x?为
T?x??xn?kM?x??R(x)2.5.1 CRC产生操作过程
以下是一个8位的数据0x02产生一个16位的CRC的过程。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
8 0 0 F
表 2－3，8位数据0x02的16位CRC数据产生
在图中我们可以看到，这个0x02数据被扩充到24位（原数据8位＋16位CRC，不足的用零填充），然后再与0x8005（CRC－16生成多项式）做模2运算。在运算过程中，第17位总是被舍去（图中红色的位）。第16位如果是零，那么，只能与0x0000作异或运算，即数据左移一位。如果为1，那么就要与0x8005作模2（异或）运算。每次运算完毕，丢弃最高位，然后将数据下一位移入，再进行模2（异或）运算，直到所有的位移完为止。
2.6循环码解码方法
Tx接收端解码的要求有两个:检错和纠错。由于任意一个码组多项式??都应
GxRx该能被生成多项式??整除，所以在接收端可以讲接收的码组??用原生成多
- 11 -