基于混合糾錯技術的北斗長報文可靠傳輸機制設計

張志峰，李中學，阮 博

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

0 引言

北斗短報文通信功能作為北斗衛星導航系統所特有的功能，在各行業領域都有著廣泛的研究和應用［1］。由于北斗傳輸能力為1 680 bit/次，對于長數據報文不能一次發送完畢，需要進行分包處理［2-3］。據統計分析，北斗短報文通信單數據包的傳輸成功率為95.5%，當報文分包數達到6包時，實際測試的傳輸成功率只有75.1%［4］。因此，需要設計一個合理的傳輸機制，提高長報文傳輸的可靠性。

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

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

1 RS編碼技術

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

1.1 編碼

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

圖1 RS編碼

1.2 解碼

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

圖2 接收端接收情況

圖3 RS解碼

1.3 范德蒙德 (Vandermonde)矩陣

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

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

2 傳輸機制設計

2.1 設計思路

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

圖4 設計思路

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

2.2 傳輸協議設計

為了便于傳輸機制的工作，在北斗短報文現有通信協議的基礎上需要添加必要的傳輸約定關鍵字進行協議拓展，如圖5所示。

圖5 協議拓展結構

具體定義如下:

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

2)數據包編號。占用1個字節，用于對分包后的數據包進行編號。長報文數據經過分包處理后，在接收端需要重新整合，為保證數據整合的完整性，按照先后順序對數據包進行編號，整合時按照編號順序進行。

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

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

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

2.3 發送端處理

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

圖6 發送端處理過程

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

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

2.4 接收端處理

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

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

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

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

3 實驗結果與分析

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

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

%編碼前矩陣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)只有當正確接收到的數據包數不少于5個時，RS糾刪碼技術才能夠使用，本實驗模擬的是不包含特殊情況的需要通過RS解碼方能回復原始數據的情況。通過“randperm”語句產生任意排序的8個整數，代表著一個發送組內的8個數據包，然后取前6個數表示接收端正確接收到的6個數據包，再通過對這6個數的升序排列，取前5個數所對應的行向量組成接收矩陣C0以及生成矩陣中形成的新矩陣g0。通過這一操作可以保證隨機性的要求，囊括了所有可能出現的情況，使得模擬結果更具說服性。

%模擬正確接收到任意六個數據包的情況

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

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中取出相應的行，組成新矩陣g0

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

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

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

ifsum(d==D)～=0

display(‘數據恢復完全’)

else

display(‘數據未能恢復完全’)

end

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

4 傳輸機制的改進

4.1 生成矩陣的改進

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

4.2 數據包的交織編碼

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

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

5 結束語

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

值得注意的是，本文所提出的可靠傳輸機制僅適用于長數據報文傳輸的情況，由于增加了冗余信息，對信道的占用率會增加，當所需傳輸的數據信息并不多時，相比于傳統的反饋重傳方式其優勢并不明顯。因此下一步考慮將可靠傳輸機制應用到短數據報文的傳輸中，以及運用相應的壓縮技術對數據進行處理，以便進一步節約傳輸信道空間。