1、 畢業設計(論文)基于FPGA的Viterbi譯碼器 姓 名： 學 院： 專 業： 班 級： 指 導 教 師： 摘 要 卷積編碼是深度空間通信系統和無線通信系統中常采用的一種編碼方式,廣泛應用于衛星通信、無線通信等多種通信系統。在1967年，Viterbi 提出了卷積碼的Viterbi 譯碼算法，它是一種卷積碼的最大似然譯碼算法，通過尋找譯碼器接收序列和卷積編碼器的輸出序列的最大似然函數來得出譯碼結果。該算法譯碼性能好、速度快，并且硬件實現結構比較簡單，是最佳的卷積碼譯碼算法。隨著可編程邏輯技術的不斷發展，使用FPGA實現viterbi譯碼器的設計方法逐漸稱為主流。因此設計viterbi譯碼器

2、，使其能夠滿足多種通信系統的應用要求，具有重要的現實意義。本文的主要內容是基于FPGA 的Viterbi 譯碼器設計。在對viterbi譯碼算深入研究過程中，重點研究了Viterbi 譯碼器各個模塊的主要功能。在本設計中，采用了硬判決計算輸入信息碼元與各狀態的期望碼元之間的分支度量值，用串行加比選碟型算法來尋找編碼器網格圖上的幸存路徑，用回溯法(trace-back)算法來對幸存路徑做處理得到譯碼輸出，用乒乓方式對幸存路徑進行存儲。本論文設計輸入是采用硬件描述語言VHDL來完成的，通過在各種EDA工具下的仿真和綜合，驗證了本文所設計的Viterbi 譯碼器的正確性和實用性。關鍵詞：卷積碼；維特

3、比；譯碼器；現場可編程門陣列 ABSTRACTConvolutional coding has been used in communication systems including deep space communications and wireless communications,which are widely used in satellite communications and wireless communication. The Viterbi algorithm , proposed in 1967 by Viterbi ,is a maximum-likelihoo

4、d algorithm for convolutional codes. The Viterbi decoder attempts to find the maximum-likelihood function of the decoded code word against received code word. This method is better decoding performance, fast, and relatively simple hardware architecture, is the best convolutional code decoding algori

5、thm. With the continuous development of programmable logic technology, the use of FPGA implementation viterbi decoder design method called mainstream gradually. Therefore, the design viterbi decoder so that it can meet the application requirements of a variety of communication systems, has important

6、 practical significance.The main content of this paper is to design a Viterbi decoder with FPGA technology. In-depth study of the viterbi decoding calculation process, focusing on the main functions of each module Viterbi decoder. In this paper, the parallel ACS (add-compare-select) Butterfly algori

7、thm is used to find the survivor path in encoder trellis. We also use trace-back algorithm to dispose the survivor path and receive the decoded results. In addition, the behavior of a design is described in VHDL. The emulated and synthesized results of this design are received by all kinds of EDA to

8、ols. Through these results the Viterbi decoders correctness and practicability can be validated.Key words：Convolutional Code; Viterbi; Viterbi; FPGA 目 錄緒 論5第一章 糾錯碼的基本原理71.1 差錯控制的基本方式71.2 糾錯編碼的基本原理91.3 糾錯編碼的分類11第二章 卷積碼和Viterbi算法122.1 卷積碼基礎122.1.1 卷積碼編碼原理122.1.2 卷積碼的描述142.2 Viterbi譯碼原理182.2.1Viterbi算法

9、描述182.2.2Viterbi算法舉例192.2.3 Viterbi譯碼器的特點23第三章 Viterbi譯碼的FPGA實現243.1 Viterbi譯碼器的基本結構243.2 分支度量模塊（BMU）263.3 加比選模塊(ACS)273.3.1狀態間的蝶形運算關系273.3.2 加比選的實現方式303.3.3 溢出處理313.4 路徑度量存儲模塊（PMU）323.5 幸存路徑寄存模塊（SMU）333.5.1 寄存器交換法343.5.2 回溯法353.6 回溯模塊(TBU)37 第四章 Viterbi譯碼器的設計與仿真結果394.1 卷積碼編碼器設計394.2 Viterbi 譯碼器的設計4

10、0第五章 結束語43參考文獻44附錄45英文文獻61 謝 辭75 緒 論 隨著現代通訊的發展，我們對通信的技術的質量跟速度提出了更高的要求。但是，由于信道的不理想以及加性噪聲和人為干擾的影響，使得信號在信道傳輸過程中會因為各種干擾而產生失真現象，使得通信質量下降。不同的系統在信號傳輸過程中會受到不同的干擾，產生不同的差錯率，進而使傳輸的可靠性也不同。隨著傳輸速率的提高，可靠性問題更加突出。為了提高傳輸的可靠性，降低誤碼率，有兩種方法：一是降低信道本身引起的誤碼，可采用的方法有選擇高質量的傳輸線路、改善信道的傳輸特性、增加信號的發送能量、選擇有較強抗干擾能力的調制解調方案等；另外一種方法就是采用

11、差錯控制編碼，即信道編碼。這種方法主要是對輸入信息序列進行各種變換，使得原來相互獨立的信息碼元產生相關性，在接收端利用這些信息碼元的相關性檢測出錯碼就糾正過來。在許多情況下，信道的改善需要大量的能量與功率，實現起來比較困難與不經濟，這時采用差錯控制編碼方法比較合理。而在 GSM、IS - 95、WCDMA 系統中有廣泛應用的卷積碼譯碼算法是 A. J.Viterbi 在 1967 年提出的Viterbi算法(VB 算法),該算法是針對卷積碼的一種最佳的最大似然譯碼方法。本設計實現了在IS-95中的前項鏈路所使用的(2,1,9)卷積碼，具有一定的實際意義。 FPGA以運行速度快、編程方便、可以實

12、現系統集成、功耗低、價格低、可以反復地編程與擦除使用的優點，在通信領域越發顯示出強大的優勢，受到廣大電子技術人員的青睞。 本設計具有以下特點：在本設計中采用了串行的加比選單元結構，這樣可以節省大量的資源，降低對硬件的要求。在對幸存路徑的處理上，一般來說有寄存器交換法和回溯法兩種處理手段，在本設計中采用了回溯法。本設計中 Viterbi 譯碼器的設計輸入是用硬件描述語言VHDL寫的，設計平臺使用的是Altera 公司的Quartus II 軟件，本設計中的輸入、功能仿真、綜合、適配及時序仿真都是在這個平臺上來完成的。本論文的具體安排如下：第一章對糾錯碼進行了簡單的介紹。第二章主要介紹了卷積碼的基

13、礎知識以及Viterbi 譯碼的基本原理，并通過舉例來具體說明。第三章主要介紹了viterbi譯碼器的FPGA的實現設計思路，viterbi譯碼器總體框體，然后還介紹了各個模塊的主要功能和實現方法。第四章簡要的介紹了FPGA的發展歷程及特點，同時給出了FPGA的一般設計方法。給出了本設計的仿真驗證，從而證明了本設計的正確性。 第一章 糾錯碼的基本原理1.1 差錯控制的基本方式 數字信號在傳輸過程中，由于加性噪聲和人為干擾的影響，使得數字信號產生失真現象。由于剩性干擾引起的失真現象可以采用均衡方法來消除。而因為加性干擾引起的誤碼現象則需要采用其他方法來消除，可以首先考慮增加數字信號發送端的發送功

14、率或采取合理的調制解調方案，使加性干擾不足以影響達到誤碼率要求。在仍不能滿足要求時，就要考慮采用差錯控制措施了。一些通用的系統，其誤碼率要求因用途而異，也可以把差錯控制作為附加手段，在需要時加用。 根據加性干擾引起錯碼分布規律的不同，可以把信道分成三類：突發信道、隨機信道和混合信道，在不同的信道中，應采用不同的差錯控制方式。差錯控制方式基本上分為兩類，一類稱為“反饋糾錯”，另一類稱為“前向糾錯”。在這兩類基礎上又派生出一種稱為 “混合糾錯”，如圖1-3所示。圖1-3 差錯控制的基本方式（1） 檢錯重發ARQ 檢錯重發方式的發送端發出有一定檢錯能力的碼，接收端接受到這些碼元后，利用碼元本身的檢錯

15、能力進行檢測，當檢測到有錯碼時，接收端通過反向信道向發送端發送信息，要求發送端重發，直到接受到正確碼元為止。ARQ只能檢測到是否有錯碼，但檢測到錯碼后，不知道如何糾正錯碼，要求發送端重新發送一遍。在二進制系統中，這種情況發生在不知道一組接收碼元中哪個碼元錯了。 該方法是通過發送有一定檢錯能力的碼元進行檢錯的，因此它的優點是只需要少量的多余碼就可以降低誤碼率。另外，由于該方法的檢錯與糾錯能力與信道干擾情況沒有關系，因此可以應用于各種類型的信道，適應性比較強，特別適合于短波、有線等干擾情況復雜而又要求誤碼率較低的場合。主要缺點是必須有反饋信道，不能進行同播。當信道干擾較大時，造成錯碼概率較大，系統

16、可能就處于重發循環中，信息傳輸的實時性和連貫性就比較差。 （2）前向糾錯FEC 前向糾錯方式是在發送端發送具有糾錯能力的碼元，接收端的糾錯譯碼器接受這些碼元后，檢測到錯碼后能及時把這些錯碼糾正過來。 該方式的優點是譯碼實時性好，不需要反饋信道，能夠進行一個用戶對多個用戶的廣播式通信，而且控制電路簡單，特別適用于移動通信。缺點是譯碼設備比較復雜難以實現，而且所選用的糾錯碼必須與信道干擾情況相匹配，因而對信道變化的適應性差。為了獲得較低的誤碼率，必須以最壞的信道條件來設計糾錯碼。 （3）反饋校驗 反饋校驗方式不需要在發送序列中加入差錯控制碼元。這種方式的基本思路是接收端將接受到的碼字原封不動地發送

17、到發送端，與發送端的碼字逐一進行比較，如果檢測到與發送端的碼字不相同，就認為接收端收到的碼字中有錯碼，發送端需要重新發送。這種技術的優點是原理和設備都很簡單，缺點是需要雙向信道，傳輸效率也較低，因為每個碼元都需要占用兩次的傳輸時間。 （4）檢錯刪除 檢錯刪除和檢錯重發的區別在于，在接收端發現錯碼后，立即將其刪除，不要求重發。這種方法只適用在少數待定系統中，在那里發送碼元中有大量多余度，刪除部分接收碼元不影響應用。例如，在循環重復發送某些遙測數據時。又如，用于多次重發仍然存在錯碼時，這時為了提高傳輸效率不再重發，而采取刪除方法。這樣做在接收端當然會有少許損失，但卻能夠及時接受后續的消息。 以上幾

18、種技術可以結合使用。例如，“混合糾錯”就是“前向糾錯”和“反饋糾錯”兩種方式的混合。當接收端出現少量錯碼并有能力糾正錯碼時，采用前向糾錯技術；當接收端出現較多錯碼沒有能力糾正時，采用檢錯重發技術。 1.2 糾錯編碼的基本原理差錯控制編碼又稱為糾錯編碼（error-correcting coding）。有的編碼方法只能檢錯而不能糾錯，不同的編碼方法，其檢錯或糾錯能力是不同的。一般來說，增加的監督碼元個數越多，檢（糾）錯的能力越強。而通常有多余度來衡量增加的監督碼個數。例如，若編碼序列中平均每三個信息碼元就添加一個監督碼元，則這種編碼的多余度為1/4。或者說，這種碼的編碼效率（簡稱碼率）為3/4。

19、我們假設編碼序列中總碼元數為n，其中信息碼元數量為k，則監督碼元數量為n-k，則碼率就是信息碼元數量與總碼元數量的比值kn；而冗余度就是監督碼元數（n-k）和信息碼元數k之比（n-k）/k。 先用一個例子說明糾錯編碼的基本原理。用一個由3位二進制數字構成的碼組來表示各種天氣，這些碼組有8種可能的組合方式，表示天氣情況如下表表1-1 各種天氣的表示方法 碼組000001010011100101110111 天氣晴云陰雨雪霜霧雹 其中任一碼組在傳輸過程中若發生一個或多個錯碼，則將變成另一個信息碼組，這時，接收端接受到的碼字是錯碼，表示的天氣信息跟發送端的完全不一樣，接收端將無法發現其錯誤。但若上述

20、8中碼組只準使用其中4種來傳送天氣，例如：000表示天氣晴，011表示天氣云，101表示天氣陰，110表示雨。這時，雖然只能傳送4種不同的天氣，但是在接收端有可能發現碼組中的一個錯碼。例如，若011（云）在傳輸過程中發生一個錯碼，則接受碼組將變成111或001或010。這3種碼組是不能表示任何天氣的，是禁止使用，稱為禁用碼組。接收端收到禁用碼組后，就認為有錯碼。當傳輸過程中發生3個錯碼時，011變成100，100也是禁用碼組，故接收端也能檢測出3個錯碼。但如果011（云）中發生2個錯碼，接受碼組就有可能變成000或110或101，這些都是許用碼組，接收端就不能檢測到錯碼，因此這種編碼不能檢測出

21、2個錯碼。上面這種編碼只有檢錯能力，沒有糾錯能力。例如，如果接收端收到禁用碼組111時，接收端能檢測出發生錯碼，但不能糾正過來，因為011（云）、101（陰）、110（雨）發生一個錯碼都能變成111，天氣晴000發生3個錯碼也能變成111，接收端無法判定是哪個碼組發生錯碼得到的。要想能夠糾正錯誤，還要增加多余度。例如，若規定許用碼組只有兩個：000表示天氣晴，111表示天氣雨，其他的碼組都為禁用碼組。這種編碼方式不僅能檢測出兩個以下錯碼，還能糾正一個錯碼。例如，當接收端收到禁用碼組001時，倘若該碼組是在傳輸過程中發生一位錯碼，則接收端能夠判斷該碼組是由000（晴）產生一位錯碼得來的，因為11

22、1（雨）產生一位錯碼無論如何都得不到001，接收端就可以糾正為000（晴）。但倘若發生錯碼的個數為1個或2個時，則接收端無法糾正過來，因為111（雨）發生2個錯碼碼組可以變成001，000（晴）發生一個錯碼也可以變成001，這時接收端只能檢測到錯碼而無法糾正過來，因此這種編碼方式只能糾正一個錯碼。從上面的例子中，我們可以了解到關于“分組碼”的一般概念。如果不要求有檢（糾）錯能力，為了傳輸4種不同的消息，用兩位的碼組就夠了，即可以用：00、01、10、11。這些兩位碼稱為信息位。而在上面中使用了3位碼，增加的那位稱為監督位。把這種將信息碼分組，為每組新碼附加若干監督碼的編碼稱為分組碼。分組碼一般

23、用符號（n，k）表示，其中n是碼組的總位數，又稱為碼組的長度（碼長），k是碼組中信息碼元的數目，n-k=r為碼組中的監督碼元數目。在分組碼中，把碼組中“1”的個數目稱為碼組的重量，簡稱碼重。把兩個碼組中對應位上數字不同的位數稱為碼組的距離，簡稱碼距。碼距又稱為漢明距離。1.3 糾錯編碼的分類 隨著數字通信技術的發展，各種差錯控制編碼方案越來越多，其檢錯與糾錯能力也是不一樣的，數學模型也不一樣，可以從不同的角度對差錯控制編碼進行分類。根據對信息元處理方式的不同，可以將糾錯碼分為分組碼與卷積碼。分組碼是將信息序列以k個碼元為一組分成幾組，每組又根據一定的編碼規則生成若干個r個監督碼元，輸出一個碼長

24、為n=k+r的碼組。分組碼中的監督碼元只與當前碼組的信息元有關，與其他碼組的信息元沒有關系。卷積碼則不一樣，卷積碼不對信息序列進行分組編碼，而且卷積碼中的監督碼不僅與當前時刻的信息碼元有關，還與之前時刻輸入的信息碼元有關。卷積碼的缺點是目前還沒有找到有效的數學工具和系統理論對卷積碼進行分析，但它的實用性遠遠超過分組碼，因此卷積碼在數字通訊領域得到廣泛的應用。 根據信息碼元與監督碼元之間的關系的不同，可以將糾錯碼分為線性碼與非線性碼。顧名思義，線性碼就是指信息碼元與監督碼元之間呈一定的線性關系，即滿足線性疊加原理；如果信息碼元與監督碼元不滿足這種關系，則為非線性碼。由于非線性碼的分析比較困難，實

25、現較為復雜，所以我們討論多為線性碼。 根據差錯控制編碼的功能不同，可分為檢錯碼、糾錯碼和糾刪碼等。檢錯碼只能檢測出錯碼而無法糾正錯碼；糾錯碼不僅具備識別錯碼功能，同時具備糾正錯碼功能；糾刪碼則不僅具備糾錯碼的所有功能，即檢測出錯碼并糾正錯碼，而且當錯碼超過糾正范圍無法糾正時，可以把無法糾正的信息刪除。 根據每個碼元取值不同，可以將糾錯碼分為二進制碼和q進制碼。根據信息碼元在編碼以后形式是否發生改變，可以分為系統碼和非系統碼。系統碼是指信息碼元在編碼之后保持原來的形式不變，而在非系統碼中，信息碼元會改變其原有的信號序列。由于原有的碼位發生了變化，使譯碼電路更為復雜，故較少選用。 第二章 卷積碼和

26、Viterbi算法 卷積碼是1955年由伊萊亞斯（Elias）提出一種非分組碼。分組碼編碼是將輸入的信息序列分成長度為k的分組，然后按照一定的編碼規則，將長度為k的信息員附加上長度為r的監督元，生成長為n=k+r的碼組。在一個碼組中，r個監督元僅與本組的k個信息元有關，而與其他各碼組均無關。分組譯碼時，也僅從本碼組的碼元內提取有關譯碼信息，而與其他碼組無關。卷積碼則不同，他先將信息序列分成長度為k的子組，然后編成長為n的子碼，其中長為n-k的監督元不僅與本子碼的k個信息碼元有關，而且還與前面m子碼的信息元密切相關。換句話說，各子碼內的監督元不僅對本子碼有監督作用，而且對前面m個子碼內的信息元也

27、有監督作用。因此常用（n，k，m）表示卷積碼，其中m為編碼記憶，它反映了輸入信息元在編碼器中需要存儲的時間長短；N=m+1稱為卷積碼的約束度，單位是組，它是相互約束的子碼的個數；N*n被稱為約束長度，單位是位，它是相互約束的二進制碼元的個數。 在線性分組碼中，單位時間內進入編碼器的信息序列一般都比較長，k可達8100。因此，編出的碼字n也較長。對于卷積碼，考慮到編、譯碼器設備的可實現性，單位時間內進入編碼器的信息碼元的個數k通常比較小，一般不超過4，往往取k=1。2.1 卷積碼基礎2.1.1 卷積碼編碼原理 我們可以通過一個例子來說明卷積碼的編碼原理，如圖2-1是（3，1，2）卷積碼編碼器的原

28、理框圖。如圖所示，（3，1，2）卷積碼編碼器主要是由兩個移位寄存器（m j-1，m j-2）和兩個模2加法器組成。編碼前，各級移位寄存器清零，輸入端依次輸入信息序列m 1，m 2，。 。m j，。每輸入一個信息碼元m j時，輸出端開關依次接到X1,j，X2,j和X3,j各端點一次。其中X1,j，X2,j和X3,j由下式決定 X1,j=m j X2,j=m j+m j-2 （2.1.1） X3,j=m j+m j-1+m j-2 由式（2.1.1）中可以看出，編碼器輸出的信息碼元X1,j，X2,j和X3,j不僅與當前時刻的信息碼元m j相關，還跟之前時刻的兩個信息碼元m j-1、m j-2相關，

29、因此編碼記憶m=2，約束度N=m+1=3（組），約束長度N*n=9（位）。 X1,j輸入 X2,j 輸出 m j-1m j-2m1,m2,.mj. X3,j 圖2-1 （3，1，2）卷積碼編碼器表2-1 (3,1,2)編碼器狀態表 m j 1 1 0 1 0 0 0 0 m j-1。m j-2 00 01 11 10 01 10 0000 X1,j，X2,j.X3,j 111 110 010 100 001011000000 狀態 a b d c b c a a 表2-1列舉了圖2-1所示編碼器的狀態。其中a，b，c，d表示 m j-1m j-2的四種可能的狀態：00，01，10，11。當第一

30、位信息比特為1時，即m1=1，因移位寄存器的狀態 m j-1。m j-2=00，故輸出比特 X1,j，X2,j.X3,j=111；第二位信息比特為1時，因m j-1。m j-2=01，故輸出比特 X1,j，X2,j.X3,j=110；其余類推。為了保證輸入的全部信息位為11010都能通過寄存器，還必須在信息位后加3個零。卷積碼編碼時，信息碼流按順序依次輸入進行編碼。分組碼卻不一樣，它需要先對信息碼流進行分組，分組完后才能進行編碼，因此卷積碼編碼只需要少量的緩沖和存儲空間。2.1.2 卷積碼的描述卷積編碼有集中描述方法，其中使用比較多的是樹狀圖、網絡圖和狀態圖，現在我們以（2，1，2）卷積碼為例

31、來說明各種卷積碼的描述方法。1、 樹狀圖 卷積碼的樹狀圖能形象的描述卷積碼編譯碼的工程，圖2-2畫出(2,1,2)卷積碼的樹狀圖。樹狀圖從節點so開始，此時移位寄存器狀態為00。現在規定：輸入信息位為“0”時，則狀態往上支路移動；輸入信息位為“1”時，則狀態往支路移動。如圖2-1所示，當第一個輸入信息位m1=0時，輸出碼元為00，移位寄存器的狀態仍為so=00；若第一個輸入信息位m1=1時，輸出碼元為11，狀態并轉換到s1=01。因此從so出發有兩條支路可供選擇，m1=0時取上面一條支路，m1=1時則取下面一條支路。輸入第二個信息位時，移位寄存器右移一位后，上支路情況下移位寄存器狀態仍為so，

32、下支路的狀態為s1。新的一位輸入信息位到來時，隨著移位寄存器狀態和輸入信息位的不同，樹狀圖繼續分叉成4條支路，2條向上，兩條向下。當輸入第二個信息位時，若此時移位寄存器的狀態仍為so，則由m2=“0”或“1”和寄存器的狀態可得，輸出碼元為00或11，狀態也傳換到so或s1狀態；若此時移位寄存器的狀態為s1，則由m2=“0”或“1”和寄存器的狀態可得，輸出碼元為10或01，狀態也傳換到s2=10或s3=11狀態。如此繼續，即可得到圖2-2所示的二叉樹圖形。樹狀圖中，每個樹杈上所標注的碼元為輸出信息位，每個節點上標注的so，s1，s2，s3為移位寄存器的狀態。顯然，對于第j個輸入信息位，有2j條支

33、路，但在j=N3時，樹狀圖的節點自上而下開始重復出現4中狀態。 圖2-2 （2，1，2）卷積碼的樹狀圖 設現在輸入碼元序列為1000時，根據上面所述，可得到輸出碼元為11，10，11，00，相對應的寄存器的狀態為s1，s2，so，so，在2-2圖中用一條粗黑線描繪出來。 2、狀態圖 由（2，1，2）編碼器結構可知，輸出碼元不僅決定于當前輸入信息位，還決定于前兩位信息位。移位寄存器中就有四種可能的狀態so=00，s1=01，s2=10，s3=11，編碼器相應的也有4種狀態。當輸入端依次輸入信息序列時，編碼器就不斷地從當前時刻的狀態轉移到下一時刻的狀態，并輸出信息碼元。卷積碼的狀態圖就是用來描述這

34、種狀態轉移的過程。圖2-3所描述就是卷積碼（2，1，2）的狀態圖，虛線表示輸入信息位為“1”時狀態轉變的路線，實線表示輸入信息位為“0”時狀態轉變的路線，線條旁的數字如0/11表示輸入信息位為0，輸出碼元為11，各狀態之間的連線與箭頭表示狀態轉移方向。設編碼器的初始狀態為so，若輸入信息位為“0”時，輸出碼元為00，狀態仍為so，；若輸入信息位為“1”時，輸出碼元為11，下一時刻狀態仍為s1。隨著信息序列的不斷輸入，編碼器就會不斷從一個狀態轉移到另外一個狀態，利用這些轉移路徑不僅可以表示出該轉移過程中對應的輸出碼元，還可以表示出所對應輸入信息位。 圖2-3 （2，1，2）卷積碼的狀態圖 3、網

35、絡圖雖然狀態轉移圖能夠描述在不同的信息序列下，編碼器的各個狀態之間的轉移關系，但是它不能描述編碼器的狀態和時間的關系。為了表示這種關系，我們引進了網絡圖，以時間為橫坐標，編碼器的狀態為縱坐標，將一個平面劃分成網格狀，就可以得到卷積碼的網絡圖。圖2-4 （2，1，2）卷積碼網絡圖上圖表示是（2，1，2）卷積碼網絡圖，它是由節點和分支組成，L=5，所以一共有L+m+1=8個節點（即時間單位），用0到7加以標號。在網絡圖中，把樹狀圖中具有相同狀態的節點合并在一起，每一狀態都有兩個輸入分支和兩個輸出分支。上分支表示輸入信息碼元為“0”時狀態轉移路線，用實線表示；下分支表示輸入信息碼元為“1”時狀態轉移

36、路線，用虛線表示。而每一分支上的n個數字(n=2)表示編碼器輸出信息序列。可以看出，在時間單位3以后的網絡圖形完全是重復2時間單位的圖形，這就反映了該卷積碼的約束長度為2。若編碼器從狀態so（00）開始，在6個時間單位后結束于狀態so（00）。在（2，1，2）卷積碼網絡圖中，由于約束長度為2，編碼器在最開始的2個時間單位（t=0，t=1）狀態由最開始的so狀態向別的狀態轉移，因此t=1編碼器的狀態只有可能處于so或s1狀態中一個。編碼器在最后的2個時間單位內（t=6，t=7），編碼器的狀態由別的狀態返回so狀態。為了在t=7時刻編碼器的狀態結束于so，編碼器在t=6時狀態只能為狀態so或s2中

37、的一個。而從t=2至第t=5時間單位中，編碼器的狀態可以處于4個狀態s0，s1，s2，s3中的任意一個。一般情況下，網絡圖中應有2N-1種狀態，輸入信息序列有2kL中可能，因而網絡圖中路徑也可能有2kL條，相應于編碼器輸出的2kL個不同的碼序列。例如若給出輸入信息位為1101000時，則這時的輸出編碼序列是11 10 10 00 01 11 00。由上述可見，用網絡圖表示編碼過程和輸入輸出關系比樹狀圖更為簡練。2.2 Viterbi譯碼原理2.2.1Viterbi算法描述Viterbi算法是一種最大似然譯碼算法，它是通過計算累積碼距，在卷積網絡圖上尋找一條與接受序列R具有最小碼距的最大似然路徑

38、。假定編碼器輸入信息序列為C，經過離散無記憶信道傳輸后，譯碼器接受到的序列為R,輸入信息序列C與接受信息序列R的關系為R=C+E，E是信息序列在信道傳輸過程中產生的錯誤序。譯碼器根據接受到的信息序列R，根據最大似然原則在卷積網絡圖上尋找到一條與接受序列R具有最小碼距的最大似然路徑，這個過程就是譯碼器尋找有“最大”度量的路徑過程，也就是尋找最大似然函數Maxf=logbp(R/Cj),j=1,2,.2kL的過程，其中L表示時間單位數，k表示輸入的bit位數，p（*）表示概率。最大似然函數Maxf=logbp(R/Cj)是Cj的似然函數，也稱為Cj的路徑度量，Cj表示某一個可能的輸入信息序列。對二

39、進制同步信道（BSC）來說，尋找具有最大路徑度量的路徑（即尋找最大似然函數）相當于尋找與接受序列R有著最小漢明距離的路徑，即尋找 Minj=d(R,Cj), j=1,2,.2KL （2.2.1-2）其中，d（*）是表示漢明距。 我們現在假定L=200，n=2，k=1時，那么卷積碼的網絡圖中就有2200條路徑，如果每一條路徑都與接受序列R進行逐一比較后尋找最大度量路徑，工作量太大啦，因此直接用上述方法進行譯碼難以實現。為了解決這一困難，Viterbi算法應用而生。Viterbi算法不需要把每一條路徑都與接受序列R進行比較，而是接受一段，計算一段，比較一段，選擇其中“最大”度量分支，再進行下一輪的

40、比較。當接受完序列R時，幸存下來的那條路徑就是我們要尋找的最大路徑度量路徑。Viterbi譯碼的總體流程是比較各分支的度量值，選擇一段最可能的分支，更新狀態的度量，并根據比較結果獲得狀態轉移表，最后通過狀態轉移表的回溯算法完成譯碼，其具體步驟如下：（1） 從某一時間單位j=m開始，對每一狀態路徑長度為j段的路徑計算其路徑度量值，然后進行比較，對于每一個狀態，選擇其中有著最大度量的部分路徑幸存下來，并存儲該部分路徑的度量值PM，保留下來的路徑稱為幸存路徑SP。（2） j+1，計算該時刻進入各個狀態的分支度量值BM，把計算得到的分支度量值BM與上一步中幸存路徑的路徑度量值PM相加，然后進行比較，選

41、擇其中相加數最小的路徑作為該狀態的幸存路徑，并更新狀態的路徑度量值PM，幸存路徑就又延長了一個分支。（3） 若j<L+m，則重復以上的兩個步驟。若j=L+m，則譯碼結束，譯碼器就可得到有最大路徑度量的路徑。 2.2.2Viterbi算法舉例 設卷積碼編碼器（2，1，2）輸入信息序列為M=(1011100),經過卷積碼編碼器后，輸出的序列C=(11,10,00,01,10,01,11)，而譯碼器接受到的序列為R=(10,10,00,01,11,01,11)，可見因為信道的干擾與噪聲影響，已經產生了2個錯碼。下面對照網絡圖來說明維特比譯碼的方法。圖2-5描述的是維特比譯碼器譯碼的過程。圖中d

42、表示各個時刻進入每一個狀態的幸存路徑的度量值（即最小漢明距離），m表示與此相對應的譯碼器估計的信息序列。由圖可以看出，在某一時刻，如j=3時刻，這一時刻接受到的子碼R2=00。尋找S1狀態的幸存路徑方法如下：這時刻進入S1狀態有兩條分支，上分支是由前一時刻狀態S2在編碼器輸入信息碼元“1”轉移而來的，這條路徑的度量值d0（S2，00）=d0（11，10,00）=ds2+0=1+0=1;下分支是由前一時刻由前一時刻狀態S0在編碼器輸入信息碼元“1”轉移而來的，這條路徑的度量值d1（S0，11）=d1（00，00,11）=ds0+2=2+2=4。根據最小漢明距離準測可得，進入S1狀態應保留上分支，

43、即第三時刻S1狀態的幸存路徑應為C（S2，00）=（11，10，00），這條路徑的度量值是d=1，譯碼器估計的信息序列m=101。若某一時刻進入某一狀態的兩條路徑有相同的度量，可以選擇其中任意一條路徑作為幸存路徑，并不會影響譯碼結果的正確性。如第四時刻，進入S2狀態的兩條路徑（11，10，00，10）和（00，11，01，01），它們的度量d都為3，故可任選一條作為S2狀態的幸存路徑，在圖中選擇（11，10，00，10）。在其他時刻及進入其余狀態的幸存路徑的選擇與此完全相同。按照這種方法依次譯碼，到了L+m=7個時刻以后，4條幸存路徑只剩一條，這條路徑就是我們要找的具有最大似然函數的路徑，譯碼

44、器輸出的估值序列C=（11，10，00，01，10，01，11），把接受信息序列R中的兩個錯誤糾正過來啦，相應的估值信息序列M=(1011100),，譯碼結果跟編碼器輸入信息序列一樣。 圖2-5 維特比譯碼器的譯碼過程2.2.3 Viterbi譯碼器的特點綜上所述，維特比譯碼器應具備如下特點： （1）（n.k.m）卷積碼編碼器中寄存器共有2km個狀態，每一個狀態都應該配置一個路徑存儲器和一個PM存儲器。路徑存儲器用來存儲譯碼起點，PM存儲器用來存儲各個狀態的PM值。因為維特比譯碼器的硬件資源和設置復雜度隨約束長度k值呈指數增加，因此在實際應用中，為了避免viterbi譯碼器功耗過大和成本太高的

45、問題，k一般小于10。（2） 每個PM存儲器存儲路徑的寬度是nL。L是卷積碼譯碼時譯碼器需要存儲的碼序列節點總長度。若nL的取值過大，維特比譯碼器所占用存儲資源的上升會給工程應用帶來很多困難。而在一般實際情況中，經過5至6級節點后，各留選SP基本完全重和為一條SP。因此，XL的寬度不必很大，只需選擇存儲X段譯碼段即可滿足譯碼需要。（3） 當譯碼器譯碼完第x段數據后，必須在所有數據仍為處理完畢前對存儲器中SP進行截尾譯碼判決輸出，雖然這樣會使誤碼率稍高，但在工程應用的情況下，取x=(5-10)倍的約束長度，對譯碼器性能影響很小。下面介紹截尾譯碼算法。由圖2-5可以看出，當譯碼器譯完第5級節點以后

46、，每個狀態留選路徑的前幾個分支已完全重合在一起，可以將相同的路徑輸出，從這一點我們可以得知:每個路徑寄存器不必存儲L很大的碼序列(或信息序列M)，而只要存儲<<L段子碼即可。也就是當譯碼器接收并處理完第個碼段后，找出最似然度量值所對應的幸存路徑作為判決輸出，當譯碼器接收并處理完第+1個碼段時，信息元仍然可以用上面幸存路徑存儲器來存儲。像這種不等處理完所有 L段碼序列，譯碼器就開始進行判決和輸出的譯碼方法稱為Viterbi譯碼的截尾譯碼，也成回溯運算。第三章 Viterbi譯碼的FPGA實現3.1 Viterbi譯碼器的基本結構 Viterbi譯碼器的基本原理是就是將接受到的信息序列

47、R與可能發送的信息序列進行比較，比如發送一個k位序列，那發送的信息序列就有2k種可能，然后將這2k種可能的發送信息序列與接收到的信息序列R進行比較，選擇其中漢明距離最小的信息序列作為譯碼結果。當k值很大時，計算量太大，存儲量也很大，不適合直接使用譯碼方法。維特比算法就解決了這個問題，它不需要比較所有可能的2k種信息序列，而是接受一段，計算和比較一段，選擇其中漢明距離最小的碼段，再進行下一輪比較，最終找到一個有著最大似然值的信息序列。維特比譯碼器主要由分支度量模塊（BMU）、加比選模塊（ACS）、路徑度量存儲模塊（PMU）、幸存路徑寄存模塊（SMU）、回溯模塊（TBU）構成，系統框架圖如圖3-1

48、。 圖3-1 Viterbi 譯碼器的內部結構圖 系統工作過程可以分為以下幾個步驟：（1） 首先從（2，1，9）卷積碼編碼器中輸入相應的信息碼元，編碼器輸出信息碼元經過分支度量模塊BMU，計算譯碼器接受的信息碼元與各狀態期望碼元之間漢明距離，把計算得到的BM值送人ACS單元進行加比選操作。（2） ACS單元從路徑度量存儲模塊PMU單元中取出前一時刻幸存路徑的度量值old_metric,然后與送人ACS單元的分支度量模塊BMU的分支度量值累計相加比較，相加度量值較小的作為該狀態新的路徑度量值new_metric存入PMU單元以備下一時刻加比選使用，并產生幸存路徑信息survivor_bit存入幸

49、存路徑寄存模塊SMU。這個幸存信息表示在加比選操作中，該狀態是由前一時刻進入該狀態的哪條分支轉移而來的，當survivor_bit=0時表示該狀態是由偶狀態（即上支路）轉移而來，當survivor_bit=1時表示該狀態是由奇狀態（即下支路）轉移而來。（3） 當達到回溯深度時，ACS單元會輸出一個路徑累加度量值最小的狀態low_state送人TBU單元，TBU開始工作，同時SMU單元根據這個信號產生一個SMU地址lookup_state,根據這個地址可以從SMU單元中讀出該狀態的幸存信息lookup_bit,進入TBU單元進行譯碼操作輸出。同時，也可以根據這個幸存比特反推出這個最小狀態是由前一

50、時刻哪個狀態轉移而來的，而根據反推出來的狀態又產生一個新SMU地址lookup_state，根據這個新的地址又可以從SMU單元中讀出該狀態的幸存信息lookup_bit,再進入TBU單元進行譯碼操作輸出。如此循環下去，就可以得到在回溯深度這個時間段內將所有譯碼輸出，再進行倒序處理，就可以得到正確的譯碼輸出。系統工作操作流程如圖3-2。 圖3-2 譯碼器的工作流程圖3.2 分支度量模塊（BMU） 分支度量模塊是比較輸入碼元與狀態分支間的似然函數值，然后將其按照加比選模塊提供的地址信號輸出相應的數值。由于信道特性的不同，可以分為硬判決跟軟判決兩種判決方式，硬判決是使用漢明距離來表示分支度量，軟判決

51、是使用歐式距離來表示分支度量，不同的判決方式計算接收碼元序列跟期望序列之間的距離的計算方法也不一樣。在硬判決中，需要設定一個門限值，高于這個門限值的就判決為1，低于這個門限值的就判決為0，因此硬判決只有兩種距離,且這兩種距離相差為1，這種判決較為簡單。例如設期望序列v=v0，v1，.vn-1,接收到的序列為r=r0，r1，.rn-1,則漢明距離,而歐式距離為，如果收到序列r=0，1,期望序列v=1，0,使用硬判決，分支度量值就為=|1-0|+|0-1|=2，若使用3比特軟判決，1量化為7（111），0量化為（000），則上述所對應的接受序列為r=5（101），4（100），期望序列v=7，0，

52、所以分支度量值則為=。由此可見使用軟判決計算分支度量值時既有平方運算又有開方運算，運算較復雜，會占用比較多的硬件資源，影響運算速度。本次實驗采用硬判決。 對于碼率為R=k/n的卷積碼來說，每個狀態都2k條分支進入，分支度量計算模塊就要計算2k個分支度量值，對于（2，1，9）卷積碼來說，共有28個即256個狀態，每個狀態又有2條分支進入，所以總共要計算512個分支度量值。但是，每一個狀態的輸出期望碼元只可能是00，01，10，11這四個中的一個，而且同一時刻接受序列是相同的，所以所有狀態的分支度量值也只有4種可能，所以分支度量模塊不需要把所有狀態的分支度量值都計算出來，只需要把這四種可能的分支度

53、量值計算出來，然后存儲到相應的寄存器中，以備不同狀態的加比選模塊選用。BM00表示期望碼字00的分支度量值，BM01表示期望碼字01的分支度量值，BM10表示期望碼字10的分支度量值，BM11表示期望碼字11的分支度量值。而對于碼率R=1/3的卷積碼來說，每一個狀態輸出期望碼元只可能是000，001，010，011，100，101，110，111中的一個，同樣，每一時刻接收到的序列是相同，因此所有狀態的分支度量值也只可能有8中情況，分別為BM000，BM001，BM010，BM011，BM100，BM101，BM110，BM111。BM000表示期望碼字000的分支度量值，BM001表示期望碼

54、字001的分支度量值，BM010表示期望碼字010的分支度量值，BM011表示期望碼字011的分支度量值，BM100表示期望碼字100的分支度量值，BM101表示期望碼字101的分支度量值，BM110表示期望碼字110的分支度量值，BM111表示期望碼字111的分支度量值。3.3 加比選模塊(ACS) 加比選模塊是整個viterbi譯碼器的核心部分，可以說它的性能直接決定著整個譯碼器的性能。它的主要功能是，把路徑度量存儲單元（PMU）中存儲的各狀態所處的路徑度量與BMU中相應狀態的各分支度量值相加，比較這些結果，選擇最小的那個作為該狀態幸存路徑再存入PMU，并得到路徑選擇的標志位存入SMU。因

55、此，加比選模塊由加法器、比較器、選擇器組成。同時，當達到回溯深度時，加比選模塊還必須選出累積路徑度量值最小的那個狀態，在回溯模塊TBU譯碼時使用。 3.3.1狀態間的蝶形運算關系 比較哪條路徑與發送碼字更接近，就是比較它們誰具有更大的似然函數，對于硬判決來說，也即比較誰具有更小的歐氏距離。此時我們面臨的主要問題，對于到達某一狀態的兩條路徑來說，它們分別來自哪兩個狀態。對于（n，k，m）卷積碼來說，每個狀態有2k條分支進入，其加比選運算如下式 （3-1） 當k=1時，轉移到每個狀態的分支為2條，每個狀態也只可能轉移到兩個狀態中去，輸入也只能是0或1，因此這類卷積碼的網絡結構是蝶形的。假設兩個相鄰的狀態Si=Y0Y1Y30和SJ=Y0Y1Y