高性能維特比在衛(wèi)星導(dǎo)航接收機(jī)中FPGA實(shí)現(xiàn)

摘要：衛(wèi)星定位接收機(jī)中卷積碼譯碼即維特比譯碼器，在處理器中面臨占有資源較多、處理時(shí)間過(guò)長(zhǎng)等問(wèn)題，為了減少處理器資源的占用和提高處理速度，采用并行加比選蝶形單元的的方法，在FPGA平臺(tái)上用硬件描述語(yǔ)言設(shè)計(jì)一種高性能維特比譯碼器，作為GPS L2頻點(diǎn)和GALILEO E1頻點(diǎn)接收機(jī)的通用譯碼器，在GPS和GALILEO接收機(jī)上運(yùn)用，大大減少資源使用，提高接收機(jī)的處理速度。
關(guān)鍵詞：Viterbi譯碼器；GPS／GALILEO接收機(jī)；卷積碼；FPGA

0 引言
    在現(xiàn)代通信系統(tǒng)中，要使信號(hào)能夠更可靠地在信道中傳輸，往往需要在信道編碼中采用糾錯(cuò)碼來(lái)降低信號(hào)受噪聲的影響，以降低傳輸?shù)恼`碼率。卷積碼及其Viterbi譯碼是常用的信道編碼方案。卷積碼在GNSS接收機(jī)中得到應(yīng)用，其中約束長(zhǎng)度K=7，碼率為1／2的卷積碼已經(jīng)成為商業(yè)衛(wèi)星通信系統(tǒng)中的標(biāo)準(zhǔn)編碼方法。在衛(wèi)星定位系統(tǒng)中，GPS L2頻點(diǎn)和GAILILEO E1的電文均采用卷積碼編碼，目前在定位接收機(jī)中用軟件進(jìn)行Viterbi譯碼較多，為了提高處理速度通用性，本文設(shè)計(jì)一種基于FPGA的通用高速Viterbi譯碼器，能作為GPS L2和GALILEO E1的電文的譯碼器，大大減少資源使用，提高接收機(jī)的處理速度和減少軟件復(fù)雜度，從而節(jié)約處理器的資源。

1 卷積編碼及Viterbi算法基本原理
    卷積碼包含由K個(gè)寄存器組(每組包括k個(gè)比特，k通常取1)構(gòu)成的移位寄存器和n個(gè)模2加法器，其中K是約束長(zhǎng)度，編碼器的輸出由當(dāng)前輸入數(shù)據(jù)和寄存器組中的數(shù)據(jù)共同決定。對(duì)于GPS L2和GALILEOE1均為(2，1．7)卷積碼，其生成多項(xiàng)式為G=(171，133)，電路圖如圖1所示。(2，1，7)卷積碼編碼器由6個(gè)延時(shí)器(圖1中的q-1模塊，可用寄存器實(shí)現(xiàn))和兩個(gè)模2加法器組成，它的編碼約束度為7，碼率為1／2，即輸入端輸入1 b信息，輸出端輸出2 b編碼信息，并分為上、下兩路并行輸出。

    對(duì)信號(hào)進(jìn)行卷積編碼后，通常采用Viterbi算法(VA)譯碼。Viterbi算法是對(duì)于卷積碼的最大似然譯碼，即利用概率譯碼。1967年Viterbi第一個(gè)提出了這個(gè)算法，F(xiàn)orney對(duì)這種算法及其性能做了可讀強(qiáng)、見(jiàn)解深刻的描述。最大似然譯碼函數(shù)，就是在已知收到的信道輸出序列，找到最有可能的傳輸序列，即通過(guò)網(wǎng)格圖找出一條路徑對(duì)應(yīng)，要求路徑輸出的碼序列具有對(duì)數(shù)最大值。對(duì)于二進(jìn)制對(duì)稱信道來(lái)說(shuō)，函數(shù)的最大化等價(jià)于在網(wǎng)格圖中找到與接收序列之間有最小漢明距離的路徑。
    Viterbi算法是通過(guò)動(dòng)態(tài)規(guī)劃的方法找出網(wǎng)格圖中具有最大度量的最大似然路徑，即局部最優(yōu)等效全局最優(yōu)。在每一步中，它將進(jìn)入每一狀態(tài)的所有路徑進(jìn)行比較，并存儲(chǔ)具有最大度量值的路徑，即幸存路徑，步驟為：
    (1)從時(shí)刻l=m開(kāi)始，計(jì)算進(jìn)入某一狀態(tài)的單個(gè)路徑的部分度量值，并存儲(chǔ)每一狀態(tài)的幸存路徑及其度量值。
    (2)l增加1，l=m+1，將進(jìn)入某一狀態(tài)的分支度量值與前一段時(shí)間的幸存度量值累加，然后計(jì)算進(jìn)入該狀態(tài)的所有最大度量的路徑，決定并存儲(chǔ)新的幸存路徑及度量，并刪除所有其他路徑。
    (3)若l<l+m，重復(fù)步驟(2)，否則結(jié)束。
    該算法主要包括兩個(gè)工作：計(jì)算度量并比較，其決定幸存路徑；另一個(gè)是記錄幸存路徑及其相關(guān)的度量值。

2 基于硬件描述語(yǔ)言的Viterbi算法
    Viterbi算法一般采用回溯法和寄存器交換法。為了減少控制的復(fù)雜度，本文采用回溯法，譯碼器由分支度量(BMU)、加比選(ACS)蝶形運(yùn)算、存儲(chǔ)單元、回溯(TB)單元4個(gè)基本部分組成，見(jiàn)圖2。

    利用二元卷積來(lái)說(shuō)明VA譯碼過(guò)程如圖3所示。

    圖4為用實(shí)線表示輸入為0時(shí)走的分支，虛線表示輸入為1走的分支，任意給定一個(gè)序列，在網(wǎng)格圖中就有一個(gè)特定路徑，圖4中，u=(1011100)，輸出的編碼為c={11_10_00_01_10_01_11}。

2．1 分支度量單元
    路徑度量單元是計(jì)算實(shí)際接收到的碼元與期望碼元之問(wèn)的差別。G1與g1比較，G2與g2比較，若接收信號(hào)為0，期望值為0時(shí)，度量值為0，期望值為1時(shí)，度量值為1；若接收信號(hào)為1，期望值為0時(shí)，度量值為1，期望值為1時(shí)，度量值為0。兩個(gè)比較結(jié)果和作為最終度量結(jié)果輸出。按此規(guī)律計(jì)算當(dāng)前狀態(tài)下進(jìn)入下一個(gè)狀態(tài)的度量值。
2．2 加比選蝶形單元
    加比選(ACS)單元是完成幸存路徑的延伸和判決向量的生成，計(jì)算過(guò)程包括度量值的累加、比較、選擇路徑操作。對(duì)(2，1，3)卷積碼而言，共4個(gè)狀態(tài)，組成2個(gè)蝶形運(yùn)算單元；而(2，1，7)卷積碼則64個(gè)狀態(tài)，組成32個(gè)蝶形單元。在K=7的卷積碼中，有64個(gè)狀態(tài)的路徑，所以根據(jù)待譯碼的長(zhǎng)度，適當(dāng)增加累加值的位寬，防止度量值溢出。
2．3 幸存路徑存儲(chǔ)單元
    幸存路徑存儲(chǔ)是用來(lái)存儲(chǔ)每次蝶形運(yùn)算完成單元后所選擇的路徑，存儲(chǔ)單元的大小為譯碼深度乘以狀態(tài)個(gè)數(shù)。對(duì)每一個(gè)加比選過(guò)程的存儲(chǔ)，實(shí)際就是對(duì)幸存路徑的存儲(chǔ)。
2．4 回溯單元
    由VA算法可知，在網(wǎng)格圖上經(jīng)過(guò)大約5倍的約束長(zhǎng)度之后，所有幸存路徑將匯聚到一起。因此選擇合適的回溯長(zhǎng)度L，并從任一條路徑開(kāi)始(比如0狀態(tài))開(kāi)始回溯，當(dāng)回溯到L個(gè)節(jié)點(diǎn)時(shí)開(kāi)始輸出譯碼比特。

3 GPS L2和GALILEO E1接收機(jī)的高性能Viterbi譯碼具體模塊設(shè)計(jì)
    根據(jù)GPS和GALILEO的接口文件，L2頻點(diǎn)電文采用(2，1，7)卷積碼的形式，碼多項(xiàng)式為(171，133)o，且與GALILEO E1的卷積碼格式相同，GALILEO采用分段卷積的形式，參與卷積的為每頁(yè)中不包含同步頭的部分，即120位進(jìn)行卷積。為了能同時(shí)作為GPS和GALILEO的譯碼器，設(shè)計(jì)譯碼深度為120的譯碼器。

    接收機(jī)的Viterbi譯碼模塊包括：地址譯碼模塊、數(shù)據(jù)加載模塊、Viterbi譯碼模塊、輸出控制模塊。為了提高譯碼器的性能，Viterbi譯碼模塊的加比選蝶形單元采用32個(gè)并行結(jié)構(gòu)，提高運(yùn)算速度。
3．1 地址譯碼及數(shù)據(jù)加載
    地址譯碼包括總線讀寫譯碼，由于Viterbi模塊作為一個(gè)獨(dú)立模塊，內(nèi)部地址采用自己的譯碼設(shè)計(jì)。
    深度為120的Viterbi譯碼器，需要輸入240個(gè)卷積碼，對(duì)于總線32位CPU，需要8次寫入完成數(shù)據(jù)輸入。最少需要8個(gè)地址單元，Viterbi譯碼輸出最少需要4個(gè)地址單元，譯碼狀態(tài)中斷輸出，狀態(tài)位清除，即整個(gè)譯碼器模塊需要14個(gè)地址單元。地址線需要4根即可。
    地址譯碼電路采用組合邏輯設(shè)計(jì)。譯碼狀態(tài)中斷輸出、狀態(tài)位清零采用不同時(shí)鐘域同步。
    數(shù)據(jù)加載模塊是加載寄存器內(nèi)數(shù)據(jù)，然后按照順序，1次按2位串行輸出。
3．2 Viterbi譯碼模塊
    Viterbi譯碼模塊采用的譯碼深度為120的(171，133)o譯碼設(shè)計(jì)，譯碼器結(jié)構(gòu)如圖6所示，由譯碼控制單元、度量值計(jì)算單元、蝶形運(yùn)算、幸存路徑存儲(chǔ)、回溯輸出單元構(gòu)成。

    (1)蝶形運(yùn)算單元。按照(2，1，7)，多項(xiàng)式為(171，133)卷積碼特點(diǎn)，基本蝶形單元分布見(jiàn)圖7。對(duì)于約束長(zhǎng)度為7的卷積碼，共計(jì)64個(gè)狀態(tài)，形成32個(gè)基2的蝶形運(yùn)算單元見(jiàn)圖8。

    蝶形單元的輸入信號(hào)為上次的度量和，與接收碼本蝶形單元中理論輸出碼的碼距度量，如圖9所示。

    輸出信號(hào)為幸存路徑、度量值和，選擇輸出為1，不選輸出為0，如表1所示。

    (2)幸存路徑存儲(chǔ)。經(jīng)過(guò)蝶形單元運(yùn)算的輸出，幸存路徑，64個(gè)狀態(tài)，幸存路徑為64位，表示該狀態(tài)有或無(wú)，每進(jìn)行一次蝶形運(yùn)算，存入一個(gè)64位路徑信息，存儲(chǔ)器的寫入控制信號(hào)和地址信息由狀態(tài)控制單元發(fā)出，存儲(chǔ)空間為120×64 b。

    (3)回溯及輸出?；厮葸^(guò)程即從地址最后向前一次讀取幸存路徑的值，得出譯碼電文。如圖10所示。

    (4)狀態(tài)控制單元。狀態(tài)控制單元是對(duì)整個(gè)譯碼過(guò)程的控制，復(fù)位后，系統(tǒng)處在空狀態(tài)，收到輸入的待譯數(shù)據(jù)后，進(jìn)入加比選狀態(tài)，按照數(shù)據(jù)流順序進(jìn)行加比選蝶形運(yùn)算操作，進(jìn)入到譯碼深度的長(zhǎng)度的加比選后，轉(zhuǎn)入譯碼回溯輸出單元，從最后一個(gè)回溯到第一個(gè)時(shí)，即完成回溯，同時(shí)輸出譯碼電文和譯碼完成中斷，系統(tǒng)再次進(jìn)入等待狀態(tài)，如圖11所示。

4 仿真及接收機(jī)測(cè)試結(jié)果
    GPS／Galileo接收機(jī)通用的Viterbi譯碼器設(shè)計(jì)通過(guò)Modelsim仿真，能夠得出正確譯碼結(jié)果，編碼后在240個(gè)碼序列的228之前加入1位或2位錯(cuò)誤碼，均能正確糾錯(cuò)，得到正確的譯碼結(jié)果。
    譯碼延時(shí)260個(gè)時(shí)鐘周期。最大譯碼數(shù)據(jù)吞吐率達(dá)240×(150×1 000 00／260)=138 Mb／s。如圖12所示。

    譯碼模塊在Altera StratixⅡ系列EP2S180F1020I4 FPGA平臺(tái)上，利用QuartusⅡ8．0進(jìn)行綜合和時(shí)序分析，最大速度可以達(dá)到150 MHz，資源使用量為：ALUTs占用2 679．Logic Registers占用1 465，與文獻(xiàn)相比，資源消耗大大減少。如圖13，圖14所示。

5 結(jié)語(yǔ)
    本文所述基于FPGA的Viterbi譯碼器用于GPS／GALILE-O接收機(jī)，能對(duì)GPS L2和GALILEO的電文進(jìn)行譯碼，糾錯(cuò)能力達(dá)到預(yù)期效果，F(xiàn)PGA資源使用量較低，主時(shí)鐘速度最大可達(dá)到150 MHz，譯碼處理延時(shí)達(dá)260個(gè)時(shí)鐘周期，譯碼深度為120，最大譯碼數(shù)據(jù)吞吐率達(dá)138 Mb／s，完全滿足GPS／GALILEO接收機(jī)電文接收譯碼速度要求。