范德蒙陣列糾刪碼在嵌入式系統(tǒng)中的應(yīng)用

程志洪，龔志勇

(中國電子科技集團(tuán)公司第五十四研究所，河北石家莊 050081)

0 引言

范德蒙陣列糾刪碼是一種低密度糾刪碼，具有較低的迭代譯碼復(fù)雜度，而且是目前接近信道容量限的最佳編碼技術(shù)之一。

衛(wèi)星數(shù)字化視頻廣播系統(tǒng)(DVB-S)采用卷積碼與里德-所羅門編碼(Reed-Solomon Codes，RS)級(jí)聯(lián)糾錯(cuò)。衛(wèi)星數(shù)字化視頻廣播的第2代標(biāo)準(zhǔn)(DVBS2)系統(tǒng)采用低密度校驗(yàn)碼(LDPC)與BCH碼級(jí)聯(lián)糾錯(cuò)?？臻g數(shù)據(jù)系統(tǒng)咨詢委員會(huì)(CCSDS)推薦采用卷積碼與RS碼級(jí)聯(lián)或Turbo碼等糾錯(cuò)。在網(wǎng)絡(luò)數(shù)據(jù)傳輸、數(shù)據(jù)存儲(chǔ)等通信系統(tǒng)中，多采用糾刪碼來提高數(shù)據(jù)傳輸可靠性。在Internet工程任務(wù)組織(IETF)草案中，推薦采用RS糾刪碼、LDPC糾刪碼和數(shù)字噴泉碼等來提高網(wǎng)絡(luò)通信的可靠性和有效性。分布式存儲(chǔ)系統(tǒng)和磁盤陣列技術(shù)(RAID)中也采用了糾刪碼來提高數(shù)據(jù)的可靠性［1］。

1 糾刪碼編譯碼

糾刪碼具有在嵌入式系統(tǒng)和計(jì)算機(jī)上處理速度快的特點(diǎn)。嵌入式系統(tǒng)輸出的數(shù)據(jù)經(jīng)過無線通信系統(tǒng)傳輸，當(dāng)系統(tǒng)可靠性不能達(dá)到指標(biāo)要求時(shí)，可以考慮在嵌入式系統(tǒng)中加入糾刪碼來提高無線通信系統(tǒng)的可靠性［2］。

目前，有關(guān)糾刪碼的研究主要集中在兩大類，一類是低密度糾刪碼，如LDPC糾刪碼、數(shù)字噴泉碼等，一類是傳統(tǒng)的編碼方法如RS類糾刪碼。LDPC糾刪碼依靠單一異或操作產(chǎn)生冗余，具有相對較低的計(jì)算復(fù)雜度。盡管數(shù)字噴泉碼的研究已取得一些可喜成果，但目前的應(yīng)用還不是非常廣泛。RS糾刪碼為最大距離可分(MDS)碼，具有最好的糾刪性能［3］，它平衡了容錯(cuò)性能和碼利用率，但是它在糾刪碼中具有較大的計(jì)算復(fù)雜度［4］。

一個(gè)(n，k)糾刪碼是把k包數(shù)據(jù)編碼為n包數(shù)據(jù)，使得用這n包數(shù)據(jù)中的任意k包數(shù)據(jù)均可重構(gòu)原來k包源數(shù)據(jù)，其中每包數(shù)據(jù)長度為m(m為正整數(shù))個(gè)字節(jié)，其編譯碼過程示意圖如圖1所示。糾刪碼通常適用于數(shù)據(jù)整包丟失或包中有數(shù)據(jù)錯(cuò)誤的通信系統(tǒng)中。

圖1 糾刪碼編譯碼過程

原始數(shù)據(jù)包為a包～f包，編碼后數(shù)據(jù)包為A包～H包，其中G包和H包為冗余包，輸出編碼數(shù)據(jù) G 的生成過程可示意為 G=f(a，b，c，d，e，f)，f為滿足一定規(guī)則的異或運(yùn)算。對RS糾刪碼來說，f為一個(gè)生成矩陣，生成矩陣可以為范德蒙矩陣和柯西矩陣，對應(yīng)的糾刪碼分別成為范德蒙糾刪碼和柯西糾刪碼。對LDPC糾刪碼來說，F(xiàn)為一個(gè)與二部圖對應(yīng)的稀疏矩陣。糾刪碼的譯碼過程為G=f'(a，b，c，d，e，f)，其中 f'為 f的逆運(yùn)算。

2 范德蒙陣列糾刪碼算法

若選取糾刪碼的生成矩陣為范德蒙矩陣或柯西矩陣，則可得相應(yīng)的糾刪碼——范德蒙碼(Vandermonde Code，VC)或柯西碼(Cauchy Code，CC)，它們都屬于RS碼類。

2.1 范德蒙矩陣

設(shè)a為佳伽羅華域上的8次本原多項(xiàng)式p(x)=1+x2+x3+x4+x8，則伽羅華域GF(28)可由p(x)的本原根 a 來生成:GF(28)={0，1，a，a2，…，a254}，其各個(gè)元素互不相同。構(gòu)造如式(1)所示的n×k范德蒙矩陣G，其中n＞k。

2.2 范德蒙碼編碼算法

使用上面的生成矩陣G進(jìn)行編碼，y=Gx，其中x=(x0，x1，…，xk-1)T，y=(y0，y1，…，yn-1)T，可以看出編碼后的數(shù)據(jù)y完全和源數(shù)據(jù)不同，不是系統(tǒng)碼，這種編碼一定程度上增加了信息的保密性，但是也大大增加了編碼和解碼的復(fù)雜度，并不適用。線性碼的生成矩陣G的構(gòu)造常常使用k×k單位矩陣與(n-k)×k的范德蒙矩陣聯(lián)合構(gòu)成。使用Gauss-Jordan消去法，把G轉(zhuǎn)換為式(2)所示的形式:

式中，Ik為k級(jí)單位矩陣。在矩陣變換過程中，所有的運(yùn)算都是伽羅華域上的模2運(yùn)算。

待編碼的k包數(shù)據(jù)為D:

式中，m為任意正整數(shù)，包長可以為任意字節(jié)數(shù)。編碼可表示為(假設(shè)需要L(L≤n-k)個(gè)檢驗(yàn)包):

矩陣E的前k包為待編碼數(shù)據(jù)D，直接復(fù)制原始數(shù)據(jù)，只需計(jì)算L個(gè)檢驗(yàn)行。例如 c11=a11*d11+a12*d21+… +a1k*dK1，“+”和“* ”為伽羅華域上的運(yùn)算。

2.3 范德蒙碼譯碼算法

假設(shè)接收到的數(shù)據(jù)第2行與第k行發(fā)生錯(cuò)誤(1行中錯(cuò)誤比特?cái)?shù)≥1，整行標(biāo)識(shí)為錯(cuò)誤)，則從冗余行中選則2行構(gòu)造如式(5)所表示的矩陣:

并對G'求逆，其逆矩陣為G'-1，則恢復(fù)數(shù)據(jù)可用式(7)表示:

只需計(jì)算D的第2行和第k行，其他行直接從D'中復(fù)制即可。

2.4 范德蒙碼編譯碼快速算法

在范德蒙碼編譯碼過程中，所有涉及到矩陣變換過程的運(yùn)算都是伽羅華域上的模2運(yùn)算。伽羅華域上的運(yùn)算與實(shí)數(shù)域上的運(yùn)算不同，其主要區(qū)別為［5］:

①伽羅華域上的加減運(yùn)算以域元素的矢量形式進(jìn)行，加減運(yùn)算為域元素的矢量表示所對應(yīng)位模2加;②域上元素見的乘除運(yùn)算以本原元素的形式進(jìn)行，乘除運(yùn)算為本原元素的冥次模加減。

由式(5)和式(6)可知，編解碼過程中涉及大量伽羅華域乘法與加法運(yùn)算。為了提高速度，事先把所有的可能加法和乘法運(yùn)算結(jié)果都計(jì)算出來存儲(chǔ)在表中，實(shí)際運(yùn)算的過程中只需進(jìn)行查表，可大大提高處理速度。

3 仿真結(jié)果分析

3.1 信道誤碼仿真

圖2為DVB-S傳輸系統(tǒng)的結(jié)構(gòu)框圖。在Matlab中構(gòu)建該系統(tǒng)，糾錯(cuò)碼外碼采用RS碼，內(nèi)碼采用卷積碼。RS選用(255，239)，交織采用32×8卷積交織，卷積編碼采用(2，1，7)，調(diào)制方式采用BPSK，AWGN信道的SNR值設(shè)為1.14 dB［6］。經(jīng)過Viterbi譯碼、解交織和RS解碼之后誤碼率為1.0×10-5。

圖2 信道誤碼仿真框圖

通過對該系統(tǒng)的仿真，得到其誤碼出現(xiàn)分布如圖3所示，其中橫軸為統(tǒng)計(jì)數(shù)據(jù)包的序號(hào)，縱軸為數(shù)據(jù)包內(nèi)誤碼個(gè)數(shù)。可以看出，數(shù)據(jù)經(jīng)過圖2所示通信系統(tǒng)處理后，誤碼不再體現(xiàn)AWGN信道的隨機(jī)誤碼特性，誤碼的表現(xiàn)形式為一包數(shù)據(jù)中出現(xiàn)多個(gè)錯(cuò)誤，且出現(xiàn)誤碼的時(shí)間間隔較大。該仿真結(jié)果表明DVB-S適合采用糾刪碼來進(jìn)一步降低系統(tǒng)的誤碼率。

3.2 糾錯(cuò)性能仿真

為了驗(yàn)證糾刪碼與無線通信系統(tǒng)中的糾錯(cuò)碼級(jí)聯(lián)使用的效果及測試糾刪碼的運(yùn)算速度，設(shè)計(jì)了如圖4所示的仿真系統(tǒng)。在數(shù)字信號(hào)處理器(DSP)上對數(shù)據(jù)進(jìn)行糾刪碼編碼，編碼之后的數(shù)據(jù)DVB-S系統(tǒng)傳輸，并把最終的數(shù)據(jù)送進(jìn)計(jì)算機(jī)由計(jì)算機(jī)完成糾刪碼解碼工作。

圖3 誤碼出現(xiàn)分布圖

圖4 仿真系統(tǒng)結(jié)構(gòu)框圖

DSP 選用 TI TMS320C6416，頻率為850 MHz，片內(nèi)RAM為1 MB，計(jì)算機(jī)配置為 CPU P4，主頻為3.0 GHz，4 G 內(nèi)存。

在該驗(yàn)證系統(tǒng)中RS糾刪碼參數(shù)如下:源數(shù)據(jù)包k=17，包長N=256字節(jié)，編碼之后數(shù)據(jù)包n=20，即冗余包為3包。經(jīng)過實(shí)際測試:當(dāng)圖2所示的系統(tǒng)誤碼率為1.0×10-5時(shí)，加入糾刪碼之后的誤碼率將為1.0×10-8左右，當(dāng)圖2所示的系統(tǒng)誤碼率為1.0×10-6時(shí)，加入糾刪碼之后的誤碼率將為1.0×10-10左右。隨著信道誤碼率的提高，糾錯(cuò)性能會(huì)下降，如果增加冗余包，能夠進(jìn)一步提高糾錯(cuò)性能。

DSP數(shù)據(jù)輸出速率為8 Mbps時(shí)，占用的DSP處理時(shí)間非常少，計(jì)算機(jī)進(jìn)行糾刪碼解碼運(yùn)算占用的CPU為2%左右。

4 結(jié)束語

通過分析范德蒙陣列糾刪碼的編解碼算法，得到一種范德蒙碼編解碼快速算法。將范德蒙碼編解碼快速算法應(yīng)用于Matlab構(gòu)建的系統(tǒng)信道誤碼仿真。實(shí)驗(yàn)結(jié)果表明，范德蒙陣列糾刪碼與通信系統(tǒng)中的糾錯(cuò)碼級(jí)聯(lián)使用大大提高系統(tǒng)的抗誤碼性能，在利用快速算法完成較高數(shù)據(jù)速率的實(shí)時(shí)處理，進(jìn)一步提高了系統(tǒng)的可靠性。

［1］LIN Shu，COSTELLO D J.著差錯(cuò)控制編碼［M］.晏堅(jiān)，何元智，潘亞漢譯.北京:機(jī)械工業(yè)出版社，2007.

［2］RIZZO L.Effective Erasure Codes for Reliable Computer Communication Protocols ［J］. ACM Computer Communication，Review，1997，27(2):24-36.

［3］張傳達(dá)，李小文.卷積編碼及其 Viterbi譯碼的實(shí)現(xiàn)［J］. 無線電工程，2006，36(7):45-48.

［4］王新梅，肖國鎮(zhèn).糾錯(cuò)碼-原理與方法［M］.西安:西安電子科技大學(xué)出版社，2002.

［5］向茜，劉釗.伽羅華域上代數(shù)運(yùn)算的最簡實(shí)現(xiàn)［J］.電子科技大學(xué)學(xué)報(bào)，2000，29(1):5-8.

［6］李雋.衛(wèi)星導(dǎo)航信號(hào)模擬器體系結(jié)構(gòu)分析［J］.無線電工程，2006，36(8):30-21，39.