LTE系統(tǒng)的CRC校驗(yàn)算法研究及DSP實(shí)現(xiàn)*

羅友寶，李小文，谷向陽(yáng)

（重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065）

LTE系統(tǒng)的CRC校驗(yàn)算法研究及DSP實(shí)現(xiàn)*

羅友寶，李小文，谷向陽(yáng)

（重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065）

通過(guò)對(duì)兩種常用CRC校驗(yàn)算法的研究分析，為T(mén)D-LTE測(cè)試儀表系統(tǒng)選擇了一種最優(yōu)的CRC校驗(yàn)算法，并在TMS320C64xDSP中實(shí)現(xiàn)。將CRC校驗(yàn)程序在CCS3.3中運(yùn)行，其結(jié)果驗(yàn)證了算法的可行性、高效性。

長(zhǎng)期演進(jìn)；循環(huán)冗余校驗(yàn)；查表法；塊異或長(zhǎng)除法；DSP實(shí)現(xiàn)

循環(huán)冗余校驗(yàn)碼[1]CRC（Cyclic Redundancy Check）是數(shù)據(jù)通信領(lǐng)域中最常用的一種差錯(cuò)校驗(yàn)碼，其特征是信息字段和校驗(yàn)字段的長(zhǎng)度可以任意選定。

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

1 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)式如下：

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

2 CRC算法分析及選擇

CRC的校驗(yàn)原理非常簡(jiǎ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，則說(shuō)明校驗(yàn)正確，否則校驗(yàn)失敗，從而判斷數(shù)據(jù)幀是否出錯(cuò)。在工程應(yīng)用中，常用的CRC校驗(yàn)算法主要有兩種：查表生成法和塊異或長(zhǎng)除法。

2.1 查表生成法

查表算法的思路是先離線計(jì)算數(shù)據(jù)信息的所有余式，把它們置于一個(gè)稱為“余式表”的表格中，供隨時(shí)讀取和調(diào)用[4]。算法描述如下：

（1）離線計(jì)算出數(shù)據(jù)的CRC余式表。

（2）初始化 CRC碼為：RnH=RnL=0。

（3）讀取信息的當(dāng)前字節(jié)M，計(jì)算I=M+RnH，用I作為索引查表得出rnH和rnL。

（4）計(jì)算新的 CRC校驗(yàn)碼：RnH=RnL+rnH；RnL=rnL。

（5）如果信息沒(méi)有處理完畢，則轉(zhuǎn)入步驟（3）；否則CRC計(jì)算完成，結(jié)果為RnH和RnL。

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

2.2 塊異或長(zhǎng)除法

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

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

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

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

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

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

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

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

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

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

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

3.1 硬件簡(jiǎn)介

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

3

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

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

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

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

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

值得注意的是：輸入數(shù)據(jù)后面應(yīng)該多寫(xiě)入一個(gè)字的0，因?yàn)槊看稳“胱痔幚?，?dāng)剩余比特為最大15 bit且CRC為最長(zhǎng) 24 bit時(shí)，組合起來(lái)也不會(huì)超過(guò) 40 bit，避免特殊性的出現(xiàn)，以便統(tǒng)一處理。同時(shí)完成CRC計(jì)算過(guò)后，可以直接將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次的移位，而沒(méi)有異或操作，表面上看在這里應(yīng)該加一個(gè)判斷，如果是這種情況則直接將數(shù)據(jù)右移 16 bit，然后接著處理第二個(gè)數(shù)據(jù)塊。但這樣會(huì)對(duì)后續(xù)的數(shù)據(jù)塊造成麻煩，因?yàn)槊總€(gè)數(shù)據(jù)塊到達(dá)此處都需判斷一次，當(dāng)數(shù)據(jù)量比較大時(shí)，會(huì)帶來(lái)更大的開(kāi)銷(xiāo)，因此在程序流程中可以忽略此問(wèn)題。

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

4 性能分析

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

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

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

表1 統(tǒng)計(jì)結(jié)果

[1]王新梅.糾錯(cuò)碼原理與方法[M].西安：西安電子科技大學(xué)出版社，2003.

[2]3GPP TS 36.212 v8.7.0：Multiplexing and channel coding. （Release 8）[S].2009-05.

[3]Qualcomm Europe.Generator polynomial for transport block CRC[EB/OL].Http：//www.3gpp.org,2007.10.

[4]張莉麗，張振權(quán)，劉仁.CRC查表生成算法匯編的實(shí)現(xiàn)及其優(yōu)化[J].計(jì)算機(jī)應(yīng)用，2005（4）.

[5]Texas Instruments Incorporated.TMS320C64x/C64x+DSP CPU and Instruction Set Reference Guide[EB/OL].Http：//www. ti.com.cn,2008.

[6]Texas Instruments Incorporated.TMS320C6000系列 DSP編程工具與指南[M].田黎育，何佩琨，朱夢(mèng)宇，譯.北京：清華大學(xué)出版社，2006：32-50.

Research and DSP realization of CRC algorithm in LTE system

LUO You Bao，LI Xiao Wen，GU Xiang Yang
（School of Communication and Information Engineering,Chongqing University of Posts and Telecommunications, Chongqing 400065，China）

：Based on the LTE（long term evolution）CRC（cyclic redundancy check）codes,this paper researched two algorithms which were used very common.It choosed the most suitable CRC algorithm for the TD-LTE test system,and realized the algorithm in the TMS320C64x DSP.The running results of the CRC check program in CCS3.3 verify that the selected algorithm is feasible and effective.

long term evolution；CRC；look-up-table；block-xor long division；DSP Realization

TN929.5

A

0258-7998（2010）09-0071-03

*國(guó)家科技重大專項(xiàng)項(xiàng)目“TD-LTE無(wú)線綜合測(cè)試儀表開(kāi)發(fā)”（No.2009ZX03002-009）

2010-04-22）

羅友寶，男，1985年生，在讀碩士研究生，主要研究方向：TD-LTE系統(tǒng)物理層算法及 DSP軟件開(kāi)發(fā)。

李小文，男，1955年生，碩士生導(dǎo)師，教授，研究員，主要研究方向：TD-SCDMA移動(dòng)通信系統(tǒng)開(kāi)發(fā)及TD-LTE系統(tǒng)開(kāi)發(fā)。

谷向陽(yáng)，男，1985年生，在讀碩士研究生，主要研究方向：TD-LTE協(xié)議棧MAC層協(xié)議研究。