淺論Ｖｉｔｅｒｂｉ算法

1、淺論算法作者：劉峰時(shí)間：2009-3-3 10:52:00 論文關(guān)鍵詞Viterbi 算法 編程 論文摘要雖然Texas Instrument推出的C6000系列DSP使對(duì)信號(hào)處理的能力顯著提高，但對(duì)信息處理能力要求的不斷提升使提對(duì)DSP程序的優(yōu)化越來越成為DSP開發(fā)工作中非常重要的環(huán)節(jié)。本文討論2Mbps視頻數(shù)據(jù)流的Viterbi算法的移植與優(yōu)化策略、技巧。 一、概述 Viterbi譯碼算法是由Viterbi于1967年提出的一種最大似然譯碼辦法，譯碼器根據(jù)接收序列R按最大似然準(zhǔn)則力圖找出正確的原始碼序列。隨著大規(guī)模集成電路技術(shù)的發(fā)展，采用Viterbi算法的卷積編碼技術(shù)已成為廣泛應(yīng)用的糾錯(cuò)

2、方案。Viterbi譯碼過程可用狀態(tài)表示。Sj，t和Sj N/2，t表示t時(shí)刻的兩個(gè)狀態(tài)。在t1時(shí)刻，這兩個(gè)狀態(tài)值根據(jù)路徑為0或者1，轉(zhuǎn)移到狀態(tài)S2j，t1和S2j1，t1。每一種可能的狀態(tài)轉(zhuǎn)移都根據(jù)接收到的有噪聲的序列R計(jì)算路徑度量，然后選擇出各個(gè)狀態(tài)的最小度量路徑(幸存路徑)。Viterbi算法就是通過在狀態(tài)中尋找最小量路徑向前回溯L步，最后得到的即為譯碼輸出。 在卷積碼(n，k，m)表示法中，參數(shù)k表示每次輸入信息碼位數(shù)，n表示編碼的輸出卷積碼位數(shù)，m稱為約束長度(一些書中采用k=m1為約束長度，也可稱(2，1，2)碼網(wǎng)格圖，r=k/n稱為信息率，即編碼效率。本文運(yùn)用的是(2，1，3)碼

3、，約速長度為2，狀態(tài)數(shù)為22=4。 TMS320C6000系列DSPs(數(shù)字信號(hào)處理器)是TI公司推出的一種并行處理的數(shù)字信號(hào)處理器，是基于TI的VLIW技術(shù)的。本文采用的是TMS320C6211。該處理器的工作頻率經(jīng)過倍頻可達(dá)到150MHz，每個(gè)時(shí)鐘周期最多可并行執(zhí)行8條指令，從而可以實(shí)現(xiàn)1200MIPS定點(diǎn)運(yùn)算能力。 二、編程實(shí)現(xiàn)及優(yōu)化 根據(jù)C6000的軟件編程流程，對(duì)Viterbi算法的編程及其優(yōu)化可分為三個(gè)階段來進(jìn)行。這三個(gè)階段分別為：開發(fā)C代碼、優(yōu)化C代碼、編寫線性匯編代碼。在代碼編寫和優(yōu)化過程中，這三個(gè)階段不是都要經(jīng)過的，只要在某一階段已經(jīng)滿足了算法代碼的功能和性能要求，就不必繼續(xù)

4、進(jìn)行下面的階段。 1.開發(fā)C代碼。這一階段完全是根據(jù)任務(wù)要求來完成算法的代碼編寫工作。在C6000的集成開發(fā)環(huán)境CCS(Code Composer Studio)下進(jìn)行代碼的編譯和功能驗(yàn)證，然后可用CCS的調(diào)試工具(如Profiler)，利用在程序中設(shè)置斷點(diǎn)的辦法可找出程序中耗時(shí)最多、最影響整體性能的代碼段。為改進(jìn)代碼性能，可進(jìn)入下一階段。 在驗(yàn)證了算法代碼實(shí)現(xiàn)功能并以設(shè)置斷點(diǎn)的辦法測試代碼的性能，這段循環(huán)運(yùn)行耗時(shí)(時(shí)鐘周期)為1790。顯然，性能不能達(dá)到要求，就要進(jìn)入代碼優(yōu)化的第二階段了。 2.一般在代碼調(diào)試中，最影響性能的是其中的循環(huán)代碼段。而軟件流水是一種用于安排循環(huán)內(nèi)的指令運(yùn)行方式，盡

5、可能充分利用CPU的功能單元等資源，使循環(huán)的多次迭代能夠并行執(zhí)行的一種技術(shù)。在C6000的C/C編譯器里，采用軟件流水使編譯出來的程序代碼優(yōu)化是一項(xiàng)核心技術(shù)。所以在進(jìn)一步優(yōu)化之前，需要調(diào)整并盡可能簡化代碼的結(jié)構(gòu)并去除影響軟件流水的因素使其能夠被編譯器充分流水，這對(duì)大幅提高整個(gè)代碼的性能非常重要。 所以，在考慮影響因素同時(shí)對(duì)Viterbi算法的循環(huán)代碼進(jìn)行如下調(diào)整； *運(yùn)用內(nèi)聯(lián)函數(shù)(intrinsics)替代復(fù)雜的C語言程序。C6000編譯器提供了許多intrinsics，可以快速優(yōu)化C代碼。Intrinsics是直接參與C6000匯編指令映射的內(nèi)聯(lián)函數(shù)。在這里運(yùn)用了_extu(x，y，z)，以

6、簡化其中hamm代碼部分。 *盡管軟件流水循環(huán)可包含intrinsics，但不能包含函數(shù)調(diào)用。所以需要把調(diào)用函數(shù)hamm在循環(huán)中展開實(shí)現(xiàn)。 *由于編譯器僅對(duì)最內(nèi)部的循環(huán)執(zhí)行流水，所以為了提高性能應(yīng)盡可能創(chuàng)造一比較大的內(nèi)循環(huán)。在代碼中可以看到，在最內(nèi)循環(huán)是i的兩次循環(huán)，僅對(duì)它進(jìn)行流水，對(duì)整個(gè)代碼的性能提高不大。所以一個(gè)想法是，將i和j循環(huán)全部展開，使編譯器直接面對(duì)最大的C循環(huán)以最大發(fā)揮軟件流水的作用。 *另外，展開循環(huán)后代碼中的變量如果可以確定其運(yùn)行中的值，就盡量以實(shí)值代入，這樣減少了變量個(gè)數(shù)，也就是減少了所需分配的寄存器個(gè)數(shù)(C62xxCPU中有32個(gè)寄存器)。 在進(jìn)行上述調(diào)整后運(yùn)行代碼，進(jìn)行

7、測試發(fā)展，性能沒有太大改善；用編譯器反饋表(feedback)進(jìn)行觀察發(fā)現(xiàn)，循環(huán)并沒有發(fā)生流水。這是為什么呢？原來在展開內(nèi)部循環(huán)后導(dǎo)致C循環(huán)內(nèi)代碼尺寸太大，需要的寄存器數(shù)目大于C62XX的32個(gè)寄存器，所以不能進(jìn)行軟件流水。為了解決這問題，需要簡化循環(huán)或?qū)⒀h(huán)拆成幾個(gè)小循環(huán)。在這里先將C循環(huán)內(nèi)部的小循環(huán)展開，然后將其拆成分別完成度量計(jì)算和累計(jì)度量比較的兩個(gè)循環(huán)，這樣就減小了每個(gè)循環(huán)中的代碼尺寸。 其中accum_err_metrici為狀態(tài)i的累計(jì)度量值，branch_metric_array為計(jì)算得到的各時(shí)刻量值，原來代碼中的二維數(shù)碼mextstatei被以實(shí)值代入。另外在編程考慮時(shí)要注意一

8、點(diǎn)：程序中對(duì)數(shù)據(jù)的取命令(load)是非常耗時(shí)的，所以應(yīng)考慮盡量減少對(duì)數(shù)據(jù)數(shù)組的操作。在上面程序的改進(jìn)中，先從數(shù)組中取出要進(jìn)行循環(huán)處理的累計(jì)度量值，再運(yùn)用accumXX及addX作為各次迭代的中間變量，在循環(huán)后將最后的結(jié)果放入數(shù)據(jù)。這樣就大大減少了對(duì)數(shù)組的操作，從而使優(yōu)化進(jìn)一步提高。 *編譯器優(yōu)化選項(xiàng)的選擇。C6000 C/C編譯器提供了大量的編譯選項(xiàng)，供用戶在編譯時(shí)選擇運(yùn)用。這些選項(xiàng)中的部分會(huì)直接影響或控制編譯器優(yōu)化過程，因而會(huì)影響編譯輸出的代碼優(yōu)化性能。選擇適合的選項(xiàng)，能極大地提高優(yōu)化性能。在這里運(yùn)用的優(yōu)化選項(xiàng)有： 03表示可得到最高程度的優(yōu)化，編譯器將執(zhí)行各種優(yōu)化循環(huán)的辦法，如軟件流水、

9、循環(huán)展開等等。 pm在運(yùn)用o3選項(xiàng)進(jìn)行優(yōu)化時(shí)盡量聯(lián)合運(yùn)用pm選項(xiàng)，pm是程序級(jí)優(yōu)化，使優(yōu)化器訪問整個(gè)程序，了解循環(huán)次數(shù)。 op1運(yùn)用了外部變量，但未運(yùn)用外部函數(shù)調(diào)用。 g使能符號(hào)調(diào)試和匯編源語句調(diào)試。 另外，還有不少考慮因素和優(yōu)化調(diào)試辦法，如消除存儲(chǔ)器相關(guān)性、對(duì)短字長的數(shù)據(jù)運(yùn)用寬離長度的存儲(chǔ)器訪問等。 測試結(jié)果：在經(jīng)過上述優(yōu)化后運(yùn)行耗時(shí)(時(shí)鐘周期)已降為406個(gè)，代碼的性能大為提高，已經(jīng)滿足系統(tǒng)要求。 3.由上述可知，在程序中影響性能的主要代碼通常是循環(huán)。優(yōu)化一個(gè)循環(huán)較好的辦法是抽出這個(gè)循環(huán)，使之成為一個(gè)單獨(dú)文件，對(duì)其進(jìn)行重新編寫、重新編譯和單獨(dú)運(yùn)行。為了提高代碼性能，對(duì)影響速度的關(guān)鍵C代碼段

10、可以用線性匯編重新編寫，運(yùn)用匯編優(yōu)化器進(jìn)行優(yōu)化后效率是非常高的。若代碼性能仍未滿足要求，則可進(jìn)行第三階段，將其抽出，全部用線性匯編來編寫，在代碼中以函數(shù)的形式將改寫的部分調(diào)用。 編寫線性匯編的工作量大，開發(fā)周期長且不能像C語言程序一樣移植到其他類型DSP上，所以盡量在第一、二階段完成工作。若仍滿足不了性能要求，則再對(duì)關(guān)鍵代碼段進(jìn)行線性匯編的改寫。 本文在TI的TMS320C6211硬件平臺(tái)上實(shí)現(xiàn)了針對(duì)(2，1，3)卷積碼的Viterbi譯碼算法的優(yōu)化，滿足了系統(tǒng)對(duì)2Mb/s的視頻數(shù)據(jù)流進(jìn)行實(shí)時(shí)處理的要求。在對(duì)1Kb數(shù)據(jù)處理時(shí)，整個(gè)代碼運(yùn)行耗時(shí)約為2100個(gè)時(shí)鐘周期，DSP資源占用率不到40%?，F(xiàn)在隨著理論技術(shù)的不斷突破，尤其是實(shí)時(shí)圖像壓縮技術(shù)如H.264等新一代技術(shù)標(biāo)準(zhǔn)的提出，如何利用高速DSP進(jìn)行復(fù)雜算法的開發(fā)與實(shí)現(xiàn)，已成為研究