應(yīng)用于通信系統(tǒng)中的高性能Viterbi譯碼器實(shí)現(xiàn)

黃 昊，秦水介

（1.貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院，貴州 貴陽　550025；2.貴州省光電子技術(shù)與應(yīng)用重點(diǎn)實(shí)驗室 貴州 貴陽　550025）

應(yīng)用于通信系統(tǒng)中的高性能Viterbi譯碼器實(shí)現(xiàn)

黃 昊1，2，秦水介2

（1.貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院，貴州 貴陽550025；2.貴州省光電子技術(shù)與應(yīng)用重點(diǎn)實(shí)驗室 貴州 貴陽550025）

針對無線通信系統(tǒng)中對于高頻率、高吞吐量的要求，提出了一種基于ASIC的高速Viterbi譯碼器實(shí)現(xiàn)方案。該譯碼器在約束度小于等于9的情況下，采用全并行結(jié)構(gòu)的加比選模塊。性能分析結(jié)果表明，在SMIC 40 nm工藝，通過使用Synopsys Design Compiler對RTL代碼進(jìn)行邏輯綜合，該譯碼器在時鐘頻率為166 MHz情況下，最終得到面積為0.2 mm2，功耗為18 mW，吞吐量達(dá)到82 Mbps。

Viterbi；譯碼器；ASIC；功耗

前向糾錯技術(shù)特別是卷積編碼是當(dāng)今數(shù)字通信系統(tǒng)的一個重要組成部分，Viterbi譯碼算法由于具有譯碼性能良好，譯碼結(jié)構(gòu)相對簡單，譯碼延時低等特性，是前向糾錯系統(tǒng)中一種最優(yōu)化的卷積碼譯碼算法［1］，在通信系統(tǒng)中，特別的衛(wèi)星系統(tǒng)中得到廣泛的應(yīng)用。當(dāng)今通信系統(tǒng)中，對吞吐量，工作頻率的要求越來越高，本文在低功耗的基礎(chǔ)上，提高了譯碼器的工作頻率和吞吐率。

1　卷積碼介紹

卷積碼編解碼的表示方法很多，這些表示方法與解碼方式有密切關(guān)系。通常使用的卷積碼的表示方法有多項式表示，狀態(tài)轉(zhuǎn)移圖表示，網(wǎng)格表示等。

卷積碼的狀態(tài)轉(zhuǎn)移圖表示就是將編碼的存儲單元所代表的值看做一個狀態(tài)，根據(jù)編碼規(guī)則，添加狀態(tài)轉(zhuǎn)移路徑。如圖1所示為（2，1，2）卷積碼的狀態(tài)轉(zhuǎn)移圖。

編碼存儲為m的卷積碼，存儲單元的個數(shù)是m，因而總的狀態(tài)數(shù)有種。圖示卷積碼總狀態(tài)數(shù)為4中，分別為00，01，10，11。對于信息元為k的卷積碼，每個狀態(tài)的狀態(tài)轉(zhuǎn)移路徑有種。狀態(tài)轉(zhuǎn)移圖能夠表示出編碼器在不同輸入的信息序列下，各個狀態(tài)之間的轉(zhuǎn)移關(guān)系。

圖1　卷積碼狀態(tài)轉(zhuǎn)移圖

卷積碼的網(wǎng)格表示如圖2所示，此圖是L=5時，（2，1，2）碼的網(wǎng)格圖，橫向表示時間單位，縱向表示狀態(tài)組成，共有L+ m+1個時間單位。在圖2所示的編碼器中，狀態(tài)從00開始，最后回到00。在編碼過程中，從00狀態(tài)開始，經(jīng)過L個時間單位，編碼器可能會進(jìn)入到任意狀態(tài)，但是加入m個額外的時間單元，每個單元中都輸入0信息元后，編碼器肯定會回到00狀態(tài)。對于（n，k，m）卷積碼，若編碼器的狀態(tài)從全0開始，在任意長度時間單元后添加m個時間單元，這m個時間單元中都輸入k個0信息元，可以保證回到全0狀態(tài)。

圖2　卷積碼網(wǎng)格圖

2　Viterbi算法流程

一般把Viterbi譯碼器劃分為4大模塊［2］，分別為分支度量計算單元（Branch Metrics Unit，BMU），加比選單元（Add-Compare-Select Unit，ACS），路徑度量存儲單元（Path Metrics Unit，PMU），幸存路徑存儲及輸出單元 （Survivor Memory Unit，SMU）如圖3所示。硬件實(shí)現(xiàn)的Viterbi算法中，BMU，用來計算一個單位時間內(nèi)，各個狀態(tài)的分支度量，ACS單元根據(jù)候選路徑的分支度量和路徑度量，比較并選擇一個具有較小路徑度量的路徑作為幸存路徑，并將這個路徑對應(yīng)的比特輸出到PMU單元中存儲。在所有的碼塊都計算完成后，存儲器中已經(jīng)存入了所有狀態(tài)對應(yīng)的前向狀態(tài)（幸存路徑），根據(jù)所使用的卷積碼的尾比特設(shè)計，從0狀態(tài)或者具有最小路徑度量的狀態(tài)開始，回溯幸存路徑，輸出解碼結(jié)果。

圖3　Viterbi譯碼器結(jié)構(gòu)圖

BMU單元：負(fù)責(zé)生成所有可能的路徑，并計算進(jìn)入加比選譯碼單元各分支的漢明距離，為后繼的ACS單元提供輸入。

ACS單元：對生成的分支路徑漢明距離進(jìn)行累加、比較、選擇并輸出路徑度量較小的節(jié)點(diǎn)。

PMU單元：存儲每一級所有節(jié)點(diǎn)的路徑度量值，并在時鐘控制下不斷進(jìn)行更新。

SMU單元：存儲幸存路徑信息并輸出譯碼序列。

2.1分支度量計算單元（BMU）設(shè)計

BMU單元計算譯碼輸入與各個狀態(tài)分支間的距離度量值，并作為加比選單元的輸入，對于8電平均勻量化軟判決譯碼器來說，是將各個狀態(tài)分支的0和1量化成0和7，再計算距離度量值，因為計算分支度量值就變得相對簡單，如果接受碼為X和Y，bm00表示分支00的分支度量，bm11表示分支11的分支度量，bm10表示分支10的分支度量，bm01表示分支01的分支度量，則：

bm00=x+y

bm11=7-x+7-y

bm10=7-x+y

bm01=x+7-y

通過分析可知，7-x與x按位取反相等，所以上式可簡化為：

bm00=x+y

bm11=～x+～y

bm10=～x+y

bm01=x+～y

～x和～y分別表示對x和y按位取反。如此只用到了加法器而已，從而簡化這部分的邏輯結(jié)構(gòu)，實(shí)現(xiàn)起來也很方便，而且便于放置運(yùn)算溢出錯誤，因為x和y是無符號數(shù)，用三比特來表示，則x，y，～x，～y都是非負(fù)整數(shù)，而在每次計算度量值時，都是幾個無符號數(shù)之和，由于每個無符號數(shù)的最大值是7，所以最大度量值是14，可以用4比特的數(shù)值的來表示。在不影響的糾錯性能的情況了減少了BMU模塊消耗的系統(tǒng)資源。

2.2加比選單元設(shè)計

在實(shí)現(xiàn)譯碼器時，針對不同的設(shè)計要求，有3種主要的ACS結(jié)構(gòu)，分別是全并行、全串行和串并行結(jié)合。本文采用全并行結(jié)構(gòu)，在全并行結(jié)構(gòu)中，含有和狀態(tài)數(shù)相同的 ACS單元，所有的 ACS單元同時操作，為了提高解碼器的吞吐量，viterbi的解碼器實(shí)現(xiàn)了256個并行的計算單元，對于約束長度m小于等于9的卷積碼，都可以在一個時鐘周期完成計算。

圖4　基二蝶形運(yùn)算圖

蝶形單元（Butterfly，BF）而不是ACS單元。很明顯，每個BF單元包含兩個ACS單元，并具有相同的輸入和輸出狀態(tài)。BF單元的兩個路徑度量值更新是由前面狀態(tài)的路徑度量值和當(dāng)前的分支度量值通過兩次ACS操作來實(shí)現(xiàn)的。整個ACS單元由下面的128個BF單元組成。

通常Viterbi譯碼的加比選單元（ACS）采用基 2的方式，利用兩個前面狀態(tài)的路徑度量值和4個分支度量計算單元（BMU）獲得的分支度量值來更新路徑度量值。

例如，對于圖2中的S0和S1狀態(tài)，有

其中BM00是從狀態(tài)分支為00的分支度量，BM11是狀態(tài)分支為11的分支

度量，ACS單元對每個輸出狀態(tài)產(chǎn)生一個代表所選路徑的判決，該判決比特存儲到SMU中，用于輸出單元。ACS的加比選擇操作判斷下面的式子是否成立，并根據(jù)判斷結(jié)果存儲留選路徑，更新狀態(tài)值。

用減法比較來代替：

式（5），（6）的減法操作，相對于式（3），（4）的操作，在計算復(fù)雜度和功耗時可以忽略。

2.3路徑度量存儲單元設(shè)計

從ACS的工作過程可以看出，譯碼時需要不斷的讀出舊的路徑度量，并寫入新的路徑度量。計算當(dāng)前時刻的路徑度量時，必須用到前一時刻的度量值，所以在傳統(tǒng)Viterbi譯碼算法實(shí)現(xiàn)時，需對每一狀態(tài)的路徑度量加倍緩存。如果能夠使度量的讀出與寫入的地址相同，就可以是存儲空間減少一半，研究發(fā)現(xiàn)，譯碼過程中的狀態(tài)轉(zhuǎn)移具有很好的規(guī)律性，如果建立了轉(zhuǎn)移后的新狀態(tài)與轉(zhuǎn)移前的老狀態(tài)的地址映射關(guān)系，就可以使度量更新在原位進(jìn)行。

2.4幸存路徑存儲及輸出單元設(shè)計

Viterbi譯碼器的輸出部分有寄存器交換法 RE（Register Exchenge）與回溯法TB（Trace Back）兩種方式。文中采用回溯法，回溯法則采用通用的RAM作為存儲主體，存儲的是幸存路徑的格狀連接關(guān)系，通過讀寫RAM來完成數(shù)據(jù)的寫入和回索輸出。其優(yōu)點(diǎn)是內(nèi)連關(guān)系簡單、規(guī)則。在回溯法中，路徑存儲器中存儲的是記錄狀態(tài)轉(zhuǎn)移時的標(biāo)志位序列，達(dá)到譯碼深度后，根據(jù)當(dāng)前的狀態(tài)和判據(jù)序列，在網(wǎng)格圖上重建編碼索走過的路徑，逐位將編碼序列輸出。

文中采用最大路徑度量對應(yīng)的狀態(tài)回溯，回溯深度L= 256，約束長度K=9時，每次ACS迭代計算得到的256bit幸存路徑信息，1個時鐘周期輸出寫入幸存路徑寄存器，由于回溯的時候處理是由后向前的，所以時間在先的譯碼比特對后譯碼輸出，因此必須將譯碼輸出比特進(jìn)行倒置。因此緩存器采用后進(jìn)先出LIFO。

3　性能與分析

信道編碼的主要作用是糾錯，因此糾錯能力是信道編碼的一個重要標(biāo)準(zhǔn)。通常，信道編碼的性能是由誤比特率（Bit Error Rate BER）來表示的［3］。下面對幾種編碼進(jìn)行性能仿真。

首先是卷積碼的性能仿真，主要影響性能的因素是約束長度，圖5是（2，1，9）卷積碼和（2，1，5）卷積碼的性能比較。

圖5?。?，1，5）與（2，1，9）卷積碼的性能比較

文中采用Verilog硬件描述語言對各模塊進(jìn)行RTL級描述，使用由頂而下的設(shè)計方法，在VCS仿真平臺進(jìn)行仿真驗證，波形如圖6所示。

圖6　VCS仿真波形圖

采用 SMIC 40 nm工藝，在時鐘頻率為166 MHz情況下，使用 Synopsys Design compiler對RTL代碼進(jìn)行邏輯綜合，最終得到面積為0.2 mm2，功耗為18 mW，吞吐量達(dá)到82 Mbps。綜合報告如圖7所示。

如表 1所示，K值代表維特比譯碼器的約束長度，由于本維特比譯碼器采用全并行結(jié)合的設(shè)計方法，使得譯碼器在速率，吞吐量上有著較大的提升，在功耗，面積上也有所控制。

圖7　綜合與功耗報告

表1　幾種Viterbi譯碼器比較

4　結(jié)束語

文中設(shè)計了一種應(yīng)用于無線通信的高速Viterbi譯碼器，在約束度小于等于9的情況下，采用全并行的加比選模塊。該譯碼器具有時鐘頻率高，吞吐量大，功耗較低等優(yōu)點(diǎn)，具有良好的應(yīng)用前景。

［1］Viterbi A J.Error bounds for convolutional codes and an asymptotically optimum decoding algorithm［M］.IEEE Transactions on Information Theory，1967.

［2］段華蓉.Viterbi譯碼器的低功耗設(shè)計［D］.重慶：重慶大學(xué)，2006.

［3］Pradhan A K，Nandy S K.A Reconfigurable Viterbi Decoder for SDR and Mobile Communications［M］.High Performance Computing and Applications（ICHPCA），2014.

［4］朱坤順，楊紅官.無線通信系統(tǒng)中的低功耗維特比譯碼器［J］.計算機(jī)工程，2014（10）：114-116.

［5］朱勝，楊華中.一種高性能可重用Viterbi譯碼器的設(shè)計［J］.微電子學(xué)，2005（2）：32-33.

［6］Kunze S，Matus E，F(xiàn)ettweis G，et al.Combining LDPC，turbo and viterbi decoders：benefits and costs［J］.Signal Processing Systems，2011.

［7］Lin C C，Shih Y H，Chang H C，et al.Design of a powerreduction Viterbi decoder for WLAN applications［J］. IEEE Trans.on Circuit and Systems I，2005，52（6）：1148-1156.

［8］金文學(xué)，劉秉坤，陳嵐.低功耗軟判決維特比譯碼器的設(shè)計［J］.計算機(jī)工程，2007，33（5）：243-247.

Used in communication system of high performance Viterbi decoder implementaion

HUANG Hao1，2，QIN Shui-jie2
（1.Big data and information engineering institute，Guizhou University，Guiyang 550025，China；2.Guizhou Province of The Key Laboratory Optoelectronic Technology and Application，Guiyang 550025，China）

We propose a high-speed Viterbi decoder imlementations based on ASIC.In order to cope with a wireless communication system for hign frequency and throughput requirement.The Viterbi decoder plus a fully parallel structure comparison module in the case of less constraint of 9.Performance analysis results show that rtl code for logic synthesis by using thssynopsys design compiler.Finally obtainted area is 0.2 mm2，power consumption is 18 mW，throughtput sent to 82 Mbps under clock frequency of 166 MHz.

Viterbi；decoder；ASIC；power

TN47

A

1674－6236（2016）09-0153-03

2015-09-21稿件編號：201509139

黃 昊（1989—），男，安徽蕪湖人，碩士。研究方向：集成電路設(shè)計，信號與信息處理。