江 寶 安
(重慶郵電大學(xué)移通學(xué)院,重慶 401520 )
北斗衛(wèi)星導(dǎo)航系統(tǒng)(BDS)是中國獨立自主研制的全球衛(wèi)星導(dǎo)航系統(tǒng),可在全球范圍內(nèi)全天候、全天時地提供各類高精度、高可靠定位、導(dǎo)航、授時服務(wù),并具短報文通信能力。目前,我國正在實施北斗三號系統(tǒng)建設(shè),2020年將完成30顆衛(wèi)星發(fā)射組網(wǎng),全面建成北斗三號系統(tǒng)。
對衛(wèi)星導(dǎo)航接收機而言,導(dǎo)航電文的準(zhǔn)確性至關(guān)重要,其含有的衛(wèi)星導(dǎo)航基本信息直接決定了接收機的定位精度[1]。為了增強導(dǎo)航電文的準(zhǔn)確性,北斗系統(tǒng)采用了循環(huán)碼BCH(15,11)作為導(dǎo)航電文的前向糾錯碼[2]。因此,設(shè)計該BCH碼的高效譯碼方案具有重要的意義。 BCH一般譯碼算法主要分為兩類:硬判決譯碼算法[3]和軟判決譯碼算法[4,5]。 硬判決譯碼算法具有簡單、易于實現(xiàn)的優(yōu)點,也是北斗系統(tǒng)接口控制文件中推薦的譯碼算法,但是其譯碼性能相對較差。軟判決譯碼算法的性能雖然得到一定的提高,但是在實際應(yīng)用中由于復(fù)雜度的增加,會增大軟硬件實現(xiàn)成本,譯碼延遲等的不利影響?;趯嶋H應(yīng)用,硬判決譯碼算法得到優(yōu)先考慮。本文提出了一種基于長除法 的北斗系統(tǒng)BCH(15,11)碼的高效硬判決譯碼算法及實現(xiàn)結(jié)構(gòu)。本算法不需要存儲錯誤圖樣,也不需要解BM方程,只需要循環(huán)移位和模2相加,軟硬件實現(xiàn)簡單易行,適合接收機工程化實現(xiàn)和應(yīng)用。
導(dǎo)航電文采取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)得原碼。
綜上所述,譯碼算法采用的是錯誤圖樣查表法,需要預(yù)先存儲錯誤圖樣,譯碼時,查找,匹配費時,效率不高。
圖1 BCH(15,11,1)編碼框圖
圖2 BCH(15,11,1)譯碼框圖
表1 糾錯信號的 ROM 表
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:設(shè)發(fā)送碼是:c(x)=m(x)·g(x)=(x10+x9+x7+x)·(x4+x+1)=x14+x13+x9+x8+x7+x5+x2+x
假設(shè)接收碼是:r(x)=m(x)·g(x)=x14+x13+x9+x8+x7+x5+x4+x2+x,有 1位錯誤e(x)=x4,當(dāng)然接收端是不知道有這 1位錯誤的。由循環(huán)長除法得錯誤多項式如 圖 3 所示,得錯誤多項式e(x)=x4,糾錯得原碼。
圖3 例1長除法得e(x)
例2:實際應(yīng)用中通常采用系統(tǒng)碼形式,編碼方程為
c(x)=xn-km(x)+xn-km(x))mod(g(x))
設(shè)發(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
假設(shè)接收碼是:
r(x)=c(x)+e(x)=x14+x11+x5+
x4+x3+x2+1
錯誤位e(x)=x12,當(dāng)然接收端是不知道有這 1位錯誤的。由循環(huán)長除法得錯誤多項式如 圖 4 所示,得錯誤多項式e(x)=x-3=x12,糾錯得原碼。
圖4 例2長除法得e(x)
循環(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結(jié)束。
③若當(dāng)前e(x)第一位為1,則g(x)和e(x)分別對應(yīng)的5位數(shù)據(jù)模2相加,g(x)逆時針移動一位;若當(dāng)前e(x)第一位為0,則g(x)直接逆時針移動直到e(x)第一位對應(yīng)位為1,g(x)和e(x)分別對應(yīng)的5位數(shù)據(jù)模2相加,g(x)逆時針移動一位;轉(zhuǎn)②。(g(x)最多逆時針移動25位)
由以上算法結(jié)構(gòu)說明可得如下結(jié)論:本算法結(jié)構(gòu)簡單,只需要15位移位寄存器存儲接收碼,由生成多項式循環(huán)模2相加接收碼,當(dāng)錯誤位數(shù)小于等于1時,即得錯誤位,類似打地鼠游戲。相對文獻[2]中給出了BCH(15,11)錯誤圖樣查表法,不需要預(yù)先存儲錯誤圖樣;譯碼時,不需要查找,匹配,速度快,資源占用少,效率較高。
仿真程序如下:
%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)結(jié)構(gòu)圖
仿真分析:運用本仿真程序?qū)λ?11=1024個原碼,及211·15=15360個含有1個錯誤位的接收碼進行仿真驗算,均能正確糾錯,由此可證明本算法有效可行。
隨著北斗導(dǎo)航系統(tǒng)的逐步完善和全面提供各種應(yīng)用服務(wù),設(shè)計體積小,功耗低的接收機芯片至關(guān)重要,而BCH(15,11)譯碼算法在研制接收機中具有重要作用。本文提出的基于循環(huán)長除法的BCH(15,11)譯碼算法操作簡單,易于軟硬件實現(xiàn),非常適合在北斗系統(tǒng)導(dǎo)航接收機中工程化應(yīng)用。