卷積碼是Elias在1955年最早提出的，稍后，Wozencraft在1957年提出了一種有效譯碼方法，即序列譯碼。Massey在1963年提出了一種性能稍差，但比較實(shí)用的門限譯碼方法，由于這一實(shí)用性進(jìn)展使卷積碼從理論走向?qū)嵱?。而后Viterbi在1967年提出了最大似然譯碼法，該方法對存儲(chǔ)器級數(shù)較小卷積碼的譯碼很容易實(shí)現(xiàn)，并具有效率高、速度快、譯碼器簡單等特點(diǎn)，人們后來稱其為維特比算法或維特比譯碼，廣泛應(yīng)用于現(xiàn)代通信中。本文主要論述了基于Xilinx公司的FPGA的卷積編碼器及相應(yīng)的維特比譯碼器的研究，并在幸存路徑存儲(chǔ)與譯碼輸出判決方面提出了改進(jìn)算法，從而使譯碼器結(jié)構(gòu)得到簡化。

1 卷積碼的編碼原理與實(shí)現(xiàn)
卷積碼是一種重要的前向糾錯(cuò)編碼FEC，用(n，k，m)表示。分組碼不同，其監(jiān)督元與本組的信息元和前若干組的信息元有關(guān)。這種編碼的糾錯(cuò)能力強(qiáng)，不僅可糾正隨機(jī)差錯(cuò)，而且可糾正突發(fā)差錯(cuò)。卷積碼根據(jù)需要，有不同的結(jié)構(gòu)及相應(yīng)的糾錯(cuò)能力，但都有類似的編碼規(guī)律。卷積碼的編碼器是一個(gè)具有k個(gè)輸入位(端)、n個(gè)輸出位(端)，m級移位寄存器的有限狀態(tài)記憶系統(tǒng)。通常稱為時(shí)序網(wǎng)絡(luò)。其中R=k／n為編碼效率，m為約束長度。卷積碼編碼原理如圖1所示。

卷積編碼充分利用各組信息元之間的相關(guān)性，在誤碼率和復(fù)雜度相同的情況下性能優(yōu)于分組碼，并且最佳譯碼更易實(shí)現(xiàn)，因此在通信系統(tǒng)中得到廣泛應(yīng)用。但是卷積碼沒有嚴(yán)格的代數(shù)結(jié)構(gòu)，尚未找到嚴(yán)密的數(shù)學(xué)手段將糾錯(cuò)性能與碼的構(gòu)成有規(guī)律地聯(lián)系起來，目前大都采用計(jì)算機(jī)搜索好碼。通常是(2，1，3)卷積碼，本文以生成多項(xiàng)式G=(111，101)的(2，1，3)卷積碼為例介紹設(shè)計(jì)和實(shí)現(xiàn)過程。

設(shè)初始狀態(tài)為SO編碼為00，根據(jù)生成矩陣分別帶入輸入O和輸入1時(shí)得到下一個(gè)狀態(tài)和相應(yīng)輸出。依次代入，可得到如圖2所示的狀態(tài)圖。

描述卷積碼的方法主要有兩類：圖解表示和解析表示。上文提到的生成多項(xiàng)式G=(111，101)即是解析表示。卷積碼的圖解表示又可分為樹狀圖、網(wǎng)格圖和狀態(tài)圖3種。下面介紹常用的樹狀圖表示(網(wǎng)格圖表示將在譯碼部分介紹)。在圖2所示的卷積編碼樹狀圖中，假設(shè)移位寄存器的起始狀態(tài)全為0，當(dāng)?shù)?個(gè)輸入比特為O時(shí)，輸出比特為00；若輸入比特為1時(shí)，則輸出比特為11。隨著第2個(gè)比特輸入，第1個(gè)比特右移1位，此時(shí)輸出比特同時(shí)受當(dāng)前輸入比特和第1個(gè)輸入比特的影響。第3個(gè)比特輸入時(shí)，第1、2比特分別右移1位，同時(shí)輸出2個(gè)由這3位移位寄存器存儲(chǔ)內(nèi)容所共同決定的比特。當(dāng)?shù)?個(gè)比特輸入時(shí)，第1個(gè)比特移出移位寄存器而消失。移位過程可能產(chǎn)生的各種序列如圖3中的二叉樹。

2 Velerbi(維特比)譯碼器原理
卷積碼的譯碼方式有3種：Veterbi譯碼、門限譯碼和序列譯碼。其中維特比譯碼具有最佳譯碼性能，但硬件實(shí)現(xiàn)相對復(fù)雜。veterbi算法是檢測離散馬兒可夫過程有限狀態(tài)序列的優(yōu)化算法。在數(shù)字通信系統(tǒng)中，前向糾錯(cuò)卷積碼編碼和維特比譯碼用來提高系統(tǒng)性能，應(yīng)用廣泛。

維特比算法是一種最大似然譯碼算法。它不是在網(wǎng)格圖上一次比較所有可能的2條完整路徑，而是接收一段，計(jì)算比較一段，選擇一段最有可能的碼段，從而達(dá)到整個(gè)碼序列是一個(gè)有最大似然函數(shù)的序列。其基本原理是：以斷續(xù)的接收碼流為基礎(chǔ)，逐個(gè)計(jì)算它與其他所有可能出現(xiàn)的連續(xù)的格狀圖路徑的距離，選出其中概率最大的一條作為譯碼輸出。

維特比(Veterbi)譯碼算法是基于卷積碼的網(wǎng)格圖表示中路徑的計(jì)算，其核心思想就是通過計(jì)算路徑矢量進(jìn)而尋找最短路徑從而最終得到譯碼序列并可以糾正傳輸過程中的錯(cuò)誤碼字。圖4中給出(2，1，3)卷積碼的網(wǎng)格圖表示。

圖4中的網(wǎng)格圖*有2k(N-1)種狀態(tài)，每個(gè)狀態(tài)(節(jié)點(diǎn))有2k條支路進(jìn)入，同時(shí)也有2k條支路引出。由于本文討論的是(2，1，3)卷積碼的情況，因此k=1，假設(shè)起始狀態(tài)為全0。

在不同時(shí)刻對于同一節(jié)點(diǎn)的所有8個(gè)狀態(tài)，分別計(jì)算以其為終點(diǎn)的2條分支路徑的對數(shù)似然函數(shù)累加值并進(jìn)行比較，舍棄其中對數(shù)似然函數(shù)累加值小的路徑，保留對數(shù)似然函數(shù)累加值較大的路徑，并將此路徑稱為剩余路徑。由此可見，上述過程可以歸納為“加-比-選”算法，經(jīng)過“加-比-選”電路以后，通過結(jié)束信息來確定最終得到的譯碼序列，其中每到來一個(gè)結(jié)束信息時(shí)，只將與已知發(fā)送信息相符的那條支路保留，以此類推，經(jīng)過N-1個(gè)結(jié)束信息后，即可得到與發(fā)送序列最相似的譯碼路徑。

3 譯碼器設(shè)計(jì)與實(shí)現(xiàn)
維特比譯碼器包括4個(gè)子模塊，如圖5所示。

1)控制單元 向各個(gè)功能模塊提供控制信號，保證譯碼器的工作時(shí)序正確，協(xié)調(diào)各個(gè)功能模塊從而促使整個(gè)譯碼器的正常工作。

2)路徑度量和“加-比-選單元”計(jì)算和比較每條支路的路徑度量，得到并保存剩余路徑提供給回溯單元。對于(2，1，3)卷積碼，譯碼深度D=5(m+1)=20，為保證存儲(chǔ)單元和回溯單元同時(shí)并行工作，存儲(chǔ)單元為2D(m+1)2m=1280 bit。

3)回溯單元 從前面“加-比-選”電路送來的剩余路徑中選擇量度最小的剩余路徑，從這條路徑對應(yīng)的狀態(tài)開始向前尋找，直到找完前面所有狀態(tài)，并從存儲(chǔ)單元中讀出譯碼信息送給譯碼控制單元。

4)譯碼控制單元 將回溯單元送來的譯碼序列反轉(zhuǎn)順序輸出即為所要輸出的正確的接收序列。其中反轉(zhuǎn)順序的操作可由RAM實(shí)現(xiàn)，順序?qū)懭氲剐蜃x出。

4 譯碼器設(shè)計(jì)中改進(jìn)和優(yōu)化算法
本文采取狀態(tài)路徑和判決比特同時(shí)存儲(chǔ)，在表示狀態(tài)信息的比特前加上1位判決比特來表示相應(yīng)狀態(tài)的輸入支路的譯碼信息，因此，譯碼器在回溯時(shí)就可直接輸出判決比特作為譯碼器的輸出，降低了譯碼器的判決難度，節(jié)省了存儲(chǔ)回溯路徑所需要的內(nèi)存，從而降低了譯碼器結(jié)構(gòu)復(fù)雜性。

本設(shè)計(jì)中譯碼器在計(jì)算所有狀態(tài)的路徑量度的同時(shí)進(jìn)行路徑存儲(chǔ)，從而大大提高了譯碼速度。路徑量度是指每個(gè)狀態(tài)的2條輸入支路和2條輸出支路，路徑存儲(chǔ)指的是狀態(tài)存儲(chǔ)以及相應(yīng)的譯碼判決比特存儲(chǔ)。該結(jié)構(gòu)的譯碼器對每一個(gè)狀態(tài)都具有獨(dú)立的處理單元，彼此互補(bǔ)影響，并行工作，提高了譯碼速度。對于(2，1，3)卷積碼，一個(gè)時(shí)鐘需要進(jìn)行2x2x2m=32次路徑量度計(jì)算和2m=8次4比特存儲(chǔ)操作。充分發(fā)揮了FPGA擁有大量LCS和RAM的優(yōu)勢。

在網(wǎng)格圖中，隨著狀態(tài)的改變，每個(gè)狀態(tài)的輸出支路的路徑量度逐漸增加，造成存儲(chǔ)資源壓力增大，設(shè)計(jì)中在每次進(jìn)行路徑量度計(jì)算時(shí)，將該狀態(tài)的量度值與上次剩余路徑量度的最小值做差后進(jìn)行保存，以達(dá)到減小存儲(chǔ)器空間的需求。對于編碼效率為1／2的卷積碼，以上差值最大不超過2m，因此，路徑量度的量化寬的為1b(2m)。對于(2，1，3)卷積碼，存儲(chǔ)路徑量度的寄存器位寬為lb(2×3)=3。

5 驗(yàn)證仿真
本設(shè)計(jì)采用Xilinx公司的ISE 9．2i為開發(fā)平臺，選用的是Xilinx Virtex 4 FPGA為開發(fā)芯片用于設(shè)計(jì)和驗(yàn)證所提出的卷積編碼和維特比(Veterbi)譯碼算法。

5．1 卷積編碼器
如圖6所示，clk為時(shí)鐘信號，reset為復(fù)位信號，din為輸入信號，out_1，out_2為編碼后得到的并行碼字序列?？煽闯觯狠斎氪a元為“101010111011 000100011011111111100……”經(jīng)過編碼得到編碼結(jié)果為“1101000100010010101000101011001101110011101001010101010 10101011”結(jié)果正確。

5．2 Verterbi譯碼器
Vertrbi譯碼器仿真波形如圖7所示，rev[1：0]為輸入譯碼器的接收序列，clk為時(shí)鐘信號，rst為復(fù)位信號，enable為使能信號，h_out為譯碼器輸出序列。可看出：譯碼輸出碼元為“10101011101100010001101111111l100……”。結(jié)果正確。

6 結(jié)束語
通過對卷積編碼原理與維特比譯碼算法的深入研究，在理解傳統(tǒng)實(shí)現(xiàn)方法的基礎(chǔ)上提出適合FPGA存儲(chǔ)器和獨(dú)立運(yùn)算單元豐富的特點(diǎn)的優(yōu)化算法，有效地提高了譯碼器的處理速度，簡化了譯碼器的復(fù)雜程度。