基于FPGA的Viterbi譯碼器

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

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

3、比；譯碼器；現(xiàn)場可編程門陣列 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 卷積碼基礎(chǔ)122.1.1 卷積碼編碼原理122.1.2 卷積碼的描述142.2 Viterbi譯碼原理182.2.1Viterbi算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

27、有監(jiān)督作用。因此常用（n，k，m）表示卷積碼，其中m為編碼記憶，它反映了輸入信息元在編碼器中需要存儲的時間長短；N=m+1稱為卷積碼的約束度，單位是組，它是相互約束的子碼的個數(shù)；N*n被稱為約束長度，單位是位，它是相互約束的二進制碼元的個數(shù)。 在線性分組碼中，單位時間內(nèi)進入編碼器的信息序列一般都比較長，k可達8100。因此，編出的碼字n也較長。對于卷積碼，考慮到編、譯碼器設(shè)備的可實現(xiàn)性，單位時間內(nèi)進入編碼器的信息碼元的個數(shù)k通常比較小，一般不超過4，往往取k=1。2.1 卷積碼基礎(chǔ)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時，輸出端開關(guān)依次接到X1,j，X2,j和X3,j各端點一次。其中X1,j，X2,j和X3,j由下式?jīng)Q定 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相關(guān)，還跟之前時刻的兩個信息碼元m j-1、m j-2相關(guān)，

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)編碼器狀態(tài)表 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 狀態(tài) a b d c b c a a 表2-1列舉了圖2-1所示編碼器的狀態(tài)。其中a，b，c，d表示 m j-1m j-2的四種可能的狀態(tài)：00，01，10，11。當?shù)谝?/p>

30、位信息比特為1時，即m1=1，因移位寄存器的狀態(tài) 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 卷積碼的描述卷積編碼有集中描述方法，其中使用比較多的是樹狀圖、網(wǎng)絡(luò)圖和狀態(tài)圖，現(xiàn)在我們以（2，1，2）卷積碼為例

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

51、是使用歐式距離來表示分支度量，不同的判決方式計算接收碼元序列跟期望序列之間的距離的計算方法也不一樣。在硬判決中，需要設(shè)定一個門限值，高于這個門限值的就判決為1，低于這個門限值的就判決為0，因此硬判決只有兩種距離,且這兩種距離相差為1，這種判決較為簡單。例如設(shè)期望序列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的卷積碼來說，每個狀態(tài)都2k條分支進入，分支度量計算模塊就要計算2k個分支度量值，對于（2，1，9）卷積碼來說，共有28個即256個狀態(tài)，每個狀態(tài)又有2條分支進入，所以總共要計算512個分支度量值。但是，每一個狀態(tài)的輸出期望碼元只可能是00，01，10，11這四個中的一個，而且同一時刻接受序列是相同的，所以所有狀態(tài)的分支度量值也只有4種可能，所以分支度量模塊不需要把所有狀態(tài)的分支度量值都計算出來，只需要把這四種可能的分支度

53、量值計算出來，然后存儲到相應的寄存器中，以備不同狀態(tài)的加比選模塊選用。BM00表示期望碼字00的分支度量值，BM01表示期望碼字01的分支度量值，BM10表示期望碼字10的分支度量值，BM11表示期望碼字11的分支度量值。而對于碼率R=1/3的卷積碼來說，每一個狀態(tài)輸出期望碼元只可能是000，001，010，011，100，101，110，111中的一個，同樣，每一時刻接收到的序列是相同，因此所有狀態(tài)的分支度量值也只可能有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）中存儲的各狀態(tài)所處的路徑度量與BMU中相應狀態(tài)的各分支度量值相加，比較這些結(jié)果，選擇最小的那個作為該狀態(tài)幸存路徑再存入PMU，并得到路徑選擇的標志位存入SMU。因

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