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

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

1 引 言

數(shù)據(jù)鏈?zhǔn)且詿o(wú)線傳輸為主,按照統(tǒng)一的消息標(biāo)準(zhǔn)和通信協(xié)議,鏈接傳感器平臺(tái)、指揮控制平臺(tái)和武器平臺(tái),實(shí)時(shí)處理和分發(fā)戰(zhàn)場(chǎng)態(tài)勢(shì)、指揮引導(dǎo)、戰(zhàn)術(shù)協(xié)同、武器控制等格式化消息的系統(tǒng),其本質(zhì)是一種高效傳輸、實(shí)時(shí)分發(fā)格式化消息的信息鏈路[1]。其中,嚴(yán)格科學(xué)的格式化消息標(biāo)準(zhǔn)是數(shù)據(jù)鏈廣泛應(yīng)用的前提條件,戰(zhàn)術(shù)數(shù)據(jù)若不能準(zhǔn)確傳輸可能會(huì)造成提供虛假信息,致使戰(zhàn)機(jī)貽誤。為了保證戰(zhàn)場(chǎng)上的各類(lèi)作戰(zhàn)數(shù)據(jù)信息準(zhǔn)確無(wú)誤地按照統(tǒng)一約定的格式傳輸分發(fā)達(dá)到共享,保證作戰(zhàn)系統(tǒng)的效能得到最大的發(fā)揮,在復(fù)雜的無(wú)線信道通信環(huán)境中,數(shù)據(jù)傳輸必須要有容錯(cuò)措施來(lái)增加傳輸數(shù)據(jù)的可靠性。由于RS碼具有同時(shí)糾隨機(jī)錯(cuò)誤和突發(fā)錯(cuò)誤的能力,且糾突發(fā)錯(cuò)誤更有效,因此在數(shù)據(jù)通信和數(shù)據(jù)存儲(chǔ)系統(tǒng)的差錯(cuò)控制中得到了廣泛的應(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)為對(duì)象,詳細(xì)分析了RS編譯碼模型及其編程實(shí)現(xiàn)方法,并采用VC++語(yǔ)言和面向?qū)ο蟮某绦蛟O(shè)計(jì)方法,設(shè)計(jì)且實(shí)現(xiàn)了應(yīng)用于數(shù)據(jù)鏈模擬系統(tǒng)中的CRSCode類(lèi),并針對(duì)數(shù)據(jù)傳輸過(guò)程中產(chǎn)生的突發(fā)和隨機(jī)錯(cuò)誤的極限情況進(jìn)行了檢驗(yàn)。仿真驗(yàn)證表明,設(shè)計(jì)的RS編譯碼類(lèi)的糾錯(cuò)能力與理論分析一致,滿足模擬系統(tǒng)的設(shè)計(jì)要求。

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

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

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

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

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

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

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

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

2.1.2 多項(xiàng)式的計(jì)算機(jī)表示及數(shù)學(xué)運(yùn)算模型

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

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

假設(shè)有兩個(gè)多項(xiàng)式

多項(xiàng)式加法運(yùn)算實(shí)現(xiàn)起來(lái)非常簡(jiǎn)單,多項(xiàng)式乘法與除法編程實(shí)現(xiàn)基本相同,圖2給出了多項(xiàng)式乘法計(jì)算電路。

圖2 多項(xiàng)式乘法電路Fig.2 Circuit of multiplicity of the polynomial

按照?qǐng)D2所示電路多項(xiàng)式乘法的實(shí)現(xiàn)步驟如下[6]:

步驟1:r個(gè)寄存器全部清零;

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

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

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

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

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

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

按照?qǐng)D3所示電路實(shí)現(xiàn)的RS編碼計(jì)算機(jī)程序流程如圖4所示。

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

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

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

表1 BM迭代過(guò)程Table 1 BM algorithm

假設(shè)我們已經(jīng)填滿了第u行,可以這樣來(lái)填第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)計(jì)算du+1:

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

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

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

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

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

3.1 RS編譯碼類(lèi)的整體設(shè)計(jì)

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

class CRSCode:public CModel

{

public:

int n;//碼字長(zhǎng)度

int k;//消息字長(zhǎng)度

int m;//伽羅華域各元素的比特?cái)?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類(lèi)中的成員函數(shù)multiply-rs(int a,int b,int m),參數(shù)a、b為十進(jìn)制表示的多項(xiàng)式中xn的系數(shù),參數(shù)m為GF(2m)域中各元素的比特?cái)?shù);函數(shù)返回值為系數(shù)a與b相乘的結(jié)果。

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

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

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

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

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

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

表2 誤碼率實(shí)驗(yàn)測(cè)量數(shù)據(jù)Table 2 BER data of test

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

4 結(jié)束語(yǔ)

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

[1]劉翠海.美軍戰(zhàn)術(shù)數(shù)據(jù)鏈的發(fā)展及作戰(zhàn)運(yù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]王昕.無(wú)線通信系統(tǒng)仿真-C++實(shí)用模型[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].北京:國(guó)防工業(yè)出版社,2007.MEI Wen-hua,CAI Shan-fa.JTIDS/Link16 Data Link[M].Beijing:National Defense Industry Press,2007.(in Chinese)

[4]陶德元,何小海,吳志華.RS碼編譯碼算法的實(shí)現(xiàn)[J].四川大學(xué)學(xué)報(bào)(自然科學(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ì)算機(jī)模擬[J].通信學(xué)報(bào),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]楊爵,郎宗木炎.實(shí)用糾錯(cuò)編碼[M].北京:中國(guó)鐵道出版社,1988.YANG Jue,LANG Zong-yan.Practical Error Correcting Coding[M].Beijing:Chinese Railroad Publishing House,1988.(in Chinese)