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

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

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

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

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

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

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

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

3 Max-Log-MAP譯碼算法的C語(yǔ)言軟件編程與實(shí)現

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

3.1 分支度量模塊(BMU)

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

這里L(fēng)x和Ly分別表示經(jīng)過(guò)信道可信度值處理過(guò)的接收信息比特與校驗比特軟信息，z表示來(lái)自另外一個(gè)成員譯碼器的外信息，N為T(mén)urbo碼的信息幀長(cháng)度。

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

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

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

3.3 對數似然比模塊(LLRU)

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

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

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

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

4.1 C6000系列芯片的結構與特點(diǎn)

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

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

4.2.1 BMU模塊

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

4.2.2 SMU模塊

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

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

4.2.3 LLRU模塊

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

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

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

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

5 結 語(yǔ)

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