基于TMS320C6000系列DSP的維特比譯碼程序優(yōu)化設計

摘要: 在軟件無(wú)線(xiàn)電技術(shù)中,經(jīng)常采用DSP芯片實(shí)現信道解碼,但維特比譯碼算法在DSP上的運行速度限制了DSP譯碼在高速實(shí)時(shí)系統中的應用。針對TMS320C6000系列DSP的特點(diǎn),提出了一種優(yōu)化的譯碼程序設計方案。利用DSP的并行運算能力,極大地縮短了譯碼器中“加比選”單元的運算時(shí)間。優(yōu)化后的程序比優(yōu)化前的程序在譯碼速度上提高了約4倍。當在167MHz的TMS320C6701上運行的時(shí)候,對(2,1,7)卷積碼的譯碼速度可以達到870kbps。

關(guān)鍵詞: 數字信號處理器  維特比譯碼器  軟件無(wú)線(xiàn)電

　　卷積碼因為其編碼器簡(jiǎn)單、編碼增益高以及具有很強的糾正隨機錯誤的能力,在通信系統中得到了廣泛的應用?；谧畲笏迫粶蕜t的維特比算法(VA)是在加性高斯白噪聲(AWGN)信道下性能最佳的卷積碼譯碼算法,也是常用的一種算法[1～2]。

　　一般來(lái)說(shuō),實(shí)現軟判決維特比譯碼可以有三種方案供選擇:專(zhuān)用集成電路(ASIC)芯片、可編程邏輯陣列(FPGA)芯片以及數字信號處理器(DSP)芯片。參考文獻[3]對這三種方案的優(yōu)劣做了詳細的比較。使用DSP芯片實(shí)現譯碼是最為靈活的一種方案,但速度也是最慢的,因為整個(gè)譯碼過(guò)程都是由軟件來(lái)實(shí)現的。

　　在近年來(lái)興起的軟件無(wú)線(xiàn)電技術(shù)中,要求采用可編程能力強的的器件(DSP、CPU等)代替專(zhuān)用的數字電路。對信道編解碼而言,這樣做的優(yōu)點(diǎn)在于只需要在程序上加以少量改動(dòng),就可以適應不同的編碼速率以及各種通信系統所要求的不同的編解碼方法。然而速度的瓶頸限制了DSP譯碼在實(shí)時(shí)系統中的應用,因此提高DSP的譯碼速度對于軟件無(wú)線(xiàn)電有著(zhù)重要的意義。本文的目的就是通過(guò)對譯碼程序結構優(yōu)化,來(lái)提高DSP芯片執行VA算法的速度。

　　1 維特比譯碼器

　　首先,需要定義兩個(gè)將在本文中用到的術(shù)語(yǔ)[2]:

　　輸入幀——每次輸入譯碼器的比特;

　　輸出幀——對應一個(gè)輸入幀,譯碼器輸出的比特。

　　圖1所示是卷積碼譯碼器(VA算法)的一種典型結構。

　　以(2,1,7)卷積碼為例(輸入幀含2比特,輸出幀為1比特),來(lái)說(shuō)明譯碼器的三個(gè)主要部分。

　　1.1 支路度量計算單元(BMG)

　　計算當前輸入幀對應的128條支路的路徑度量值,并將其存入支路度量存儲單元(BMM)。

　　1.2 加比選單元(ACS)

　　將支路度量值與相連的前面的路徑度量值相加得到延伸后的新路徑的度量值;比較連接在同一個(gè)狀態(tài)上的兩條新路徑的度量值;選擇其中度量值較小的那條路徑(幸存路徑),并將它的度量值存儲到新路徑度量存儲器(SM)中,幸存路徑值(對應編碼狀態(tài)的輸入比特)存儲到路徑存儲器(PM)中。

　　1.3 幸存路徑計算單元

　　找到64條幸存路徑中度量值最小的一個(gè)(最大似然路徑),通過(guò)回溯操作(Traceback)在PM中找出該路徑對應的所有輸入比特,依次輸出即為譯碼結果。

　　每輸出一幀,都對應著(zhù)一次支路單元計算和64次ACS操作。ACS操作在總的運算時(shí)間里占了很大的比例。程序優(yōu)化的主要工作就是設法減少每個(gè)ACS操作所需要的時(shí)鐘周期數。

　　2 TMS320C6000 DSP芯片的特點(diǎn)

　　TMS320C6000系列DSP是基于TMS320C6000平臺的32位浮點(diǎn)DSP處理器[4]。它包含兩個(gè)子系列:用于定點(diǎn)計算的TMS320C62x系列和用于浮點(diǎn)計算的TMS320C67x系列。TMS320C6000系列CPU結構如圖2所示。時(shí)鐘頻率最高可達到250MHz。該系列DSP包含兩個(gè)通用的寄存器組A和B,每組有16個(gè)32位的寄存器。芯片內含8個(gè)運算功能單元:兩個(gè)乘法器(.M1和.M2);六個(gè)算術(shù)邏輯單元(.L1 .L2 .S1 .S2 .D1 .D2)。所有單元都能獨立并行操作。以TM320C6701為例,它的工作頻率最高為167MHz,最快速度可達8×167=1336MIPS。

　　實(shí)際上,要實(shí)現這個(gè)速度存在很多瓶頸,主要有下面幾種限制:

　　(1)功能模塊的限制  8個(gè)功能模塊能夠執行的指令不盡相同。在實(shí)際程序中,由于程序流程的限制,指令的位置不能隨便調換,因此不可能在每一個(gè)時(shí)鐘周期都讓8個(gè)模塊同時(shí)工作。程序優(yōu)化的主要手段就是要提高指令的并行程度,即平均每一周期內同時(shí)執行的指令數。

　　(2)交叉路徑(Cross Path)的限制  每一個(gè)功能模塊都只能對其所屬的寄存器組中的寄存器進(jìn)行直接操作。例如.L1只能將結果直接寫(xiě)入寄存器組A。如果要對另一個(gè)寄存器組執行讀或寫(xiě)操作,需要用到“交叉路徑”,而整個(gè)CPU中只有兩條交叉路徑。也就是說(shuō),一個(gè)周期內至多能同時(shí)容納兩個(gè)相反方向的交叉讀寫(xiě)。

　　(3)多周期指令的限制  LD命令的功能是將數據從存儲器讀到寄存器中,由.D模塊執行。但執行LD命令后必須等待4個(gè)周期才能得到需要的數據。類(lèi)似這樣的需要多個(gè)周期才能完成的命令(例如跳轉指令B)都成為提高指令并行處理程度的障礙。

　　(4)對長(cháng)數據操作的限制  C6000指令集只能以8比特、16比特、32比特或者40比特為單位對數據進(jìn)行操作。

　　3 VA在DSP上的優(yōu)化實(shí)現

　　ACS操作是整個(gè)VA算法中運算量最大的部分。在通常的程序設計中,使用一種對稱(chēng)的蝶形運算實(shí)現ACS操作,每次可以完成兩個(gè)ACS操作[5]。因此優(yōu)化的核心任務(wù)就是減少每個(gè)蝶形運算所消耗的運算周期數。

　　蝶形運算的原理請參見(jiàn)圖3。對前一級的兩個(gè)相鄰狀態(tài)2i和2i+1,一共有四條支路。計算出四條支路與接收信號的歐氏距離,與兩個(gè)前一級狀態(tài)2i和2i+1中存儲的以前路徑的度量值相加得到四條路徑A1、A2、B1、B2的度量值。然后在對應的兩個(gè)當前狀態(tài)i和i+32下兩兩比較,每個(gè)當前狀態(tài)都留下度量值較小的一條路徑(幸存路徑),同時(shí)將當前狀態(tài)的度量值以及與幸存路徑對應的輸入比特存入相應的位置,準備下一級計算。

　　每個(gè)蝶形運算包括:三次加載數據操作(load),因為可以證明一個(gè)蝶形中的四條支路的度量具有相同的絕對值,所以每次只需要加載一個(gè)由BMU預先計算的結果;四次加法操作;兩次比較操作;比較之后的四次存儲操作。其中,四次加法操作可以在一個(gè)周期內同時(shí)完成;狀態(tài)i和i+32的幸存路徑則是獨立計算和存儲的。

　　針對前面提到的提高并行處理程度的幾個(gè)障礙,可以用以下的方法分別加以解決:

　　(1)解決功能模塊的限制  可以用不同的命令相互替代。例如賦值操作MV只能用.L、.S和.D功能模塊完成,如果這些模塊都被其它的并行指令占用,可以用乘1的方法實(shí)現賦值,而乘法指令MPY是用.M單元實(shí)現的。類(lèi)似地,也可以用加零或減零的指令代替MV指令。

　　(2)解決交叉路徑的限制   需要依靠寄存器的分配和倒換,讓同一指令涉及到的寄存器盡量處在同一個(gè)寄存器組中,減少需要用到交叉路徑的機會(huì )。

　　(3)解決多周期指令的限制  加載數據的結果需要在4個(gè)周期以后才能得到。為了有效地利用等待的這段時(shí)間,在程序設計中把加載數據的指令放在前面的蝶形運算中執行,當進(jìn)入本次蝶形運算時(shí),就能立即使用加載的新數據。同樣,本次蝶形運算也要執行為下一個(gè)蝶形運算加載數據的指令。B指令(跳轉指令)的問(wèn)題可以用類(lèi)似的方法來(lái)處理。

　　(4)解決對長(cháng)數據操作的限制   在(2,1,7)卷積碼的VA譯碼器中,幸存路徑存儲在PM里。每一個(gè)輸入幀對應64個(gè)可能的狀態(tài),會(huì )產(chǎn)生64比特的幸存路徑比較結果。但TMS320C6701不能直接對64比特長(cháng)的數據進(jìn)行讀寫(xiě)操作,所以把PM分成兩個(gè)相同的32位數組PM0和PM1。前者用來(lái)存儲狀態(tài)0-31對應的幸存路徑;后者存儲狀態(tài)32-64對應的幸存路徑。PM0[i]和PM1[i]合在一起表示第i級網(wǎng)格的所有64條幸存路徑。當編碼約束長(cháng)度更大時(shí),也可以用同樣的辦法來(lái)分開(kāi)存儲。例如(2,1,9)卷積碼的PM就可以分成8個(gè)32位的數組來(lái)存儲256個(gè)狀態(tài)的信息?；厮莶僮鞯臅r(shí)候,先確定路徑經(jīng)過(guò)哪一個(gè)狀態(tài),就可以從相應的某一個(gè)數組中讀出路徑值,只需要一次LD(加載)操作。

　　圖4給出了優(yōu)化后的蝶形運算流程圖。每次循環(huán)需要4個(gè)時(shí)鐘周期,分別為圖中的E0-E3,對應著(zhù)一次蝶形運算。除了一些關(guān)鍵的加比選運算之外,還需要一些輔助運算來(lái)實(shí)現循環(huán)以及寄存器的相互拷貝,平均下來(lái)每個(gè)時(shí)鐘周期可并行執行6條指令。

　　4 優(yōu)化的效果和推廣

　　譯碼器輸出一幀所需要的時(shí)鐘周期數為:

　　TBMC+n·TButter+Ttb

　　其中,TBMC、TButter和Ttb分別表示支路度量計算、蝶形運算以及回溯操作所需要的周期數,n表示每一輸出幀對應的蝶形運算的次數。

　　對于(2,1,7)卷積碼譯碼器,輸出一個(gè)幀需要32次蝶形運算,因此n=32。在回溯幸存路徑的時(shí)候,有兩種方案輸出譯碼結果:一種是輸入一幀碼序列,就輸出一幀譯碼結果;另一種是輸入N幀碼序列,然后輸出N幀譯碼結果。后一種方法輸出每一幀所需要的周期數可以減小為T(mén)tb/N,但同時(shí)延時(shí)也增大為(N-1)TButter/TCPS,其中TCPS是DSP每秒運行的時(shí)鐘周期數,等于DSP的工作頻率。

　　如果使用TI公司定義的線(xiàn)性匯編語(yǔ)言[6]用圖1所示的結構來(lái)實(shí)現(2,1,7)譯碼,經(jīng)過(guò)CCS2軟件編譯并自動(dòng)進(jìn)行-o1級優(yōu)化以后,每譯出一個(gè)比特,大約需要1000個(gè)時(shí)鐘周期(TButter=22,n=32),時(shí)鐘為167MHz時(shí)譯碼速度不超過(guò)160kbps。

　　在經(jīng)過(guò)本文所述方法優(yōu)化以后的程序中,仍然是(2,1,7)卷積碼,TBMC=20,TButter=4,n=32;Ttb=700,選擇N=16,因此譯出一個(gè)比特的平均時(shí)間是128+20+(700/16)=192個(gè)時(shí)鐘周期。以TMS320C6701為例,它工作在167MHz,該程序的譯碼速率能達到大約870kbps,而延時(shí)僅為18μs。顯然,本文中的優(yōu)化程序性能遠遠高于自動(dòng)優(yōu)化的效果。

　　對于不同編碼約束長(cháng)度的卷積碼,例如WCDMA中用到的(2,1,9)碼,蝶形運算單元的流程與(2,1,7)碼是完全相同的。不同的地方在于每一級的狀態(tài)數增加到了256個(gè)。因此只需要對程序中的存儲和回溯路徑的指令做一些改動(dòng)就可以使用。

　　對于不同的DSP系統,因為在指令集、總線(xiàn)、寄存器等諸多方面存在差異,針對C6000系列的優(yōu)化的匯編程序不能直接應用。但譯碼程序優(yōu)化中遇到的問(wèn)題也是大致相同的,優(yōu)化的重點(diǎn)任務(wù)都是設法減少ACS的運算量,因此本文提出的程序流程的基本思想以及一些解決問(wèn)題的技巧都可以繼續加以運用。

　　參考文獻

　　1 G. David Forney, Jr. The Viterbi algorithm. Proc.IEEE, Mar.1973;61

　　2 Peter Sweeney. Error Control Coding-From Theory to Practice. John Wiley & Sons LTD, Chapter 2, 2002

　　3 G.C. Ahlquist, M. Rice, and B. Nelson. Error Control  Coding in Software Radios: An FPGA Approach. IEEE Personal Communications, Mag., Aug. 1999:35～39

　　4 TMS320C62x/C67x CPU and Instruction Set Reference Guide. Texas Instruments Corporation, 1998

　　5 Ahmad Khan, S., Saqib, M.M., Ahmed, S. Parallel  Viterbi Algorithm for a VLIW DSP. Acoustics, Speech,and Signal Processing, 2000. ICASSP’00 Proceedings 2000. IEEE International Conference on, 2000;6

　　6 TMS320C6000 Optimizing C Complier User’s Guide.Texas Instruments Corporation, 1999