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

1引 言

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

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

2 Turbo碼的反饋迭代譯碼結(jié)構(gòu)與Max-Log-MAP譯碼算法

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

Max-Log-MAP算法下的對(duì)數(shù)似然比可以表示如下：

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

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

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

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

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

3.1 分支度量模塊(BMU)

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

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

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

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

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

3.3 對(duì)數(shù)似然比模塊(LLRU)

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

語(yǔ)句中的BSM表示后向狀態(tài)度量，LLR表示對(duì)數(shù)似然比，ω為輸入至另外一個(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編譯器提供了對(duì)代碼的優(yōu)化功能，人們可以通過(guò)選項(xiàng)設(shè)置、循環(huán)展開(kāi)、加注關(guān)鍵字、使用內(nèi)聯(lián)函數(shù)(intrinsic)等操作完成對(duì)C代碼的優(yōu)化。本文主要針對(duì)TMS320C6000系列芯片的結(jié)構(gòu)與特點(diǎn)討論Max-Log-MAP譯碼算法代碼的優(yōu)化設(shè)計(jì)，包括軟件流水、數(shù)據(jù)存取優(yōu)化等，以達(dá)到充分利用DSP芯片的硬件資源，獲得高效處理性能的目的。

4.1 C6000系列芯片的結(jié)構(gòu)與特點(diǎn)

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

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

4.2.1 BMU模塊

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

4.2.2 SMU模塊

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

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

4.2.3 LLRU模塊

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

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

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

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

5 結(jié) 語(yǔ)

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