一種低復雜度的Log-MAP譯碼器結構

孫增友，李歡歡

(東北電力大學信息工程學院，吉林吉林 132012)

從1993年，Turbo碼被 C.Berrou等人［1］提出以來，就以其優異的性能和相對簡單可行的編譯碼算法吸引了眾多研究者的目光。Turbo碼的實質是并行級聯的卷積碼，它與以往所有碼的不同之處在于它通過一個交織器的作用，達到接近隨機編碼的目的。它所采用的迭代譯碼策略，使得譯碼復雜性大大降低。Bahl等人［2］于1974年首次提出可以由最大后驗概率(MAP)迭代譯碼算法進行譯碼。Turbo碼已被應用于各種通信系統，如深空通信、蜂窩移動通信和衛星通信網絡，并且作為第三代移動通信標準，如CDMA2000。

MAP譯碼算法由于存在非線性函數和大量的乘法和加法運算［3］，實際中Turbo碼譯碼器的硬件實施很困難。因此，在次優譯碼算法——Log-MAP譯碼解決方案中，通常在對數域運算。次最優譯碼算法的目的是降低譯碼復雜度，同時保持編碼的誤碼率(BER)性能在適度的水平，與最優譯碼(MAP)相比，只有很小分貝的譯碼性能損失。

近幾年，提出的各種算法均旨在簡化Turbo譯碼算法Log-MAP算法中的max*運算，包括:改進的Max-Log-MAP算法、Constant Log-MAP 算法［4］、Linear Log-MAP 算法、Lookup Log-MAP算法等。這些次最優算法采用近似的方法使得譯碼算法簡化，但性能與最優算法相比略有損失，為了減少性能的損失，額外的修正項需要添加到max運算中。本文提出了一種新的max*運算的近似方法，應用于Turbo碼的Log-MAP譯碼算法中。這種近似方法可以很好地降低每個譯碼步驟運算的復雜度，相對于傳統的Log-MAP算法，性能降低很少。

1 Turbo碼的編譯碼

1.1 Turbo碼編碼方案

基于并行級聯卷積碼(PCCC)的Turbo碼編碼器結構圖如圖1所示，在Turbo碼編碼過程中，信息序列u={u1，u2，…，uN}經過交織器后，形成一個新的序列u'={u1'，u2'，…，uN'}。然后將這兩個序列u和u'分別傳送到兩個分量編碼器(RSC1，)中進行編碼，令生成的編碼序列分別為Xp1和Xp2，經過刪余器，刪除一些校驗位，形成新的校驗序列Xp，這樣做的目的是為了提高碼率和系統頻譜效率。最后將校驗序列Xp與未編碼的系統信息Xs經過復接器生成Turbo碼的編碼序列X。

圖1 PCCC型Turbo編碼結構

1.2 Turbo碼譯碼方案

Turbo碼譯碼是基于兩個SISO譯碼器之間的迭代過程。如圖2所示，第一個SISO譯碼器的輸入端是由比特先驗信息Lin，2，經信道傳輸的信息比特rs，以及第一個編碼器輸出的校驗比特rp，1這3部分構成。然后產生一個軟輸出值Le，1，作為隨后SISO譯碼器2的先驗信息Lin，2，稱為外部信息。SISO譯碼器2的輸出經過解交織后作為先驗信息Le，2又反饋給SISO譯碼器1作為輸入，這樣就完成了一次迭代的過程。經過一定的迭代次數后，SISO譯碼器2的輸出L^u，2進行解交織后經硬判決就是Turbo碼的譯碼輸出。

圖2 Turbo碼的迭代譯碼示意圖

工程中常用的譯碼算法有基于最大后驗概率的軟輸出算法和軟輸出Viterbi算法兩大類。由于MAP算法中的Log-MAP和Max-Log-MAP計算復雜度較低而更適合并行計算。假設u是N比特的信息塊。經過Turbo編碼和BPSK調制，通過AWGN信道，接收的信息序列為y。在Turbo譯碼之前先進行軟解調。設由輸入引起的柵格由K-1時刻的狀態S'轉移為K時刻狀態S。前向遞歸和后向遞歸可以遞歸計算為［5］

式中:ˉαk和 ˉβk應先進行初始化［2］;ˉγk是在迭代過程中與之對應的柵格狀態過渡的分支轉移概率。傳輸比特uk的譯碼軟輸出，可以用對數似然比(LLR)計算，即

其中，max*運算，可以利用Jacobian算法定義為

式中:fc(·)為相關函數。為了使得Log-MAP算法復雜度最低，相關函數fc(·)可由查找表來實現。如果忽略相關函數的值，采用這種簡化方法得到的就是Max-Log-MAP算法［6］。

2 Log-MAP近似譯碼算法

2.1 簡化的max*運算

max*運算是Log-MAP算法的計算核心。當編碼器中寄存器個數為M時，譯碼器中就有2M個max*運算，且max*運算需要遞歸運算，當M≥3時，這種算法硬件實現復雜，而采用Max-Log-MAP算法譯碼后性能損失很大，因此提出一種簡化的Log-MAP算法。

為了降低對n個輸入變量參數的max*運算近似算法的復雜度，針對這個問題，采用Chebyshev不等式，所提出的改進的Log-MAP算法的n輸入max*運算為

式中:y1=max{x1，x2，…，xn}為n個輸入值中的最大值;y2=max{x1，x2，…，xn|y1}是次最大值;δ=y1-y2;K1=(n-1)/n，K2=ln［2n/(n+1)］。近似的第一項是一個簡單的max運算，第二項可以認為是另一個校正功能的函數fc(·)。

在計算信息比特的L(uk)時，式(3)中的max*運算用式(7)中的max運算。而對式(1)和式(2)中2個變量的max*運算均如式(4)作精確計算。

式(7)中，K2是一個正常數，在迭代譯碼過程中可以忽略，當n的值很大時，K1≈1，所以式(7)可以簡化為

3.2 max*運算中相關函數的實現及硬件結構簡化

式(8)的實現需要設計合適的數字電路找出y1和y2，計算出δ，然后應用于相關函數fc(·)。在文獻［7］中提出的一種有效的基于樹結構的最大值產生器(MVGs)，用于從n個元素中找出y1和y2。這種結構由2個(n/2)-MVG結構和3個最大值單元(MVUs)組成，如圖3所示。則式(8)可以通過一個n-MVG結構結合減法器計算δ，利用查找表(LUT)計算fc(δ)的值，再通過加法器實現。其中，s表示A-B。

圖3 改進的結構圖(灰色框為改進部分)

Log-MAP算法中簡化的max*運算中的相關函數曲線fc(x)=lg(1+e-x)和Constant Log-MAP算法的近似的相關函數fc(x)如圖4所示。Log-MAP算法的近似算法中，Constant Log-MAP算法具有最低的復雜度，并且接近最優的Turbo碼BER性能。

圖4 Log-MAP相關函數fc(x)和近似的fc(x)

Constant Log-MAP相關函數算法［4］為一個8位二進制的補碼整數運算，數值表示為5個整數位和3個小數位，因此，fc(x)的最小值為1/8，對應x的最大值為2.0。如果x≥2，那么fc(x)≈0。另外，根據文獻［4］，當x ＜2，fc(x)可以近似為［0，2)的平均值，即，最佳取值為fc(x)≈3/8(即0.375)，因此Constant Log-MAP算法的近似相關函數fc(x)為

Constant Log-MAP算法可以通過其相關函數fc(x)的實現進一步降低其硬件結構復雜度。

因為δ≥0，fc(δ)的實現可以更簡化。設c是給定δ={δp-1…δ0}時 fc(δ)的取值，c={cp-1…c0}。可以看出:

1)如果 c=3/8，則 cp-1…c0=“0…0．011”，或 cp-1…c0=“0…0．000”。

2)如果 δ＜2，那么 δp-2…δ0=“0…0x．xxx”，其中 x 任意表示為1或0。因此c0和c1僅當δj=0，4≤j≤p-2時等于1，即

式中:(·)表示非邏輯運算，∨表示或邏輯運算。所以在硬件實現式(8)時，在計算得出δ后，進行c0的計算時，只需在原有的Constant Log-MAP譯碼算法硬件結構中引入幾個額外的門結構(非門和或門)。改進的結構圖如圖3中的灰色框部分。這樣，所提出的算法利用了δ≥0的優勢，使得相關函數的硬件實現的復雜度大約降為Constant Log-MAP譯碼算法的一半。

3 MATLAB仿真分析

3.1 Turbo碼在CCSDS標準中的應用仿真

將所提出的max*近似方法應用于Turbo譯碼中，對應信噪比下(Eb/N0)的BER性能仿真如圖5所示。4條BER曲線分別代表Constant Log-MAP算法［4］、本文提出的改進算法(用Log-MAP max*表示)、Log-MAP和Max-Log-MAP算法的BER性能。

圖5 不同譯碼算法的在CCSDS標準中的性能仿真比較

仿真的Turbo碼參數為移位寄存器具有16個狀態，碼率為R=1/2，生成多項式為(1，33/23)o，33和23為8進制數，分別代表前饋多項式和反饋多項式。信息序列N=103bit，傳輸幀總數為106。

為了保證仿真結果性能的準確性，每個性能仿真實驗中至少引入了100個位錯誤。使用了偽隨機Turbo交織器，在接收端最多進行10次迭代，采用BPSK調制，應用于CCSDS標準［8］中。由圖5可知，所提出的改進的Log-MAP算法(用虛線表示)總能達到接近最優的譯碼算法的BER性能，其譯碼復雜度接近Max-Log-MAP算法，而糾錯能力明顯強于Max-Log-MAP算法;在低誤碼率時，如10-6時，改進的譯碼算法可以實現與另外兩種算法大致相同的BER性能。

3.2 Turbo碼在WiMAX標準中的應用仿真

將雙二進制的Turbo碼，考慮其含有8種狀態的分量卷積碼的情況，應用于WiMAX標準［9］中，碼率為 R=1/3，2/3和4/5，信息序列長度為N=752 bit，調制方式為QPSK。在接收器端，至少進行10次譯碼迭代。仿真結果如圖6所示。

圖6 不同譯碼算法在WiMAX標準中的性能仿真比較

在圖6中，與使用二進制Turbo碼的性能仿真相比，所提出的算法與Constant Log-MAP算法的BER性能之間的差異減小，Log-MAP算法與Max-Log-MAP算法的BER性能差異也減小。尤其，當R＞1/2時，可以看出所提出的算法達到了與Constant Log-MAP算法幾乎相同的性能，BER=10-6時，甚至更低。

4 硬件復雜度分析

表1給出了所提出的n輸入近似max*算法結構(用C表示)在空間(用A表示)和延遲(用D表示)兩個方面與兩種基于樹結構的算法進行比較:1)基于3 bit LUT的2輸入的Log-MAP算法結構(用A表示);2)2輸入的Constant Log-MAP算法結構［4］(用 B 表示)。

表1 不同算法的硬件結構空間及延遲比較

實驗均表明，所提出算法的結構不但比基于LUT的Log-MAP算法的遞歸結構和近似的Constant Log-MAP算法的結構空間大大減小，而且在更高的時鐘頻率運行時具有較低的延遲。如表1中，假設n=16，p=16時，所提出的n輸入的max*結構需要5 768個等同的門，具有2 ns的最小延遲，而2輸入的Constant Log-MAP結構需要7 312個等同的門，具有2.8 ns的最小延遲。因此所提出的n輸入的max*結構空間減少了21%，延遲降為2輸入Constant Log-MAP結構的28.5%。在具有與Constant Log-MAP算法(B)相同的延遲時(DB)作更近一步比較，對應的比較結果如表1中最后一列所示。可以看出，此時與Constant Log-MAP硬件復雜度相比，所提出的結構平均節省了大概30%的空間。

5 小結

本文給出了Turbo碼譯碼的簡化的Log-MAP譯碼算法，對其譯碼過程中的max*運算進行新的近似，并對其硬件實現結構進行了簡化。max*運算是廣義上的對n個輸入值計算的簡化，將max*運算近似為簡單的max運算和相關函數的計算。仿真結果表明，這種方法相對于Log-MAP譯碼算法，性能有很小的損失，可以忽略不計。從實踐的角度來看，新的改進算法的優勢是顯著降低了每個譯碼步驟的譯碼復雜度，簡化了硬件結構，降低了延遲，具有廣闊的工程應用前景。

［1］ BERROU C，GLAVIEUX A，THITIMAJSHIMA P.Near Shannon limit error-correcting coding and decoding:Turbo codes［C］//Proc.the IEEE International Conference on Communications.Geneva:IEEE Press，1993:1064-1070.

［2］ BAHL L R，COCKE J，JELINEK F，et al.Optimal decoding of linear codes for minimizing symbol error rate［J］.IEEE Trans.Information Theory，1974，3(20):284-287.

［3］孫增友，張利杰，田勇.SF-MAX-Log-MAP并行譯碼算法及其在LTE中的應用研究［J］.東北電力大學學報，2012，32(4):35-39.

［4］ GROSSW J，GULAK P G.Simplified MAP algorithm suitable for implementation of turbo SISOalgorithms based on Log-MAPand Max-Log-MAP turbo decoding［J］.IET Proc.Commun.，2007，1(1):49-57.

［5］ PAPAHARALABOSS，SWEENEY P，EVANS B G.SISO algorithms based on Log-MAP and Max-Log-MAP turbo decoding［J］.IET Proc.Commun.，2007，1(1):49-57.

［6］劉東華.Turbo碼原理與應用技術［M］.北京:電子工業出版社，2004.

［7］ WEY CL，SHIEH M D，LIN SY.Algorithms of finding the first two minimum values and their hardware implementation ［J］.IEEE Trans.Circuits Syst.I，2008，55(11):3430-3437.

［8］張凱.CCSDS標準Turbo碼譯碼器設計及實現［D］.北京:北京郵電大學，2013.

［9］ IEEE802.16e-2005，Standard for local and metropolitan area networks.Part16:air interface for fixed and mobile broadband wireless access systems［S］.2006.