劉楊，章敏

（桂林電子科技大學(xué) 廣西 桂林 541004）

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

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級(jí)移位寄存器的有限狀態(tài)記憶系統(tǒng)，通常稱為時(shí)序網(wǎng)絡(luò)。其中R=k/n為編碼效率，m為約束長(zhǎng)度。卷積碼編碼原理如圖1所示。

圖1卷積碼編碼器原理圖Fig.1 Principle diagram of convolutional encoder

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

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

圖2編碼器狀態(tài)圖Fig.2 State diagram of encoder

描述卷積碼的方法主要有兩類[1]：圖解表示和解析表示。上文提到的生成多項(xiàng)式G=（111，101）即是解析表示。卷積碼的圖解表示又可分為樹(shù)狀圖、網(wǎng)格圖和狀態(tài)圖3種。下面介紹常用的樹(shù)狀圖表示（網(wǎng)格圖表示將在譯碼部分介紹）。在圖2所示的卷積編碼樹(shù)狀圖中，假設(shè)移位寄存器的起始狀態(tài)全為0，當(dāng)?shù)?個(gè)輸入比特為0時(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è)比特移出移位寄存器而消失。移位過(guò)程可能產(chǎn)生的各種序列如圖3中的二叉樹(shù)。

圖3 （2，1，3）卷積碼的樹(shù)狀圖表示Fig.3 Tree diagram of（2,1,3）convolutional codes

2 Veterbi（維特比）譯碼器原理

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

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

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

圖 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。

圖4 （2，1，3）卷積碼的網(wǎng)格圖表示Fig.4 Trellis of（2,1,3）convolutional codes

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

3 譯碼器設(shè)計(jì)與實(shí)現(xiàn)

維特比譯碼器包括4個(gè)子模塊，如圖5所示。

圖5維特比譯碼器的總體框架Fig.5 Overall framework of veterbi decoder

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

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

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

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

4 譯碼器設(shè)計(jì)中改進(jìn)和優(yōu)化算法

本文采取狀態(tài)路徑和判決比特同時(shí)存儲(chǔ)，在表示狀態(tài)信息的比特前加上1位判決比特來(lái)表示相應(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)的譯碼器對(duì)每一個(gè)狀態(tài)都具有獨(dú)立的處理單元，彼此互補(bǔ)影響，并行工作，提高了譯碼速度。對(duì)于（2，1，3）卷積碼，一個(gè)時(shí)鐘需要進(jìn)行 2×2×2m=32次路徑量度計(jì)算和2m=8次4比特存儲(chǔ)操作。充分發(fā)揮了FPGA擁有大量LCS和RAM的優(yōu)勢(shì)。

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

5 驗(yàn)證仿真

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

5.1 卷積編碼器

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

5.2 Verterbi譯碼器

Verterbi譯碼器仿真波形如圖7所示，rev[1:0]為輸入譯碼器的接收序列，clk為時(shí)鐘信號(hào)，rst為復(fù)位信號(hào)，enable為使能信號(hào)，h_out為譯碼器輸出序列?？煽闯觯鹤g碼輸出碼元為“101010111011000100011011111111100……”，結(jié)果正確。

圖6卷積編碼器的仿真波形Fig.6 Simulation waveform of convolutional encoder

圖7維特比譯碼器的仿真波形Fig.7 Simulation waveform of veterbi decoder

6 結(jié)束語(yǔ)

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

[1]曹志剛.現(xiàn)代通信原理[M].北京：清華大學(xué)出版社，1994.

[2]王新梅，肖國(guó)鎮(zhèn).糾錯(cuò)碼原理與方法[M].西安：西安電子科技大學(xué)出版社，1991.

[3]夏宇聞.Verilog數(shù)字系統(tǒng)設(shè)計(jì)教程[M].北京:北京航空航天大學(xué)出版社，2003.

[4]ViterbiAJ.Errorboundsofconvolutionalcodesandanasymptotically optimum decoding algorithm [J].IEEE Transations on Information Theory,1967,13（2）:260-269.

[5]Anderson J B,Offer E.Reduced-state sequence detection with convolutional codes[J].IEEE Transactions on Information Theory,1994,40（3）:965-972.

[6]Proakis J G， Salehi M.Digital communications[M].北京：電子工業(yè)出版社，2006.