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

1、基于TMS320C6000系列DSP的維特比譯碼程序優(yōu)化設計基于TMS320C6000系列DSP的維特比譯碼程序優(yōu)化設計 基于TMS320C6000系列DSP的維特比譯碼程序優(yōu)化設計 關鍵字：數字信號處理器維特比譯碼器軟件無線電 卷積碼因為其編碼器簡單、編碼增益高以及具有很強的糾正 隨機錯誤的能力，在通信系統(tǒng)中得到了廣泛的應用?；谧畲笏迫?準則的維特比算法(VA)是在加性高斯白噪聲(AWGN)信道下性能最 佳的卷積碼譯碼算法，也是常用的一種算法12。一般來說，實現軟判決維特比譯碼可以有三種方案供選擇：專 用集成電路(ASIC)芯片、可編程邏輯陣列(FPGA)芯片以及數字信 號處理器(DSP)

2、芯片。參考文獻3對這三種方案的優(yōu)劣做了詳細 的比較。使用DSP芯片實現譯碼是最為靈活的一種方案，但速度也 是最慢的，因為整個譯碼過程都是由軟件來實現的。在近年來興起的軟件無線電技術中，要求采用可編程能力強的 的器件(DSP、CPU等)代替專用的數字電路。對信道編解碼而言，這 樣做的優(yōu)點在于只需要在程序上加以少量改動，就可以適應不同的 編碼速率以及各種通信系統(tǒng)所要求的不同的編解碼方法。然而速 度的瓶頸限制了 DSP譯碼在實時系統(tǒng)中的應用，因此提高DSP的譯第1頁共1頁 碼速度對于軟件無線電有著重要的意義。本文的目的就是通過對 譯碼程序結構優(yōu)化，來提高DSP芯片執(zhí)行VA算法的速度。1維特比譯碼器首

3、先，需要定義兩個將在本文中用到的術語2：輸入幀一一每次輸入譯碼器的比特；輸出幀一一對應一個輸入幀，譯碼器輸出的比特。圖1所示是卷積碼譯碼器(VA算法)的一種典型結構。 ； ；以(2,1,7)卷積碼為例(輸入幀含2比特，輸出幀為1比特)，來 說明譯碼器的三個主要部分。1. 1支路度量計算單元(BMG)計算當前輸入幀對應的128條支路的路徑度量值，并將其存入 支路度量存儲單元(BMM) o1.2加比選單元(ACS)將支路度量值與相連的前面的路徑度量值相加得到延伸后的 新路徑的度量值；比較連接在同一個狀態(tài)上的兩條新路徑的度量值; 選擇其中度量值較小的那條路徑(幸存路徑)，并將它的度量

4、值存儲 到新路徑度量存儲器(SM)中，幸存路徑值(對應編碼狀態(tài)的輸入比 特)存儲到路徑存儲器(PM)中。1.3幸存路徑計算單元第1頁共1頁找到64條幸存路徑中度量值最小的一個(最大似然路徑)，通 過回溯操作(Traceback)在PM中找出該路徑對應的所有輸入比特， 依次輸出即為譯碼結果。每輸出一幀，都對應著一次支路單元計算和64次ACS操作。 ACS操作在總的運算時間里占了很大的比例。程序優(yōu)化的主要工作 就是設法減少每個ACS操作所需要的時鐘周期數。2 TMS320C6000 DSP芯片的特點TMS320C6000系列DSP是基于TMS320C6000平臺的32位浮點 DSP處理器4。它包含

5、兩個子系列：用于定點計算的TMS320C62X 系列和用于浮點計算的TMS320C67X系列。TMS320C6000系列CPU 結構如圖2所示。時鐘頻率最高可達到250MHzo該系列DSP包含 兩個通用的寄存器組A和B，每組有16個32位的寄存器。芯片內 含8個運算功能單元：兩個乘法器(.Ml和.M2)；六個算術邏輯單元 (.L1.L2.S1.S2.D1.D2)。所有單元都能獨立并行操作。以 TM320C6701為例，它的工作頻率最高為167MHz,最快速度可達 8X167=1336MIPSO ； ；實際上，要實現這個速度存在很多瓶頸，主要有下面幾種限制：(1) 功能模塊的限制

6、8個功能模塊能夠執(zhí)行的指令不盡相同。 在實際程序中，由于程序流程的限制，指令的位置不能隨便調換，因 此不可能在每一個時鐘周期都讓8個模塊同時工作。程序優(yōu)化的第1頁共1頁 主要手段就是要提高指令的并行程度，即平均每一周期內同時執(zhí)行 的指令數。(2) 交叉路徑(Cross Path)的限制每一個功能模塊都只能對其 所屬的寄存器組中的寄存器進行直接操作。例如.L1只能將結果直 接寫入寄存器組A。如果要對另一個寄存器組執(zhí)行讀或寫操作，需 要用到“交叉路徑”，而整個CPU中只有兩條交叉路徑。也就是說, 一個周期內至多能同時容納兩個相反方向的交叉讀寫。(3) 多周期指令的限制LD命令的功能是將數據從存儲器

7、讀到 寄存器中，由.D模塊執(zhí)行。但執(zhí)行LD命令后必須等待4個周期才 能得到需要的數據。類似這樣的需要多個周期才能完成的命令(例 如跳轉指令B)都成為提高指令并行處理程度的障礙。(4) 對長數據操作的限制C6000指令集只能以8比特、16比 特、32比特或者40比特為單位對數據進行操作。3 VA在DSP上的優(yōu)化實現ACS操作是整個VA算法中運算量最大的部分。在通常的程序 設計中，使用一種對稱的蝶形運算實現ACS操作，每次可以完成兩 個ACS操作5。因此優(yōu)化的核心任務就是減少每個蝶形運算所消 耗的運算周期數。蝶形運算的原理請參見圖3。對前一級的兩個相鄰狀態(tài)2i和 2i+l,共有四條支路。計算出四條

8、支路與接收信號的歐氏距離， 與兩個前一級狀態(tài)2i和2i+l中存儲的以前路徑的度量值相加得 到四條路徑Al、A2、Bl. B2的度量值。然后在對應的兩個當前狀第1頁共1頁 態(tài)i和i+32下兩兩比較，每個當前狀態(tài)都留下度量值較小的一條 路徑(幸存路徑)，同時將當前狀態(tài)的度量值以及與幸存路徑對應的 輸入比特存入相應的位置，準備下一級計算。 ；每個蝶形運算包括：三次加載數據操作(load)，因為可以證明 一個蝶形中的四條支路的度量具有相同的絕對值，所以每次只需要 加載一個由BMU預先計算的結果；四次加法操作；兩次比較操作；比 較之后的四次存儲操作。其中，四次加法操作可以在一個周期內同 時完成；

9、狀態(tài)i和i+32的幸存路徑則是獨立計算和存儲的。針對 前面提到的提高并行處理程度的幾個障礙，可以用以下的方法分別 加以解決：(1) 解決功能模塊的限制可以用不同的命令相互替代。例如賦 值操作MV只能用.L、. S和.D功能模塊完成，如果這些模塊都被其 它的并行指令占用，可以用乘1的方法實現賦值，而乘法指令MPY 是用.M單元實現的。類似地，也可以用加零或減零的指令代替MV 指令。(2) 解決交叉路徑的限制需要依靠寄存器的分配和倒換，讓同 一指令涉及到的寄存器盡量處在同一個寄存器組中，減少需要用到 交叉路徑的機會。(3) 解決多周期指令的限制加載數據的結果需要在4個周期以 后才能得到。為了有效地

10、利用等待的這段時間，在程序設計中把加 載數據的指令放在前面的蝶形運算中執(zhí)行，當進入本次蝶形運算時,第1頁共1頁 就能立即使用加載的新數據。同樣，本次蝶形運算也要執(zhí)行為下一 個蝶形運算加載數據的指令。B指令(跳轉指令)的問題可以用類似 的方法來處理。(4) 解決對長數據操作的限制在(2,1,7)卷積碼的VA譯碼器中, 幸存路徑存儲在PM里。每一個輸入幀對應64個可能的狀態(tài)，會產 生64比特的幸存路徑比較結果。但TMS320C6701不能直接對64 比特長的數據進行讀寫操作，所以把PM分成兩個相同的32位數組 PMO和PM1。前者用來存儲狀態(tài)0-31對應的幸存路徑；后者存儲狀 態(tài)32-64對應的幸

11、存路徑。PMOi和PMli合在一起表示第i級 網格的所有64條幸存路徑。當編碼約束長度更大時，也可以用同 樣的辦法來分開存儲。例如(2,1,9)卷積碼的PM就可以分成8個 32位的數組來存儲256個狀態(tài)的信息?；厮莶僮鞯臅r候，先確定路 徑經過哪一個狀態(tài)，就可以從相應的某一個數組中讀出路徑值，只 需要一次LD(加載)操作。圖4給出了優(yōu)化后的蝶形運算流程圖。每次循環(huán)需要4個時 鐘周期，分別為圖中的E0-E3,對應著一次蝶形運算。除了一些關鍵 的加比選運算之外，還需要一些輔助運算來實現循環(huán)以及寄存器的 相互拷貝，平均下來每個時鐘周期可并行執(zhí)行6條指令。 ； ；4優(yōu)化的效果和推廣譯碼器

12、輸出一幀所需要的時鐘周期數為：第1頁共1頁TBMC+n TButter+Ttb其中，TBMC、TButter和Ttb分別表示支路度量計算、蝶形運 算以及回溯操作所需要的周期數,n表示每一輸出幀對應的蝶形運 算的次數。對于(2,1,7)卷積碼譯碼器，輸出一個幀需要32次蝶形運算， 因此n=32o在回溯幸存路徑的時候，有兩種方案輸出譯碼結果：一 種是輸入一幀碼序列，就輸出一幀譯碼結果；另一種是輸入N幀碼 序列，然后輸出N幀譯碼結果。后一種方法輸出每一幀所需要的周 期數可以減小為Ttb/N,但同時延時也增大為(N-l)TButter/TCPS, 其中TCPS是DSP每秒運行的時鐘周期數，等于DSP的

13、工作頻率。如果使用TI公司定義的線性匯編語言6用圖1所示的結構 來實現(2,1,7)譯碼，經過CCS2軟件編譯并自動進行-。1級優(yōu)化以 后，每譯出一個比特，大約需要1000個時鐘周期 (TButter二22, n二32),時鐘為167MHz時譯碼速度不超過160kbps。在經過本文所述方法優(yōu)化以后的程序中，仍然是(2,1,7)卷積 碼,TBMC=20,TButter=4,n=32；Ttb=700，選擇 N二 16,因此譯出一個比 特的平均時間是128+20+(700/16)=192個時鐘周期。以 TMS320C6701為例，它工作在167MIIz,該程序的譯碼速率能達到大 約870kbps,而

14、延時僅為18 us。顯然，本文中的優(yōu)化程序性能遠遠 高于自動優(yōu)化的效果。對于不同編碼約束長度的卷積碼，例如WCDMA中用到的(2,1,9) 碼，蝶形運算單元的流程與(2,1,7)碼是完全相同的。不同的地方第1頁共1頁 在于每一級的狀態(tài)數增加到了 256個。因此只需要對程序中的存 儲和回溯路徑的指令做一些改動就可以使用。對于不同的DSP系統(tǒng)，因為在指令集、總線、寄存器等諸多方 面存在差異，針對C6000系列的優(yōu)化的匯編程序不能直接應用。但 譯碼程序優(yōu)化中遇到的問題也是大致相同的,優(yōu)化的重點任務都是 設法減少ACS的運算量，因此本文提出的程序流程的基本思想以及 一些解決問題的技巧都可以繼續(xù)加以運用

15、。參考文獻1 G. David Forney, Jr. The Viterbi algorithm.Proc. IEEE, Mar. 1973；612 Peter Sweeney. Error Control Coding-From Theory to Practice. John Wiley &； Sons LTD, Chapter 2, 20023 G. C. Ahlquist, M Rice, and B Nelson. ErrorControl Coding in Software Radios： An FPGA Approach. IEEE Personal munications, Mag，Aug. 1999：35394 TMS320C62x/C67x CPU and Instruction Set Reference Guide Texas Instruments Corporation, 19985 Ahmad Khan, S,Saqib, M , Ahmed, S. Parallel Vit