基于DSP的信道譯碼算法優(yōu)化

1、    基于DSP的信道譯碼算法優(yōu)化    基于DSP的信道譯碼算法優(yōu)化    類別：單片機(jī)/DSP          來源：單片機(jī)及嵌入式系統(tǒng)應(yīng)用 作者：閏 冬 王建國摘要：在DSP上移植算法，代碼優(yōu)化程度成為提高系統(tǒng)性能、縮短開發(fā)周期的瓶頸。同時針對復(fù)雜算法在DSP上的實現(xiàn)，也產(chǎn)生很多優(yōu)化策略、方法。本文以在數(shù)字通信系統(tǒng)中應(yīng)用廣泛的Viterbi算法為例，簡述Viterbi

2、算法的基本原理和目標(biāo)處理器（TMS320C6211）的處理能力；介紹C6000軟件編程及優(yōu)化的步驟，并提出一些具體的優(yōu)化策略和技巧。 關(guān)鍵詞：Viterbi算法 TMS320C6000 優(yōu)化雖然Texas Instrument推出的C6000系列DSP使對信號處理的能力顯著提高，但對信息處理能力要求的不斷提升使提對DSP程序的優(yōu)化越來越成為DSP開發(fā)工作中非常重要的環(huán)節(jié)。本文討論2Mbps視頻數(shù)據(jù)流的Viterbi算法的移植與優(yōu)化策略、技巧。 1 Viterbi算法原理簡介Viterbi譯碼算法是由Viterbi于1967年提出的一種最大似然譯碼方法，譯碼器根據(jù)接收序列R按最大似然準(zhǔn)則力圖找出

3、正確的原始碼序列。隨著大規(guī)模集成電路技術(shù)的發(fā)展，采用Viterbi算法的卷積編碼技術(shù)已成為廣泛應(yīng)用的糾錯方案。Viterbi譯碼過程可用狀態(tài)圖表示，圖1表示2個狀態(tài)的狀態(tài)轉(zhuǎn)移圖。Sj,t和Sj+N/2,t表示t時刻的兩個狀態(tài)。在t+1時刻，這兩個狀態(tài)值根據(jù)路徑為0或者1，轉(zhuǎn)移到狀態(tài)S2j,t+1和S2j+1,t+1。每一種可能的狀態(tài)轉(zhuǎn)移都根據(jù)接收到的有噪聲的序列R計算路徑度量，然后選擇出各個狀態(tài)的最小度量路徑（幸存路徑）。Viterbi算法就是通過在狀態(tài)圖中尋找最小量路徑向前回溯L步，最后得到的即為譯碼輸出。 在卷積碼（n,k,m）表示法中，參數(shù)k表示每次輸入信息碼位數(shù)，n表示編碼的輸出卷積碼

4、位數(shù)，m稱為約束長度（一些書中采用k=m+1為約束長度，也可稱（2，1，2）碼網(wǎng)格圖，r=k/n稱為信息率，即編碼效率。本文使用的是（2，1，3）碼，約速長度為2，狀態(tài)數(shù)為2 2=-4。 2 目標(biāo)處理器簡介TMS320C6000系列DSPs（數(shù)字信號處理器）是TI公司推出的一種并行處理的數(shù)字信號處理器，是基于TI的VLIW技術(shù)的。本文采用的是TMS320C6211。該處理器的工作頻率經(jīng)過倍頻可達(dá)到150MHz，每個時鐘周期最多可并行執(zhí)行8條指令，從而可以實現(xiàn)1200MIPS定點運算能力。C6000系列CPU采用哈佛結(jié)構(gòu)，其程序總線與數(shù)據(jù)總線分開，取指令與執(zhí)行指令可以并行運行。其程序總線寬度為2

5、56位，每一次取指操作都是取8條指令，稱為一個取指包，執(zhí)行時每條指令占用1個功能單元。取指、指令分配和指令譯碼單元都具有每周期讀取并傳遞8條32位指令的能力。C6000系列CPU有2個類似的可進(jìn)行數(shù)據(jù)處理的數(shù)據(jù)通道A和B，每個通路有4個功能單元（.L、.S、.M、.D）和1組包括16個（C64有32個）32位寄存器的通用寄存器組，每個功能單元完成一定的算術(shù)或邏輯運算。 C6000的特殊結(jié)構(gòu)使多個指令交迭地在不同功能單元內(nèi)處理，大大提高了微處理器的處理能力。另外在其CPU硬件結(jié)構(gòu)上，C6000的流水線分為三個階段：取指、譯碼、執(zhí)行，每一級又包含幾個節(jié)拍。流水處理使得若干條指令的不同執(zhí)行階段可以并

6、行執(zhí)行，從而能夠大幅度提高程序運行速度。 3 算法的編程實現(xiàn)及優(yōu)化根據(jù)C6000的軟件編程流程，對Viterbi算法的編程及其優(yōu)化可分為三個階段來進(jìn)行。這三個階段分別為：開發(fā)C代碼、優(yōu)化C代碼、編寫線性匯編代碼。在代碼編寫和優(yōu)化過程中，這三個階段不是必須都要經(jīng)過的，只要在某一階段已經(jīng)滿足了算法代碼的功能和性能要求，就不必繼續(xù)進(jìn)行下面的階段。 開發(fā)C代碼。這一階段完全是根據(jù)任務(wù)要求來完成算法的代碼編寫工作。在C6000的集成開發(fā)環(huán)境CCS（Code Composer Studio）下進(jìn)行代碼的編譯和功能驗證，然后可用CCS的調(diào)試工具（如Profiler）,利用在程序中設(shè)置斷點的方法可找出程序中耗

7、時最多、最影響整體性能的代碼段。為改進(jìn)代碼性能，可進(jìn)入下一階段。如下是針對（2，1，3）碼的Viterbi算法代碼中完成算法功能的核心循環(huán)，也是最耗時、最影響代碼整體性能的低效率段。 for(c=0;c<unmber_of_input;c+) /對每一個輸入值，設(shè)number_of_input=24 for(j=0;j<number_of_states;j+) /對于每個狀態(tài)（2，1，3）狀態(tài)數(shù)為4 for(i=0;i<2;i+) /對于狀態(tài)的每個可能輸入，比如1，0 /*計算度量值*/ branch_metric=hamm(conv_outputi,c,channel_da

8、ta); /*比較累計度量保留其中最小，并且記錄其狀態(tài)路徑*/ if(accum_err_metricnextstatej1>accum_err_metricj0+branch_metric accum_err_metricnextstateji1=accum_err_metricj0+branch_metri; state_historynextstatejish_ptr=j; */end of i<2*/ /*end of j<number_of_states*/ /*end of c<number_of_input*/ 其中調(diào)用函數(shù)hanmm是計算當(dāng)前輸入值與網(wǎng)絡(luò)

9、圖上的值相比較所返回的度量值。 Int hamm(char output_vector,int x,char channel_output24) char target_vector=0; int hamm=0; int i=0; int i=0; target_vector=(output_vector)channel_outputx; for(i=1;i>=0;i-) hamm+=(target_vector>>i)&0x01; return hamm; 在驗證了算法代碼實現(xiàn)功能并以設(shè)置斷點的方法測試代碼的性能，這段循環(huán)運行耗時（時鐘周期）為1790。顯然，性能不

10、能達(dá)到要求，就要進(jìn)入代碼優(yōu)化的第二階段了。 一般在代碼調(diào)試中，最影響性能的是其中的循環(huán)代碼段。而軟件流水是一種用于安排循環(huán)內(nèi)的指令運行方式，盡可能充分利用CPU的功能單元等資源，使循環(huán)的多次迭代能夠并行執(zhí)行的一種技術(shù)。在C6000的C/C+編譯器里，采用軟件流水使編譯出來的程序代碼優(yōu)化是一項核心技術(shù)。所以在進(jìn)一步優(yōu)化之前，需要調(diào)整并盡可能簡化代碼的結(jié)構(gòu)并去除影響軟件流水的因素使其能夠被編譯器充分流水，這對大幅提高整個代碼的性能非常重要。 所以，在考慮影響因素同時對Viterbi算法的循環(huán)代碼進(jìn)行如下調(diào)整； *使用內(nèi)聯(lián)函數(shù)（intrinsics）替代復(fù)雜的C語言程序。C6000編譯器提供了許多i

11、ntrinsics，可以快速優(yōu)化C代碼。Intrinsics是直接參與C6000匯編指令映射的內(nèi)聯(lián)函數(shù)。在這里使用了_extu(x,y,z)，以簡化其中hamm代碼部分。 *盡管軟件流水循環(huán)可包含intrinsics，但不能包含函數(shù)調(diào)用。所以需要把調(diào)用函數(shù)hamm在循環(huán)中展開實現(xiàn)。 *由于編譯器僅對最內(nèi)部的循環(huán)執(zhí)行流水，所以為了提高性能應(yīng)盡可能創(chuàng)造一比較大的內(nèi)循環(huán)。在代碼中可以看到，在最內(nèi)循環(huán)是i的兩次循環(huán)，僅對它進(jìn)行流水，對整個代碼的性能提高不大。所以一個想法是，將i和j循環(huán)全部展開，使編譯器直接面對最大的C循環(huán)以最大發(fā)揮軟件流水的作用。 *另外，展開循環(huán)后代碼中的變量如果可以確定其運行中的

12、值，就盡量以實值代入，這樣減少了變量個數(shù)，也就是減少了所需分配的寄存器個數(shù)（C62xxCPU中有32個寄存器）。 在進(jìn)行上述調(diào)整后運行代碼，進(jìn)行測試發(fā)展，性能沒有太大改善；用編譯器反饋表（feedback）進(jìn)行觀察發(fā)現(xiàn)，循環(huán)并沒有發(fā)生流水。這是為什么呢？原來在展開內(nèi)部循環(huán)后導(dǎo)致C循環(huán)內(nèi)代碼尺寸太大，需要的寄存器數(shù)目大于C62XX的32個寄存器，所以不能進(jìn)行軟件流水。為了解決這問題，需要簡化循環(huán)或?qū)⒀h(huán)拆成幾個小循環(huán)。在這里先將C循環(huán)內(nèi)部的小循環(huán)展開，然后將其拆成分別完成度量計算和累計度量比較的兩個循環(huán)，這樣就減小了每個循環(huán)中的代碼尺寸。限于篇幅這里只寫出累計度量比較的循環(huán)代碼。 /*完成累計度

13、量比較的循環(huán)*/ accum00=accum_err_metric0;accum10=accum_err_metric1; accum20=accum_err_metric2;accum30=accum_err_metric3; for(c=0;c<n;c+)/n=24 sh_ptr+； add1=accum10+branch_metric_arrayc1; add2=accum00+branch_metric_arrayc0; add3=accum10+branch_metric_arrayc0; add4=accum00+branch_metric_arrcyc1; add5=acc

14、um30+branch_metric_arrayc2; add6=accum20+branch_metric_arrayc3; add7=accum30+branch_metric_arrayc3; add8=accum20+branch_metric_arrayc2; if(add1>add2)accum00=add2;state_history0sh_ptr=0; elseaccum00=add1;state_history0sh_ptr=1; if(add3>add4)accum20=add4;state_history2sh_ptr=0; elseaccum20=add3;

15、state_history2sh_ptr=1; if(add5>add6)accum30=add6;state_history3sh_ptr=2; elseaccum30=add5;state_history3sh_ptr=3; if(add7>add8)accum10=add8;state_history1sh_ptr=2; elseaccum10=add7;state_history1sh_ptr=3; accum_err_metric0=accum00;accum_err_metic1=accum10; accum_err_metric2=accum20;accum_err_

16、metric3=accum30; 其中accum_err_metrici為狀態(tài)i的累計度量值，branch_metric_array為計算得到的各時刻量值，原來代碼中的二維數(shù)碼mextstateji被以實值代入。另外在編程考慮時要注意一點：程序中對數(shù)據(jù)的取命令（load）是非常耗時的，所以應(yīng)考慮盡量減少對數(shù)據(jù)數(shù)組的操作。在上面程序的改進(jìn)中，先從數(shù)組中取出要進(jìn)行循環(huán)處理的累計度量值，再使用accumXX及addX作為各次迭代的中間變量，在循環(huán)后將最后的結(jié)果放入數(shù)據(jù)。這樣就大大減少了對數(shù)組的操作，從而使優(yōu)化進(jìn)一步提高。 *編譯器優(yōu)化選項的選擇。C6000 C/C+編譯器提供了大量的編譯選項，供用戶

17、在編譯時選擇使用。這些選項中的部分會直接影響或控制編譯器優(yōu)化過程，因而會影響編譯輸出的代碼優(yōu)化性能。選擇適合的選項，能極大地提高優(yōu)化性能。在這里使用的優(yōu)化選項有： -03表示可得到最高程度的優(yōu)化，編譯器將執(zhí)行各種優(yōu)化循環(huán)的方法，如軟件流水、循環(huán)展開等等。 -pm在使用-o3選項進(jìn)行優(yōu)化時盡量聯(lián)合使用-pm選項，-pm是程序級優(yōu)化，使優(yōu)化器訪問整個程序，了解循環(huán)次數(shù)。 -op1使用了外部變量，但未使用外部函數(shù)調(diào)用。 -g使能符號調(diào)試和匯編源語句調(diào)試。 另外，還有不少考慮因素和優(yōu)化調(diào)試方法，如消除存儲器相關(guān)性、對短字長的數(shù)據(jù)使用寬離長度的存儲器訪問等。由于篇幅所限不能在這里一一列出，詳細(xì)資料可參考

18、TMS320C6000 Code Composer Studio Manuals中的TMS320C6000 Optimizing C Compiler User's Guide。 測試結(jié)果：在經(jīng)過上述優(yōu)化后運行耗時（時鐘周期）已降為406個，代碼的性能大為提高，已經(jīng)滿足系統(tǒng)要求。 由上述可知，在程序中影響性能的主要代碼通常是循環(huán)。優(yōu)化一個循環(huán)較好的方法是抽出這個循環(huán)，使之成為一個單獨文件，對其進(jìn)行重新編寫、重新編譯和單獨運行。為了提高代碼性能，對影響速度的關(guān)鍵C代碼段可以用線性匯編重新編寫，使用匯編優(yōu)化器進(jìn)行優(yōu)化后效率是非常高的。若代碼性能仍未滿足要求，則可進(jìn)行第三階段，將其抽出，全部用線性匯編來編寫，在代碼中以函數(shù)的形式將改寫的部分調(diào)用。將循環(huán)代碼段改寫為線性匯編調(diào)用函數(shù)的格式如下： .global_KernelLoop ；函數(shù)名定義前加_ _KernelLoop:.cproc channel_data,branch_metric_array,depunc ;定義入口形參變量 .reg