張超逸,劉海洋,李金海,孫金海,閻躍鵬
(1.中國科學(xué)院 微電子研究所,北京 100029; 2.中國科學(xué)院大學(xué),北京 100049)
基于可靠性的北斗系統(tǒng)BCH碼擦除譯碼算法
張超逸1,2,劉海洋1,李金海1,孫金海1,閻躍鵬1
(1.中國科學(xué)院 微電子研究所,北京 100029; 2.中國科學(xué)院大學(xué),北京 100049)
針對北斗衛(wèi)星導(dǎo)航系統(tǒng)中的BCH碼譯碼算法性能低下問題,本文提出了一種擦除譯碼算法。該算法根據(jù)硬判決矢量中各個位置的可靠性,構(gòu)造了一組各包含兩個擦除位置的矢量。采用擦除譯碼算法對這些矢量進行譯碼,并根據(jù)一定準(zhǔn)則選擇譯碼結(jié)果中的一個碼字作為譯碼輸出。為了提高算法效率,設(shè)計了一種可以減少譯碼矢量數(shù)目的終止機制。仿真結(jié)果表明,本文設(shè)計的終止機制可以在幾乎不損失性能的條件下,有效降低算法的復(fù)雜度。同傳統(tǒng)硬判決譯碼算法相比,提出的算法在增加少量額外復(fù)雜度的條件下,譯碼性能得到改善,從而實現(xiàn)了在譯碼性能和復(fù)雜度之間的良好折中,是實際接收機的良好選擇。
北斗系統(tǒng); BCH碼; 硬判決; 軟判決; 可靠性; 擦除譯碼
Abstract:An efficient decoding erasure algorithm for the improvement of the decoding performance of the BCH code in the BeiDou satellite navigation system is proposed in this paper. The algorithm is used to construct a group of vectors on the basis of the reliability of each position in the hard- decision vector. Each group of vectors contains two erasure locations, and each vector is decoded by the decoding erasure algorithm. One obtained code word is selected as the output of the proposed algorithm in accordance with certain rules. To improve the efficiency of the algorithm, a termination mechanism is developed to decrease the number of decoded vectors. Simulation results show that the designed termination mechanism can effectively reduce the complexity of the proposed algorithm with little performance degradation. The proposed algorithm outperforms the traditional hard- decision decoding algorithm with a negligible increase in complexity. Therefore, the proposed algorithm achieves good tradeoff between decoding performance and complexity and is thus a good choice for practical navigation receivers.
Keywords:BeiDou system; BCH code; hard decision; soft decision; reliability; decoding erasure
目前,北斗衛(wèi)星導(dǎo)航系統(tǒng)可向中國及其周邊區(qū)域提供全天候的定位、導(dǎo)航及授時服務(wù),北斗衛(wèi)星導(dǎo)航接收機的設(shè)計與開發(fā)也引起了學(xué)術(shù)界和工業(yè)界的廣泛興趣[1-2]。對于衛(wèi)星導(dǎo)航接收機而言,導(dǎo)航電文至關(guān)重要,其含有的衛(wèi)星基本導(dǎo)航信息、歷書信息以及與其他系統(tǒng)時間同步信息的準(zhǔn)確性直接決定了接收機的定位精度。為了增強導(dǎo)航電文的準(zhǔn)確性,北斗系統(tǒng)采用了一組循環(huán)BCH碼作為導(dǎo)航電文的前向糾錯碼[3]。因此,設(shè)計該BCH碼的高效譯碼方案具有非常重要的意義。當(dāng)前北斗系統(tǒng)中的BCH譯碼算法主要分為兩類:硬判決譯碼算法[4-5]和軟判決譯碼算法[6-8]。硬判決譯碼算法具有簡單、易于實現(xiàn)的優(yōu)點,也是北斗系統(tǒng)接口控制文件中推薦的譯碼算法,但是其譯碼性能相對較差。針對這一問題,多種軟判決譯碼算法被設(shè)計出來。同硬判決譯碼算法相比,這些算法的性能得到了改善,但由于復(fù)雜度的增加,在實現(xiàn)過程中往往會遇到許多困難。
除了這兩類算法,擦除譯碼也是線性分組碼(尤其是循環(huán)碼)的一種重要譯碼算法[9-13]??梢则炞C,北斗系統(tǒng)中的BCH碼最小漢明距離為3。由線性分組碼的性質(zhì)可知,擦除譯碼可以糾正包含有不超過2個擦除位置且其余位置沒有錯誤的任意接收矢量[14]。基于上述性質(zhì),本文提出了一種北斗系統(tǒng)BCH碼的高效譯碼算法。該算法將接收矢量每個位置的可靠性同硬判決矢量相結(jié)合,通過用擦除位替換掉硬判決矢量中的兩個位置,構(gòu)造出一組矢量。此后,對每個構(gòu)造出來的矢量分別采用擦除譯碼算法進行譯碼,并根據(jù)一定準(zhǔn)則選擇譯碼結(jié)果中的一個碼字作為譯碼輸出。此外,為了提高算法的效率,提出了一種可以減少譯碼矢量數(shù)目的機制。
北斗系統(tǒng)中的前向糾錯碼采用循環(huán)BCH碼,碼長和信息長度分別為15和11,記為BCH(15,11)碼[4],其生成多項式為
g(x)=x4+x+1
(1)
由于該碼是循環(huán)碼,其編碼可以通過線性移位寄存器電路有效實現(xiàn)[15-16]。具體編碼步驟如下:
1)將待編碼的信息多項式m(x)乘以xr,其中r=deg(g(x))=4。
2)用xrm(x)除以生成多項式g(x),得到余式b(x)。
3)構(gòu)造碼字c(x)=b(x)+xrm(x)。
BCH(15,11)碼的最小漢明距離為3,采用硬判決算法可以糾正出現(xiàn)在接收矢量中任意位置的單個錯誤。硬判決譯碼算法可以通過基于校正子的查找表實現(xiàn),主要包括如下步驟[4]:
1)將接收矢量v除以生成多項式g,得到余式r,余式即該接收矢量對應(yīng)的校正子。
2)根據(jù)校正子r查表得到相對應(yīng)的錯誤圖樣e。
可以驗證,BCH(15,11)碼是完備碼(perfect code)[14]。也就是說,對于長度為15的任意硬判決接收矢量v,在BCH(15,11)碼中存在唯一的一個碼字c,使得v和c之間的漢明距離不超過1。這時,用硬判決譯碼算法對接收矢量v進行譯碼得到的結(jié)果即是碼字c。這種譯碼方式的一個缺點是當(dāng)接收矢量錯誤數(shù)大于1時會出現(xiàn)譯碼失敗。
為了解釋上述現(xiàn)象,考慮下面的例子。假定通過信道發(fā)送碼字[1 1 1 0 0 0 1 0 0 1 0 1 0 0 0],在接收端的硬判決矢量為[1 1 1 0 1 0 1 1 0 1 0 1 0 0 0]。可以看出,接收矢量在第5和第8兩個位置上出現(xiàn)了錯誤。這時通過硬判決譯碼算法得到的碼字為[1 1 1 0 1 0 1 1 1 1 0 1 0 0 0]。同發(fā)送碼字相比,譯碼結(jié)果出現(xiàn)了3個錯誤,比接收矢量還多出一個錯誤。因此,硬判決譯碼算法僅在信道噪聲相對較低時有效,其編碼增益也相對有限。
本節(jié)提出BCH(15,11)碼的一種基于可靠性的擦除譯碼算法,并設(shè)計了一種能提高譯碼算法效率的機制。
由第1節(jié)可知,任意包含有超過1個錯誤的接收矢量無法通過硬判決譯碼算法正確糾錯。下面分析接收矢量中出現(xiàn)不同錯誤個數(shù)的概率。假定一個BCH(15,11)碼字經(jīng)過二進制相移鍵控(BPSK)調(diào)制后通過加性高斯白噪聲(AWGN)信道傳輸。由文獻[17]可知每個位置的錯誤概率為
(2)
其中
(3)
式中:R=11/15為碼率,Eb/N0為信噪比(SNR)。
由概率論可知[17]:
(4)
表1不同信噪比下接收矢量錯誤概率
Table1TheerrorprobabilitiesofareceivedvectoratdifferentSNRs
SNR/dBP(E=0)P(E=1)P(E=2)P(E>2)20.37270.38020.18100.066130.51260.35030.11170.025440.65850.27900.05520.0074
對于最小漢明距離為dmin的BCH碼,擦除譯碼算法可以糾正含有e個擦除位置且其余位置沒有錯誤的所有組合,需要滿足如下關(guān)系[14]:
e+1≤dmin
(5)
由于BCH(15,11)碼的最小漢明距離為3,擦除譯碼算法可以糾正包含有2個擦除位置且其余位置沒有錯誤的接收矢量。這說明任意包含有兩個錯誤的硬判決矢量在準(zhǔn)確得到其錯誤位置的情況下,可以通過擦除譯碼算法得到糾正。文獻[14]中給出了擦除譯碼算法的主要步驟:1)通過在一個矢量的兩個位置上用擦除位替換掉原先的值構(gòu)造一個新的矢量;2)分別設(shè)置擦除位的值為00和11后各自采用硬判決譯碼算法進行兩次譯碼,得到兩個碼字;3)統(tǒng)計這兩個碼字在非擦除位置上的值與之前構(gòu)造出的矢量對應(yīng)位置上的值相同的個數(shù),選取相同個數(shù)多的碼字作為譯碼結(jié)果輸出。
在實際中,由于錯誤位置無法提前獲得,從而限制了上述譯碼方法的應(yīng)用。但是,北斗系統(tǒng)可以提供不同位置的可靠性信息,該信息由導(dǎo)航接收機中的跟蹤通道實時獲得。接收機完成某顆衛(wèi)星的捕獲后,轉(zhuǎn)入跟蹤狀態(tài),相應(yīng)衛(wèi)星的跟蹤通道經(jīng)過解旋、解擴、積分累加等數(shù)字信號處理算法后得到當(dāng)前衛(wèi)星信號上調(diào)制的數(shù)據(jù)比特觀測值。這一觀測值通常不是僅有兩個電平0或1的硬判決量,而是可量化為具有一定位寬的多個電平值。對每個數(shù)據(jù)比特,其觀測值取符號位即得到硬判決結(jié)果,而每個觀測值的絕對值大小則反映了該判決的可靠性。觀測值越大,表明該比特的判決結(jié)果越可靠;反之,表明判決結(jié)果越不可靠。因此,可以將可靠性信息與擦除譯碼相結(jié)合,設(shè)計出一種高效的譯碼算法。
該算法首先選擇接收矢量中的L(L≥2)個不可靠位置。然后,每次選取這L個位置中的任意兩個位置當(dāng)作擦除位置來構(gòu)造一個新的矢量。最后,對每個構(gòu)造出的矢量采用上述的擦除譯碼算法進行譯碼。不難看出,構(gòu)造的矢量和需要譯碼的矢量數(shù)目分別為N和2N,其中
(6)
為便于實現(xiàn),假定N個位置按照其可靠性進行字典排序[18]。
記某個譯碼矢量為vk(l),其中l(wèi)=0表明擦除位被設(shè)置為00,l=1表明擦除位被設(shè)置為11,k=1,2,…,N。這2N個譯碼矢量依次為v1(0)、v1(1)、v2(0)、v2(1)、…、vN(0)、vN(1),進行硬判決譯碼后得到2N個碼字,分別為c1(0)、c1(1)、c2(0)、c2(1)、…、cN(0)、cN(1)。記符號A(ck(l),vk(l))表示在非擦除位置上ck(l)與vk(l)值相同的個數(shù),其中k=1,2,…,N,l=0,1。算法選取A(ck(l),vk(l))具有最大值的ck(l)作為輸出碼字。
可以看出,譯碼矢量的總數(shù)2N與L的呈平方關(guān)系增加,為了減少譯碼矢量的個數(shù),本文進一步設(shè)計了一種終止機制(termination mechanism, TM)。在擦除譯碼過程中,若錯誤位置正好與擦除位置一致時,那么在非擦除位置的譯碼結(jié)果與接收矢量應(yīng)是完全相同的[14]。
四是加強監(jiān)督隊伍建設(shè)。“打鐵還需自身硬”,推進監(jiān)管體制機制的創(chuàng)新,需要運用信息化手段,提升監(jiān)督人員業(yè)務(wù)和技術(shù)水平,使監(jiān)管執(zhí)法標(biāo)準(zhǔn)化、規(guī)范化,促使工程質(zhì)量持續(xù)健康發(fā)展。同時應(yīng)鼓勵采取政府購買服務(wù)的方式,讓社會力量參與監(jiān)督檢查活動,解決因編制受限造成監(jiān)管力量不足的問題。
假定對所有2N個構(gòu)造出的矢量進行順序譯碼。對某一個構(gòu)造出的矢量vk(l),如果譯碼得到的碼字ck(l)與vk(l)在所有13個非擦除位置上的值完全一致,即A(ck(l),vk(l))=13,這時認(rèn)為譯碼輸出碼字為ck(l),同時終止譯碼過程。這種終止機制的有效性將在下一節(jié)中通過仿真進行驗證。
綜上所述,基于可靠性的北斗系統(tǒng)BCH(15,11)碼的擦除譯碼步驟描述如下:
輸入:硬判決矢量v;每個位置的可靠性信息R;參數(shù)L。
1)根據(jù)硬判決矢量v中每個位置的可靠性信息R選擇L個不可靠位置。
2)構(gòu)造一組矢量vk(l)(k=1,2,…,N;l=0,1)。
3)對這些構(gòu)造出來的矢量順序地進行硬判決譯碼,得到譯碼碼字ck(l)。
基于可靠性的北斗系統(tǒng)BCH(15,11)碼的擦除譯碼算法的復(fù)雜度主要集中在步驟1)到步驟3)。在步驟1)中,找到L個不可靠位置需要進行15L次比較。在步驟3)中,復(fù)雜度正比于譯碼矢量的平均數(shù)目。通常情況下譯碼矢量數(shù)目為L(L-1),但應(yīng)用設(shè)計的終止機制后,能有效減少譯碼矢量的數(shù)目。在下一節(jié)可以看到,在合適的信噪比范圍內(nèi),采用終止機制后的平均譯碼矢量的數(shù)目很少。例如,當(dāng)L=4時,算法中的譯碼矢量數(shù)目不會超過2個,同傳統(tǒng)的硬判決譯碼算法相比較,本文提出的算法僅多增加60次比較操作和1次硬判決譯碼操作,因此該算法具有低復(fù)雜度的優(yōu)點。
通過仿真確定參數(shù)L的取值,并評估設(shè)計的終止機制。仿真中每個位置上的可靠性信息采取6 bit均勻量化[17]。為了進行比較,本文同時仿真了北斗系統(tǒng)接口控制文件中推薦的硬判決譯碼算法和文獻[8]中的最大似然軟判決譯碼算法的譯碼性能。
圖1給出了參數(shù)L取不同值時,提出的基于可靠性的擦除譯碼算法的性能。從圖1中可以看出,提出的譯碼算法的性能隨著L取值的增加而獲得改善。特別地,當(dāng)L=4時算法的性能相對于L=2和L=3時的性能有較大改善,而當(dāng)L=5時算法的性能相對于L=4時的性能改善相對較小。因此,在實際中建議參數(shù)L取值為4。
圖1 提出的譯碼算法在L=2,3,4,5時的性能比較Fig.1 Performance comparisons of the proposed algorithm if L=2,3,4,5
圖2對比了BCH(15,11)碼采用不同譯碼算法的性能。
圖2 BCH(15,11)碼采用不同譯碼算法的性能Fig.2 Performances of BCH(15,11) code under different decoding algorithms
可以看出,本文提出的算法譯碼性能明顯優(yōu)于傳統(tǒng)的硬判決譯碼算法。例如,對任意的譯碼算法,總會存在一個編碼閾值,當(dāng)?shù)陀谶@個閾值時,編碼無效。對于實際系統(tǒng),應(yīng)當(dāng)設(shè)計譯碼算法,使得編碼閾值盡量地低[18-19]。由圖2中可以看出,本文提出的算法相對于傳統(tǒng)硬判決譯碼算法的編碼閾值性能得到了改善。如傳統(tǒng)的硬判決譯碼算法的編碼閾值約為4 dB,而當(dāng)選取L=4時本文提出的算法的編碼閾值約為2.2 dB。
為了提供首次定位服務(wù),要求導(dǎo)航電文的誤比特率必須小于10-3[20]。從圖2中可以看出,在滿足誤比特率小于10-3條件下,當(dāng)選取L=4時,提出的算法同傳統(tǒng)的硬判決譯碼算法和未編碼BPSK相比,性能分別提升0.8 dB和1.8 dB左右。
另外,本文提出的算法在性能上接近最大似然軟判決譯碼算法(即在BCH(15,11)碼中選擇碼字c,使得內(nèi)積
圖3對比了采用終止機制和不采用終止機制時提出的譯碼算法的性能。從圖中可以看出,采用了終止機制后,算法的性能幾乎沒有任何損失。表2給出了在不同信噪比下的譯碼矢量的平均數(shù)目??梢钥闯?,提出的算法的譯碼矢量的平均數(shù)目不多,并且隨著信噪比的提高,譯碼矢量的平均數(shù)目減少。這說明了采用終止機制后算法的平均復(fù)雜度會很低,從而驗證了終止機制的有效性。
圖3 提出的終止機制的性能評估Fig.3 Performance evaluation for the proposed TM
綜上所述,本文提出的基于可靠性的擦除譯碼算法是實際導(dǎo)航接收機的良好選擇。
表2不同信噪比下譯碼矢量平均數(shù)目
Table2TheaveragenumberofdecodedvectorsunderdifferentSNRs
LSNR/dB23456732.2701.8271.4711.2991.2391.22842.8662.1191.5821.3271.2431.229
1)基于可靠性的高效擦除譯碼算法在增加少量復(fù)雜度的基礎(chǔ)上能明顯改善譯碼性能,避免了傳統(tǒng)硬判決譯碼算法性能相對較差以及軟判決譯碼算法復(fù)雜度高的缺點。
2)對算法的參數(shù)L進行了仿真,結(jié)果表明L取4時能最大程度平衡性能提升與復(fù)雜度增加之間的矛盾,是一個合理的選擇。
3)本文提出的譯碼算法在性能上同傳統(tǒng)的硬判決譯碼算法和未編碼BPSK相比有明顯提升,同最大似然軟判決譯碼算法相比性能接近。
4)提出了一種譯碼算法終止機制,使得在算法性能幾乎沒有任何損失的條件下有效減少譯碼矢量數(shù)目。
5)復(fù)雜度分析表明,本文提出的算法操作簡單,易于通過軟硬件加以實現(xiàn),非常適合在北斗系統(tǒng)導(dǎo)航接收機(特別是低成本接收機)中應(yīng)用。
[1] 中國衛(wèi)星導(dǎo)航系統(tǒng)管理辦公室. 北斗衛(wèi)星導(dǎo)航系統(tǒng)發(fā)展報告[J]. 國際太空, 2012(4): 6-11. China satellite navigation office. Report on the development of BeiDou navigation satellite system[J]. Space international, 2012(4): 6-11.
[2] 吳海玲, 高麗峰, 汪陶勝, 等. 北斗衛(wèi)星導(dǎo)航系統(tǒng)發(fā)展與應(yīng)用[J]. 導(dǎo)航定位學(xué)報, 2015, 3(2): 1-6. WU Hailing, GAO Lifeng, WANG Taosheng, et al. Development and application of Beidou navigation satellite system[J]. Journal of navigation and positioning, 2015, 3(2): 1-6.
[3] 王迪, 郝士琦, 朱斌. “北斗”2代B1I信號導(dǎo)航電文分析[J]. 航天電子對抗, 2013, 29(6): 30-32. WANG Di, HAO Shiqi, ZHU Bin. Analysis for navigation message of BeiDouII B1I signal[J]. Aerospace electronic warfare, 2013, 29(6): 30-32.
[4] 中國衛(wèi)星導(dǎo)航系統(tǒng)管理辦公室. 北斗衛(wèi)星導(dǎo)航系統(tǒng)空間信號接口控制文件公開服務(wù)信號B1I[EB/OL]. [2013-12-27]. http://www.beidou.gov.cn. China satellite navigation office. BeiDou navigation satellite system signal in space interface control document[EB/OL]. [2013-12-27]. http://www.beidou.gov.cn.
[5] MEGGITT J E. Error correction codes and their implementation for data transmission systems[J]. IEEE transactions on information theory, 1961, 7(4): 232-244.
[6] VARDY A, BEERY Y. Maximum- likelihood soft decision decoding of BCH codes[J]. IEEE transactions on information theory, 1994, 40(2): 546-554.
[7] MULLER B, HOLTERS M, ZOLZER U. Low complexity soft- input soft- output hamming decoder[C]//FITCE congress, Italy, 2011: 1-5.
[8] SUN J, LI J, LIU H, et al. Efficient soft- decision maximum- likelihood decoding of BCH code in the GNSS[J]. Journal of Harbin Institute of Technology (New Series), 2015, 22(1): 54-58.
[9] STEVENS P. Error- erasure decoding of binary cyclic codes, up to a particular instance of the Hartmann- Tzeng bound[J]. IEEE transactions on information theory, 1990, 36(5): 1144-1149.
[10] SHAHRI H, TZENG K K. On error- and- erasure decoding of cyclic codes[J]. IEEE transactions on information theory, 1992, 38(2): 489-496.
[11] LIVA G, PAOLINI E, MATUZ B, et al. A decoding algorithm for LDPC codes over erasure channels with sporadic errors[C]//2010 48th Annual Allerton conference on communication, control, and computing, Allerton, 2010: 458-465.
[12] SONG S, LIN S, ABDEL K, et al. Burst decoding of cyclic codes based on circulant parity- check matrices[J]. IEEE transactions on information theory, 2010, 56(3): 1038-1047.
[13] PAOLINI E, LIVA G, MATUZ B, et al. Maximum likelihood erasure decoding of LDPC codes: pivoting algorithms and code design[J]. IEEE transactions on communications, 2012, 60(11): 3209-3220.
[14] MACWILLIAMS F J, SLOANE N J A. The theory of error correcting codes[M]. Amsterdam: North- Hooland publishing company, 1977: 185-186.
[15] 張彥, 李署堅, 崔金. 一種BCH碼編譯碼器的設(shè)計與實現(xiàn)[J]. 通信技術(shù), 2010, 43(12): 24-25+186. ZHANG Yan, LI Shujian, CUI Jin. Design and implementation of BCH encoder/decoder[J]. Communications technology, 2010, 43(12): 24-25+186.
[16] PETERSON W W. Encoding and error- correction procedures for the Bose- Chaudhuri codes[J]. IEEE transactions on information theory, 1960, 6(4): 459-470.
[17] PROAKIS J G. Digital communications[M]. 5th. New York: mcgraw- hill, 2007.
[18] LEISERSON C C E, RIVEST R R L, STEIN C, et al. Introduction to algorithms[M]. 3rd Ed. Massachuseus: MIT press and mcgraw- hill, 2009: 118-118.
[19] LIN S, COSTELLO D J. Error control coding: fundamentals and applications[M]. 2nd ed. Englewood Cliffs, NJ, USA: Prentice- Hall, 2004.
[20] KAPLAN E D, HEGARTY C J. Understanding GPS: principles and applications[M]. 2nd ed. Norwood, MA: Artech House, Inc, 2006.
Reliability-baseddecodingerasurealgorithmforBCHcodeintheBeiDousystem
ZHANG Chaoyi1,2, LIU Haiyang1, LI Jinhai1, SUN Jinhai1, YAN Yuepeng1
(1.Institute of Microelectronics, Chinese Academy of Sciences, Beijing 100029, China; 2.University of Chinese Academy of Sciences, Beijing 100049, China)
10.11990/jheu.201605010
http://www.cnki.net/kcms/detail/23.1390.u.20170427.1510.064.html
TN911.22
A
1006- 7043(2017)09- 1426- 05
2016-05-05. < class="emphasis_bold">網(wǎng)絡(luò)出版日期
日期:2017-04-27.
國家自然科學(xué)基金項目(61271423).
張超逸(1990-), 男,博士研究生; 閻躍鵬(1964-), 男,研究員,博士生導(dǎo)師.
張超逸,E- mail: zhangchaoyi@ime.ac.cn.
本文引用格式:張超逸,劉海洋,李金海,等. 基于可靠性的北斗系統(tǒng)BCH碼擦除譯碼算法[J]. 哈爾濱工程大學(xué)學(xué)報, 2017, 38(9): 1426-1430.
ZHANG Chaoyi, LIU Haiyang, LI Jinhai, et al. Reliability- based decoding erasure algorithm for BCH code in the BeiDou system[J]. Journal of Harbin Engineering University, 2017, 38(9): 1426-1430.