CRC（Cyclic Redundancy Check）循環(huán)冗余校驗(yàn)碼是數(shù)據(jù)通信領(lǐng)域中常用的一種差錯(cuò)校驗(yàn)碼，在早期的通信中運(yùn)用廣泛，因?yàn)樵缙诘?a href="http://www.brongaenegriffin.com/soft/data/43-44/" target="_blank">通信技術(shù)不夠可靠（不可靠性的是通信技術(shù)決定的，比如電磁波通信時(shí)受雷電等因素的影響），不可靠的通信就會(huì)帶來‘確認(rèn)信息’的困惑，書上提到紅軍和藍(lán)軍通信聯(lián)合進(jìn)攻山下的敵軍的例子，天紅軍發(fā)了條信息要藍(lán)軍第二天一起進(jìn)攻，藍(lán)軍收到之后，發(fā)一條確認(rèn)信息，但是藍(lán)軍擔(dān)心的是‘確認(rèn)信息’如果也不可靠而沒有成功到達(dá)紅軍那里，那自己不是很危險(xiǎn)？于是紅軍再發(fā)一條‘對確認(rèn)的確認(rèn)信息’，但同樣的問題還是不能解決，紅軍仍然不敢貿(mào)然行動(dòng)。對通信的可靠性檢查就需要‘校驗(yàn)’，校驗(yàn)是從數(shù)據(jù)本身進(jìn)行檢查，它依靠某種數(shù)學(xué)上約定的形式進(jìn)行檢查，校驗(yàn)的結(jié)果是可靠或不可靠，如果可靠就對數(shù)據(jù)進(jìn)行處理，如果不可靠，就丟棄重發(fā)或者進(jìn)行修復(fù)。其特征是信息字段和校驗(yàn)字段的長度可以任意選定。

為了完成信號(hào)傳輸過程中誤碼檢測，獲得正確無誤的傳輸數(shù)據(jù)，LTE（Long Term Evolution）系統(tǒng)針對不同的數(shù)據(jù)傳輸采用了多種格式的循環(huán)冗余碼，以適應(yīng)系統(tǒng)高速率高性能的需求。

LTE系統(tǒng)中的循環(huán)冗余碼

LTE作為準(zhǔn)4G技術(shù)，以正交頻分復(fù)用OFDM（Orthogonal Frequency Division Multiplexing）和多輸入多輸出MIMO（Multiple-Input Multiple-Out-put）技術(shù)為基礎(chǔ)，下行采用正交頻分（OFDM）多址技術(shù)，上行采用單載波頻分（SC-FDMA）多址技術(shù)，在20 MHz頻譜帶寬下能夠提供下行100 Mb/s與上行50 Mb/s的峰值速率。

LTE TDD（亦稱TD-LTE）系統(tǒng)采用了4種格式［2］的CRC：CRC24A、CRC24B、CRC16、CRC8。其生成多項(xiàng)式如下：

其中長度為24的CRC24A和CRC24B主要用于共享信道數(shù)據(jù)傳輸［3］，長度為16的CRC16主要用于下行控制信道和廣播信道數(shù)據(jù)傳輸，長度為8的CRC8主要用于CQI（Control quality information）信息的傳輸。

循環(huán)冗余校驗(yàn)碼（CRC）的基本原理

循環(huán)冗余校驗(yàn)碼（CRC）的基本原理是：在K位信息碼后再拼接R位的校驗(yàn)碼，整個(gè)編碼長度為N位，因此，這種編碼又叫（N，K）碼。對于一個(gè)給定的（N，K）碼，可以證明存在一個(gè)次冪為N-K=R的多項(xiàng)式G（x）。根據(jù)G（x）可以生成K位信息的校驗(yàn)碼，而G（x）叫做這個(gè)CRC碼的生成多項(xiàng)式。

校驗(yàn)碼的具體生成過程為：假設(shè)發(fā)送信息用信息多項(xiàng)式C（X）表示，將C（x）左移R位，則可表示成C（x）*2R，這樣C（x）的右邊就會(huì)空出R位，這就是校驗(yàn)碼的位置。通過C（x）*2R除以生成多項(xiàng)式G（x）得到的余數(shù)就是校驗(yàn)碼。

CRC算法分析及選擇

CRC的校驗(yàn)原理非常簡單，它要求發(fā)送方和接收方采用同一個(gè)生成多項(xiàng)式g（x），且g（x）的首位和末位的系數(shù)必須為l。編碼時(shí)將待發(fā)送的數(shù)據(jù)t（x）除以g（x），得到的余數(shù)作為CRC校驗(yàn)碼添加到t（x）的后面；譯碼時(shí)將接收到的數(shù)據(jù)r（x）除以g（x），如果余數(shù)為0，則說明校驗(yàn)正確，否則校驗(yàn)失敗，從而判斷數(shù)據(jù)幀是否出錯(cuò)。在工程應(yīng)用中，常用的CRC校驗(yàn)算法主要有兩種：查表生成法和塊異或長除法。

這種算法的優(yōu)點(diǎn)是運(yùn)算量小、速度快、效率高；缺點(diǎn)是可移植性較差，且要事先計(jì)算出余式表，而不同長度的生成多項(xiàng)式的余式表不同，因此余式表會(huì)占用系統(tǒng)較大的存儲(chǔ)空間，增大系統(tǒng)資源開銷。

1.塊異或長除法

塊異或長除法是依據(jù)CRC校驗(yàn)碼的產(chǎn)生原理實(shí)現(xiàn)的。算法描述如下：

（1）初始化，將寄存器初始化為0。

（2）在信息比特后添加CRC長度個(gè)0，終作為CRC添加的空間。

（3）讀取一個(gè)數(shù)據(jù)塊（塊的大小由處理器的字的單位長度決定）。

（4）判斷塊的位是否為‘1’，若為‘1’則數(shù)據(jù)塊與生成多項(xiàng)式做異或操作。

（5）將數(shù)據(jù)左移一位，如果當(dāng)前塊的剩余比特等于CRC生成多項(xiàng)式的長度，則轉(zhuǎn)入步驟（3）；否則轉(zhuǎn)入步驟（4）。

（6）如果所有數(shù)據(jù)都已經(jīng)操作完畢，則計(jì)算結(jié)束，寄存器中的值為終求得的CRC。

這種算法的優(yōu)點(diǎn)是算法簡單、容易實(shí)現(xiàn)、修改靈活、可移植性好，對任意長度的生成多項(xiàng)式都適用；但因?yàn)樗荒芴幚硪晃粩?shù)據(jù)，因此計(jì)算效率低，運(yùn)算量大。

如前所述，在TD-LTE系統(tǒng)中采用了4種格式的CRC，如果采用查表算法，則需要建立4張查找表，會(huì)占用系統(tǒng)較大的存儲(chǔ)空間，且程序移植性差；如果采用塊異或長除法，則又會(huì)出現(xiàn)計(jì)算效率低，運(yùn)算量大的問題。

綜上分析，結(jié)合項(xiàng)目需求及系統(tǒng)硬件配置，考慮到系統(tǒng)所采用的高效DSP處理器——TMS320C64x（主頻可達(dá)到1.2 GHz）可以彌補(bǔ)塊異或長除法的低效性，系統(tǒng)終采用塊異或長除法來實(shí)現(xiàn)。

CRC編碼規(guī)則

CRC碼是由兩部分組成，前部分是信息碼，就是需要校驗(yàn)的信息，后部分是校驗(yàn)碼，如果CRC碼共長n個(gè)bit，信息碼長k個(gè)bit，就稱為（n，k）碼。 它的編碼規(guī)則是：

1.移位

將原信息碼（kbit）左移r位（k+r=n）

2.相除

運(yùn)用一個(gè)生成多項(xiàng)式g（x）（也可看成二進(jìn)制數(shù)）用模2除上面的式子，得到的余數(shù)就是校驗(yàn)碼。

非常簡單，要說明的：模2除就是在除的過程中用模2加，模2加實(shí)際上就是我們熟悉的異或運(yùn)算，就是加法不考慮進(jìn)位，公式是：

0+0=1+1=0，1+0=0+1=1

即‘異’則真，‘非異’則假。

由此得到定理：a+b+b=a 也就是‘模2減’和‘模2加’直值表完全相同。

有了加減法就可以用來定義模2除法，于是就可以用生成多項(xiàng)式g（x）生成CRC校驗(yàn)碼。

生成多項(xiàng)式應(yīng)滿足以下原則

a、生成多項(xiàng)式的位和位必須為1。

b、當(dāng)被傳送信息（CRC碼）任何一位發(fā)生錯(cuò)誤時(shí)，被生成多項(xiàng)式做模2除后應(yīng)該使余數(shù)不為0。

c、不同位發(fā)生錯(cuò)誤時(shí)，應(yīng)該使余數(shù)不同。

d、對余數(shù)繼續(xù)做模2除，應(yīng)使余數(shù)循環(huán)。

例子

例如：

g（x）=x4+x3+x2+1，（7，3）碼，信息碼110產(chǎn)生的CRC碼就是：

對于g（x）=x4+x3+x2+1的解釋：（都是從右往左數(shù)）x4就是第五位是1，因?yàn)闆]有x1所以第2位就是0。

11101 | 110，0000（設(shè)a=11101 ，b=1100000）

取b的前5位11000跟a異或得到101

101加上b沒有取到的00得到10100

然后跟a異或得到01001

也就是余數(shù)1001

余數(shù)是1001，所以CRC碼是1001， 傳輸碼為：110，1001

標(biāo)準(zhǔn)的CRC碼是，CRC-CCITT和CRC-16，它們的生成多項(xiàng)式是：

CRC-CCITT=x^16+x^12+x^5+1 　　CRC-16=x^16+x^15+x^2+1

CRC算法的DSP實(shí)現(xiàn)

1.硬件簡介

TMS320C6000系列DSP是TI公司1997年2月推向市場的高性能DSP，綜合了目前DSP性價(jià)比高、功耗低等優(yōu)點(diǎn)。TMS320C64x系列在TMS320C6000 DSP芯片中處于水平，它不但提高了時(shí)鐘頻率，而且在體系結(jié)構(gòu)上采用了VelociTI甚長指令集VLIW（Very Long Instruction Word）結(jié)構(gòu)［5］，片內(nèi)有8個(gè)獨(dú)立功能單元的內(nèi)核，每個(gè)周期可以并行執(zhí)行8條32 bit指令，峰值速度4 800 MIPS，2組共64個(gè)32 bit 通用寄存器，32 bit 尋址范圍，支持8/16/32/40位的數(shù)據(jù)訪問，片內(nèi)集成大容量SRAM，可達(dá)8 Mbit。由于其出色的運(yùn)算能力、高效的指令集、大范圍的尋址能力，使其特別適用于無線基站、測試儀表等對運(yùn)算能力和存儲(chǔ)量有高要求的應(yīng)用場合。

2. CRC校驗(yàn)的DSP實(shí)現(xiàn)

因?yàn)橄到y(tǒng)采用了4種格式的CRC，如果對每種格式進(jìn)行單獨(dú)實(shí)現(xiàn)，不僅任務(wù)繁瑣，而且增加了系統(tǒng)的代碼量，更給代碼測試和維護(hù)增加了難度。因此本實(shí)現(xiàn)采用統(tǒng)一實(shí)現(xiàn)，即同一個(gè)程序，支持系統(tǒng)中的所有CRC格式，僅需在程序頭部增添一點(diǎn)格式判斷的代碼即可。

雖然TMS320C64x DSP處理器的字長為32 bit，但是為了兼容4種格式的CRC，終決定數(shù)據(jù)的分塊長度為半字，即16 bit，這樣做的目的就是為了支持CRC24，因?yàn)門MS320C64x DSP的寄存器在用作邏輯移位寄存器使用時(shí)，其有效長度為40 bit。

根據(jù)LTE協(xié)議，輸入數(shù)據(jù)按大端模式輸入。為了處理方便，每次讀入半字都將其倒序，采用低端對齊的方式進(jìn)行CRC除法，因此，CRC多項(xiàng)式也必須經(jīng)過倒序。生成的CRC也是倒序的，需要再次倒序，然后進(jìn)行加擾［2］（如果必要的話），添加到輸入數(shù)據(jù)后面。倒序可使用指令“BITR”，簡單易行。

輸出數(shù)據(jù)仍為大端模式。由前面所述可知：CRC8的生成多項(xiàng)式倒序值為0x1b3；CRC16的生成多項(xiàng)式倒序值為0x10811；CRC24A的生成多項(xiàng)式倒序值為0x1be64c3；CRC24B的生成多項(xiàng)式倒序值為0x18c0003。

值得注意的是：輸入數(shù)據(jù)后面應(yīng)該多寫入一個(gè)字的0，因?yàn)槊看稳“胱痔幚恚?dāng)剩余比特為15 bit且CRC為長24 bit時(shí)，組合起來也不會(huì)超過40 bit，避免特殊性的出現(xiàn)，以便統(tǒng)一處理。同時(shí)完成CRC計(jì)算過后，可以直接將CRC添加到原數(shù)據(jù)之后，而不擔(dān)心其會(huì)覆蓋系統(tǒng)中的其他數(shù)據(jù)，引起不必要的錯(cuò)誤。

圖1為CRC計(jì)算及添加的程序?qū)崿F(xiàn)流程。當(dāng)CRC格式為CRC16、CRC24A、CRC24B時(shí)，讀取的個(gè)數(shù)據(jù)塊（半字）在次內(nèi)循環(huán)中將只作16次的移位，而沒有異或操作，表面上看在這里應(yīng)該加一個(gè)判斷，如果是這種情況則直接將數(shù)據(jù)右移16 bit，然后接著處理第二個(gè)數(shù)據(jù)塊。但這樣會(huì)對后續(xù)的數(shù)據(jù)塊造成麻煩，因?yàn)槊總€(gè)數(shù)據(jù)塊到達(dá)此處都需判斷，當(dāng)數(shù)據(jù)量比較大時(shí)，會(huì)帶來更大的開銷，因此在程序流程中可以忽略此問題。

在接收端，CRC的校驗(yàn)與發(fā)送端的計(jì)算基本相同，只是由于LTE系統(tǒng)的特殊性，如果在發(fā)送端CRC曾被加擾過，則在接收端校驗(yàn)之前，應(yīng)先從接收到的數(shù)據(jù)末尾截取出CRC進(jìn)行解擾，然后再將解擾后的CRC添加回去，對整個(gè)接收數(shù)據(jù)進(jìn)行CRC校驗(yàn)。如果CRC校驗(yàn)正確，則接收數(shù)據(jù)正確；否則接收數(shù)據(jù)錯(cuò)誤，在此程序流程不再贅述。

性能分析

在DSP軟件實(shí)現(xiàn)中，通過指令并行，盡量優(yōu)化程序循環(huán)體［6］，減少或消除程序中的“NOP”指令。對于不同格式的CRC，根據(jù)它們所用的環(huán)境以及數(shù)據(jù)的大致長度，通過程序仿真運(yùn)行，可以得到統(tǒng)計(jì)結(jié)果如表1。

表1的數(shù)據(jù)長度僅為個(gè)別舉例，但不失一般性。從表中可以看出，雖然塊異或長除法的運(yùn)算量較大，但是當(dāng)運(yùn)用TMS320C64x芯片實(shí)現(xiàn)時(shí)，由于處理器的超高主頻，其計(jì)算速率也非?？?，完全可以忽略它的計(jì)算量。因此，本實(shí)現(xiàn)采用塊異或長除法不僅簡化了程序?qū)崿F(xiàn)方法，還減少了模塊程序代碼，節(jié)約了系統(tǒng)存儲(chǔ)空間。

關(guān)于LTF

LTE（Long Term Evolution，長期演進(jìn)）項(xiàng)目是3G的演進(jìn)，始于2004年3GPP的多倫多會(huì)議。LTE并非人們普遍誤解的4G技術(shù)，而是3G與4G技術(shù)之間的一個(gè)過渡，是3.9G的標(biāo)準(zhǔn)，它改進(jìn)并增強(qiáng)了3G的空中接入技術(shù)，采用OFDM和MIMO作為其無線網(wǎng)絡(luò)演進(jìn)的標(biāo)準(zhǔn)。在20MHz頻譜帶寬下能夠提供下行326Mbit/s與上行86Mbit/s的峰值速率。改善了小區(qū)邊緣用戶的性能，提高小區(qū)容量和降低系統(tǒng)延遲。

結(jié)束語

本文從理論分析出發(fā)，根據(jù)TD-LTE系統(tǒng)特性，選擇了一種的CRC校驗(yàn)算法，并在TMS320C64x芯片上加以實(shí)現(xiàn)，詳細(xì)講述了塊異或長除法在DSP中的實(shí)現(xiàn)方法。程序運(yùn)行結(jié)果表明，本實(shí)現(xiàn)能夠滿足LTE系統(tǒng)的需要，具有可行性和高效性。