- 相關推薦
基于DSP的信道譯碼算法優化
摘要：在DSP上移植算法，代碼優化程度成為提高系統性能、縮短開發周期的瓶頸。同時針對復雜算法在DSP上的實現，也產生很多優化策略、方法。本文以在數字通信系統中應用廣泛的Viterbi算法為例，簡述Viterbi算法的基本原理和目標處理器（TMS320C6211）的處理能力；介紹C6000軟件編程及優化的步驟，并提出一些具體的優化策略和技巧。關鍵詞：Viterbi算法 TMS320C6000 優化
雖然Texas Instrument推出的C6000系列DSP使對信號處理的能力顯著提高，但對信息處理能力要求的不斷提升使提對DSP程序的優化越來越成為DSP開發工作中非常重要的環節。本文討論2Mbps視頻數據流的Viterbi算法的移植與優化策略、技巧。
1 Viterbi算法原理簡介
Viterbi譯碼算法是由Viterbi于1967年提出的一種最大似然譯碼方法，譯碼器根據接收序列R按最大似然準則力圖找出正確的原始碼序列。隨著大規模集成電路技術的發展，采用Viterbi算法的卷積編碼技術已成為廣泛應用的糾錯方案。Viterbi譯碼過程可用狀態圖表示，圖1表示2個狀態的狀態轉移圖。Sj,t和Sj+N/2,t表示t時刻的兩個狀態。在t+1時刻，這兩個狀態值根據路徑為0或者1，轉移到狀態S2j,t+1和S2j+1,t+1。每一種可能的狀態轉移都根據接收到的有噪聲的序列R計算路徑度量，然后選擇出各個狀態的最小度量路徑（幸存路徑）。Viterbi算法就是通過在狀態圖中尋找最小量路徑向前回溯L步，最后得到的即為譯碼輸出。
在卷積碼（n,k,m）表示法中，參數k表示每次輸入信息碼位數，n表示編碼的輸出卷積碼位數，m稱為約束長度（一些書中采用k=m+1為約束長度，也可稱（2，1，2）碼網格圖，r=k/n稱為信息率，即編碼效率。本文使用的是（2，1，3）碼，約速長度為2，狀態數為2 2=-4。
2 目標處理器簡介
TMS320C6000系列DSPs（數字信號處理器）是TI公司推出的一種并行處理的數字信號處理器，是基于TI的VLIW技術的。本文采用的是TMS320C6211。該處理器的工作頻率經過倍頻可達到150MHz，每個時鐘周期最多可并行執行8條指令，從而可以實現1200MIPS定點運算能力。C6000系列CPU采用哈佛結構，其程序總線與數據總線分開，取指令與執行指令可以并行運行。其程序總線寬度為256位，每一次取指操作都是取8條指令，稱為一個取指包，執行時每條指令占用1個功能單元。取指、指令分配和指令譯碼單元都具有每周期讀取并傳遞8條32位指令的能力。C6000系列CPU有2個類似的可進行數據處理的數據通道A和B，每個通路有4個功能單元（.L、.S、.M、.D）和1組包括16個（C64有32個）32位寄存器的通用寄存器組，每個功能單元完成一定的算術或邏輯運算。(范文先生網www.baimashangsha.com收集整理)
C6000的特殊結構使多個指令交迭地在不同功能單元內處理，大大提高了微處理器的處理能力。另外在其CPU硬件結構上，C6000的流水線分為三個階段：取指、譯碼、執行，每一級又包含幾個節拍。流水處理使得若干條指令的不同執行階段可以并行執行，從而能夠大幅度提高程序運行速度。
3 算法的編程實現及優化
根據C6000的軟件編程流程，對Viterbi算法的編程及其優化可分為三個階段來進行。這三個階段分別為：開發C代碼、優化C代碼、編寫線性匯編代碼。在代碼編寫和優化過程中，這三個階段不是必須都要經過的，只要在某一階段已經滿足了算法代碼的功能和性能要求，就不必繼續進行下面的階段。
①開發C代碼。這一階段完全是根據任務要求來完成算法的代碼編寫工作。在C6000的集成開發環境CCS（Code Composer Studio）下進行代碼的編譯和功能驗證，然后可用CCS的調試工具（如Profiler）,利用在程序中設置斷點的方法可找出程序中耗時最多、最影響整體性能的代碼段。為改進代碼性能，可進入下一階段。如下是針對（2，1，3）碼的Viterbi算法代碼中完成算法功能的核心循環，也是最耗時、最影響代碼整體性能的低效率段。
for(c=0;c<unmber_of_input;c++) //對每一個輸入值，設number_of_input=24
{for(j=0;j<number_of_states;j++) //對于每個狀態（2，1，3）狀態數為4
{for(i=0;i<2;i++) //對于狀態的每個可能輸入，比如1，0
{/*計算度量值*/
branch_metric=hamm(conv_output[i],c,channel_data);
/*比較累計度量保留其中最小，并且記錄其狀態路徑*/
if(accum_err_metric[nextstate[j][1]>accu
m_err_metric[j][0]+branch_metric]
{accum_err_metric[nextstate[j][i][1]=accum_err_metric[j][0]+branch_metri;
state_history[nextstate[j][i]][sh_ptr]=j;
}
}*/end of i<2*/
}/*end of j<number_of_states*/
}/*end of c<number_of_input*/
其中調用函數hanmm是計算當前輸入值與網絡圖上的值相比較所返回的度量值。
Int hamm(char output_vector,int x,char channel_output[24])
{char target_vector=0;
int hamm=0;
int i=0;
int i=0;
target_vector=(output_vector)^channel_output[x];
for(i=1;i>=0;i--)
hamm+=(target_vector>>i)&0x01;
return hamm;
}
在驗證了算法代碼實現功能并以設置斷點的方法測試代碼的性能，這段循環運行耗時（時鐘周期）為1790。顯然，性能不能達到要求，就要進入代碼優化的第二階段了。
②一般在代碼調試中，最影響性能的是其中的循環代碼段。而軟件流水是一種用于安排循環內的指令運行方式，盡可能充分利用CPU的功能單元等資源，使循環的多次迭代能夠并行執行的一種技術。在C6000的C/C++編譯器里，采用軟件流水使編譯出來的程序代碼優化是一項核心技術。所以在進一步優化之前，需要調整并盡可能簡化代碼的結構并去除影響軟件流水的因素使其能夠被編譯器充分流水，這對大幅提高整個代碼的性能非常重要。
所以，在考慮影響因素同時對Viterbi算法的循環代碼進行如下調整；
*使用內聯函數（intrinsics）替代復雜的C語言程序。C6000編譯器提供了許多intrinsics，可以快速優化C代碼。Intrinsics是直接參與C6000匯編指令映射的內聯函數。在這里使用了_extu(x,y,z)，以簡化其中hamm代碼部分。
*盡管軟件流水循環可包含intrinsics，但不能包含函數調用。所以需要把調用函數hamm在循環中展開實現。
*由于編譯器僅對最內部的循環執行流水，所以為了提高性能應盡可能創造一比較大的內循環。在代碼中可以看到，在最內循環是i的兩次循環，僅對它進行流水，對整個代碼的性能提高不大。所以一個想法是，將i和j循環全部展開，使編譯器直接面對最大的C循環以最大發揮軟件流水的作用。
*另外，展開循環后代碼中的變量如果可以確定其運行中的值，就盡量以實值代入，這樣減少了變量個數，也就是減少了所需分配的寄存器個數（C62xxCPU中有32個寄存器）。
在進行上述調整后運行代碼，進行測試發展，性能沒有太大改善；用編譯器反饋表（feedback）進行觀察發現，循環并沒有發生流水。這是為什么呢？原來在展開內部循環后導致C循環內代碼尺寸太大，需要的寄存器數目大于C62XX的32個寄存器，所以不能進行軟件流水。為了解決這問題，需要簡化循環或將循環拆成幾個小循環。在這里先將C循環內部的小循環展開，然后將其拆成分別完成度量計算和累計度量比較的兩個循環，這樣就減小了每個循環中的代碼尺寸。限于篇幅這里只寫出累計度量比較的循環代碼。
/*完成累計度量比較的循環*/
accum00=accum_err_metric[0];accum10=accum_err_metric[1];
accum20=accum_err_metric[2];accum30=accum_err_metric[3];
for(c=0;c<n;c++)//n=24
{sh_ptr++；
add1=accum10+branch_metric_array[c][1];
add2=accum00+branch_metric_array[c][0];
add3=accum10+branch_metric_array[c][0];
add4=accum00+branch_metri
c_arrcy[c][1];
add5=accum30+branch_metric_array[c][2];
add6=accum20+branch_metric_array[c][3];
add7=accum30+branch_metric_array[c][3];
add8=accum20+branch_metric_array[c][2];
if(add1>add2){accum00=add2;state_history[0][sh_ptr]=0;}
else{accum00=add1;state_history[0][sh_ptr]=1;}
if(add3>add4){accum20=add4;state_history[2][sh_ptr]=0;}
else{accum20=add3;state_history[2][sh_ptr]=1;}
if(add5>add6){accum30=add6;state_history[3][sh_ptr]=2;}
else{accum30=add5;state_history[3][sh_ptr]=3;}
if(add7>add8){accum10=add8;state_history[1][sh_ptr]=2;}
else{accum10=add7;state_history[1][sh_ptr]=3;}
}
accum_err_metric[0]=accum00;accum_err_metic[1]=accum10;
accum_err_metric[2]=accum20;accum_err_metric[3]=accum30;
其中accum_err_metric[i]為狀態i的累計度量值，branch_metric_array[][]為計算得到的各時刻量值，原來代碼中的二維數碼mextstate[j][i]被以實值代入。另外在編程考慮時要注意一點：程序中對數據的取命令（load）是非常耗時的，所以應考慮盡量減少對數據數組的操作。在上面程序的改進中，先從數組中取出要進行循環處理的累計度量值，再使用accumXX及addX作為各次迭代的中間變量，在循環后將最后的結果放入數據。這樣就大大減少了對數組的操作，從而使優化進一步提高。
*編譯器優化選項的選擇。C6000 C/C++編譯器提供了大量的編譯選項，供用戶在編譯時選擇使用。這些選項中的部分會直接影響或控制編譯器優化過程，因而會影響編譯輸出的代碼優化性能。選擇適合的選項，能極大地提高優化性能。在這里使用的優化選項有：
-03——表示可得到最高程度的優化，編譯器將執行各種優化循環的方法，如軟件流水、循環展開等等。
-pm——在使用-o3選項進行優化時盡量聯合使用-pm選項，-pm是程序級優化，使優化器訪問整個程序，了解循環次數。
-op1——使用了外部變量，但未使用外部函數調用。
-g——使能符號調試和匯編源語句調試。
另外，還有不少考慮因素和優化調試方法，如消除存儲器相關性、對短字長的數據使用寬離長度的存儲器訪問等。由于篇幅所限不能在這里一一列出，詳細資料可參考TMS320C6000 Code Composer Studio Manuals中的TMS320C6000 Optimizing C Compiler User's Guide。
測試結果：在經過上述優化后運行耗時（時鐘周期）已降為406個，代碼的性能大為提高，已經滿足系統要求。
③由上述可知，在程序中影響性能的主要代碼通常是循環。優化一個循環較好的方法是抽出這個循環，使之成為一個單獨文件，對其進行重新編寫、重新編譯和單獨運行。為了提高代碼性能，對影響速度的關鍵C代碼段可以用線性匯編重新編寫，使用匯編優化器進行優化后效率是非常高的。若代碼性能仍未滿足要求，則可進行第三階段，將其抽出，全部用線性匯編來編寫，在代碼中以函數的形式將改寫的部分調用。將循環代碼段改寫為線性匯編調用函數的格式如下：
.global_KernelLoop ；函數名定義前加_
_KernelLoop:.cproc channel_data,branch_metric_array,depunc ;定義入口形參變量
.reg c,q0,q1,y1,y2,x1,x2,cc,temp,temp0,temp1,temp2,temp3
.reg counter,valuel,value2,value3定義中間變量
no_mdep ；表明存儲器地址不相關
zer0 c ；初始化變量
zero cc
loop: .trip 24 ；聲明循環24次
·
·
·
運行語句
·
·
·
[counter]sub counter,23,counter;循環計數
[counter]b loop ;循環跳轉
.return ;完成返回
.endproc ；結束
編寫線性匯編的工作量大，開發周期長且不能像C語言程序一樣移植到其它類型DSP上，所以盡量在第一、二階段完成工作。若仍滿足不了性能要求，則再對關鍵代碼段進行線性匯編的改寫。
結語
本文在TI的TMS320C6211硬件平臺上實現了針對（2，1，3）卷積碼的Viterbi譯碼算法的優化，滿足了系統對2Mb/s的視頻數據流進行實時處理的要求。在對1Kb數據處理時，整個代碼運行耗時約為2100個時鐘周期，DSP資源占用率不到40%。目前隨著理論技術的不斷突破，尤其是實時圖像壓縮技術如H.264等新一代技術標準的提出，如何利用高速DSP進行復雜算法的開發與實現，已成為研究的重點。所以本文以Viterbi算法為例介紹TMS320C6000的編程優化，有較強實用性。
【基于DSP的信道譯碼算法優化】相關文章：
基于TMS320C6000系列DSP的維特比譯碼程序優化設計08-06
基于DSP的自動對焦系統08-06
基于DSP平臺的USB接口設計08-06
高速Viterbi譯碼器的優化和實現08-06
基于DSP的紙幣號碼識別系統08-06
基于GP算法的知識發現系統08-06
基于GP算法的知識發現系統08-06