基于DSP處理器的UMTS Turbo MAP 解碼器高效實(shí)現

Turbo碼自1993年問(wèn)世以來(lái)，以其出色的性能，在工業(yè)和科研領(lǐng)域都引起了廣泛的關(guān)注。Turbo碼性能逼近（信噪比差為0.7dB或更?。┯蒀laude E. Shannon確定的信道容限。Berrou、Glavieux和Thitimajshima最先提出了Turbo碼，其結構由兩個(gè)并行級聯(lián)卷積編碼器組成。Turbo碼編碼方案產(chǎn)生同一信息序列的兩個(gè)不同交織形式的分量碼。解碼時(shí)，由兩個(gè)MAP解碼器以迭代方式對判決結果進(jìn)行解碼。MAP 解碼算法利用接收數據和校驗符號（以真實(shí)和交織形式的數據計算而來(lái)的校驗位），以及其他的解碼軟輸出（外部的）信息，得到更加可靠的判決結果。

本文將討論在A(yíng)DI Blackfin通用定點(diǎn)DSP處理器上如何高效實(shí)現Turbo MAP 解碼器的技術(shù)。

TURBO解碼器

在Turbo解碼過(guò)程中,MAP算法被用于確定最接近傳輸數據的信息位。MAP算法先對每個(gè)傳送的數據位計算一個(gè)后驗概率值（APPs），然后根據最大的后驗概率值為該數據位分配一個(gè)判決值，再進(jìn)行解碼。MAP 算法使用后驗概率值APP計算每一個(gè)傳送位Cn的最大似然比LLR，使誤碼率（BER）最小，其計算公式如下：

(1)
其中，Y1N=[y1,y2,…,yN]。
譯出的信息位通過(guò)以下硬判決得到：

在UMTS Turbo解碼器中，應用一個(gè)八狀態(tài)的RSC編碼網(wǎng)格，在n時(shí)刻，當輸入序列為Y1N時(shí)，比特“1”和比特“0”的APP可分別由式（2）和式（3）求得。

(2)

(3)
其中，分別是的對數, 是在n時(shí)刻和狀態(tài)m下的前向狀態(tài)度量， 是n時(shí)刻和狀態(tài)m下的分支度量，是n+1時(shí)刻和狀態(tài)k下的反向狀態(tài)度量。每級中，只需要兩個(gè)（當采用BPSK調制來(lái)傳輸數據比特流時(shí)）分支度量，而這些分支度量值可以由解碼輸入和另一個(gè)解碼器的中間軟輸出計算得到。

式（4）中，前向狀態(tài)度量根據編碼器狀態(tài)（對應于每級或時(shí)刻n）的網(wǎng)格表示從n=0時(shí)刻進(jìn)行遞歸計算（由于在對數域內，采用累加）得到，這里假定的初值為，當1≤k≤2M-1時(shí)，。其中，M是編碼生成多項式(1+D2+D3)的冪。類(lèi)似的，式（5）中的反向狀態(tài)度量從網(wǎng)格級n=N+1開(kāi)始進(jìn)行遞歸計算得到，同樣假定的初始狀態(tài)為和，其中1≤k≤2M-1。狀態(tài)度量和的遞歸算法如下。
(4)
(5)
其中，b(i,m)和f(i,m)分別是與第n級的狀態(tài)m相關(guān)的第n-1級和第n+1級狀態(tài)值。在α，β和LLR的計算中，我們必須解一個(gè)形如ez=ex+ey的方程。其和的近似值可由ex=emax(x,y)(1+e-|x-y|)或z=max(x,y)+ln(1+e-|x-y|)= max*(x, y)計算得到。該算子被稱(chēng)為L(cháng)og-MAP算子。修正項ln(1+e-|x-y|) 是一個(gè)非線(xiàn)性函數，它對MAP解碼器在低信噪比下的性能增益帶來(lái)最高0.5dB的提高。如果我們忽略了這個(gè)修正項，算子z=max(x,y)則被稱(chēng)為Max-Log-MAP算子。本文只考慮Turbo MAP解碼器實(shí)現中的Max-Log-MAP算子。

TURBO解碼器的實(shí)現

Turbo解碼器由兩個(gè)MAP解碼器組成，這兩個(gè)解碼器由一個(gè)交織器和解交織器分隔開(kāi)。由于篇幅有限，我們將不討論Turbo解碼器的完全實(shí)現而只討論性能敏感度最高的“度量計算”部分。

1度量計算

式（1）中LLR的值由APP求得，而APP則由式（2）和式（3）計算得到。在計算APP時(shí)，我們要用到第n級所有狀態(tài)下的α (前向狀態(tài)度量)，β(后向狀態(tài)度量)和γ(分支度量)。在第n級，γ值根據已接收到的信息和第n級的外部信息計算得到，而α用第n-1級的α和第n級的γ計算得到，β則由第n+1級的β和第n級的γ計算得到。換句話(huà)說(shuō)，為了計算第n級的LLR值，我們要同時(shí)利用由前n級計算出的α值和由后N-n級計算出的β值，如圖1所示。

圖1 第n級LLR的計算圖解

2 基于窗口的算法實(shí)現

如圖1所示，Turbo解碼器工作于符號長(cháng)度為N的序列或結構上。因此，Turbo解碼器的實(shí)現就需要一個(gè)超大容量的存儲器（用來(lái)存儲所有N級的α、β、γ、LLR、外部信息、接收序列、緩存等等），但是可以通過(guò)加窗的方法降低對存儲容量的要求?；诩哟翱诘姆椒ň褪菍⒄麄€(gè)數據結構分成一些小的數據塊或數據窗（有6K級窗口的重疊，K=M+1，是編碼器的約束長(cháng)度），每次只在一個(gè)窗口上執行解碼操作。在 MAP 解碼中，三個(gè)主要的算子是α估計，β估計和LLR估計。在計算當前窗的β和LLR的同時(shí)，計算下一個(gè)窗中的α，這樣就可以平衡ALU和DAG（加載/存儲）單元對帶寬的需求，如圖2所示。

圖 2 基于窗口的Turbo解碼器的高效實(shí)現

BLACKFIN處理器上MAP解碼器度量計算實(shí)現

在這一部分，將討論Turbo MAP解碼器中復雜的度量計算如何在A(yíng)DI Blackfin處理器上實(shí)現，并充分利用Blackfin處理器提供的專(zhuān)用特性高效實(shí)現Turbo解碼器。

1 狀態(tài)度量計算實(shí)現

圖3 第n+1級和第n級計算的蝶形算法

狀態(tài)度量α和β可由式（4）和式（5）求得，該狀態(tài)度量的計算可用圖3所示的方法得以實(shí)現。α由正向（從左到右）計算得到，而β則由反向（從右到左）計算得到。圖中，實(shí)線(xiàn)和虛線(xiàn)分別對應于輸入“1”和“0”的編碼。雖然通過(guò)分支度量（γ），可以由兩個(gè)輸入狀態(tài)度量計算出兩個(gè)輸出狀態(tài)度量（α和β），但這兩個(gè)度量的輸出狀態(tài)卻根據它們各自的輸入狀態(tài)而有所不同。在執行過(guò)程中，這一輸入和輸出狀態(tài)度量的位置改變，在將數據從ALU寄存器存入存儲器和將數據從存儲器載入ALU寄存器時(shí)，可以通過(guò)加載/存儲（DAG）模塊解決。

圖4 UMTS Turbo解碼器狀態(tài)度量估計的高效實(shí)現

UMTS Turbo解碼過(guò)程中，α和β計算在Blackfin處理器上的高效實(shí)現如圖4。由于Blackfin處理器能以向量模式運行，在單個(gè)指令周期執行四個(gè)16位加/減操作或兩個(gè)16位求最大值操作，每一級α的計算需要8個(gè)循環(huán)周期來(lái)完成，而每一級β的計算則需要另外8個(gè)周期來(lái)完成。

2 LLR的實(shí)現

對于UMTS Turbo解碼器，MAP算法的LLR可由式（1），式（2）和式（3）計算得到。式（2）和式（3）分別說(shuō)明了通過(guò)α、γ和β來(lái)計算位“1”和位“0”的APP值的關(guān)系。這些MAP LLR的關(guān)系如圖5(a)和圖5(b)所示。

圖5(a) 位“1”的 MAP關(guān)系，(b)位“0”的MAP關(guān)系

對于兩個(gè)相同的輸入和輸出，位“1”和位“0”的MAP關(guān)系并不相似（極少情況下?tīng)顟B(tài)被交換），而這類(lèi)不對稱(chēng)流程使我們無(wú)法利用Blackfin中計算單元和加載/存儲單元的最大帶寬。例如，圖5（a）和圖5（b）中標示的部分，我們考慮與式（2）和式（3）的前兩項相對應的頂端蝶形運算。

圖6 在Blackfin ALU上的LLR計算

由于Blackfin只需要三個(gè)周期就能完成四個(gè)16位加法和兩個(gè)16位求最大值操作，要平衡加載/存儲（DAG）單元的帶寬和計算單元，只能用三個(gè)周期來(lái)加載數據。假設三個(gè)寄存器在三個(gè)周期中分別加載了α0|α0, α1|α1和 β4|β0，如圖6所示。那么通過(guò)16位加法操作，我們可以在兩個(gè)周期中計算出α0+β4|α0+β0和α1+β4|α1+β0。但是，MAX 操作要求仿照式（3）從反方向由α1+β0|α1+β4求得輸出的第二項。Blackfin的16位加法指令所支持的交叉選項（CO）選項可用來(lái)?yè)Q回加法的中間輸出，如圖6所示。如果沒(méi)有交叉選項（CO），我們將耗費四個(gè)周期來(lái)計算四次加法，而不是兩個(gè)。采用（CO）選項換回之后，執行最大向量操作（一個(gè)周期）即可得到兩個(gè)Log-Max 輸出。這一部分程序代碼如圖7所示。有了（CO）選項，就可以在18個(gè)Blackfin指令周期內計算某一級上的LLR值。

圖7 利用BF5xx處理器交叉選項（CO）的LLR高效實(shí)現

總結

本文介紹了在A(yíng)DI BF5xx處理器上Turbo MAP解碼器的高效實(shí)現，詳細說(shuō)明了基于窗口的存儲空間降低方法，并利用16位加/減和16位求最大值向量指令以及交叉選項（CO），高效地在Blackfin嵌入式處理器上實(shí)現了Turbo MAP解碼。該方法耗費大約36個(gè)BF5xx周期，即可計算得到一個(gè)LLR輸出。同時(shí)，利用約50kB的BF5xx存儲空間，完成了UMTS Turbo MAP解碼算法的數據和程序存儲。