RFID系統(tǒng)中的CRC算法的研究與設(shè)計(jì)

陳 燕，郭 鋒

(鄭州輕工業(yè)學(xué)院計(jì)算機(jī)與通信工程學(xué)院，河南鄭州450002)

射頻識(shí)別(Radio Frequency IDentification，RFID)技術(shù)是一種非接觸式的自動(dòng)識(shí)別技術(shù)，具有數(shù)據(jù)量大、保密性好、抗干擾能力強(qiáng)等優(yōu)點(diǎn)，被廣泛應(yīng)用于物流管理、高速公路的收費(fèi)、圖書(shū)館自助借閱系統(tǒng)、電子門(mén)票等領(lǐng)域［1－3］.RFID 系統(tǒng)中閱讀器的設(shè)計(jì)方案有多種，F(xiàn)PGA以其高集成度、高可靠性、設(shè)計(jì)周期短等優(yōu)點(diǎn)成為設(shè)計(jì)方案的一種.尤其在超高頻環(huán)境中，數(shù)據(jù)傳輸?shù)乃俾矢哌_(dá)幾十kbps，高速的FPGA器件可利用其流水線技術(shù)，完成閱讀器基帶信號(hào)編碼、解碼、校驗(yàn)等的處理.

在RFID系統(tǒng)中數(shù)據(jù)的傳輸不可避免地會(huì)產(chǎn)生差錯(cuò)，而循環(huán)冗余校驗(yàn)(Cyclic Redundancy Check，CRC)是一種檢錯(cuò)率高、編碼簡(jiǎn)單的檢錯(cuò)方法，故在RFID系統(tǒng)中數(shù)據(jù)傳輸常采用CRC.RFID系統(tǒng)中，CRC的計(jì)算作用于SOF后的所有字節(jié)，并將計(jì)算得到的CRC附加在每一幀內(nèi)EOF前的兩字節(jié)上用于每一次請(qǐng)求和應(yīng)答.當(dāng)收到來(lái)自閱讀器的請(qǐng)求時(shí)，電子標(biāo)簽將校對(duì)CRC的值是否有效.如果無(wú)效，電子標(biāo)簽將丟掉該幀，并不做回答(調(diào)制).

CRC在FPGA上的實(shí)現(xiàn)，可采用串行和并行兩種實(shí)現(xiàn)方式［4－6］.采用串行方式時(shí)，編碼按位逐位輸入線性反饋移位寄存器組(LSFR)中，當(dāng)所有位輸入完后觸發(fā)器的狀態(tài)就是所輸入編碼的CRC的校驗(yàn)碼.采用串行方式電路結(jié)構(gòu)簡(jiǎn)單，但每次只能處理一位二進(jìn)制數(shù)據(jù)，也很難滿足速度較高的場(chǎng)合.而當(dāng)數(shù)據(jù)傳輸?shù)乃俣群芨?，或者是多位?shù)據(jù)并行傳輸時(shí)，需要引入并行計(jì)算的實(shí)現(xiàn)方法.并行計(jì)算的實(shí)現(xiàn)方法可以在同一個(gè)時(shí)鐘內(nèi)對(duì)多位數(shù)據(jù)進(jìn)行編碼，從而提高CRC的計(jì)算速度.

1 RFID系統(tǒng)中的循環(huán)冗余校驗(yàn)

假設(shè)要傳送 k 位二進(jìn)制數(shù)據(jù)，即 dk－1，dk－2，…，d1，d0，則k位二進(jìn)制數(shù)據(jù)序列可表示為:

式中:G(x)為生成多項(xiàng)式;余數(shù)R(x)為所求的r位校驗(yàn)位.發(fā)送端將r位校驗(yàn)碼附加在傳輸?shù)臄?shù)據(jù)流后邊構(gòu)成一個(gè)新的二進(jìn)制碼序列(共k+r位)，然后將其發(fā)送出去.在接收端也進(jìn)行同樣的除法過(guò)程，如果接收端的除法結(jié)果不為零，則表明數(shù)據(jù)傳輸產(chǎn)生了差錯(cuò)，數(shù)據(jù)接收端自動(dòng)請(qǐng)求重發(fā)，實(shí)現(xiàn)糾錯(cuò).

在RFID 系統(tǒng)中，ISO/IEC 14443，ISO/IEC 15693，ISO/IEC 18000—6中長(zhǎng)命令多采用CRC-CCITT國(guó)際標(biāo)準(zhǔn)，其生成多項(xiàng)式為G(x)=x16+x12+x5+1.ISO/IEC 18000—6中，短命令采用CRC—5，其生成多項(xiàng)式為G(x)=x5+x3+1.

2 多字節(jié)的并行CRC算法

2.1 單字節(jié)的CRC并行算法

以CRC-CCITT國(guó)際標(biāo)準(zhǔn)生成的多項(xiàng)式

為例，通用的CRC串行編碼器采用LSFR，其串行編碼器如圖1所示.

圖1 CRC串行編碼器

編碼前先將所有的寄存器置0，之后將信息序列從高位到低位依次從input端輸入.信息序列全部輸入后，寄存器中的值就是所要求的余數(shù)，即CRC的校驗(yàn)碼.串行的方法雖然可以計(jì)算各種CRC，但是一個(gè)時(shí)鐘周期只能計(jì)算一位數(shù)據(jù)，效率比較低，只適用于低速的串行輸入輸出系統(tǒng).如果可以在同一個(gè)時(shí)鐘周期內(nèi)并行處理若干位數(shù)據(jù)，便可以大大地提高速度，因此在串行處理的基礎(chǔ)上推導(dǎo)出了并行算法.

先輸入高位，再輸入低位，當(dāng)經(jīng)過(guò)8個(gè)時(shí)鐘信號(hào)，即一個(gè)字節(jié)(d7d6d5d4d3d2d1d0)的所有信息位都輸入后，寄存器的輸出即為該字節(jié)的CRC校驗(yàn)碼.寄存器的輸出結(jié)果如下:

2.2 n個(gè)字節(jié)的CRC的并行算法

n個(gè)字節(jié)的二進(jìn)制數(shù)據(jù)序列可表示為:

其中:

式中:G(x)為生成多項(xiàng)式;Rn，H(x)為Rn(x)的高8位;Rn，L(x)為 Rn(x)的低 8 位.

由式(4)知，對(duì)于CRC－16，本字節(jié)的CRC的校驗(yàn)碼=(上一字節(jié)的CRC校驗(yàn)碼的高8位+本字節(jié))的CRC校驗(yàn)碼xor(上一字節(jié)的CRC校驗(yàn)碼左移8位).

3 基于FPGA的CRC校驗(yàn)碼的實(shí)現(xiàn)

3.1 關(guān)鍵代碼

下面是用VHDL代碼實(shí)現(xiàn)循環(huán)冗余校驗(yàn)的主要源程序.

3.2 運(yùn)行結(jié)果及性能分析

選用的FPGA芯片是Altera公司開(kāi)發(fā)的Cyclone系列的FLEX10K10LC84－3，輸入端輸入數(shù)據(jù)流為(02，06，42，A5)，高位在前，低位在后.采用圖1串行編碼器和筆者提出的算法(初始值取00H)分別在modelsim SE 6.5中進(jìn)行仿真，波形分別如圖2和圖3所示.

圖3 多字節(jié)的并行算法運(yùn)行結(jié)果

從圖2和圖3可以看出:計(jì)算結(jié)果都為D129，與式(2)的理論結(jié)果一致，符合CRC算法規(guī)則;在接收完最后一個(gè)數(shù)據(jù)A5后，多字節(jié)的并行算法在延時(shí)1個(gè)clk就計(jì)算出了所輸入字節(jié)的CRC，運(yùn)算速度較快.雖然該并行算法使用了38個(gè)邏輯單元，比只使用了16個(gè)邏輯單元的串行方式多用了一倍的資源，但求解速度卻提高了很多，較好地做到速度與資源的平衡.采用更高端的FPGA芯片，速度更高，完全可以滿足超高頻和微波段的CRC計(jì)算.

4 結(jié)語(yǔ)

CRC是數(shù)據(jù)通信中應(yīng)用廣泛的差錯(cuò)控制算法，檢錯(cuò)能力強(qiáng)，占用系統(tǒng)資源少，是RFID系統(tǒng)中重要的錯(cuò)誤檢測(cè)和恢復(fù)機(jī)制.通過(guò)對(duì)CRC原理的分析，研究了一種可求解多字節(jié)的并行CRC算法，并采用VHDL設(shè)計(jì)實(shí)現(xiàn).該算法首先通過(guò)分析經(jīng)過(guò)8個(gè)時(shí)鐘信號(hào)后線性反饋移位寄存器的輸出狀態(tài)與輸入的字節(jié)、寄存器的初始狀態(tài)的關(guān)系，從而得到單字節(jié)的并行CRC算法;然后通過(guò)計(jì)算CRC的公式推導(dǎo)出當(dāng)前字節(jié)的CRC與當(dāng)前字節(jié)、上一字節(jié)的CRC的關(guān)系，從而得到多字節(jié)的并行CRC算法.仿真實(shí)驗(yàn)證明了該算法的正確性和高效性，提高了RFID系統(tǒng)的編解碼速度.

［1］單承贛，單玉峰，姚磊，等.射頻識(shí)別(RFID)原理與應(yīng)用［M］.北京:電子工業(yè)出版社，2008.

［2］汪浩.物聯(lián)網(wǎng)的觸點(diǎn)——RFID技術(shù)及專利的案例應(yīng)用［M］.北京:科學(xué)出版社，2010.

［3］蔡孟欣.圖書(shū)館RFID研究［M］.北京:國(guó)家圖書(shū)館出版社，2010.

［4］莫元?jiǎng)?，黃水永.并行CRC在FPGA上的實(shí)現(xiàn)［J］.電子設(shè)計(jì)工程，2011，19(15):133 －135.

［5］羅志聰，孫奇燕.CRC－16算法與FPGA實(shí)現(xiàn)［J］.四川兵工學(xué)報(bào)，2010，31(5):89 －92.

［6］范文兵，李建華，禹士鵬，等.RFID系統(tǒng)數(shù)據(jù)傳輸中CRC算法的分析與實(shí)現(xiàn)［J］.鄭州大學(xué)學(xué)報(bào):工學(xué)版，2010，31(2):97 －101.