北斗衛(wèi)星導航糾錯碼BCH(15,11)快速譯碼算法及實現(xiàn)結構 ①

江 寶 安

(重慶郵電大學移通學院，重慶 401520 )

0 引言

北斗衛(wèi)星導航系統(tǒng)(BDS)是中國獨立自主研制的全球衛(wèi)星導航系統(tǒng)，可在全球范圍內全天候、全天時地提供各類高精度、高可靠定位、導航、授時服務，并具短報文通信能力。目前，我國正在實施北斗三號系統(tǒng)建設，2020年將完成30顆衛(wèi)星發(fā)射組網(wǎng)，全面建成北斗三號系統(tǒng)。

對衛(wèi)星導航接收機而言,導航電文的準確性至關重要，其含有的衛(wèi)星導航基本信息直接決定了接收機的定位精度[1]。為了增強導航電文的準確性，北斗系統(tǒng)采用了循環(huán)碼BCH(15,11)作為導航電文的前向糾錯碼[2]。因此，設計該BCH碼的高效譯碼方案具有重要的意義。 BCH一般譯碼算法主要分為兩類：硬判決譯碼算法[3]和軟判決譯碼算法[4，5]。 硬判決譯碼算法具有簡單、易于實現(xiàn)的優(yōu)點，也是北斗系統(tǒng)接口控制文件中推薦的譯碼算法，但是其譯碼性能相對較差。軟判決譯碼算法的性能雖然得到一定的提高,但是在實際應用中由于復雜度的增加，會增大軟硬件實現(xiàn)成本，譯碼延遲等的不利影響?；趯嶋H應用，硬判決譯碼算法得到優(yōu)先考慮。本文提出了一種基于長除法 的北斗系統(tǒng)BCH(15,11)碼的高效硬判決譯碼算法及實現(xiàn)結構。本算法不需要存儲錯誤圖樣，也不需要解BM方程，只需要循環(huán)移位和模2相加，軟硬件實現(xiàn)簡單易行，適合接收機工程化實現(xiàn)和應用。

1 北斗導航電文數(shù)據(jù)碼糾錯編碼方式[2]

導航電文采取BCH(15,11)碼加交織方式進行糾錯。BCH(15,11)碼長為15比特，信息位為11比特，糾錯能力為1比特，生成多項式為g(x)=x4+x+1。

BCH(15,11)碼是循環(huán)碼，可以通過線性移位寄存器電路有效實現(xiàn)其編碼[8]

編碼框圖如圖1所示，文獻[2]有詳細論述。

文獻[2]中給出了BCH(15,11)硬判決譯碼算法，譯碼框圖見圖2，主要步驟如下：

(1)用接收碼r(x)除以生成多項式g(x)得余式，此余式即為校正子。

(2)由校正子查錯誤圖樣表1，得錯誤碼e(x)。

(3)由接收碼r(x)模2相加e(x)得原碼。

綜上所述，譯碼算法采用的是錯誤圖樣查表法，需要預先存儲錯誤圖樣，譯碼時，查找，匹配費時，效率不高。

圖1 BCH(15,11,1)編碼框圖

圖2 BCH(15,11,1)譯碼框圖

表1 糾錯信號的 ROM 表

2 本文提出的基于長除法的BCH(15,11)譯碼算法

BCH(15,11)生成多項式為g(x)=x4+x+1。

信息多項式為：m(x)=m10x10+m9x9+…+m1x+m0，(mi取0或1,i=0,1,…,10)

則，BCH(15,11)編碼多項式為：c(x)=m(x)·g(x)。

此譯碼算法分為以下 2 步：

(1)由接收到的含有錯誤的r(x)=c(x)+e(x)循環(huán)長除g(x)得余式，若余式項數(shù)小于等于 1，即為錯誤多項式。

(2)錯誤多項式模2相加r(x)得原碼。

證明：r(x)=m(x)g(x)+e(x)?e(x)≡r(x)mod(g(x))，故只要r(x)mod(g(x))余式相數(shù)小于等于1必為錯誤多項式。證畢。

例1：設發(fā)送碼是：c(x)=m(x)·g(x)=(x10+x9+x7+x)·(x4+x+1)=x14+x13+x9+x8+x7+x5+x2+x

假設接收碼是：r(x)=m(x)·g(x)=x14+x13+x9+x8+x7+x5+x4+x2+x，有 1位錯誤e(x)=x4，當然接收端是不知道有這 1位錯誤的。由循環(huán)長除法得錯誤多項式如 圖 3 所示，得錯誤多項式e(x)=x4，糾錯得原碼。

圖3 例1長除法得e(x)

例2：實際應用中通常采用系統(tǒng)碼形式，編碼方程為

c(x)=xn-km(x)+xn-km(x))mod(g(x))

設發(fā)送信息為：m(x)=x10+x8+x7+x+1

則，發(fā)送碼是：

c(x)=x15-11m(x)+(xn-km(x))mod(g(x))

=x14+x12+x11+x5+x4+x3+x2+1

假設接收碼是：

r(x)=c(x)+e(x)=x14+x11+x5+

x4+x3+x2+1

錯誤位e(x)=x12，當然接收端是不知道有這 1位錯誤的。由循環(huán)長除法得錯誤多項式如 圖 4 所示，得錯誤多項式e(x)=x-3=x12，糾錯得原碼。

圖4 例2長除法得e(x)

3 新算法軟硬件實現(xiàn)結構

循環(huán)長除法軟硬件實現(xiàn)如圖5所示，主要包括循環(huán)移位，模2相加，判斷r(x)不為0的個數(shù)。

①先寄存接收碼r(x)，e(x)←r(x)。

②判斷e(x)不為0的個數(shù)s，若s<2，則c=e+r結束。

③若當前e(x)第一位為1，則g(x)和e(x)分別對應的5位數(shù)據(jù)模2相加，g(x)逆時針移動一位；若當前e(x)第一位為0，則g(x)直接逆時針移動直到e(x)第一位對應位為1，g(x)和e(x)分別對應的5位數(shù)據(jù)模2相加，g(x)逆時針移動一位；轉②。(g(x)最多逆時針移動25位)

由以上算法結構說明可得如下結論：本算法結構簡單，只需要15位移位寄存器存儲接收碼，由生成多項式循環(huán)模2相加接收碼，當錯誤位數(shù)小于等于1時，即得錯誤位，類似打地鼠游戲。相對文獻[2]中給出了BCH(15,11)錯誤圖樣查表法，不需要預先存儲錯誤圖樣；譯碼時，不需要查找，匹配，速度快，資源占用少，效率較高。

4 MATLAB仿真

仿真程序如下：

%BCH(15,11,1)

msg=gf(randint(1,11),1):%information code

c=bchenc(msg,15,11);%encode

n=gf([010000000000000],1);%1bit error

r=c+n;%receive code

e=r;

g=gf([1 0 0 1 1]);%generator polynomial

m=sum(e～=0);k=0;

while m>1 & k<2

k=k+1；

for j=1:11

if e(j)==1

e(j)=0;e(j+3)= e(j+3)+1; e(j+4)= e(j+4)+1;

end

if sum(e～=0)<2

disp('OK r(x)=e(x) mod(g(x))');e,

return

end

end

for j=12:15

if e(j)==1

e(j)=0; j1=mod(j+3,15); j2=mod(j+4,15);

e(j1)=e(j1)+1; e(j2)=e(j2)+1;

end

if sum(e～=0)<2

disp('OK r(x)=e(x) mod(g(x))');e,

return

end

end

end

disp('OK c=r+e');c=r+e;

圖5 BCH(15,11)循環(huán)長除法實現(xiàn)結構圖

仿真分析：運用本仿真程序對所有211=1024個原碼，及211·15=15360個含有1個錯誤位的接收碼進行仿真驗算，均能正確糾錯，由此可證明本算法有效可行。

5 結束語

隨著北斗導航系統(tǒng)的逐步完善和全面提供各種應用服務,設計體積小，功耗低的接收機芯片至關重要，而BCH(15,11)譯碼算法在研制接收機中具有重要作用。本文提出的基于循環(huán)長除法的BCH(15,11)譯碼算法操作簡單，易于軟硬件實現(xiàn)，非常適合在北斗系統(tǒng)導航接收機中工程化應用。