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

　　本文將討論在ADI Blackfin通用定點DSP處理器上如何高效實現(xiàn)Turbo MAP 解碼器的技術。

　　DSP（digital signal processor）是一種獨特的微處理器，是以數(shù)字信號來處理大量信息的器件。其工作原理是接收模擬信號，轉換為0或1的數(shù)字信號，再對數(shù)字信號進行修改、刪除、強化，并在其他系統(tǒng)芯片中把數(shù)字數(shù)據(jù)解譯回模擬數(shù)據(jù)或實際環(huán)境格式。它不僅具有可編程性，而且其實時運行速度可達每秒數(shù)以千萬條復雜指令程序，遠遠超過通用微處理器，是數(shù)字化電子世界中日益重要的電腦芯片。它的強大數(shù)據(jù)處理能力和高運行速度，是值得稱道的兩大特色。

　　TURBO解碼器

    Turbo編碼器采用兩個并行相連的系統(tǒng)遞歸卷積編碼器，并以一個交織器輔之。兩個卷積編碼器的輸出經(jīng)并串轉換和鑿孔（Puncture）操作后輸出。相應地，Turbo解碼器由首尾相接、中間由交織器和解交織器隔離的兩個以迭代方式工作的軟判輸出卷積解碼器構成。雖然目前尚未得到嚴格的Turbo編碼理論性能分析結果，但從計算機仿真結果看，在交織器長度大于1000、軟判輸出卷積解碼采用標準后驗概率（MAP）算法的條件下，其性能比約束長度為9的卷積碼提高1～2.5dB。目前Turbo碼用于第三代移動通信系統(tǒng)的主要困難體現(xiàn)在：（1）由于交織長度的限制，無法用于速率較低、時延要求較高的數(shù)據(jù)傳輸；（2）基于MAP的軟輸出解碼算法所需計算量和存儲量較大；（3）Turbo編碼在衰落信道下的性能還有待于進一步研究。

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

　　(1)

　　其中，Y1N=[y1,y2,…,yN]。

　　譯出的信息位通過以下硬判決得到：

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

（3）

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

　　式（4）中，前向狀態(tài)度量根據(jù)編碼器狀態(tài)（對應于每級或時刻n）的網(wǎng)格表示從n=0時刻進行遞歸計算（由于在對數(shù)域內，采用累加）得到，這里假定的初值為，當1≤k≤2M-1時，。其中，M是編碼生成多項式（1+D2+D3）的冪。類似的，式（5）中的反向狀態(tài)度量從網(wǎng)格級n=N+1開始進行遞歸計算得到，同樣假定的初始狀態(tài)為和，其中1≤k≤2M-1。狀態(tài)度量和的遞歸算法如下。

（4）

（5）

　　其中，b（i,m）和f（i,m）分別是與第n級的狀態(tài)m相關的第n-1級和第n+1級狀態(tài)值。在α，β和LLR的計算中，我們必須解一個形如ez=ex+ey的方程。其和的近似值可由ex=emax（x,y）（1+e-|x-y|）或z=max（x,y）+ln（1+e-|x-y|）= max*（x, y）計算得到。該算子被稱為Log-MAP算子。修正項ln（1+e-|x-y|） 是一個非線性函數(shù)，它對MAP解碼器在低信噪比下的性能增益帶來0.5dB的提高。如果我們忽略了這個修正項，算子z=max（x,y）則被稱為Max-Log-MAP算子。本文只考慮Turbo MAP解碼器實現(xiàn)中的Max-Log-MAP算子。

　　TURBO解碼器的實現(xiàn)

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

　　1度量計算

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

　　圖1 第n級LLR的計算圖解

　　2 基于窗口的算法實現(xiàn)

　　如圖1所示，Turbo解碼器工作于符號長度為N的序列或結構上。因此，Turbo解碼器的實現(xiàn)就需要一個超大容量的存儲器（用來存儲所有N級的α、β、γ、LLR、外部信息、接收序列、緩存等等），但是可以通過加窗的方法降低對存儲容量的要求。基于加窗口的方法就是將整個數(shù)據(jù)結構分成一些小的數(shù)據(jù)塊或數(shù)據(jù)窗（有6K級窗口的重疊，K=M+1，是編碼器的約束長度），每次只在一個窗口上執(zhí)行解碼操作。在 MAP 解碼中，三個主要的算子是α估計，β估計和LLR估計。在計算當前窗的β和LLR的同時，計算下一個窗中的α，這樣就可以平衡ALU和DAG（加載/存儲）單元對帶寬的需求，如圖2所示。

　　圖 2 基于窗口的Turbo解碼器的高效實現(xiàn)

　　BLACKFIN處理器上MAP解碼器度量計算實現(xiàn)

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

　　1 狀態(tài)度量計算實現(xiàn)

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

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

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

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

　　2 LLR的實現(xiàn)

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

　　圖5（a） 位“1”的 MAP關系，（b）位“0”的MAP關系

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

　　圖6 在Blackfin ALU上的LLR計算

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

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

　　總結

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