朱坤順,楊紅官,樊曉華,喬樹山

(1.湖南大學(xué)物理與微電子科學(xué)學(xué)院,長沙410082;2.中國科學(xué)院微電子研究所,北京100020)

無線通信中的低功耗維特比譯碼器設(shè)計(jì)

朱坤順1,楊紅官1,樊曉華2,喬樹山2

(1.湖南大學(xué)物理與微電子科學(xué)學(xué)院,長沙410082;2.中國科學(xué)院微電子研究所,北京100020)

針對(duì)無線通信中低功耗維特比譯碼器設(shè)計(jì)結(jié)構(gòu)復(fù)雜的問題,提出一種四級(jí)流水串并結(jié)合的(2,1,9)低功耗維特比譯碼器。該譯碼器采用改進(jìn)的加-比-選(ACS)單元,以降低硬件復(fù)雜度,在提高時(shí)鐘運(yùn)行速率的基礎(chǔ)上減少運(yùn)行功耗。幸存路徑存儲(chǔ)單元采用改進(jìn)的路徑相消方法,減少譯碼器的輸出延遲,提高譯碼效率。性能分析結(jié)果表明,基于TSMC 0.18 μm CMOS邏輯工藝,在1.62 V,125℃操作環(huán)境下,該譯碼器數(shù)據(jù)最大速度為50 MHz,自動(dòng)布局布線后的譯碼器芯片面積約為0.212 mm2,功耗約為23.9 mW。

維特比譯碼器;低功耗;加-比-選;路徑度量存儲(chǔ);路徑相消;幸存路徑

1 概述

在無線通信中,數(shù)據(jù)的傳輸過程總會(huì)受到各種噪聲和電磁的干擾,使得接收到的信息有一些錯(cuò)誤的傳輸。為了保證較高的糾錯(cuò)能力,卷積碼編碼被廣泛應(yīng)用于數(shù)字通信發(fā)送器,如WiFi、GSM、CDMA等。相應(yīng)的,在無線通信接收器中,維特比譯碼器成為了卷積碼譯碼恢復(fù)與校正數(shù)據(jù)為原始數(shù)據(jù)的關(guān)鍵部分。

維特比譯碼是在1967年由Viterbi提出的一種最大似然譯碼算法[1]。它已成功應(yīng)用于各種場合,如CDMA、GSM、衛(wèi)星、深空通信、無線局域網(wǎng)、演講識(shí)別、關(guān)鍵詞識(shí)別、計(jì)算語言學(xué)和生物信息學(xué)等, IEEE 802.11協(xié)議標(biāo)準(zhǔn)是維特比譯碼器最典型的應(yīng)用[2]。本文在低功耗的基礎(chǔ)上,設(shè)計(jì)了(2,1,9)維特比譯碼器,提高了譯碼器的工作頻率。

2 維特比譯碼算法與結(jié)構(gòu)

維特比譯碼是一種最大似然卷積碼譯碼。在維特比譯碼器中,卷積碼編碼的接收信號(hào)通常被噪聲損壞,本文通過計(jì)算路徑的對(duì)數(shù)似然函數(shù),將可能的估計(jì)序列與接收到序列的漢明距離或歐氏距離度量進(jìn)行比較,在樹狀圖或網(wǎng)格圖中選擇一條最小路徑的狀態(tài),從該狀態(tài)中估計(jì)出輸入最可能的序列編碼。

本文設(shè)計(jì)選用(2,1,9)維特比譯碼,其糾錯(cuò)性能優(yōu)異,在IEEE 802.11協(xié)議標(biāo)準(zhǔn)中得到廣泛的使用。(2,1,9)維特比譯碼生成多項(xiàng)式選擇為(753,561)8,圖1為(2,1,3)維特比譯碼器的網(wǎng)格圖[3],假設(shè)接收到的二位碼元數(shù)據(jù)為(00,11,10,10,00),通過維特比譯碼后,輸出一位二進(jìn)制數(shù)據(jù)為(0,1,1,0,1)。具體過程如下,首先定義接收的起始狀態(tài)為00,接著由起始點(diǎn)出發(fā),每輸入一個(gè)數(shù)據(jù),計(jì)算每一個(gè)狀態(tài)分支路徑的度量值(圓圈內(nèi)即該狀態(tài)的度量值),分支路徑的度量值即漢明距,圖中實(shí)線表示輸入數(shù)據(jù)為0,虛線表示輸入數(shù)據(jù)為1,當(dāng)?shù)竭_(dá)最大約束長度,每個(gè)狀態(tài)節(jié)點(diǎn)將開始重復(fù)出現(xiàn)這4種狀態(tài)。

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

一般的維特比譯碼器主要包括4個(gè)基本組成部分[4]:路徑生成單元(Branch Metric Unit,BMU),加-比-選單元(Add-compare-select,ACS),路徑存儲(chǔ)單元(Path Metric Memory,PMM),以及幸存路徑存儲(chǔ)單元(Survivor Memory Unit,SMU)。

2.1 路徑生成單元BMU設(shè)計(jì)

每當(dāng)接收到一條新支路的一組2個(gè)量度值(硬判決時(shí)為2 bit),路徑生成單元就對(duì)網(wǎng)格圖中每一條不同的支路確定一個(gè)新的量度值[5]。對(duì)R=1/2碼來說,每次將有2個(gè)不同的量度值。在軟判決維特比譯碼時(shí),支路量度值不但隨支路不同而異,而且還與接收信號(hào)的量化值有關(guān)[6]。為了簡化設(shè)計(jì),本文采用硬判決設(shè)計(jì)。在設(shè)計(jì)過程中,(2,1,9)維特比譯碼器將產(chǎn)生28即256個(gè)狀態(tài),對(duì)應(yīng)512個(gè)分支,為在滿足速度的同時(shí)又達(dá)到低功耗的目的,本文采用256種狀態(tài)4級(jí)流水64種狀態(tài)串結(jié)合的方法,如圖2所示,設(shè)計(jì)中的BMU單元由8個(gè)度量分支單元形成譯碼器的512個(gè)分支狀態(tài)。

圖2 4路ACS單元

2.2 加-比-選單元ACS設(shè)計(jì)

加-比-選單元是維特比譯碼的核心運(yùn)算單元[7],它主要將支路量度與以前所存儲(chǔ)的路徑量度相加,然后對(duì)匯聚到同一節(jié)點(diǎn)外的支路進(jìn)行路徑量度比較,選擇一條路徑量度最小的路徑保留,作為到達(dá)該狀態(tài)的幸存路徑,并且更新該狀態(tài)的度量值,并輸出最終的判決比特。

如圖2所示,本文將維特比譯碼器的256個(gè)狀態(tài)4級(jí)流水形成4個(gè)ACS單元[7-8],每個(gè)ACS單元包括加法器、比較器和路徑度量存儲(chǔ)單元。從圖中可以看出,在路徑度量mm0移位存儲(chǔ)更新后,分別與2路分支路徑bm0與bm4相加,通過比較器com0選擇出較小的幸存路徑,存入存儲(chǔ)單元mm0,循環(huán)執(zhí)行。最后,隨著每輸入一個(gè)數(shù)據(jù),從mm0,mm1,mm2, mm3的路徑度量值中選擇最小路徑譯碼輸出。

在路徑度量存儲(chǔ)設(shè)計(jì)過程中,由于采用4級(jí)流水64種狀態(tài)串并執(zhí)行的方法,路徑存儲(chǔ)單元需要不斷進(jìn)行存儲(chǔ)更新,因此根據(jù)0＜N≤7、N=8、N=9以及N≥10的不同情況對(duì)路徑的存儲(chǔ)更新單元進(jìn)行分析,由維特比譯碼原理可知,當(dāng)N≤9時(shí),存儲(chǔ)路徑度量只對(duì)支路度量值執(zhí)行加法運(yùn)算,不進(jìn)行比較[9],只有到N≥10,即256個(gè)狀態(tài)出現(xiàn)蝶形分支時(shí),才進(jìn)行路徑度量比較,因此,由圖3可知,當(dāng)0＜N≤7、N= 8、N=9以及N≥10時(shí),每輸入一個(gè)數(shù)據(jù),分別需要64,128,256和512個(gè)寄存器對(duì)存儲(chǔ)狀態(tài)的路徑度量值移位存儲(chǔ)更新;這樣的方法使得譯碼器在N≥10的情況下,對(duì)每一次輸入的數(shù)據(jù),節(jié)省大量路徑存儲(chǔ)寄存器,從而達(dá)到本設(shè)計(jì)中低功耗的目的[10]。

圖3 路徑度量存儲(chǔ)分布

由于在存儲(chǔ)路徑度量更新值與分支度量相加的過程中,路徑度量的狀態(tài)與分支的狀態(tài)并不對(duì)應(yīng),因此在輸入第i個(gè)數(shù)據(jù)時(shí),路徑度量寄存器的值均需要移位更新,并通過t條門控制線控制狀態(tài)(2t(1,2t),其中,1＜t≤32,使支路分支路徑值與路徑存儲(chǔ)更新值對(duì)應(yīng)相加。如圖4所示。

圖4 路徑度量存儲(chǔ)的更新

在第0個(gè)～第31個(gè)狀態(tài),先使mm0(i)的路徑存儲(chǔ)更新移位,然后使用前16條門控制線,控制路徑路徑更新值與路徑分支bm0～bm1,bm2～bm3,…, bm30～bm31對(duì)應(yīng)相加得到 mm0(i+1);而在第32個(gè)～第63個(gè)狀態(tài)中,路徑存儲(chǔ)mm0(i)的存儲(chǔ)值無需移位,使用后16條門控制線,控制路徑度量存儲(chǔ)值與bm32～bm33,…,bm34～bm35,bm62～bm63對(duì)應(yīng)相加得到mm1(i+1)。

2.3 幸存路徑存儲(chǔ)單元SMU的設(shè)計(jì)

在幸存路徑存儲(chǔ)單元中,可使用回溯譯碼、寄存器交換和路徑相消3種方法,回溯追蹤方法(TB)是比較好的方法,尤其應(yīng)用維特比譯碼[11]。為了達(dá)到高速功能,回溯追蹤方法的緩存器采用后進(jìn)先出(LIFO)和多任務(wù)讀取功能,這個(gè)多任務(wù)的結(jié)果是建立在復(fù)雜的控制邏輯上的。而寄存器交換方法實(shí)現(xiàn)方法簡單,但因?yàn)橐蠛艽蟮墓募懊娣e與本文的目的不符,所以不使用于本文方案中。路徑相消法,即每更新一次狀態(tài)則與下一個(gè)狀態(tài)相比較,并且將較小路徑的狀態(tài)路徑完全刪除,最后只幸存一個(gè)最小路徑狀態(tài)。本文要討論的維特比譯碼器選用路徑相消法,只要檢查到最小路徑的狀態(tài)即馬上進(jìn)行譯碼輸出,提升譯碼速率,減小譯碼延遲。

由本文設(shè)計(jì)中的結(jié)構(gòu)可以看出,由幸存路徑的狀態(tài)轉(zhuǎn)換得到最后的譯碼數(shù)據(jù)。最終比較后幸存留下的數(shù)據(jù)包括2個(gè)值,一個(gè)為幸存路徑度量值,另一個(gè)為幸存路徑度量值的狀態(tài)地址,該狀態(tài)地址即包含譯碼信息。

硬件電路的實(shí)現(xiàn)過程如圖5所示,由路徑存儲(chǔ)更新得到的4路數(shù)據(jù)mm0,mm1,mm2,mm3后,通過3個(gè)并行比較器得到串行64個(gè)狀態(tài)的相對(duì)較小路徑值,而后再對(duì)64個(gè)狀態(tài)的相對(duì)較小路徑值進(jìn)行隊(duì)列存儲(chǔ)[12],并且在接下來輸入數(shù)據(jù)的首個(gè)狀態(tài)開始進(jìn)行逐個(gè)比較,最后輸出幸存的最小路徑,記錄狀態(tài)地址,得到寄存器內(nèi)數(shù)據(jù)的最低位即譯碼的輸出數(shù)據(jù)。

圖5 幸存路徑存儲(chǔ)單元

3 性能分析與比較

本文采用Verilog硬件描述語言對(duì)各模塊進(jìn)行RTL級(jí)描述,使用由頂而下的設(shè)計(jì)方法,在modelsim仿真平臺(tái)得到實(shí)現(xiàn),采用TSMC 0.18邏輯工藝,使用DC compiler對(duì)RTL級(jí)代碼進(jìn)行邏輯綜合,生成的網(wǎng)表使用formality進(jìn)行功能驗(yàn)證通過,然后利用encounter自動(dòng)布局布線設(shè)計(jì)版圖,如圖6所示,最終得到芯片面積為0.212 mm2,功耗約為23.9 mW。設(shè)計(jì)時(shí)序通過Primetime靜態(tài)時(shí)序檢驗(yàn),設(shè)計(jì)版圖已通過Calibre工具的LVS、DRC等驗(yàn)證。

圖6 維特比譯碼器設(shè)計(jì)版圖

如表1所示,K值代表維特比譯碼器的約束長度,由于本維特比譯碼器采用串并結(jié)合的設(shè)計(jì)方法,使得數(shù)據(jù)的譯碼速度稍有降低,但本文使用改進(jìn)的ACS結(jié)構(gòu),使得譯碼器在約束長度K=9的情況下,在功耗上比已有的文獻(xiàn)有了很大的改善。

表1 維特比譯碼器結(jié)構(gòu)比較

4 結(jié)束語

本文設(shè)計(jì)了一種應(yīng)用于無線通信中的(2,1,9)低功耗維特比譯碼器,使用四級(jí)流水64個(gè)狀態(tài)串并結(jié)合的方法,采用優(yōu)化的加-比-選單元模塊,簡化了ACS單元整體設(shè)計(jì)的復(fù)雜度,有效地減少了電路的功耗和芯片的面積。幸存路徑單元采用路徑相消的方法,使得譯碼器在50 MHz的工作條件下,時(shí)間延遲僅有64個(gè)時(shí)鐘周期,降低了譯碼數(shù)據(jù)的輸出延遲。設(shè)計(jì)結(jié)果表明,實(shí)現(xiàn)的譯碼器穩(wěn)定工作后,在每輸入一個(gè)碼元就能有一個(gè)正確譯碼輸出的條件下,電路能以更少的功耗達(dá)到較快的數(shù)據(jù)吞吐率,具有良好的應(yīng)用前景。

[1] 王新梅,肖國政.糾錯(cuò)碼——原理與方法[M].西安:西安電子科技大學(xué)出版社,2001.

[2] Chen C J,Yu Chu,Hsu M,et al.Design of a Low Power Viterbi Decoder for Wireless Communication Applications [C]//Proc.of the 14th International Symposium on Consumer Electronics.Braunschweig,Germany:[s.n.], 2010:1-4.

[3] 董時(shí)華,喬廬峰,胡慶生.(2,1,7)維特比譯碼器結(jié)構(gòu)優(yōu)化設(shè)計(jì)與實(shí)現(xiàn)[J].電路與系統(tǒng)學(xué)報(bào),2010,15(2): 128-133.

[4] 劉曉瑩,王 一,王新安.一種應(yīng)用于802.11a的高速的Viterbi IP核的實(shí)現(xiàn)[J].計(jì)算機(jī)技術(shù)與發(fā)展,2006, 16(10):9-11.

[5] 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

[6] 游余新,王進(jìn)祥,來逢昌,等.高速低功耗維特比譯碼器的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)研究與發(fā)展,2003,40 (2):360-365.

[7] 黃高峰.維特比譯碼器的FPGA實(shí)現(xiàn)[D].成都:成都理工大學(xué),2010.

[8] Page K,Chau P.Improved Architectures for the Addcompare-select Operation in Long Constraint Length Viterbi Decoding[J].IEEE Journal Solid-State Circuits, 1998,33(1):151-155.

[9] 劉曉瑩,王 一,王新安.應(yīng)用于無線局域網(wǎng)的高速維特比譯碼器電路[J].計(jì)算機(jī)技術(shù)與發(fā)展,2008,18 (1):11-13.

[10] Tang Y C,Hu D C,Wei Weiyi,et al.A Memoryefficient Architecture for Low Latency Viterbi Decoders [C]//Proc.of IEEE International Symposium on VLSI Design.Hsinchu,China:[s.n.],2009:335-338.

[11] 金文學(xué),劉秉坤,陳 嵐.低功耗軟判決維特比譯碼器的設(shè)計(jì)[J].計(jì)算機(jī)工程,2007,33(5):243-245.

[12] 李 慶,鄧運(yùn)松.高速Viterbi譯碼器的VLSI設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)研究與發(fā)展,2007,44(12):2143-2148.

編輯 任吉慧

Design of Low Power Viterbi Decoder for Wireless Communication

ZHU Kun-shun1,YANG Hong-guan1,FAN Xiao-hua2,QIAO Shu-shan2
(1.Academy of Physics and Microelectronics Sciences,Hunan University,Changsha 410082,China;
2.Institute of Microelectronics of Chinese Academy of Sciences,Beijing 100020,China)

Toward the complicated structure of low power implementation of the Viterbi decoder in wireless communication,a low power(2,1,9)Viterbi decoder with the structure of series and parallel combination in four-level pipeline is proposed in the paper.To increase working rate,with the consideration of the implementation hardware complexity,a modified Add-compare-select(ACS)unit is used to satisfy its low power decoding requirment.In order to increase the efficiency of decoding and decrease the latency of decoder,a method of path mutual eliminating is employed in the design.Implemented by TSMC 0.18 μm standard CMOS technology under 1.62 V and 125℃,and analysed with placement and route,the chip’s highest speed is about 50 MHz,the area is 0.212 mm2,and the power comsumption is 23.9 mW.

Viterbi decoder;low power;Add-compare-select(ACS);path metric memory;path mutual eliminating; survivor path

1000-3428(2014)10-0114-04

A

TH166

10.3969/j.issn.1000-3428.2014.10.022

湖南省科技計(jì)劃基金資助項(xiàng)目(2012GK3151)。

朱坤順(1989-),女,碩士研究生,主研方向:數(shù)字集成電路設(shè)計(jì);楊紅官,副教授、博士;樊曉華,研究員、博士;喬樹山,副研究員。

2013-10-08

2013-12-03E-mail:zhukunshun_2014@163.com

中文引用格式:朱坤順,楊紅官,樊曉華,等.無線通信中的低功耗維特比譯碼器設(shè)計(jì)[J].計(jì)算機(jī)工程,2014, 40(10):114-117.

英文引用格式:Zhun Kunshun,Yang Hongguan,Fan Xiaohua,et al.Design of Low Power Viterbi Decoder for Wireless Communication[J].Computer Engineering,2014,40(10):114-117.