卷積碼Viterbi譯碼算法的FPGA實(shí)現(xiàn)

1、卷積碼Viterbi譯碼算法的FPGA實(shí)現(xiàn)發(fā)布日期:2006-04-20作者:趙旦峰 劉會(huì)紅摘 要：探討了卷積碼Viterbi譯碼的FPGA實(shí)現(xiàn)問題。在Viterbi譯碼算法中，提出了減少路徑 量度的位數(shù)和流水線回索法的幸存路徑等方法，能有效地減少存儲(chǔ)量、降低功耗、提高速度，使 得K = 7的Viterbi譯碼算法可在以單片F(xiàn)PGA為主的器件上實(shí)現(xiàn)。關(guān)鍵詞：差錯(cuò)控制；Viterbi譯碼；FPGA實(shí)現(xiàn)；卷積碼1引言在數(shù)字通信中，如何降低數(shù)據(jù)傳輸?shù)恼`碼率，提高通信質(zhì)量是一個(gè)很關(guān)鍵的問題。衛(wèi)星通信 系統(tǒng)以很遠(yuǎn)的距離傳送數(shù)據(jù)，由于衰落、噪聲和干擾等的影響，信號(hào)在傳輸過程中將產(chǎn)生嚴(yán)重的 畸變。這就要求信

2、號(hào)應(yīng)具有盡可能大的能量，但是，由于衛(wèi)星體積和載重等的限制，不可能給信 號(hào)提供太大的能量，這樣，就要求采用具有很強(qiáng)糾錯(cuò)能力的差錯(cuò)控制方法1 以保證誤碼率在允 許的范圍之內(nèi)。為實(shí)現(xiàn)強(qiáng)大的糾錯(cuò)能力，除了構(gòu)造所謂“好碼”之外還要求譯碼時(shí)采用最大似然 譯碼算法。一般認(rèn)為衛(wèi)星通信信道是功率受限，對(duì)于衛(wèi)星通信采用編碼來改善通信效率是特別有 吸引力的。自1985年Xilinx公司推出第一片F(xiàn)PGA至今，F(xiàn)PGA已經(jīng)歷了十幾年的發(fā)展歷史，占據(jù)了巨 大的市場(chǎng)，逐漸取代了 ASIC，其原因在于：FPGA不僅解決了電路系統(tǒng)小型化、低功耗、高可靠 性等問題，而且其開發(fā)周期短、開發(fā)軟件投入少、芯片價(jià)格不斷降低，特別是對(duì)小

3、批量、多品種 的產(chǎn)品需求，使FPGA成為首選。針對(duì)FPGA設(shè)計(jì)的特點(diǎn)，本方案在不改變糾錯(cuò)性能的前提下提出了一系列的方法。如減少連 接線、流水線回索法等。目的是減少存儲(chǔ)器的容量，降低功耗，提高速度。Viterbi譯碼算法在卷積碼譯碼中，Viterbi譯碼算法是糾錯(cuò)能力很強(qiáng)的一種，已廣泛應(yīng)用于衛(wèi)星通信系統(tǒng)。 Viterbi譯碼算法是一種最大似然譯碼算法。Viterbi譯碼算法的步驟：根據(jù)接收碼符號(hào)，計(jì)算出相應(yīng)的分支量度值；將進(jìn)入某一狀態(tài)的2條分支量度與其前面的狀態(tài)量度累加求和；比較到達(dá)同一狀態(tài)的2條新的路徑量度的大小，選擇最小者作為新的狀態(tài)量度存儲(chǔ)起 來，并記住與此路徑(幸存路徑)對(duì)應(yīng)的信息碼元；

4、對(duì)所有的2m個(gè)狀態(tài)都實(shí)施上述相加/比較/選擇(ACS)運(yùn)算；路徑量度最小的一條 路徑(約為以前碼元長(zhǎng)度的5倍)作為譯碼數(shù)據(jù)輸出；(6)將譯碼時(shí)刻向前延伸一步，重復(fù)以上步驟，直至譯碼結(jié)束。Viterbi譯碼器的實(shí)現(xiàn)下面將介紹(2, 1，7)卷積碼8電平量化的Viterbi譯碼器的實(shí)現(xiàn)。其編碼器如圖1所示。 譯碼器的方框圖如圖2所示。圖11.7毒枳碼始碼WfclS困 2 Viterbi 框圖Viterbi譯碼器主要有5部分組成：（1）輸入轉(zhuǎn)換及分支量度計(jì)算電路。（2）相加/比較/選擇電路及狀態(tài)量度存儲(chǔ)器。（3）路徑判據(jù)存儲(chǔ)器、最佳狀態(tài)選擇和輸出緩沖器。（4）同步電路。（5）時(shí)序電路。輸入轉(zhuǎn)換電路用

5、一些簡(jiǎn)單的邏輯電路實(shí)現(xiàn)，分支量度計(jì)算用ROM來實(shí)現(xiàn)。分支量度單元接收 I和Q兩路數(shù)據(jù)，產(chǎn)生路徑量度需要的分支量度。對(duì)于本方案，采用8電平軟判決，I和Q路數(shù) 據(jù)各用3 b表示，分支量度用歐氏距離計(jì)算，經(jīng)過壓縮整數(shù)化可用4 b表示。對(duì)于3 b表示的I 和Q路數(shù)據(jù)，能夠產(chǎn)生64個(gè)分支量度。實(shí)際上，可用64個(gè)字，每個(gè)字16 b的查找表實(shí)現(xiàn)。對(duì)于（2, 1，7）卷積碼，有64個(gè)狀態(tài)，也就意味著，在每一步，要計(jì)算64個(gè)路徑量度。 基于速度要求，采用全并行算法，即在每一步同時(shí)計(jì)算64個(gè)路徑量度，需要64個(gè)并行處理 的ACS模塊或32個(gè)蝶形結(jié)構(gòu)（每一個(gè)蝶形結(jié)構(gòu)由2個(gè)ACS模塊組成）。每一個(gè)ACS單元由2 個(gè)加

6、法器和1個(gè)比較器構(gòu)成，這樣總共有128個(gè)加法器和64個(gè)比較器。顯然，路徑量度單元是 整個(gè)Viterbi譯碼器的核心，對(duì)于提高速度有著實(shí)質(zhì)的影響。ACS實(shí)現(xiàn)結(jié)構(gòu)如圖3所示。E3 ACS電路框圖文獻(xiàn)】1中，已經(jīng)證明在每一步的量度的最大值與最小值的差值用下面的公式計(jì)算：IPg - PMm K -一在本方案中.K=7 EA/m*x =】4 * BMmn=E最大的路徑量度和最小的路徑量度之間的最大差值為84。這樣要求用7b來表示路徑量度。事實(shí)上， 在每一步的路徑量度的歸一化操作保證了具有最小量度的路徑量度不受路徑量度的比特?cái)?shù)的影 響。經(jīng)過驗(yàn)證，用5b表示路徑量度的Viterbi譯碼器的性能仍然很好。為了

7、防止溢出，當(dāng)每一 個(gè)路徑量度都大于或等于所選擇的固定的數(shù)值時(shí)，在下一個(gè)周期，所有的路徑量度都減去這個(gè)固 定的數(shù)。在本方案中選擇4為固定的數(shù)值，是基于比較器簡(jiǎn)單和快速，用或非門實(shí)現(xiàn)。只要路徑 量度中最高3位有一個(gè)為1就意味著此量度大于或等于4。若所有的路徑量度都大于或等于4 時(shí)，進(jìn)行歸一化操作，即從所有的路徑量度中減去4。這樣還需要一個(gè)64輸入的或非門電路， 來產(chǎn)生歸一化標(biāo)志。在Viterbi算法中，幸存路徑存儲(chǔ)的實(shí)現(xiàn)有2種傳統(tǒng)方法：寄存器交換法RE (Register Exchange)和回索法 TB (Trace Back)。寄存器交換法采用專用寄存器作為存儲(chǔ)主體，存儲(chǔ)的是路徑上的信號(hào)信息，

8、利用數(shù)據(jù)在寄存 器陣列中的不斷交換實(shí)現(xiàn)信息的譯碼。優(yōu)點(diǎn)是存儲(chǔ)單元少，譯碼延時(shí)短，I/O端固定。缺點(diǎn)是 內(nèi)連關(guān)系過于復(fù)雜，不適于大狀態(tài)譯碼器的FPGA實(shí)現(xiàn)?；厮鞣ㄊ褂猛ㄓ玫腞AM作為存儲(chǔ)體，存儲(chǔ)的是幸存路徑的格狀連接關(guān)系，通過讀寫RAM來完成數(shù)據(jù)的寫入為回索輸出。優(yōu)點(diǎn)是內(nèi)連關(guān)系簡(jiǎn)單、規(guī)則，適 合用FPGA實(shí)現(xiàn)。缺點(diǎn)是譯碼延時(shí)較長(zhǎng)。匹13CIO_QZJ bFFR-FFFHFFFFHR 一 I frl_l ? _ - k_ E J - i M IWtWWhsmufCSDCSJCZJ03_IZ20 -5：jj. n 王新梅，肖國(guó)鎮(zhèn).糾錯(cuò)碼一原理與方法M.西安：西安電子科技大學(xué)出版社，2001. 朱明程

9、.Xilinx數(shù)字系統(tǒng)現(xiàn)場(chǎng)集成技術(shù)M .南京：東南大學(xué)出版社，2001. 宣建華，姚慶棟.高速Viterbi處理器的并行算法和結(jié)構(gòu)J .信號(hào)處理，1993. 韓雁，王匡.一種寄存器回索型Viterbi譯碼器的VLSI設(shè)計(jì)J .浙江大學(xué)學(xué)報(bào)工學(xué)版， 1997，(4).!j -iFT-|fT=q TTr|E |“，-J田4 2r Ih 7）因流本燧回費(fèi)法板圖本文提出了一種基于流水線結(jié)構(gòu)的回索法4，提高了譯碼的速度。流水線回索算法如圖4 所示。在每一個(gè)時(shí)鐘周期進(jìn)行一次回索，同時(shí)幸存信息進(jìn)行移位操作，最佳狀態(tài)暫存在寄存器中， 隨著下一階段的回索，上一步的最佳狀態(tài)被覆蓋。這種方法的好處就是可以使用更高的時(shí)鐘來處 理，缺點(diǎn)是延時(shí)較長(zhǎng)。但綜合考慮，譯碼速率還是較快的。以上這些操作都用VHDL語(yǔ)言描述，利用XILINX公司專用軟件ISE編譯，并用Modelsim專 用仿真軟件進(jìn)行了功能及時(shí)序