新聞中心

EEPW首頁(yè) > 嵌入式系統(tǒng) > 設(shè)計(jì)應(yīng)用 > CCITT CRC-16計(jì)算原理與實(shí)現(xiàn)

CCITT CRC-16計(jì)算原理與實(shí)現(xiàn)

作者: 時(shí)間:2011-08-28 來(lái)源:網(wǎng)絡(luò) 收藏

CRC的全稱(chēng)為Cyclic Redundancy Check,中文名稱(chēng)為循環(huán)冗余校驗(yàn)。它是一類(lèi)重要的線(xiàn)性分組碼,編碼和解碼方法簡(jiǎn)單,檢錯(cuò)和糾錯(cuò)能力強(qiáng),在通信領(lǐng)域廣泛地用于差錯(cuò)控制。實(shí)際上,除 數(shù)據(jù)通信外,CRC在其它很多領(lǐng)域也是大有用武之地的。例如我們讀軟盤(pán)上的文件,以及解壓一個(gè)ZIP文件時(shí),偶爾會(huì)碰到“Bad CRC”錯(cuò)誤,由此它在數(shù)據(jù)存儲(chǔ)方面的應(yīng)用可略見(jiàn)一斑。

本文引用地址:http://butianyuan.cn/article/150280.htm

差錯(cuò)控制理論是在代數(shù)理論基礎(chǔ)上建立起來(lái)的。這里我們著眼于介紹CRC的算法與,對(duì)只能捎帶說(shuō)明一下。若需要進(jìn)一步了解線(xiàn)性碼、分組碼、循環(huán)碼、糾錯(cuò)編碼等方面的,可以閱讀有關(guān)資料。

利用CRC進(jìn)行檢錯(cuò)的過(guò)程可簡(jiǎn)單描述為:在發(fā)送端根據(jù)要傳送的k位二進(jìn)制碼序列,以一定的規(guī)則產(chǎn)生一個(gè)校驗(yàn)用的r位監(jiān)督 碼(CRC碼),附在原始信息后邊,構(gòu)成一個(gè)新的二進(jìn)制碼序列數(shù)共k+r位,然后發(fā)送出去。在接收端,根據(jù)信息碼和CRC碼之間所遵循的規(guī)則進(jìn)行檢驗(yàn),以 確定傳送中是否出錯(cuò)。這個(gè)規(guī)則,在差錯(cuò)控制理論中稱(chēng)為“生成多項(xiàng)式”?!?/p>

1 代數(shù)學(xué)的一般性算法

在代數(shù)編碼理論中,將一個(gè)碼組表示為一個(gè)多項(xiàng)式,碼組中各碼元當(dāng)作多項(xiàng)式的系數(shù)。例如 1100101 表示為
1·x6+1·x5+0·x4+0·x3+1·x2+0·x+1,即 x6+x5+x2+1。

設(shè)編碼前的原始信息多項(xiàng)式為P(x),P(x)的最高冪次加1等于k;生成多項(xiàng)式為G(x),G(x)的最高冪次等于r;CRC多項(xiàng)式為R(x);編碼后的帶CRC的信息多項(xiàng)式為T(mén)(x)。

發(fā)送方編碼方法:將P(x)乘以xr(即對(duì)應(yīng)的二進(jìn)制碼序列左移r位),再除以G(x),所得余式即為R(x)。用公式表示為
T(x)=xrP(x)+R(x)

接收方解碼方法:將T(x)除以G(x),如果余數(shù)為0,則說(shuō)明傳輸中無(wú)錯(cuò)誤發(fā)生,否則說(shuō)明傳輸有誤。

舉例來(lái)說(shuō),設(shè)信息碼為1100,生成多項(xiàng)式為1011,即P(x)=x3+x2,G(x)=x3+x+1,CRC的過(guò)程為

xrP(x) x3(x3+x2) x6+x5 x
-------- = ---------- = -------- = (x3+x2+x) + --------
G(x) x3+x+1 x3+x+1 x3+x+1
即 R(x)=x。注意到G(x)最高冪次r=3,得出CRC為010。

如果用豎式除法,過(guò)程為

1110
-------
1011 /1100000 (1100左移3位)
1011
----
1110
1011
-----
1010
1011
-----
0010
0000
----
010
因此,T(x)=(x6+x5)+(x)=x6+x5+x, 即 1100000+010=1100010

如果傳輸無(wú)誤,

T(x) x6+x5+x
------ = --------- = x3+x2+x,
G(x) x3+x+1
無(wú)余式。回頭看一下上面的豎式除法,如果被除數(shù)是1100010,顯然在商第三個(gè)1時(shí),就能除盡。

上述推算過(guò)程,有助于我們理解CRC的概念。但直接編程來(lái)上面的算法,不僅繁瑣,效率也不高。實(shí)際上在工程中不會(huì)直接這樣去和驗(yàn)證CRC。

下表中列出了一些見(jiàn)于標(biāo)準(zhǔn)的CRC資料:

名稱(chēng)

生成多項(xiàng)式

簡(jiǎn)記式*

應(yīng)用舉例

CRC-4

x4+x+1

ITU G.704

CRC-12

x12+x11+x3+x+1

x16+x12+x2+1

1005

IBM SDLC

CRC-ITU**

x16+x12+x5+1

1021

ISO HDLC, ITU X.25, V.34/V.41/V.42, PPP-FCS

CRC-32

x32+x26+x23+...+x2+x+1

04C11DB7

ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCS

CRC-32c

x32+x28+x27+...+x8+x6+1

1EDC6F41

SCTP

* 生成多項(xiàng)式的最高冪次項(xiàng)系數(shù)是固定的1,故在簡(jiǎn)記式中,將最高的1統(tǒng)一去掉了,
如04C11DB7實(shí)際上是104C11DB7。

** 前稱(chēng)CRC-。ITU的前身是。

2.CRC算法的實(shí)現(xiàn)
---------------
要用程序?qū)崿F(xiàn)CRC算法,考慮對(duì)第2節(jié)的長(zhǎng)除法做一下變換,依然是M = 11100110,G = 1011,
其系數(shù)r為3。

11001100
------------------------
1011 )11100110000
1011.......
----.......
1010......
1011......
----......
1110...
1011...
------...
1010..
1011..
-------
100 ---校驗(yàn)碼



評(píng)論


相關(guān)推薦

技術(shù)專(zhuān)區(qū)

關(guān)閉