RDS基帶編碼CRC算法的研究

于麗秋，路 勇

（北京交通大學(xué) 電子信息工程學(xué)院，北京 100044）

RDS（廣播數(shù)據(jù)系統(tǒng),Raidio data System）是一種應(yīng)用在無線廣播領(lǐng)域中的技術(shù)。在不增加傳輸信道的情況下，調(diào)頻立體聲廣播可以增加多種通信業(yè)務(wù)，傳送多工信息。由于在通信系統(tǒng)中可靠性與傳輸率往往是相互制約的，當(dāng)要求提高傳輸率時(shí)，校驗(yàn)碼位數(shù)就必須要少，這樣在受到干擾后會(huì)產(chǎn)生錯(cuò)誤的可能性增加，傳送信息的可靠性下降[1]。當(dāng)要求可靠性時(shí)，校驗(yàn)碼位數(shù)就要增加，這就導(dǎo)致傳送的速率變慢。為了降低信道內(nèi)噪聲及信道傳輸特性不理想造成的傳輸差錯(cuò)，在要求的傳輸率下，盡可能的提高通信的可靠性，在RDS系統(tǒng)中采用CRC（循環(huán)冗余效驗(yàn)碼，Cyclic Redundancy Check）縮短碼編碼技術(shù)對可能或已經(jīng)出現(xiàn)的差錯(cuò)進(jìn)行控制[2]。

1 RDS基帶信號(hào)編碼格式

在RDS基帶編碼的結(jié)構(gòu)中，以“組”為單元，每組包含4個(gè)塊，每個(gè)塊有26 bit，其中包含16 bit信息字和10 bit檢驗(yàn)字，整個(gè)組共有104 bit[6]。

在該結(jié)構(gòu)中信息字、校驗(yàn)字、二進(jìn)制數(shù)或二進(jìn)制地址都是先傳送高位，數(shù)據(jù)傳送是完全同步的，各數(shù)據(jù)塊與數(shù)據(jù)組之間不留空隙。其中，為了使傳送的信息誤碼校驗(yàn)和組塊同步，校驗(yàn)字部分是由信息字生成的校驗(yàn)字模2加上組和塊同步的偏置字。在這里主要研究由信息字生成的校驗(yàn)字的兩種不同CRC并行算法，及仿真和綜合結(jié)果的分析。

2 適用于RDS基帶信號(hào)的誤碼校驗(yàn)

RDS數(shù)據(jù)格式使用了一種縮短循環(huán)的塊編碼，它是由原始長為341 bit的循環(huán)碼315 bit而得到的（26,16）分組糾錯(cuò)碼. 所用編碼是一種最佳的糾正突發(fā)誤碼的縮短循環(huán)碼，其生成多項(xiàng)式為[7]：

為了使接收機(jī)的解碼器能檢測出并糾正傳送中的誤碼，故在發(fā)送端每發(fā)送一個(gè)26 bit塊就含有10 bit校驗(yàn)字，這正是選擇（1）式所示的生成多項(xiàng)式的原因。

下面介紹以信息字生成的校驗(yàn)字的形成方法。

（1）將16 bit信息字多項(xiàng)式左移10 bit；

（2）用（1）式得到的新的26 bit多項(xiàng)式除以生成多項(xiàng)式G(x)，得到的余數(shù)多項(xiàng)式R(x)；

（3）余數(shù)多項(xiàng)式R(x)，即為所求的校驗(yàn)字。

CRC縮短循環(huán)碼有明顯的分組碼結(jié)構(gòu)，即前16 bit是信息位，后10 bit是檢驗(yàn)位，這種結(jié)構(gòu)利于在解碼時(shí)快速提取信息位。對于信息位和校驗(yàn)位的編碼過程，通常會(huì)考慮用它的生成短矩陣G，關(guān)于短陣G的詳細(xì)說明及生成過程參考相關(guān)文獻(xiàn)。

3 對常見的CRC算法實(shí)現(xiàn)的分析研究

CRC碼常見的算法主要有串行和并行算法。

串行數(shù)據(jù)通信中有著得天獨(dú)厚的優(yōu)勢，電路成本低，占用資源少；但是如果要求提高串行通信的速度就得完全依賴于時(shí)鐘頻率的提高，對于速度要求較高的場合，特別是實(shí)時(shí)通信，用串行通信就很難滿足要求。

CRC碼的并行計(jì)算方法對于高速的實(shí)時(shí)通信的要求非常高，對于長幀結(jié)構(gòu)，采用并行算法有利于減少算法的運(yùn)算時(shí)間，但其所占用的資源相對于串行算法要多，同時(shí)要有嚴(yán)格的數(shù)學(xué)算法模型。

下面將通過對兩種不同的并行算法的仿真綜合結(jié)果進(jìn)行分析和對比，來找到適合RDS 傳輸?shù)男ｒ?yàn)碼算法。

3.1 異或并行算法

將根據(jù)短陣G給出RDS傳輸?shù)臋z驗(yàn)碼（26，16）的VHDL編碼器的算法，該算法的信息字與校驗(yàn)字的邏輯關(guān)系如表1，它其實(shí)是利用短陣G的相應(yīng)的信息位之間的異或運(yùn)算來直接得到校驗(yàn)字的不同位。具體的VHDL代碼就是根據(jù)表1得到的。

表1 校驗(yàn)位與信息位的邏輯關(guān)系

3.2 循環(huán)并行算法

下面給出的算法是模擬人腦思維的并行算法，它主要是利用VHDL的循環(huán)語句來實(shí)現(xiàn)的，其具體實(shí)現(xiàn)的流程圖如圖1 。

從流程圖1中看出，該方法主要是根據(jù)實(shí)際中每次的模2除法后所得的余數(shù)來判斷余數(shù)最高位是否為“0”，如果為“0”時(shí)，則從信息位依次后補(bǔ)位數(shù)，直到為“1”，接著進(jìn)行模2除法，循環(huán)處理。直到最后所得到的余數(shù)，即為信息字的校驗(yàn)位。

4 仿真結(jié)果

根據(jù)上面給出的兩種不同的并行算法，將通過對這兩種并行算法的時(shí)序仿真波形、占用資源情況及延遲時(shí)間這3方面來進(jìn)行分析比較，來找出來找到適合RDS傳輸?shù)男ｒ?yàn)碼算法。

圖1 循環(huán)并行算法流程圖

4.1 功能仿真

本仿真采用的是Xilinx ISE 10.1軟件平臺(tái)自帶的仿真工具進(jìn)行功能仿真，采用的是Spartan系列的XC3S500E芯片進(jìn)行功能仿真，由于異或并行算法和循環(huán)并行算法所實(shí)現(xiàn)算法功能相同，所以它們所形成的功能仿真波形圖相同，如圖2。

圖2 功能仿真

4.2 資源占用情況

利用短陣G的邏輯關(guān)系進(jìn)行的異或運(yùn)算來實(shí)現(xiàn)的算法，其占用資源的情況如圖3。

圖3 異或運(yùn)算資源占用情況

運(yùn)用模擬人腦思維的模2并行循環(huán)算法，所占用的資源情況如下圖4。

圖4 循環(huán)運(yùn)算資源占用情況

根據(jù)以上給出的這兩種算法占用資源的情況來看，可以得出，Slices的占用情況為，異或并行算法使用量為15，循環(huán)并行算法則為16；

而異或并行算法占用LUT2、LUT3和LUT4的資源數(shù)量分別為8、3、和15；而循環(huán)并行算法使用LUT2、LUT3和LUT4的資源數(shù)量分別為1、8和19，故異或算法比循環(huán)算法占用LUT資源相對節(jié)省約0.21%。

4.3 延時(shí)時(shí)間情況

下面將給出這兩種算法的延時(shí)時(shí)間的情況，并對它們的延時(shí)時(shí)間進(jìn)行分析和對比。

（1）異或并行算法的時(shí)間延時(shí)情況的報(bào)告結(jié)果如圖5 。

圖5 異或運(yùn)算時(shí)間延遲情況

（2）循環(huán)并行算法的時(shí)間延時(shí)情況的報(bào)告結(jié)果如圖6 。

從以上這兩種并行算法的時(shí)間延時(shí)情況，可以看出，異或算法總的延時(shí)的時(shí)間為8.051 ns，而循環(huán)算法總的延時(shí)時(shí)間為14.242 ns，由于延遲時(shí)間短，信息傳輸速率就快，所以可以得出異或并行算法的傳輸時(shí)間相對于循環(huán)并行算法的傳輸時(shí)間要快6.191 ns，尤其在進(jìn)行大量的數(shù)據(jù)信息傳輸時(shí)這種優(yōu)勢就會(huì)更加明顯。

圖6 循環(huán)運(yùn)算時(shí)間延遲情況

5 結(jié)束語

通過上面對這兩個(gè)不同的并行算法的仿真時(shí)序，占用資源及延時(shí)時(shí)間的結(jié)果分析和對比，很容易看出，無論從占用資源情況還是延時(shí)時(shí)間上，異或并行算法都要比循環(huán)并行算法占優(yōu)勢，尤其是對于傳送多位的數(shù)據(jù)信息字的通信系統(tǒng)來說就優(yōu)勢就更突出了，可以得出，異或并行算法要比循環(huán)并行算法更適合RDS傳輸?shù)男ｒ?yàn)碼算法。

[1]唐 躍. 編碼在通信中的應(yīng)用[J]. 湖北廣播電視大學(xué)學(xué)報(bào)，2006（5）.

[2]顧文斌，王 怡，馬 莉. 基于FPGA的CRC算法的實(shí)現(xiàn)[J]. 計(jì)算機(jī)與現(xiàn)代化，2008（5）.

[3]葉 懋，劉宇紅，劉 橋. CRC碼的FPGA實(shí)現(xiàn)[J]. 重慶學(xué)院學(xué)報(bào)（自然科學(xué)版）. 2007， 21 （3）：85-87.

[4]梁少潔，常天海. 循環(huán)冗余校驗(yàn)碼并行算法的FPGA實(shí)現(xiàn)[J]. 廣東通信技術(shù)，2008（2）：57-59，63.

[5]王海光. 并行CRC算法硬件實(shí)現(xiàn)研究與VHDL設(shè)計(jì)[J]. 漳州師范學(xué)院學(xué)報(bào)（自然科學(xué)版），2007（4）：51-56.

[6]盧云川，過 靜. RDS編碼和解碼技術(shù)及應(yīng)用[J]. 工程勘察，2000（2）：50-52，58.

[7]姚冬蘋，蔡超時(shí)，宋宜純. 廣播數(shù)據(jù)系統(tǒng)（RDS）的信道編解碼[J]. 鐵道學(xué)報(bào)，1997（2）：46，71-75.