SBAS 衛(wèi)星信號(hào)的Viterbi 譯碼優(yōu)化方案

林木龍,易清明

(暨南大學(xué) 電子工程系,廣州510632)

1 引 言

SBAS(Satellite-based Augmentation System )是利用地球同步衛(wèi)星(GEO)作為媒介,提供差分GPS 校正值和完好性數(shù)據(jù)的系統(tǒng)[1]。其數(shù)據(jù)速率由250 bit/s經(jīng)由卷積編碼后變換為500 bit/s, 用于與1 kHz的GPS C/A 碼歷元保持同步并向用戶廣播。SBAS 衛(wèi)星信號(hào)采用(2,1,7)卷積編碼,是遙測(cè)信道編碼在衛(wèi)星通信系統(tǒng)中的一種典型應(yīng)用。

另一方面,用戶接收到衛(wèi)星信號(hào)后,必須經(jīng)過正確譯碼恢復(fù)出衛(wèi)星信息,才能順利進(jìn)行導(dǎo)航校正。對(duì)于SBAS 信號(hào),傳統(tǒng)的方法就是直接進(jìn)行Viterbi 譯碼。考慮到實(shí)際應(yīng)用中,用戶需要接收多個(gè)SBAS 衛(wèi)星信號(hào),假如等接收齊500 bit的數(shù)據(jù)后才開始譯碼,硬件的實(shí)時(shí)性就比較差。因此,本文研究了一種優(yōu)化的Viterbi 譯碼方案,在不降低譯碼性能的前提下,盡可能地滿足實(shí)時(shí)性要求,并可以為硬件節(jié)省資源。

2 卷積碼編碼原理

卷積碼是一種性能優(yōu)越的信道編碼,由于具備較強(qiáng)的糾錯(cuò)能力,在各種數(shù)字系統(tǒng)中得到了廣泛應(yīng)用。其一般的表示形式為(n, k,N),即由k 位信息輸入編碼為n 位輸出,N 為編碼約束長(zhǎng)度,R =k/n是編碼效率,對(duì)應(yīng)的編碼器有2N-1種狀態(tài)。卷積編碼后的n bit數(shù)據(jù)不僅與當(dāng)前時(shí)刻的k 個(gè)信息比特有關(guān),還與前N-1 個(gè)時(shí)刻的信息比特有關(guān)。編碼過程中相互關(guān)聯(lián)的碼元有N×n 個(gè),糾錯(cuò)能力隨著N 的增加而增強(qiáng),誤碼率則隨著N 的增加而下降。

SBAS 衛(wèi)星信號(hào)采用的是(2,1,7)卷積編碼,其移位寄存器有6 級(jí),編碼器示意圖如圖1 所示。其中,生成多項(xiàng)式分別為G1=(1111001)2=(171)8,G2=(1011011)2=(133)8。

圖1 SBAS 信號(hào)卷積編碼示意圖Fig.1 Convolutional code for SBAS signal

每輸入一個(gè)比特,通過6 級(jí)移位寄存器中對(duì)應(yīng)G1、G2 路徑處理后,輸出2 bit的碼組,于是SBAS 信號(hào)250 bit/s的輸入轉(zhuǎn)化為了500 bit/s的輸出。移位寄存器共有6 位,存儲(chǔ)的是前6 bit的輸入值,對(duì)應(yīng)的狀態(tài)有(000000 ～111111)64 種,當(dāng)前輸入的比特為0或1 將決定狀態(tài)間不同的跳轉(zhuǎn),對(duì)應(yīng)的2 bit輸出則是由當(dāng)前的輸入比特及移位寄存器的狀態(tài)共同決定的,即每一次2 bit 輸出不僅與當(dāng)前的1 bit輸入有關(guān),還與之前的6 bit輸入有關(guān)。用十進(jìn)制來表示狀態(tài),比如i=0 ～63 對(duì)應(yīng)表示狀態(tài)S 0 ～S 63,則可以用下面的公式來表示編碼時(shí)寄存器狀態(tài)的跳轉(zhuǎn):

式中, i 表示當(dāng)前狀態(tài), %表示取模,b0 表示輸入的比特值0 或1,j 為跳轉(zhuǎn)后的狀態(tài)。如輸入b0 為0,則S 0 和S 32 轉(zhuǎn)移到S0 狀態(tài),b0 為1 則有S0 和S32 轉(zhuǎn)移到S 1 狀態(tài)。

限于篇幅,下文以(2,1,3)的卷積編碼為例,并通過直觀的網(wǎng)格圖來描述其編碼過程。圖2 表示的是6 bit輸入對(duì)應(yīng)的可能路徑,其中實(shí)線表示輸入0時(shí)所走的分支,虛線表示輸入1 時(shí)所走的分支,編碼時(shí)只需從起始狀態(tài)開始依次選擇路線并讀出輸出即可。假設(shè)從a 狀態(tài)開始,輸入為[1 0 1 1] ,則可由圖2 中讀出輸出為[11 10 10 01] 。

圖2 (2, 1,3)卷積編碼網(wǎng)格圖Fig.2 Lattice of(2,1,3)convolutionanl code

3 Viterbi 譯碼原理及其優(yōu)化處理

3.1 Viterbi 譯碼基本原理

卷積碼的譯碼方式有門限譯碼、序列譯碼和Viterbi 譯碼[2]。Viterbi 譯碼具有最佳性能,本文對(duì)其進(jìn)行研究并作優(yōu)化處理,用于實(shí)現(xiàn)對(duì)SBAS 衛(wèi)星信號(hào)的卷積碼進(jìn)行譯碼。

Viterbi 譯碼采用最大似然譯碼算法,即在所有可能的碼字序列中選取一條使得似然函數(shù)極大的碼字序列作為發(fā)送碼的估計(jì)。仍以圖2 為例,圖中共有2k(N-1)=4 種狀態(tài),每個(gè)狀態(tài)有2 條支路到達(dá),也有2 條支路引出。前N-1 條連續(xù)支路的路徑互不相交,即最初的2N-1條路徑各不相同,當(dāng)接收到第N 條支路時(shí),每條路徑都有2 條支路延伸到第N 級(jí)上,而第N 級(jí)上的每2 條支路又都匯聚到一個(gè)狀態(tài)[3]。通過比較每個(gè)狀態(tài)到達(dá)的2 條路徑的漢明距累加值,丟棄漢明距較大的路徑同時(shí)保持較小那條,最終到第N 級(jí)只剩下2N-1條路徑,稱之為幸存路徑。在此過程中,挑選的路徑及其漢明距累加值都需要保存下來。另外,由于每個(gè)狀態(tài)引出2 條支路,故其后各級(jí)的延伸也都增加1 倍,但經(jīng)過漢明距累加值的比較選擇后,丟棄了較大的那一半,剩下的路徑總數(shù)保持常數(shù)。簡(jiǎn)單來看,Viterbi 譯碼的過程就是一個(gè)“加、比、選”的過程,最終結(jié)果便是選擇一條漢明距最小的發(fā)送路徑,即路徑度量最大的路徑。

3.2 優(yōu)化處理

標(biāo)準(zhǔn)的譯碼算法要求路徑回到初始的全零狀態(tài),這必須在傳輸中最后添加N-1 個(gè)0,從而損失了(N-1)/(N+L -1), L 為輸入序列長(zhǎng)度。雖然加大L 值可以減少這種資源損失,但用于寄存路徑及其度量值的存儲(chǔ)器也隨之成正比增大,同時(shí)譯碼延遲也會(huì)加大,故必須作出一些折衷考慮。

另外,對(duì)于SBAS 信號(hào)500 bit/s的數(shù)據(jù)量,若等接收齊全部信息再進(jìn)行譯碼,中間會(huì)浪費(fèi)不少時(shí)間,特別是硬件同時(shí)處理幾個(gè)信號(hào)的時(shí)候。因此考慮通過截?cái)嘧g碼器路徑存儲(chǔ)的方法,達(dá)到一邊接收一邊開始譯碼的目的,從而提高處理效率,但這樣的處理顯然其譯碼性能會(huì)有所下降。考慮到卷積碼前后時(shí)刻碼字的相關(guān)性,由截?cái)嘣斐傻男阅芟陆悼梢酝ㄟ^利用下一段數(shù)據(jù)包含的信息來補(bǔ)償。經(jīng)驗(yàn)表明,若x(每條幸存路徑最近的x(x

從理論上分析,截?cái)嗪蟮漠?dāng)前段碼流傳遞給下一段截?cái)啻a流的初始狀態(tài)主要有兩種方式:傳遞漢明距累加值和傳遞最佳路徑的終止態(tài)。前者是將當(dāng)前碼流譯碼結(jié)束時(shí)保留的2N-1條路徑對(duì)應(yīng)的2N-1個(gè)漢明距累加值作為下一段碼流譯碼的初始漢明距;后者則僅僅把2N-1條路徑中最佳路徑的終止態(tài)保存下來,作為下一段譯碼序列的初始態(tài)。顯然,保留最佳路徑終止態(tài)的方式可以大大節(jié)省硬件資源。舉個(gè)例子,SBAS 信號(hào)有64 個(gè)狀態(tài),假如存儲(chǔ)一條路徑的漢明距需8 bit,存儲(chǔ)一個(gè)狀態(tài)需6 bit, 硬件同時(shí)處理5 個(gè)SBAS 信號(hào),則傳遞漢明距累加值的方式需要64×8×5=2 560 bit,而最佳狀態(tài)只有一個(gè),僅需1×6×5=30 bit,這樣直接可以節(jié)省2 000多個(gè)寄存器。

因此,本文根據(jù)應(yīng)用的需求,對(duì)SBAS 信號(hào)的Viterbi 譯碼進(jìn)行有性能補(bǔ)償?shù)姆侄翁幚?以期達(dá)到和500 bit全段譯碼相當(dāng)?shù)淖g碼效果,同時(shí)能夠減少時(shí)間和資源消耗。

3.3 仿真模型

在Matlab 環(huán)境下,針對(duì)1 s的數(shù)據(jù)量(即500 bit)進(jìn)行Viterbi 譯碼。為了在較短時(shí)間內(nèi)盡快處理數(shù)據(jù),采取以“64 bit輸入-32 bit輸出”為單元的分段譯碼方式。為了確定這種分段譯碼方式的性能,需要通過與全段譯碼的性能作對(duì)比參考。具體的建模仿真思路如圖3 所示。

圖3 SBAS 信號(hào)Viterbi 譯碼建模仿真框架Fig.3 SBAS signal Viterbi decoding model

將250 bit 輸入建立的(2,1,7)卷積編碼器模型,輸出的500 bit序列碼,經(jīng)過翻轉(zhuǎn)位置可設(shè)定的比特翻轉(zhuǎn)模塊后,同時(shí)送給500 bit全段譯碼器和64 bit分段譯碼器,最后把兩者的譯碼結(jié)果均與起始的250 bit原碼比對(duì),比較譯碼準(zhǔn)確度。其中,比特翻轉(zhuǎn)模塊可實(shí)現(xiàn)500 bit序列中任意個(gè)數(shù),任意位置處比特?cái)?shù)值的翻轉(zhuǎn)操作,目的是在譯碼器的輸入序列當(dāng)中引入錯(cuò)誤,以500 bit全段譯碼的糾錯(cuò)能力為基準(zhǔn),來檢測(cè)64 bit分段Viterbi 譯碼處理的糾錯(cuò)能力。

整個(gè)仿真體系中, 比對(duì)模型的做法是將隨機(jī)100 次的譯碼結(jié)果分別同250 bit原碼比對(duì),記錄下每次比對(duì)過程中錯(cuò)誤譯碼的比特個(gè)數(shù)diff(1),diff(2),diff(3), …,diff(100),以及100 次譯碼無法全部譯對(duì)的次數(shù)T ,統(tǒng)計(jì)出的譯碼準(zhǔn)確率η定義如下:

仿真過程的具體做法是:針對(duì)比特出錯(cuò)的情況對(duì)64 bit進(jìn)行比特補(bǔ)償,即譯碼64+b,但輸出只取前32 bit,b 為下一段64 bit開頭部分的比特?cái)?shù),對(duì)于最后一段不夠64 bit的情況,該模型對(duì)其單獨(dú)處理,否則不足64 bit部分會(huì)被默認(rèn)添0,導(dǎo)致最后譯碼出現(xiàn)幾比特錯(cuò)誤。

4 仿真結(jié)果

針對(duì)500 bit 全段譯碼糾錯(cuò)能力限度的測(cè)試,采用的是遍歷1 ～500 bit位置的方法,在比特翻轉(zhuǎn)模塊中分別設(shè)定0 bit錯(cuò)誤、任意1 bit錯(cuò)誤、任意連續(xù)2 bit錯(cuò)誤、任意連續(xù)3 bit錯(cuò)誤、任意連續(xù)4 bit錯(cuò)誤、任意連續(xù)5 bit錯(cuò)誤、任意連續(xù)6 bit錯(cuò)誤,測(cè)試結(jié)果如表1 所示。

表1 500 bit 全段譯碼糾錯(cuò)能力測(cè)試說明Tab le 1 Decoding error-correcting ability for 500 bit

由信道編碼定理可知,卷積碼中增大約束長(zhǎng)度可以降低誤碼率,但約束長(zhǎng)度不能取得很大,因此Viterbi 譯碼不可能使錯(cuò)誤概率任意小。對(duì)于連續(xù)6 bit錯(cuò)誤的情況,整段序列都無法保證100%能完全糾錯(cuò),說明已經(jīng)到了正確譯碼的糾錯(cuò)極限。同時(shí),由表1 可知,對(duì)于連續(xù)5 bit錯(cuò)誤以內(nèi)的情況,500 bit全段序列譯碼僅在后面的30 bit范圍內(nèi)譯碼糾錯(cuò)較差。同樣,對(duì)于每段64 bit的后面幾個(gè)比特處,譯碼糾錯(cuò)能力也較差,但通過補(bǔ)償?shù)姆椒?達(dá)到和全序列譯碼一樣的譯碼效果。下面給出本文的處理方法(加補(bǔ)償和不加補(bǔ)償兩種情況)與500 bit全段譯碼的對(duì)比結(jié)果,見圖4 ～7。

圖4 最后52 bit 分段序列的不同處理結(jié)果Fig.4 Different processing results for the last 52 bit

圖5 單比特錯(cuò)誤譯碼結(jié)果Fig.5 One bit error decoding result

圖6 連續(xù)2 bit 錯(cuò)誤譯碼結(jié)果Fig.6 Two successive bit error decoding resu lt

圖7 連續(xù)3 bit 錯(cuò)誤譯碼結(jié)果Fig.7 Three successive bit error decoding result

上述結(jié)果相應(yīng)的比特錯(cuò)誤配置在分段序列的銜接處附近,其他位置的比特錯(cuò)誤不用補(bǔ)償也有相當(dāng)?shù)淖g碼糾錯(cuò)能力。連續(xù)4 bit、5 bit錯(cuò)誤的情況與連續(xù)3 bit錯(cuò)誤結(jié)果類似,仿真圖不再給出。仿真結(jié)果表明,對(duì)于全段譯碼能正常糾錯(cuò)的所有情況,分段加性能補(bǔ)償?shù)奶幚矸椒軌颢@得與之同等的譯碼性能,同時(shí)減少了譯碼過程的存儲(chǔ)容量,這對(duì)于SBAS信號(hào)Viterbi 譯碼器的硬件設(shè)計(jì)具有很好的參考意義。當(dāng)然,這里僅是優(yōu)化方案在算法級(jí)的仿真,真正應(yīng)用到硬件上還需進(jìn)行充分的驗(yàn)證與仿真。

[1] Kaplan E D.GPS 原理與應(yīng)用[M] .寇艷紅, 譯.北京:電子工業(yè)出版社, 2008.

Kaplan E D.Understanding GPS Princip les and Applications[M] .Translated by KOU Yan -hong.Beijing:Publishing House of Electronics Industry, 2008.(in Chinese)

[2] 韓可,鄧中亮,施樂寧.(2,1,7)卷積碼Viterbi 譯碼器FPGA實(shí)現(xiàn)方案[J] .現(xiàn)代電子技術(shù),2007(15):90-92,96.

HAN Ke, DENG Zhong-liang, SHI Le-ning.Imp lement method with FPGA for Viterbi decoder of(2, 1, 7)convolutional code[ J] .Modern Electronics Technique, 2007(15):90-92,96.(in Chinese)

[3] 仇佩亮.信息論與編碼[M] .北京:高等教育出版社,2006.

QIU Pei-liang.Information theory and coding[M] .Beijing:Higher Education Press,2006.(in Chinese)