基于混合糾錯技術(shù)的北斗長報(bào)文可靠傳輸機(jī)制設(shè)計(jì)

張志峰，李中學(xué)，阮 博

(陸軍勤務(wù)學(xué)院軍事物流系，重慶 401311)

0 引言

北斗短報(bào)文通信功能作為北斗衛(wèi)星導(dǎo)航系統(tǒng)所特有的功能，在各行業(yè)領(lǐng)域都有著廣泛的研究和應(yīng)用［1］。由于北斗傳輸能力為1 680 bit/次，對于長數(shù)據(jù)報(bào)文不能一次發(fā)送完畢，需要進(jìn)行分包處理［2-3］。據(jù)統(tǒng)計(jì)分析，北斗短報(bào)文通信單數(shù)據(jù)包的傳輸成功率為95.5%，當(dāng)報(bào)文分包數(shù)達(dá)到6包時，實(shí)際測試的傳輸成功率只有75.1%［4］。因此，需要設(shè)計(jì)一個合理的傳輸機(jī)制，提高長報(bào)文傳輸?shù)目煽啃浴?/p>

目前，通信系統(tǒng)中解決數(shù)據(jù)丟包問題應(yīng)用比較廣泛的兩種方法是自動重傳請求 (ARQ)技術(shù)和前向糾錯 (FEC)技術(shù)［5-6］。ARQ技術(shù)對于信道的占用率比較高，F(xiàn)EC技術(shù)糾錯能力具有一定的限值且無回執(zhí)信息，應(yīng)用于北斗長報(bào)文通信的可靠傳輸中都具有一定的缺陷。因此，本文采用混合糾錯 (HEC)技術(shù)將兩者進(jìn)行結(jié)合，通過FEC技術(shù)進(jìn)行糾錯的同時，運(yùn)用ARQ技術(shù)發(fā)送反饋信息，并對FEC技術(shù)無法糾錯的情況通過數(shù)據(jù)重傳的方法解決［7］。

在FEC技術(shù)的應(yīng)用上，本文所采用的是Reed－Solomen(RS)糾刪碼，它的糾錯能力很強(qiáng)，可以糾正多個隨機(jī)錯誤，并且編碼簡單，構(gòu)造方便［8］。在ARQ技術(shù)的應(yīng)用上，結(jié)合RS糾刪碼工作的特點(diǎn)，以發(fā)送組為單元發(fā)送反饋信息并進(jìn)行相應(yīng)的重傳操作，減少了反饋的次數(shù)，節(jié)約了信道空間。整個傳輸機(jī)制的設(shè)計(jì)思路是運(yùn)用HEC技術(shù)，在糾錯能力范圍內(nèi)時進(jìn)行自動糾錯，超過了糾錯能力范圍則通過反饋信息進(jìn)行重傳，從而實(shí)現(xiàn)北斗長報(bào)文的可靠傳輸。

1 RS編碼技術(shù)

RS編碼技術(shù)編碼過程如下:假設(shè)要發(fā)送k個原始數(shù)據(jù)包，通過RS編碼后會生成m個冗余數(shù)據(jù)包，將k+m個數(shù)據(jù)包作為一個發(fā)送組，令n=k+m，記作RS(n，k)。在接收端只要任意接收到k個數(shù)據(jù)包，就能夠通過運(yùn)算還原出發(fā)送組中的原始數(shù)據(jù)，發(fā)送組中允許丟失的數(shù)據(jù)包不大于nk個［9-11］。

1.1 編碼

如圖1所示，將RS編碼看作是矩陣運(yùn)算。編碼過程可以表示為C=G0*D，其中生成矩陣G0是由k維單位矩陣I和m*k維的范德蒙德矩陣G組成的 (m+k)*k維矩陣，編碼前矩陣D由k個原始數(shù)據(jù)包d1，d2，d3，……，dk組成，編碼后矩陣C由k個原始數(shù)據(jù)包和m個冗余數(shù)據(jù)包c(diǎn)1，c2，c3，……，cm組成。

圖1 RS編碼

1.2 解碼

如圖2所示，接收端收到任意不少于k個數(shù)據(jù)包時，取其中的k個數(shù)據(jù)包組成接收矩陣C’，根據(jù)矩陣C可以知道接收到的數(shù)據(jù)包在發(fā)送組中的位置，并從生成矩陣G0中提取出對應(yīng)的行，組成新的矩陣G0’，則有等式C’=G0’*D成立。由此可推出D=(G0’)－1*C’成立，如圖3所示，從而實(shí)現(xiàn)了原始數(shù)據(jù)包中丟失數(shù)據(jù)包的恢復(fù)，其中(G0’)－1為 G0’的逆矩陣。

圖2 接收端接收情況

圖3 RS解碼

1.3 范德蒙德 (Vandermonde)矩陣

由RS解碼的過程可知，要使解碼成功，G0’必須為k維可逆矩陣，所以要求生成矩陣G0的任意一個k*K維子矩陣必須可逆。由于矩陣I為單位陣，必然存在逆矩陣，因此要求矩陣G存在逆矩陣。在線性代數(shù)中有一種矩陣稱為范德蒙德矩陣，它的任意的子方陣均為可逆方陣。一個m行n列的范德蒙德矩陣定義如式 (1)所示，其中ai均不相同，且不為0。

令 a1、a2、a3…an分別為1、2、3…n，則得到范德蒙德矩陣為:

2 傳輸機(jī)制設(shè)計(jì)

2.1 設(shè)計(jì)思路

如圖4所示，發(fā)送端對于長報(bào)文首先進(jìn)行分包處理，將其切分成符合北斗發(fā)送規(guī)則的數(shù)據(jù)包;然后對數(shù)據(jù)包進(jìn)行分組處理，將其按照發(fā)送組中原始數(shù)據(jù)包的個數(shù)k進(jìn)行分組，以便按照RS編碼技術(shù)對數(shù)據(jù)包進(jìn)行處理;最后對劃分成組的數(shù)據(jù)包進(jìn)行RS編碼，生成m個冗余數(shù)據(jù)包，并和k個原始數(shù)據(jù)包組成一個發(fā)送組進(jìn)行發(fā)送。

圖4 設(shè)計(jì)思路

接收端在接收完一個發(fā)送組的數(shù)據(jù)包后，首先對接收到的數(shù)據(jù)包進(jìn)行編碼檢驗(yàn)，并根據(jù)檢驗(yàn)結(jié)果向發(fā)送端發(fā)送反饋信息;然后根據(jù)檢驗(yàn)結(jié)果決定接下來的處理，當(dāng)丟失的數(shù)據(jù)包數(shù)在糾錯能力之內(nèi)時，通過RS解碼技術(shù)進(jìn)行數(shù)據(jù)包的還原并存放于接收端存儲空間中，當(dāng)超過糾錯范圍時，將已經(jīng)接收到的原始數(shù)據(jù)包存放在接收端存儲空間中，并對丟失的原始數(shù)據(jù)包進(jìn)行重傳處理;最后將存儲空間中的原始數(shù)據(jù)包進(jìn)行整合處理，還原出長報(bào)文內(nèi)容。

2.2 傳輸協(xié)議設(shè)計(jì)

為了便于傳輸機(jī)制的工作，在北斗短報(bào)文現(xiàn)有通信協(xié)議的基礎(chǔ)上需要添加必要的傳輸約定關(guān)鍵字進(jìn)行協(xié)議拓展，如圖5所示。

圖5 協(xié)議拓展結(jié)構(gòu)

具體定義如下:

1)反饋標(biāo)識。占用1個比特，用于表示該數(shù)據(jù)包是否為反饋數(shù)據(jù)包。設(shè)定若反饋標(biāo)識為0，則為反饋數(shù)據(jù)包;若反饋標(biāo)識為1，則不是反饋數(shù)據(jù)包。由于北斗短報(bào)文通信本質(zhì)上為不可靠通信方式，為了提高通信可靠性，必不可少的需要添加反饋信息。

2)數(shù)據(jù)包編號。占用1個字節(jié)，用于對分包后的數(shù)據(jù)包進(jìn)行編號。長報(bào)文數(shù)據(jù)經(jīng)過分包處理后，在接收端需要重新整合，為保證數(shù)據(jù)整合的完整性，按照先后順序?qū)?shù)據(jù)包進(jìn)行編號，整合時按照編號順序進(jìn)行。

3)發(fā)送組編號。占用4個比特，用于對發(fā)送組進(jìn)行編號。本文將幾個數(shù)據(jù)包看作是一個發(fā)送組進(jìn)行處理，因此會形成多個發(fā)送組，為避免接收端混淆組內(nèi)信息，需要對每一個發(fā)送組進(jìn)行編號。

4)發(fā)送組內(nèi)編號。占用3個比特，用于對一個發(fā)送組內(nèi)的數(shù)據(jù)包進(jìn)行編號。本文采用的是RS(8，5)編碼，每個發(fā)送組內(nèi)有8個數(shù)據(jù)包，正好可用3個比特位編號。

5)CRC校驗(yàn)。占用1個字節(jié)，用于對數(shù)據(jù)包內(nèi)數(shù)據(jù)進(jìn)行檢驗(yàn)。為了保證接收端接收到的數(shù)據(jù)包在傳輸過程中數(shù)據(jù)沒有出錯，需要進(jìn)行CRC校驗(yàn)，只有檢驗(yàn)沒有錯誤的數(shù)據(jù)包解碼才有意義。

2.3 發(fā)送端處理

如圖6所示，發(fā)送端對于需要發(fā)送的長數(shù)據(jù)報(bào)文，首先根據(jù)所用設(shè)備的傳輸容量限值以及添加的關(guān)鍵字大小，確定分包數(shù)據(jù)量的大小，對長報(bào)文進(jìn)行分包處理。然后依照RS編碼的規(guī)則，以5個原始數(shù)據(jù)包為一組，對數(shù)據(jù)包進(jìn)行分組處理，以便進(jìn)行RS編碼的操作。最后以發(fā)送組為單位，進(jìn)行RS編碼處理后在發(fā)送組中加入3個冗余數(shù)據(jù)包，并將處理好的發(fā)送組發(fā)送出去。

圖6 發(fā)送端處理過程

本文所采用的是RS(8，5)編碼方式，即每個發(fā)送組中包含5個原始數(shù)據(jù)包和3個冗余數(shù)據(jù)包，接收端只要接收到其中的任意5個數(shù)據(jù)包即可通過RS解碼技術(shù)還原出所有的原始數(shù)據(jù)包。按照這種方法進(jìn)行RS編碼的空間冗余率為1.6，在犧牲一部分的傳輸信道空間的前提下，能夠?yàn)楸倍范虉?bào)文通信功能增加一定的傳輸糾錯能力。

值得注意的是，在分包的過程中，對于末尾數(shù)據(jù)包數(shù)據(jù)量不足的情況用0補(bǔ)足，保持分包后每個數(shù)據(jù)包內(nèi)的數(shù)據(jù)量相同，以便進(jìn)行RS編碼處理。由于RS編碼的丟包恢復(fù)能力有限，本文中只允許每個發(fā)送組中丟失的數(shù)據(jù)包數(shù)不大于3個，否則就超出了糾錯范圍。為了保證數(shù)據(jù)的可靠傳輸，在這種情況下就需要根據(jù)反饋數(shù)據(jù)包所反饋回來的信息進(jìn)行數(shù)據(jù)包的重傳。

2.4 接收端處理

接收端在接收到數(shù)據(jù)包后，首先通過CRC檢驗(yàn)碼對數(shù)據(jù)包編碼進(jìn)行檢驗(yàn)，對于檢驗(yàn)出錯的數(shù)據(jù)包沒有解碼的必要，將其按照數(shù)據(jù)包丟失的情況進(jìn)行處理。根據(jù)檢驗(yàn)結(jié)果決定數(shù)據(jù)包進(jìn)行RS解碼還是反饋重傳。

當(dāng)一個發(fā)送組內(nèi)接收到的數(shù)據(jù)包數(shù)不少于5個時，反饋數(shù)據(jù)包向發(fā)送端發(fā)送該發(fā)送組發(fā)送成功的消息，并進(jìn)行RS編碼處理。當(dāng)接收到的數(shù)據(jù)包恰好包含所有原始數(shù)據(jù)包d1，d2，d3，d4，d5時，不必進(jìn)行RS解碼，直接按照發(fā)送組內(nèi)編號進(jìn)行數(shù)據(jù)包整合即可。當(dāng)接收到的數(shù)據(jù)包中原始數(shù)據(jù)包出現(xiàn)丟包現(xiàn)象時，選取所有正確接收到的原始數(shù)據(jù)包和相應(yīng)數(shù)量的冗余數(shù)據(jù)包，組成一個由5個數(shù)據(jù)包組成的數(shù)據(jù)包組，通過RS解碼技術(shù)還原出所有的原始數(shù)據(jù)包，進(jìn)而進(jìn)行數(shù)據(jù)包整合處理。

當(dāng)一個發(fā)送組內(nèi)接收到的數(shù)據(jù)包數(shù)少于5個時，超過了RS編碼的糾錯范圍，此時就需要通過反饋重傳對數(shù)據(jù)包進(jìn)行重新發(fā)送。根據(jù)發(fā)送組內(nèi)編號確定接收成功的數(shù)據(jù)包的類型。對于接收成功的原始數(shù)據(jù)包暫時保存在接收端儲存空間中，以便進(jìn)行后續(xù)的數(shù)據(jù)包整合處理，對于接受成功的冗余數(shù)據(jù)包，由于所在的發(fā)送組不會進(jìn)行RS編碼處理，因此沒有存在的價值，直接刪除即可。

對于丟失的原始數(shù)據(jù)包，在反饋信息中說明其數(shù)據(jù)包編號即可，當(dāng)發(fā)送端接收到反饋數(shù)據(jù)包后，在存儲空間中找到相對應(yīng)的原始數(shù)據(jù)包，重新進(jìn)行分組以及RS編碼后通過另一個發(fā)送組重新進(jìn)行發(fā)送。特殊情況下，當(dāng)一個發(fā)送組內(nèi)的5個原始數(shù)據(jù)包全部丟失時，可以在反饋信息中說明發(fā)送組編號，接收端接收到反饋數(shù)據(jù)包后，在存儲空間中找到相對應(yīng)的發(fā)送組，對整個發(fā)送組進(jìn)行重傳，這樣就不必重新進(jìn)行分組以及RS編碼，減少對數(shù)據(jù)包的處理。

3 實(shí)驗(yàn)結(jié)果與分析

本文采用matlab軟件對所提出的傳輸機(jī)制進(jìn)行模擬仿真，主要是驗(yàn)證RS糾刪碼對于數(shù)據(jù)的恢復(fù)效果，其主要的編程及解釋如下所示。

1)本文采用的是RS(8，5)糾刪碼，編碼前矩陣D由d1，d2，d3，d4，d5組成，用語句“d=1+round(7*rand(1，30))”生成一個包含30個元素的行向量，元素為1－8之間的任意整數(shù)，以此來模擬分包后的數(shù)據(jù)包。

%編碼前矩陣D

d1=1+round(7*rand(1，30)):

d2=1+round(7*rand(1，30)):

d3=1+round(7*rand(1，30)):

d4=1+round(7*rand(1，30)):

d5=1+round(7*rand(1，30)):

D=［d1:d2:d3:d4:d5］

2)只有當(dāng)正確接收到的數(shù)據(jù)包數(shù)不少于5個時，RS糾刪碼技術(shù)才能夠使用，本實(shí)驗(yàn)?zāi)M的是不包含特殊情況的需要通過RS解碼方能回復(fù)原始數(shù)據(jù)的情況。通過“randperm”語句產(chǎn)生任意排序的8個整數(shù)，代表著一個發(fā)送組內(nèi)的8個數(shù)據(jù)包，然后取前6個數(shù)表示接收端正確接收到的6個數(shù)據(jù)包，再通過對這6個數(shù)的升序排列，取前5個數(shù)所對應(yīng)的行向量組成接收矩陣C0以及生成矩陣中形成的新矩陣g0。通過這一操作可以保證隨機(jī)性的要求，囊括了所有可能出現(xiàn)的情況，使得模擬結(jié)果更具說服性。

%模擬正確接收到任意六個數(shù)據(jù)包的情況

out=randperm(8)%返回一行包含從1到8的整數(shù)%完成的是不重復(fù)的重排采樣

datal=out(1:6)

data=sort(datal) %升序排列

C1=C(data(1)，:)

C2=C(data(2)，:)

C3=C(data(3)，:)

C4=C(data(4)，:)

C5=C(data(5)，:)

C0=［C1:C2:C3:C4:C5］ %接收矩陣C0

g1=G0(data(1)，:)

g2=G0(data(2)，:)

g3=G0(data(3)，:)

g4=G0(data(4)，:)

g5=G0(data(5)，:)

g0=［g1:g2:g3:g4:g5:］ %從生成矩陣G0中取出相應(yīng)的行，組成新矩陣g0

3)按照RS糾刪碼的工作原理還原出編碼前矩陣d，并比較還原出的矩陣和編碼前矩陣是否一致，以驗(yàn)證RS編碼的效果。

g=inv(g0) %對新矩陣g0取逆

d=g*C0%還原出編碼前矩陣

ifsum(d==D)～=0

display(‘?dāng)?shù)據(jù)恢復(fù)完全’)

else

display(‘?dāng)?shù)據(jù)未能恢復(fù)完全’)

end

通過實(shí)驗(yàn)可以看出RS糾刪碼技術(shù)在滿足應(yīng)用條件的情況下對于數(shù)據(jù)能夠很好的進(jìn)行恢復(fù)。但是值得注意的是，本實(shí)驗(yàn)僅僅是對于RS編碼的可行性進(jìn)行了簡單的模擬，受限于設(shè)備的原因，并沒有對整個的可靠傳輸機(jī)制進(jìn)行實(shí)驗(yàn)，因此本實(shí)驗(yàn)還有很大的改進(jìn)之處。

4 傳輸機(jī)制的改進(jìn)

4.1 生成矩陣的改進(jìn)

生成矩陣G0中的矩陣G考慮到必須存在逆矩陣，本文采用的是范德蒙德矩陣，其實(shí)還可選用柯西矩陣 (如式(2)所示)。范德蒙德矩陣求逆運(yùn)算的復(fù)雜度為o(n3)，相比而言，柯西矩陣求逆運(yùn)算的復(fù)雜度為o(n2)，并且柯西矩陣通過有限域轉(zhuǎn)換，將迦羅華有限域GF(2w)域中的元素轉(zhuǎn)換成二進(jìn)制矩陣，降低了乘法運(yùn)算的復(fù)雜度。

4.2 數(shù)據(jù)包的交織編碼

北斗短報(bào)文通信受工作環(huán)境等因素的影響，有時候出現(xiàn)丟包的情況呈現(xiàn)出連續(xù)性的特點(diǎn)，采用RS編碼提高容錯性并不能達(dá)到理想的效果。為了彌補(bǔ)RS糾刪碼對于連續(xù)性丟包問題恢復(fù)能力差的弊端，最大限度的使用FEC技術(shù)進(jìn)行數(shù)據(jù)的恢復(fù)，考慮在RS編碼的基礎(chǔ)上進(jìn)行發(fā)送組之間的交織編碼。通過將連續(xù)丟包的情況離散的分布到不同的發(fā)送組上，進(jìn)一步提高RS糾刪碼的容錯性能。由于發(fā)送組間交織時并沒有添加多余的冗余信息，因此不會降低發(fā)送組的編碼效率。

交織編碼根據(jù)交織方式的不同，可分為線性交織、卷積交織和偽隨機(jī)交織。其中線性交織編碼是一種比較常見的形式。所謂線性交織編碼器，是指把糾錯編碼器輸出信號均勻分成m個碼組，每個碼組由n段數(shù)據(jù)組成，這樣就夠成一個n×m的矩陣，稱為交織矩陣。如圖9所示，數(shù)據(jù)以橫排順序存入，經(jīng)過交織處理后以豎列的順序輸出，這樣就完成了對數(shù)據(jù)的交織編碼。在接收時通過上述過程的逆向重復(fù)，即先按豎列存入存儲器，再橫排讀出，就可恢復(fù)成原來的RS編碼，但在傳輸時的突發(fā)錯誤被分散了。

5 結(jié)束語

本文使用混合糾錯技術(shù)來達(dá)到提高北斗長報(bào)文傳輸可靠性的目的，通過理論分析以及模擬實(shí)驗(yàn)的驗(yàn)證，證明了其可行性。通過自動重傳請求技術(shù)和前向糾錯技術(shù)的綜合應(yīng)用，在提高通信功能容錯性能的同時，盡可能節(jié)省了傳輸信道空間，對于北斗短報(bào)文功能的廣泛應(yīng)用具有一定的貢獻(xiàn)。

值得注意的是，本文所提出的可靠傳輸機(jī)制僅適用于長數(shù)據(jù)報(bào)文傳輸?shù)那闆r，由于增加了冗余信息，對信道的占用率會增加，當(dāng)所需傳輸?shù)臄?shù)據(jù)信息并不多時，相比于傳統(tǒng)的反饋重傳方式其優(yōu)勢并不明顯。因此下一步考慮將可靠傳輸機(jī)制應(yīng)用到短數(shù)據(jù)報(bào)文的傳輸中，以及運(yùn)用相應(yīng)的壓縮技術(shù)對數(shù)據(jù)進(jìn)行處理，以便進(jìn)一步節(jié)約傳輸信道空間。