基于DSP的Max-Log-MAP算法實現(xiàn)與優(yōu)化

1引 言

Turbo碼接近Shannon理論極限的優(yōu)越性能使其在衛(wèi)星通信、深空通信、多媒體通信等領域具有非常大的誘惑力，因此自提出以來一直受到廣泛而持續(xù)的關注。

Turbo碼的工程應用與實現(xiàn)是近年來研究工作的熱點。Turbo碼采用反饋迭代譯碼結構，成員譯碼器使用最大后驗概率(MAP)譯碼算法譯碼，由于MAP算法含有大量的指數運算與對數運算，給實現(xiàn)帶來極大的困難，在工程應用中，通常采用其對數域的簡化算法——Log-MAP和Max-Log-MAP算法。相對于Log-MAP算法，Max-Log-MAP雖然損失0.5 dB的增益，但由于其大大簡化了復雜度，在應用與實現(xiàn)中倍受關注。本文基于TMS320C6000系列DSP芯片討論了Max-Log-MAP算法的實現(xiàn)與優(yōu)化。

2 Turbo碼的反饋迭代譯碼結構與Max-Log-MAP譯碼算法

Turbo碼又稱為并行級聯(lián)卷積碼(PCCC)，編碼器由兩個RSC成員碼通過交織器并行級聯(lián)。與之對應，在譯碼端Turbo碼則采用兩個成員譯碼器串聯(lián)構成的反饋迭代結構，如圖1所示，其中DEC1與DEC2表示兩個軟輸入軟輸出(SISO)的成員譯碼器，假設編碼輸出采用BPSK調制方式，xk，yk為解調器輸出的受噪聲污染的信息比特與校驗比特，zk(zn)表示從另一個譯碼器經過解交織(交織)后得到的外信息。每個成員譯碼器有兩個輸出端口，分別輸出信息比特的對數似然比LLR(L1(ak)，L2(an))及被另一個成員譯碼器使用的外信息叫ω1k，ω2k，經過若干次迭代和兩個成員譯碼器的外信息交換，對信息比特的對數似然比進行硬判決即可完成Turbo碼的譯碼。

Max-Log-MAP算法下的對數似然比可以表示如下：

其中m′，m分別對應k-1和k時刻的編碼器狀態(tài)，αk(m)，βk(m)分別稱為前向和后向狀態(tài)度量，可以根據RSC碼的網格圖由分支度量rk(i，m′，m)(i=±1)遞推計算：

外信息若采用Robertson使用方式，AWGN信道下碼率為1／2的RSC碼分支度量rk(i，m′，m)計算公式可以表示為：

式中j=±1，表示對應信息比特ak=i編碼應輸出的雙極性校驗比特，Lc=4Es／N0定義為信道可信度值。外信息與對數似然比的關系為：

3 Max-Log-MAP譯碼算法的C語言軟件編程與實現(xiàn)

分析可知，Max-Log-MAP算法需要根據每時刻的接收信息計算幾種度量值：分支度量rk(i，m ′，m)，前向狀態(tài)度量αk(m)和后向狀態(tài)度量βk(m)，最后由3個度量值計算該時刻的對數似然比L(ak)，從而得到另一個成員譯碼器需要的外信息ωk。因此算法可以大致分為幾個模塊：分支度量模塊，前、后向狀態(tài)度量模塊及對數似然比模塊，各個模塊的計算均是基于網格圖的遞推完成，故均可以使用C語言中的for循環(huán)語句實現(xiàn)，這里以八狀態(tài)(13，15)RSC碼為例逐一分析。

3.1 分支度量模塊(BMU)

狀態(tài)度量的遞推是在分支度量的基礎上進行的，因此分支度量是算法的基本量度，由式(4)可知，分支度量實際上是由接收信息與網格圖上轉移路徑對應輸出的相關運算。對于八狀態(tài)(13，15)RSC碼，網格圖上兩個相鄰時刻的狀態(tài)轉移路徑共有16條，考慮到(i，j)組合的取值只有4種，且(-1，-1)與(+1，+1)，(-1，+1)與(+1，-1)條件下的分支度量值互為相反數，故為了減少數據的存儲，每一時刻只需計算兩個分支度量值即可，不妨設為BM11與BM10，BMU的算法實現(xiàn)結構為：

這里Lx和Ly分別表示經過信道可信度值處理過的接收信息比特與校驗比特軟信息，z表示來自另外一個成員譯碼器的外信息，N為Turbo碼的信息幀長度。

3.2 狀態(tài)度量模塊(SMU)

前向狀態(tài)度量的遞推與后向狀態(tài)度量的遞推在算法上是相似的，我們以前向狀態(tài)度量為例說明狀態(tài)度量模塊(SMU)的算法編程實現(xiàn)，用FSMj表示基于RSC(13，15)碼網格圖j狀態(tài)的前向狀態(tài)度量累加值(j=0，1，…，7)，前向狀態(tài)度量的遞推循環(huán)語句結構為(其中語句中的temp1，temp2表示臨時變量)：

事實上，SMU完成在每一個網格圖狀態(tài)將轉移至該狀態(tài)的分支度量進行“累加”、“選大”的功能即所謂的ASC操作。

3.3 對數似然比模塊(LLRU)

對數似然比模塊(LLRU)根據分支度量與狀態(tài)度量值計算對數似然比與外信息，其基本運算也是類似SMU中的加比選(ACS)操作，相應的算法結構如下(轉移路徑按輸入分別為0和1分為兩組，狀態(tài)從0～7排列)：

語句中的BSM表示后向狀態(tài)度量，LLR表示對數似然比，ω為輸入至另外一個成員譯碼器的外信息，其他均為臨時變量。

4 基于DSP的Max-Log-MAP譯碼算法代碼優(yōu)化

基于C語言的DSP開發(fā)關鍵在于代碼的精簡優(yōu)化，TI公司CCS開發(fā)軟件中的C編譯器提供了對代碼的優(yōu)化功能，人們可以通過選項設置、循環(huán)展開、加注關鍵字、使用內聯(lián)函數(intrinsic)等操作完成對C代碼的優(yōu)化。本文主要針對TMS320C6000系列芯片的結構與特點討論Max-Log-MAP譯碼算法代碼的優(yōu)化設計，包括軟件流水、數據存取優(yōu)化等，以達到充分利用DSP芯片的硬件資源，獲得高效處理性能的目的。

4.1 C6000系列芯片的結構與特點

TMS320C6000系列DSP是TI公司推出的一種基于VLIW技術，具有8個功能單元的數字信號處理器，其CPU采用哈佛結構，程序總線與數據總線分開，取指令與執(zhí)行指令可以并行運行，VLIW技術的使用可以使指令獲取、指令分配、指令執(zhí)行和數據存儲等操作形成多級流水，在同一時鐘周期多條指令交迭地在不同功能單元內處理。C6000系列芯片在每個時鐘周期內可以同時執(zhí)行8條指令。

4.2 基于DSP的各算法模塊代碼優(yōu)化

4.2.1 BMU模塊

BMU算法模塊為單循環(huán)語句，由于循環(huán)體內的指令較少，為了更多地同時利用CPU資源，一個有效的做法即是將循環(huán)展開，這樣在減少循環(huán)次數的同時可以使更多的操作形成流水(pipeline)，充分發(fā)揮多個功能單元的并行處理能力。優(yōu)化后的代碼如下：

4.2.2 SMU模塊

由于狀態(tài)度量的遞推具有遞歸性，即本時刻遞推得到的數值將用作下一時刻的遞推初值，因此對于該算法模塊的數據讀入讀出操作是一個值得考慮的問題。從3.2節(jié)SMU的程序分析可知，F(xiàn)SM的讀寫致使CPU寄存器與數據存儲器之間頻繁的進行l(wèi)oad與store操作，為了減少該操作的指令消耗，我們引入3組臨時變量FSM_tempj，F(xiàn)SMj_old和FSMj_new(j=0，1，…，7)用來存儲FSM的計算結果，這樣在下次遞推時CPU可以直接從內部的寄存器讀取數據，避免了從數據存儲器的load操作。優(yōu)化后的代碼結構如下：

與先前只采用兩個臨時變量sum1和sum2相比，優(yōu)化后的代碼采用更多的變量，這樣可以保持數據的獨立性，避免造成CPU寄存器的關聯(lián)，使代碼更易于流水線操作。

4.2.3 LLRU模塊

對于LLRU算法模塊的代碼優(yōu)化主要從減少加減操作指令入手，這涉及到對算法的改進。前文提到每一時刻的轉移路徑有16條，如果采用3.3節(jié)的程序結構，對分支度量要進行16次加減操作?？紤]到分支度量只有4種取值，結合RSC(13，15)網格圖的映射關系，按照分支度量的取值將轉移路徑分為4組，這4組分別對于分支度量的加減操作先不予處理，即先選最大后再進行相應的分支度量加減操作，這樣每一次循環(huán)可以將分支度量的加減操作由原來的16次減少至4次，故可以大大降低CPU資源的消耗。相應的優(yōu)化代碼結構如下：

4.3 代碼優(yōu)化前后消耗的指令周期對比

我們使用合眾達公司的SEED—C6416仿真開發(fā)板，采用C6416-T系列DSP芯片在CCS 3.1編譯環(huán)境下對各個算法模塊及整個Max-Log-MAP算法進行了編譯與硬件仿真，Turbo碼的信息幀長選為144 b，代碼的數據類型定義為int型，編譯選項設置為-03-mt-pm。使用CCS附帶的定時器(Timer)功能，對優(yōu)化前后代碼消耗的指令周期進行了測試，結果如表1所示。

可見，優(yōu)化后的代碼大大降低了CPU指令周期的消耗，提高了DSP的工作效率。值得提出的是，在代碼優(yōu)化時主要針對算法本身的指令操作與數據存儲等方面進行了改進，事實上，在具體的開發(fā)過程中還可以根據實際的數據寬度采用內聯(lián)函數(intrinsics)，數據封裝處理(packeddata processing)等措施對代碼進行進一步優(yōu)化，以獲得更高效的性能。

5 結 語

本文研究了基于標準C語言的Turbo碼Max-Log-MAP譯碼算法的軟件編程與實現(xiàn)方法，并結合TMS320C6000系列DSP芯片的結構與特點深入探討了代碼的優(yōu)化設計，通過循環(huán)展開、數據存取優(yōu)化、算法的改進等措施提高代碼的效率，測試結果表明，經過優(yōu)化的代碼可以大大降低CPU的指令周期消耗，從而獲得了比較高效的處理性能。