??? 摘? 要: 在軟件無線電技術中,經常采用DSP芯片實現信道解碼,但維特比譯碼算法在DSP上的運行速度限制了DSP譯碼在高速實時系統中的應用。針對TMS320C6000系列DSP的特點,提出了一種優化的譯碼程序設計方案。利用DSP的并行運算能力,極大地縮短了譯碼器" title="譯碼器">譯碼器中“加比選”單元的運算時間。優化后的程序比優化前的程序在譯碼速度上提高了約4倍。當在167MHz的TMS320C6701上運行的時候,對(2,1,7)卷積碼的譯碼速度可以達到870kbps。?
????關鍵詞: 數字信號處理器? 維特比譯碼器? 軟件無線電
?
??? 卷積碼因為其編碼器簡單、編碼增益高以及具有很強的糾正隨機錯誤的能力,在通信系統中得到了廣泛的應用。基于最大似然準則的維特比算法(VA)是在加性高斯白噪聲(AWGN)信道下性能最佳的卷積碼譯碼算法,也是常用的一種算法[1～2]。?
??? 一般來說,實現軟判決維特比譯碼可以有三種方案供選擇:專用集成電路(ASIC)芯片、可編程邏輯陣列(FPGA)芯片以及數字信號處理器(DSP)芯片。參考文獻[3]對這三種方案的優劣做了詳細的比較。使用DSP芯片實現譯碼是最為靈活的一種方案,但速度也是最慢的,因為整個譯碼過程都是由軟件來實現的。?
??? 在近年來興起的軟件無線電技術中,要求采用可編程能力強的的器件(DSP、CPU等)代替專用的數字電路。對信道編解碼而言,這樣做的優點在于只需要在程序上加以少量改動,就可以適應不同的編碼速率以及各種通信系統所要求的不同的編解碼方法。然而速度的瓶頸限制了DSP譯碼在實時系統中的應用,因此提高DSP的譯碼速度對于軟件無線電有著重要的意義。本文的目的就是通過對譯碼程序結構優化,來提高DSP芯片執行VA算法的速度。?
1 維特比譯碼器
??? 首先,需要定義兩個將在本文中用到的術語[2]:
??? 輸入幀——每次輸入譯碼器的比特;?
??? 輸出幀——對應一個輸入幀,譯碼器輸出的比特。?
??? 圖1所示是卷積碼譯碼器(VA算法)的一種典型結構。?
?
?
??? 以(2,1,7)卷積碼為例(輸入幀含2比特,輸出幀為1比特),來說明譯碼器的三個主要部分。?
1.1 支路度量計算單元(BMG)?
??? 計算當前輸入幀對應的128條支路的路徑度量值,并將其存入支路度量存儲單元(BMM)。?
1.2 加比選單元(ACS)?
??? 將支路度量值與相連的前面的路徑度量值相加得到延伸后的新路徑的度量值;比較連接在同一個狀態上的兩條新路徑的度量值;選擇其中度量值較小的那條路徑(幸存路徑),并將它的度量值存儲到新路徑度量存儲器(SM)中,幸存路徑值(對應編碼狀態的輸入比特)存儲到路徑存儲器(PM)中。?
1.3 幸存路徑計算單元?
??? 找到64條幸存路徑中度量值最小的一個(最大似然路徑),通過回溯操作(Traceback)在PM中找出該路徑對應的所有輸入比特,依次輸出即為譯碼結果。?
??? 每輸出一幀,都對應著一次支路單元計算和64次ACS操作。ACS操作在總的運算時間里占了很大的比例。程序優化" title="程序優化">程序優化的主要工作就是設法減少每個ACS操作所需要的時鐘周期" title="時鐘周期">時鐘周期數。?
2 TMS320C6000 DSP芯片的特點?
??? TMS320C6000系列DSP是基于TMS320C6000平臺的32位浮點DSP處理器[4]。它包含兩個子系列:用于定點計算的TMS320C62x系列和用于浮點計算的TMS320C67x系列。TMS320C6000系列CPU結構如圖2所示。時鐘頻率最高可達到250MHz。該系列DSP包含兩個通用的寄存器組" title="寄存器組">寄存器組A和B,每組有16個32位的寄存器。芯片內含8個運算功能單元:兩個乘法器(.M1和.M2);六個算術邏輯單元(.L1 .L2 .S1 .S2 .D1 .D2)。所有單元都能獨立并行操作。以TM320C6701為例,它的工作頻率最高為167MHz,最快速度可達8×167=1336MIPS。
?
?
??? 實際上,要實現這個速度存在很多瓶頸,主要有下面幾種限制:?
??? (1)功能模塊的限制? 8個功能模塊能夠執行的指令不盡相同。在實際程序中,由于程序流程的限制,指令的位置不能隨便調換,因此不可能在每一個時鐘周期都讓8個模塊同時工作。程序優化的主要手段就是要提高指令的并行程度,即平均每一周期內同時執行的指令數。?
??? (2)交叉路徑(Cross Path)的限制? 每一個功能模塊都只能對其所屬的寄存器組中的寄存器進行直接操作。例如.L1只能將結果直接寫入寄存器組A。如果要對另一個寄存器組執行讀或寫操作,需要用到“交叉路徑”,而整個CPU中只有兩條交叉路徑。也就是說,一個周期內至多能同時容納兩個相反方向的交叉讀寫。?
??? (3)多周期指令的限制? LD命令的功能是將數據從存儲器讀到寄存器中,由.D模塊執行。但執行LD命令后必須等待4個周期才能得到需要的數據。類似這樣的需要多個周期才能完成的命令(例如跳轉指令B)都成為提高指令并行處理程度的障礙。?
??? (4)對長數據操作的限制? C6000指令集只能以8比特、16比特、32比特或者40比特為單位對數據進行操作。?
3 VA在DSP上的優化實現?
??? ACS操作是整個VA算法中運算量最大的部分。在通常的程序設計中,使用一種對稱的蝶形運算實現ACS操作,每次可以完成兩個ACS操作[5]。因此優化的核心任務就是減少每個蝶形運算所消耗的運算周期數。?
??? 蝶形運算的原理請參見圖3。對前一級的兩個相鄰狀態2i和2i+1,一共有四條支路。計算出四條支路與接收信號的歐氏距離,與兩個前一級狀態2i和2i+1中存儲的以前路徑的度量值相加得到四條路徑A1、A2、B1、B2的度量值。然后在對應的兩個當前狀態i和i+32下兩兩比較,每個當前狀態都留下度量值較小的一條路徑(幸存路徑),同時將當前狀態的度量值以及與幸存路徑對應的輸入比特存入相應的位置,準備下一級計算。?
?
?
??? 每個蝶形運算包括:三次加載" title="加載">加載數據操作(load),因為可以證明一個蝶形中的四條支路的度量具有相同的絕對值,所以每次只需要加載一個由BMU預先計算的結果;四次加法操作;兩次比較操作;比較之后的四次存儲操作。其中,四次加法操作可以在一個周期內同時完成;狀態i和i+32的幸存路徑則是獨立計算和存儲的。
??? 針對前面提到的提高并行處理程度的幾個障礙,可以用以下的方法分別加以解決:?
??? (1)解決功能模塊的限制? 可以用不同的命令相互替代。例如賦值操作MV只能用.L、.S和.D功能模塊完成,如果這些模塊都被其它的并行指令占用,可以用乘1的方法實現賦值,而乘法指令MPY是用.M單元實現的。類似地,也可以用加零或減零的指令代替MV指令。?
??? (2)解決交叉路徑的限制?? 需要依靠寄存器的分配和倒換,讓同一指令涉及到的寄存器盡量處在同一個寄存器組中,減少需要用到交叉路徑的機會。?
??? (3)解決多周期指令的限制? 加載數據的結果需要在4個周期以后才能得到。為了有效地利用等待的這段時間,在程序設計中把加載數據的指令放在前面的蝶形運算中執行,當進入本次蝶形運算時,就能立即使用加載的新數據。同樣,本次蝶形運算也要執行為下一個蝶形運算加載數據的指令。B指令(跳轉指令)的問題可以用類似的方法來處理。?
??? (4)解決對長數據操作的限制?? 在(2,1,7)卷積碼的VA譯碼器中,幸存路徑存儲在PM里。每一個輸入幀對應64個可能的狀態,會產生64比特的幸存路徑比較結果。但TMS320C6701不能直接對64比特長的數據進行讀寫操作,所以把PM分成兩個相同的32位數組PM0和PM1。前者用來存儲狀態0-31對應的幸存路徑;后者存儲狀態32-64對應的幸存路徑。PM0[i]和PM1[i]合在一起表示第i級網格的所有64條幸存路徑。當編碼約束長度更大時,也可以用同樣的辦法來分開存儲。例如(2,1,9)卷積碼的PM就可以分成8個32位的數組來存儲256個狀態的信息。回溯操作的時候,先確定路徑經過哪一個狀態,就可以從相應的某一個數組中讀出路徑值,只需要一次LD(加載)操作。?
??? 圖4給出了優化后的蝶形運算流程圖。每次循環需要4個時鐘周期,分別為圖中的E0-E3,對應著一次蝶形運算。除了一些關鍵的加比選運算之外,還需要一些輔助運算來實現循環以及寄存器的相互拷貝,平均下來每個時鐘周期可并行執行6條指令。?
?
?
4 優化的效果和推廣?
??? 譯碼器輸出一幀所需要的時鐘周期數為:?
??? TBMC+n·TButter+Ttb?
其中,TBMC、TButter和Ttb分別表示支路度量計算、蝶形運算以及回溯操作所需要的周期數,n表示每一輸出幀對應的蝶形運算的次數。?
??? 對于(2,1,7)卷積碼譯碼器,輸出一個幀需要32次蝶形運算,因此n=32。在回溯幸存路徑的時候,有兩種方案輸出譯碼結果:一種是輸入一幀碼序列,就輸出一幀譯碼結果;另一種是輸入N幀碼序列,然后輸出N幀譯碼結果。后一種方法輸出每一幀所需要的周期數可以減小為Ttb/N,但同時延時也增大為(N-1)TButter/TCPS,其中TCPS是DSP每秒運行的時鐘周期數,等于DSP的工作頻率。?
??? 如果使用TI公司定義的線性匯編語言[6]用圖1所示的結構來實現(2,1,7)譯碼,經過CCS2軟件編譯并自動進行-o1級優化以后,每譯出一個比特,大約需要1000個時鐘周期(TButter=22,n=32),時鐘為167MHz時譯碼速度不超過160kbps。?
??? 在經過本文所述方法優化以后的程序中,仍然是(2,1,7)卷積碼,TBMC=20,TButter=4,n=32;Ttb=700,選擇N=16,因此譯出一個比特的平均時間是128+20+(700/16)=192個時鐘周期。以TMS320C6701為例,它工作在167MHz,該程序的譯碼速率能達到大約870kbps,而延時僅為18μs。顯然,本文中的優化程序性能遠遠高于自動優化的效果。
??? 對于不同編碼約束長度的卷積碼,例如WCDMA中用到的(2,1,9)碼,蝶形運算單元的流程與(2,1,7)碼是完全相同的。不同的地方在于每一級的狀態數增加到了256個。因此只需要對程序中的存儲和回溯路徑的指令做一些改動就可以使用。?
??? 對于不同的DSP系統,因為在指令集、總線、寄存器等諸多方面存在差異,針對C6000系列的優化的匯編程序不能直接應用。但譯碼程序優化中遇到的問題也是大致相同的,優化的重點任務都是設法減少ACS的運算量,因此本文提出的程序流程的基本思想以及一些解決問題的技巧都可以繼續加以運用。?
參考文獻?
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