RS碼類的構(gòu)建及在數(shù)據(jù)鏈模擬系統(tǒng)中的應(yīng)用

劉翠海 ,姜 波,溫 東,徐松巖

(海軍潛艇學(xué)院,山東 青島266071)

1 引 言

數(shù)據(jù)鏈?zhǔn)且詿o線傳輸為主,按照統(tǒng)一的消息標(biāo)準(zhǔn)和通信協(xié)議,鏈接傳感器平臺、指揮控制平臺和武器平臺,實時處理和分發(fā)戰(zhàn)場態(tài)勢、指揮引導(dǎo)、戰(zhàn)術(shù)協(xié)同、武器控制等格式化消息的系統(tǒng),其本質(zhì)是一種高效傳輸、實時分發(fā)格式化消息的信息鏈路[1]。其中,嚴(yán)格科學(xué)的格式化消息標(biāo)準(zhǔn)是數(shù)據(jù)鏈廣泛應(yīng)用的前提條件,戰(zhàn)術(shù)數(shù)據(jù)若不能準(zhǔn)確傳輸可能會造成提供虛假信息,致使戰(zhàn)機貽誤。為了保證戰(zhàn)場上的各類作戰(zhàn)數(shù)據(jù)信息準(zhǔn)確無誤地按照統(tǒng)一約定的格式傳輸分發(fā)達到共享,保證作戰(zhàn)系統(tǒng)的效能得到最大的發(fā)揮,在復(fù)雜的無線信道通信環(huán)境中,數(shù)據(jù)傳輸必須要有容錯措施來增加傳輸數(shù)據(jù)的可靠性。由于RS碼具有同時糾隨機錯誤和突發(fā)錯誤的能力,且糾突發(fā)錯誤更有效,因此在數(shù)據(jù)通信和數(shù)據(jù)存儲系統(tǒng)的差錯控制中得到了廣泛的應(yīng)用,其中RS(31,15)碼現(xiàn)已經(jīng)成為美軍在三軍聯(lián)合戰(zhàn)術(shù)信息分發(fā)系統(tǒng)(JTIDS)中采用的標(biāo)準(zhǔn)碼。

本文以戰(zhàn)術(shù)數(shù)據(jù)鏈通信系統(tǒng)為對象,詳細分析了RS編譯碼模型及其編程實現(xiàn)方法,并采用VC++語言和面向?qū)ο蟮某绦蛟O(shè)計方法,設(shè)計且實現(xiàn)了應(yīng)用于數(shù)據(jù)鏈模擬系統(tǒng)中的CRSCode類,并針對數(shù)據(jù)傳輸過程中產(chǎn)生的突發(fā)和隨機錯誤的極限情況進行了檢驗。仿真驗證表明,設(shè)計的RS編譯碼類的糾錯能力與理論分析一致,滿足模擬系統(tǒng)的設(shè)計要求。

2 RS編譯碼模型及編程實現(xiàn)

RS碼是一種多進制BCH循環(huán)分組碼,其碼字符號均在GF(2m)上取值。對于(n,k)RS碼,n=2m-1為碼長,k為信息碼元數(shù)目,n-k為監(jiān)督碼元數(shù)目,d=n-k+1表示碼元距離。RS碼是一種極大最小距離可分碼,即在所有線性分組碼中其最小距離最大,也就意味著RS碼(糾2t=n-k個差錯)的糾錯能力最強[4-5]。

RS碼的基本思想就是選擇一合適的多項式g(x),并且使得對每個信息碼計算得到的碼字多項式c(x)都是g(x)的倍式,即使得c(x)除以g(x)的余數(shù)多項式為0。這樣,如果接收到的碼字多項式除以g(x)的余數(shù)多項式不為0,則可以知道接收的碼字中存在錯誤,因此可以進一步計算并糾正t個錯誤。

2.1 RS編碼模型及編程實現(xiàn)

RS碼屬于循環(huán)碼的一種,它的編碼過程就是用其信息多項式m(x)乘以 xn-k后再除以生成多項式g(x),所得余式即為校驗多項式h(x),然后將h(x)置于m(x)之后,即形成RS碼。其中,各多項式的所有運算均在伽羅華域進行,因此,在計算機仿真實現(xiàn)中,有必要首先完成伽羅華域元素產(chǎn)生的程序。

2.1.1 構(gòu)造伽羅華域GF(2m)[2]

對于GF(2m)中的元素,首先給定1=α0,連乘 α可以在m重的形式里通過對α0連續(xù)左移來產(chǎn)生α1、α2、…、αm-1。對 αm-1的左移生成 10…0(共 m 個0),左移結(jié)果該元素為m+1比特,因此必須要映射到m比特,即通過 αm=α+1多項式。其比特數(shù)據(jù)計算方法是將 m+1重數(shù)中的最高位掩去得到 m重數(shù)后,通過按比特的模2加“11”到掩碼后的m 重結(jié)果(即加 α+1)來實現(xiàn)的。隨后繼續(xù)左移可以產(chǎn)生 αm+1、αm+2、…、α2m-1。伽羅華域元素產(chǎn)生編程實現(xiàn)的框圖如圖1所示。

圖1 伽羅華域元素產(chǎn)生流程圖Fig.1 Generation of a Galois Field′s element

2.1.2 多項式的計算機表示及數(shù)學(xué)運算模型

有限域GF(pm)中的每個元素均可由一個多達m項的多項式表示,每一項的系數(shù)是一個模 p值。在計算機中,系數(shù)可以存儲在一個數(shù)組里,其中 xn的系數(shù)存放到數(shù)組中的位置n,即假設(shè)數(shù)組從0開始標(biāo)記,如C和C++。對于像Matlab從1開始標(biāo)記的語言,xn的系數(shù)將存到數(shù)組中n+1的位置。對于GF(2m)中的元素,多項式可以存儲在一個整型變量中,用每比特代表一個二進制系數(shù)。

RS編碼、譯碼過程中用到了大量的多項式元素的乘法、加法和倒數(shù)運算。我們知道,其運算均是在伽羅華域GF(2m)中進行的,其乘法運算對應(yīng)的是指數(shù)模2m相加,加法運算則是模2運算。為此,在實現(xiàn)了伽羅華域元素產(chǎn)生函數(shù)的基礎(chǔ)上,需要編程實現(xiàn)RS編譯碼中常用的多項式加法、乘法、除法等基本運算函數(shù)。

假設(shè)有兩個多項式

多項式加法運算實現(xiàn)起來非常簡單,多項式乘法與除法編程實現(xiàn)基本相同,圖2給出了多項式乘法計算電路。

圖2 多項式乘法電路Fig.2 Circuit of multiplicity of the polynomial

按照圖2所示電路多項式乘法的實現(xiàn)步驟如下[6]:

步驟1:r個寄存器全部清零;

步驟2:A(x)最高次系數(shù) ak首先送入時,乘法器輸出乘積的最高次項xk+r的系數(shù)akbr,同時 ak存入寄存器的第一級;

步驟3:A(x)的第二個系數(shù) ak-1送入時,ak由第一級寄存器進入第二級寄存器,同時與 br-1相乘,乘法器輸出 ak-1br+akbr-1,即得到了乘積的xk+r-1的系數(shù);

步驟4:如此重復(fù)進行,直至 k+r+1次移位后,乘法器輸出乘積的常數(shù)項a0b0。

2.1.3 RS編碼的編程實現(xiàn)

假設(shè)需發(fā)送的信息碼字序列為m1,m2,…,mk,RS碼的編碼電路如圖3所示。

圖3 RS編碼電路Fig.3 Encoding circuit for RS code

按照圖3所示電路實現(xiàn)的RS編碼計算機程序流程如圖4所示。

圖4 R S編碼程序流程圖Fig.4 Flowchart of encoding program of RS code

2.2 RS譯碼模型及編程實現(xiàn)[6]

相對于RS編碼,其譯碼過程比較繁瑣、復(fù)雜。RS譯碼主要包括計算伴隨多項式、確定差錯位置多項式、計算差錯位置多項式的根和求錯誤圖樣4個步驟。第一、三、四步計算機編程實現(xiàn)起來比較簡單,第一步求伴隨多項式是將 αi(i=1,2,…,2t)代入接收多項式r(x)而得到的;第三步依據(jù)錢氏搜索算法確定錯誤位置,得到差錯數(shù)量;第四步根據(jù)錯誤位置和錯誤值得到錯誤圖樣。第二步是整個譯碼過程中最復(fù)雜的一步,大多采用BM迭代算法。實現(xiàn)BM迭代算法可以以列表形式完成,如表1所示,表中 lu是σ(u)(x)的次數(shù)。

表1 BM迭代過程Table 1 BM algorithm

假設(shè)我們已經(jīng)填滿了第u行,可以這樣來填第u+1行:

(1)如果 du=0,則 σ(u+1)(x)=σ(u)(x)且 lu+1=lu;

(2)如果du≠0,尋找第 u行前的第ρ行,使 dρ≠0及最后一列(ρ-lρ)為最大值,則由式(1)可得σ(u+1)(x),且

(3)不管du是否等于零,都要依據(jù)式(3)計算du+1:

最后一行的多項式 σ(2t)(x)即為需要的 σ(x)。如果它的次數(shù)大于t,則表明接收序列的錯誤多于t,一般來說就無法決定它們的位置。

3 RS碼類的構(gòu)建和在模擬系統(tǒng)中的實現(xiàn)

數(shù)據(jù)鏈模擬系統(tǒng)以戰(zhàn)術(shù)數(shù)據(jù)鏈通信系統(tǒng)為模擬對象,以VC++語言為編程實現(xiàn)平臺,采用面向?qū)ο蟮某绦蛟O(shè)計方法,以戰(zhàn)術(shù)數(shù)據(jù)鏈通信系統(tǒng)各模塊為類對象,編程實現(xiàn)了各類對象并進行了封裝?；赗S編譯碼的數(shù)據(jù)鏈模擬系統(tǒng)結(jié)構(gòu)如圖5所示。

圖5 數(shù)據(jù)鏈模擬系統(tǒng)信號流程圖Fig.5 Block diagram of the data link simulating system

依據(jù)圖5各模塊的劃分,數(shù)據(jù)鏈模擬系統(tǒng)設(shè)計并實現(xiàn)了CModel類,該類是VC++中CObject類的派生類,定義了供所有模型類調(diào)用的公共過程,是圖5所有模塊的基類。CRSCode類、CCSK類、CMSK類以及CDSSS類都是CModel類的派生類,它們分別是RS編譯碼類、循環(huán)碼移位鍵控類、最小移頻鍵控類、直接序列擴頻類的基類。

3.1 RS編譯碼類的整體設(shè)計

根據(jù)上一節(jié)的分析,CRSCode類定義有自己的成員變量和成員函數(shù),完成整個模擬系統(tǒng)中的編碼和譯碼。下面給出了CRSCode類定義的部分內(nèi)容:

class CRSCode:public CModel

{

public:

int n;//碼字長度

int k;//消息字長度

int m;//伽羅華域各元素的比特數(shù)

int generate-GF(int m);//生成GF(2m)域所有元素

int multiply-rs(int a,int b,int m);

int reverse-rs(int a,int m);

int polymul-rs(int a,int b,int m);

int polydiv-rs(int a,int b,int m);

}

CRSCode類中的成員函數(shù)multiply-rs(int a,int b,int m),參數(shù)a、b為十進制表示的多項式中xn的系數(shù),參數(shù)m為GF(2m)域中各元素的比特數(shù);函數(shù)返回值為系數(shù)a與b相乘的結(jié)果。

成員函數(shù)reverse-rs(int a,int m),參數(shù)a為十進制表示的多項式中xn的系數(shù),參數(shù)m為GF(2m)域中各元素的比特數(shù);函數(shù)返回值為系數(shù)a-1的結(jié)果。

成員函數(shù)polymul-rs(int a,int b,int m),參數(shù)a、b為一數(shù)組,是以十進制表示的多項式中從 x0～xn各項的系數(shù),a、b的排列順序是以多項式次數(shù)從低到高的順序排列,參數(shù)m為GF(2m)域中各元素的比特數(shù);函數(shù)返回值為系數(shù)多項式 a(x)與b(x)相乘的結(jié)果。

成員函數(shù)polydiv-rs(int a,int b,int m),參數(shù)a、b為一數(shù)組,是以十進制表示的多項式中從 x0～xn各項的系數(shù),a、b的排列順序是以多項式次數(shù)從低到高的順序排列。參數(shù) a為待發(fā)送信息碼字,參數(shù)b為生成多項式,參數(shù)m為GF(2m)域中各元素的比特數(shù);函數(shù)返回值為校驗多項式各系數(shù),排列順序是以多項式次數(shù)從低到高的順序排列。

3.2 RS編譯碼類在模擬系統(tǒng)中的應(yīng)用及校驗

數(shù)據(jù)鏈模擬系統(tǒng)模擬了時分多址的工作方式,每個時隙長為7.8125 ms。在不考慮同步信息的情況下,傳輸?shù)南ㄐ畔?biāo)志和數(shù)據(jù)兩部分[3]。信息標(biāo)志部分主要包括了時隙號、用戶號、消息類型等報頭信息。數(shù)據(jù)部分模擬了固定格式的消息字,每個消息字包含15個碼元,每個碼元5 b字符,其中數(shù)據(jù)占70 b,奇偶校驗位占5 b。為保證傳輸消息的可靠性,信息標(biāo)志部分采用的是RS(16,7)編碼,對消息字采用的是RS(31,15)編碼。通過(16,7)RS編碼,在傳輸中即使這7個碼元有4個碼元出現(xiàn)了錯誤也可得到糾正。數(shù)據(jù)部分的(31,15)RS編碼,每組可糾8個錯誤,7組交織可糾56個錯誤。這種編碼使得在由31個字符組成的大組中,由于干擾或傳播等原因,即便有16個字符無法判決或有8個字符判決錯誤,在譯碼時也能得到糾正。

為了檢驗CRSCode類的運算速度和糾錯能力及正確性,分別對數(shù)據(jù)傳輸過程中產(chǎn)生的突發(fā)和隨機錯誤的極限情況進行了檢驗,表2給出了信源產(chǎn)生104個符號、信噪比在0～7 dB范圍測得的實驗數(shù)據(jù),根據(jù)數(shù)據(jù)繪出的性能曲線如圖6所示。仿真結(jié)果表明CRSCode類的糾錯能力與理論分析一致,與設(shè)計的功能相符,達到了譯碼的預(yù)期效果。

表2 誤碼率實驗測量數(shù)據(jù)Table 2 BER data of test

圖6 RS編碼BER性能曲線Fig.6 Reed-Solomon error performance evaluation

4 結(jié)束語

數(shù)據(jù)鏈模擬系統(tǒng)的實現(xiàn)大體可分為建立模型、用建立的模型構(gòu)造目標(biāo)系統(tǒng)和系統(tǒng)仿真三部分工作,構(gòu)造系統(tǒng)的模型是完成所有工作的基礎(chǔ)。由于RS編譯碼在戰(zhàn)術(shù)數(shù)據(jù)鏈通信系統(tǒng)中有著重要的意義,它能夠提高整個系統(tǒng)的可靠性和抗干擾能力,進而提高系統(tǒng)性能,因而準(zhǔn)確地對其建模、編程實現(xiàn)及封裝是整個數(shù)據(jù)鏈模擬系統(tǒng)中關(guān)鍵的環(huán)節(jié)。本文以VC++為軟件平臺,以面向?qū)ο蟮某绦蛟O(shè)計方法實現(xiàn)了RS編譯碼類,并簡要介紹了數(shù)據(jù)鏈模擬系統(tǒng)的程序組成。本模擬系統(tǒng)只考慮了編碼、交織、CCSK基帶調(diào)制以及MSK調(diào)制等模型,沒有考慮同步以及其他信道模型,因此還需要進一步完善。

[1]劉翠海.美軍戰(zhàn)術(shù)數(shù)據(jù)鏈的發(fā)展及作戰(zhàn)運用[J].電訊技術(shù),2007,47(5):6-10.LIU Cui-hai.The Development and OperationalApplication of the U.S.Forces′Tactical Dada Links[J].Telecommunication Engineering,2007,47(5):6-10.(in Chinese)

[2]王昕.無線通信系統(tǒng)仿真-C++實用模型[M].北京:電子工業(yè)出版社,2005.WANG Xin.Simulating Wireless Communication Systems PracticalModels in C++[M].Beijing:Publishing House of Electronics Industry,2005.(in Chinese)

[3]梅文華,蔡善法.JTIDS/Link16數(shù)據(jù)鏈[M].北京:國防工業(yè)出版社,2007.MEI Wen-hua,CAI Shan-fa.JTIDS/Link16 Data Link[M].Beijing:National Defense Industry Press,2007.(in Chinese)

[4]陶德元,何小海,吳志華.RS碼編譯碼算法的實現(xiàn)[J].四川大學(xué)學(xué)報(自然科學(xué)版),2000,37(6):868-872.TAO De-yuan,HEXiao-hai,WU Zhi-hua.The Implementation of RS Encoding and Decoding[J].Journal of Sichuan U-niversity(Natural Science Edition),2000,37(6):868-872.(in Chinese)

[5]韓作生,袁東風(fēng).RS碼頻域編譯碼的計算機模擬[J].通信學(xué)報,1994,15(6):104-112.HAN Zuo-sheng,YUAN Dong-feng.Computer Simulation of the Coding and Decoding of RS Code in Frequency Domain[J].Journal of China Institute of Communications,1994,15(6):104-112.(in Chinese)

[6]楊爵,郎宗木炎.實用糾錯編碼[M].北京:中國鐵道出版社,1988.YANG Jue,LANG Zong-yan.Practical Error Correcting Coding[M].Beijing:Chinese Railroad Publishing House,1988.(in Chinese)