應用于通信系統中的高性能Viterbi譯碼器實現

黃 昊，秦水介

（1.貴州大學 大數據與信息工程學院，貴州 貴陽　550025；2.貴州省光電子技術與應用重點實驗室 貴州 貴陽　550025）

應用于通信系統中的高性能Viterbi譯碼器實現

黃 昊1，2，秦水介2

（1.貴州大學 大數據與信息工程學院，貴州 貴陽550025；2.貴州省光電子技術與應用重點實驗室 貴州 貴陽550025）

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

Viterbi；譯碼器；ASIC；功耗

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

1　卷積碼介紹

卷積碼編解碼的表示方法很多，這些表示方法與解碼方式有密切關系。通常使用的卷積碼的表示方法有多項式表示，狀態轉移圖表示，網格表示等。

卷積碼的狀態轉移圖表示就是將編碼的存儲單元所代表的值看做一個狀態，根據編碼規則，添加狀態轉移路徑。如圖1所示為（2，1，2）卷積碼的狀態轉移圖。

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

圖1　卷積碼狀態轉移圖

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

圖2　卷積碼網格圖

2　Viterbi算法流程

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

圖3　Viterbi譯碼器結構圖

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

ACS單元：對生成的分支路徑漢明距離進行累加、比較、選擇并輸出路徑度量較小的節點。

PMU單元：存儲每一級所有節點的路徑度量值，并在時鐘控制下不斷進行更新。

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

2.1分支度量計算單元（BMU）設計

BMU單元計算譯碼輸入與各個狀態分支間的距離度量值，并作為加比選單元的輸入，對于8電平均勻量化軟判決譯碼器來說，是將各個狀態分支的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按位取反。如此只用到了加法器而已，從而簡化這部分的邏輯結構，實現起來也很方便，而且便于放置運算溢出錯誤，因為x和y是無符號數，用三比特來表示，則x，y，～x，～y都是非負整數，而在每次計算度量值時，都是幾個無符號數之和，由于每個無符號數的最大值是7，所以最大度量值是14，可以用4比特的數值的來表示。在不影響的糾錯性能的情況了減少了BMU模塊消耗的系統資源。

2.2加比選單元設計

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

圖4　基二蝶形運算圖

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

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

例如，對于圖2中的S0和S1狀態，有

其中BM00是從狀態分支為00的分支度量，BM11是狀態分支為11的分支

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

用減法比較來代替：

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

2.3路徑度量存儲單元設計

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

2.4幸存路徑存儲及輸出單元設計

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

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

3　性能與分析

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

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

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

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

圖6　VCS仿真波形圖

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

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

圖7　綜合與功耗報告

表1　幾種Viterbi譯碼器比較

4　結束語

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

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

［2］段華蓉.Viterbi譯碼器的低功耗設計［D］.重慶：重慶大學，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］朱坤順，楊紅官.無線通信系統中的低功耗維特比譯碼器［J］.計算機工程，2014（10）：114-116.

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

［6］Kunze S，Matus E，Fettweis 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］金文學，劉秉坤，陳嵐.低功耗軟判決維特比譯碼器的設計［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—），男，安徽蕪湖人，碩士。研究方向：集成電路設計，信號與信息處理。