宋洋軍， 權(quán)進(jìn)國， 林孝康

（清華大學(xué) 深圳研究生院現(xiàn)代通信實(shí)驗(yàn)室，廣東 深圳 518055）

0 引言

DMR[1]的全稱是 Digital Mobile Radio（數(shù)字移動(dòng)無線電），是2006年歐洲電信標(biāo)準(zhǔn)協(xié)會(huì)（ETSI）頒布的數(shù)字對(duì)講機(jī)標(biāo)準(zhǔn)。它采用FDMA接入，每個(gè)射頻載波帶寬為12.5 kHz；對(duì)每個(gè)載波而言，又采用TDMA分成兩個(gè)時(shí)隙。

它比模擬對(duì)講機(jī)具有更窄的頻帶寬度、頻譜效率更高、鄰帶干擾更小、功耗更低和支持?jǐn)?shù)據(jù)業(yè)務(wù)等優(yōu)點(diǎn)，是對(duì)講機(jī)未來發(fā)展的方向。

DMR標(biāo)準(zhǔn)的數(shù)據(jù)和控制幀采用了多種信道編碼，Reed-Solomon(RS)碼是其中的一種。具體采用的是 RS(12,9,4)。本文根據(jù)RS(12,9,4)碼的特性，設(shè)計(jì)了一種新的譯碼方式，減少了ROM查找表的使用，降低了譯碼的復(fù)雜度，并在Xilinx FPGA上得到了驗(yàn)證。

1 RS碼的表示和運(yùn)算

RS碼[2]通常表示為RS（n, k, δ），其中n, k, δ分別表示碼長、信息碼位和最小碼重。RS碼采用稱為伽羅華域（Galois Field, GF）的有限域中的數(shù)據(jù)來表示。對(duì)于任何質(zhì)數(shù)q，存在一個(gè)有限域，表示為GF(q)，其中包含有q個(gè)元素，可以將GF(q)延伸為一個(gè)含有qm個(gè)元素的域，這稱為GF(q)的擴(kuò)展域，表示為GF(qm)，m是一個(gè)正整數(shù)。GF(q)是GF(qm)的子集。RS碼一般采用GF(2m)，這種情況下的1碼元相當(dāng)于m比特。對(duì)于m階本原多項(xiàng)式p(x)，假設(shè)α是p(x)=0的根，那么α也會(huì)滿足式（1）:

GF(2m)中任何非 0元素都可以用 α的冪次表示，所以GF(2m)中的元素構(gòu)成一個(gè)有限元素的集合F，表示為式（2），其中α0=1：

GF(2m)的每個(gè)元素除了用α的冪表示外，還可以表示為F的線性組合，為了表示方便，用x代替α：

兩個(gè)元素的和仍然在有限域F中。兩個(gè)元素的積定義為對(duì)應(yīng)的冪次方之和，冪次方之和可能大于2m-2，可以表示為式（5）,兩個(gè)元素的積仍然在有限域F中：

2 RS碼編碼算法

RS 碼一般為外碼且是較長的碼組，如RS(255,239)[3]，RS(255,223)[4]，也有采用縮短碼的應(yīng)用，例如使用在跳頻通信系統(tǒng)中的前向糾錯(cuò)碼 RS(31,25)[5]，和蜂窩數(shù)字分組數(shù)據(jù)（CDPD）系統(tǒng)中的RS(63,47)[6]。DMR標(biāo)準(zhǔn)采用的RS(12,9,4)是用于內(nèi)碼，它是將RS(255,252,4)前 243個(gè)碼元設(shè)為 0，截取后 12個(gè)碼元得到的。它是在GF(28)域中的，每個(gè)碼元包含8比特。它有3個(gè)校驗(yàn)碼元，因此能糾正1個(gè)錯(cuò)誤碼元，或者發(fā)現(xiàn)2個(gè)錯(cuò)誤碼元。它的生成多項(xiàng)式有兩種表示方法[1]：

其中式（7）中的數(shù)字為16進(jìn)制。兩個(gè)生成多項(xiàng)式是等效的，是數(shù)據(jù)的不同表示方法，這里即有α6=40H。在GF(28)域中，本原多項(xiàng)式為：

根據(jù)生成多項(xiàng)式（7），編碼器電路可以用圖1表示。在開始編碼的前9個(gè)周期，switch1閉合，switch2連接至B，輸出序列c和輸入序列i相同；第10至12個(gè)周期，switch1斷開，switch2連接至A，輸出保存在P中的監(jiān)督碼元。有限域加法器和有限域乘法器是設(shè)計(jì)的關(guān)鍵。有限域加法器直接由位異或運(yùn)算實(shí)現(xiàn)，有限域乘法器可以通過構(gòu)造有限域乘法器單元、查表、多項(xiàng)式系數(shù)模2和實(shí)現(xiàn)。有限域乘法器結(jié)構(gòu)清晰，通用性強(qiáng)，但比多項(xiàng)式系數(shù)模2和延時(shí)要大；查表法需要一片ROM存儲(chǔ)冪次與多項(xiàng)式系數(shù)的映射關(guān)系；多項(xiàng)式系數(shù)模2和只需最多2級(jí)異或運(yùn)算即可實(shí)現(xiàn)，但要求一個(gè)乘數(shù)為常數(shù)。以圖1為例，乘以16進(jìn)制數(shù)40相當(dāng)于乘以α6，設(shè)輸入可表示為式（9），輸出為式（10）：

根據(jù)本原多項(xiàng)式（8）化簡冪次大于等于 8的項(xiàng)，設(shè)化簡后有式（11）：

那么有：

類似地，其他兩個(gè)乘法器也可以轉(zhuǎn)化為多項(xiàng)式系數(shù)模2和。特別地，譯碼時(shí)需要的乘α-1也是可以這樣計(jì)算的。

圖1 RS(12,9,4)編碼器結(jié)構(gòu)

3 RS碼譯碼算法

RS(12,9,4) 碼譯碼主要分三部分：伴隨式計(jì)算、逐碼元計(jì)算新的伴隨式和錯(cuò)誤值、譯碼輸出。如圖2所示。

圖2 RS(12,9,4)譯碼器結(jié)構(gòu)

其中i=1,2,3。計(jì)算S需要的有限域乘法器可以采用和編碼器相同的方法實(shí)現(xiàn)。如圖3所示。

圖3 RS(12,9,4)譯碼器伴隨式的計(jì)算

需要12個(gè)周期把S計(jì)算出來。構(gòu)造一個(gè)新的矩陣N：

根據(jù)文獻(xiàn)[7]，可知當(dāng)錯(cuò)誤碼元數(shù)為1或0時(shí)，N為奇異矩陣；當(dāng)錯(cuò)誤碼元數(shù)為2時(shí)，N為非奇異矩陣。由于判定N是否奇異仍然需要有限域乘法器，并且判定后，計(jì)算錯(cuò)誤位置和錯(cuò)誤值也要有限域乘法器，用 Step-by-Step算法則可采用和編碼器相同的方法實(shí)現(xiàn)有限域乘法器。假設(shè)接收碼元中有1個(gè)錯(cuò)誤：

j表示錯(cuò)誤位置。譯碼的任務(wù)就是求出錯(cuò)誤位置 j和錯(cuò)誤值ej。由于伴隨式S為：

那么，經(jīng)過j次乘法運(yùn)算，有：

該部分的乘法運(yùn)算采用和編碼器相同的有限域乘法器。若有2個(gè)碼元錯(cuò)誤，N為非奇異矩陣，上述等式不成立。若有0個(gè)錯(cuò)誤，把ej=0當(dāng)成1個(gè)錯(cuò)誤處理。由此譯碼算法可以表示如下：

② 初始化錯(cuò)誤值e′、錯(cuò)誤位置j′和新的伴隨式S′；

③ 如果j′ =12，說明碼元錯(cuò)誤個(gè)數(shù)大于2，譯碼結(jié)束；如果 S′1=S′3，跳至下一步，否則：

④ 譯碼碼字：

4 RS碼硬件實(shí)現(xiàn)

根據(jù)第2部分的編碼算法和第3部分的譯碼算法，設(shè)計(jì)Verilog HDL寄存器傳輸級(jí)（RTL）的實(shí)現(xiàn)。使用Xilinx ISE 9.2i綜合代碼，F(xiàn)PGA選擇Xilinx Virtex-II Pro XC2VP30型號(hào)，綜合的結(jié)果是：編碼器為797 gates，譯碼器是2 800 gates，總計(jì)3597 gates。將綜合結(jié)果下載到Xilinx Virtex-II Pro XC2VP30 FF896的FPGA內(nèi)，再使用ChipScope Pro 9.2i內(nèi)嵌邏輯分析儀獲得關(guān)鍵引腳的波形，如圖 4，為了方便比較，這里使用了Visio對(duì)原圖進(jìn)行重繪。

i,c,r,i_dec分別表示發(fā)送的信息碼(9 symbols)、編碼后的碼組(12 symbols)、接收的碼組(12 symbols)和譯碼后的信息碼(9 symbols)。 經(jīng)編碼后在發(fā)送信息碼后增加了3個(gè)校驗(yàn)碼元。r是對(duì)c添加1碼元錯(cuò)誤后得到的接收碼組。通過圖4可以得知，當(dāng)?shù)?個(gè)碼元從35加噪聲變成D0后，在state=4的末尾，譯碼輸出i_dec得到了正確的結(jié)果35。

圖4 RS(12,9,4)碼FPGA的實(shí)現(xiàn)

5 結(jié)語

本文提出了一種適合縮短碼RS(12,9)的譯碼算法，該算法通過計(jì)算伴隨式并按照 Step-by-Step算法逐碼元檢查錯(cuò)誤值和錯(cuò)誤位置，簡化了有限域內(nèi)的負(fù)冪次方的運(yùn)算，從而無需用于有限域負(fù)冪次方運(yùn)算的查找表等，在譯碼性能和譯碼復(fù)雜度之間達(dá)到很好的折中。該算法經(jīng)Verilog HDL硬件描述語言表示，下載到Xilinx FPGA內(nèi)，使用線性反饋移位寄存器構(gòu)成的隨機(jī)數(shù)錯(cuò)誤來模擬噪聲，并用ChipScope工具獲得內(nèi)部信號(hào)波形得到驗(yàn)證。該算法已經(jīng)應(yīng)用在DMR標(biāo)準(zhǔn)的RS編譯碼器的FPGA實(shí)現(xiàn)上了。類似的算法也可以用于其他RS縮短碼。

[1] ETSI. TS 102361-1, 2006，Electromagnetic compatibility and Radio spectrum Matters (ERM);Digital Mobile Radio (DMR)Systems; Part 1: DMR Air Interface (AI) protocol[S]. Sophia Antipolis Cedex, France: ETSI:130-132. http://www.etsi.org.

[2] Sklar B. Digitsal Communications-2nd ed[M]. New Jersey:Prentice Hall PTR, 2001:445-450.

[3] 胡慶生,王志功,張軍,等. 2.5Gb/s Reed-Solomon譯碼器的VLSI優(yōu)化實(shí)現(xiàn)[J].電路與系統(tǒng)學(xué)報(bào),2005,10(02):57-65.

[4] 戴小紅,潘志文.Reed-Solomon編譯碼器的設(shè)計(jì)與FPGA實(shí)現(xiàn)[J].現(xiàn)代電子技術(shù),2006(03):119-124.

[5] 張珣,羅漢文,宋文濤.跳頻通信系統(tǒng)中的糾錯(cuò)碼設(shè)計(jì)與實(shí)現(xiàn)[J].通信技術(shù),2001(02):11-13.

[6] 董威，蔣鈴鴿，戎蒙恬.CDPD系統(tǒng)中RS譯碼器的改進(jìn)設(shè)計(jì)與實(shí)現(xiàn)[J].通信技術(shù),2002(11):10-12.

[7] Massey J L. Step-by-Step Decoding of the Bose-Chaudhuri-Hocquenghem Codes[J].IEEE Trans. Inform. Theory,1965(11):580-585.