MAP譯碼器的免歸一化處理信息更新算法*

王 璇，杜 軍

(1.南京信息職業技術學院 電子信息學院，南京 210023；2.中興光電子技術有限公司，南京 210012)

0 引 言

數據傳輸的可靠性是無線通信系統設計中一個非常重要的指標。Turbo編碼[1]可以獲得逼近香農信道容量的譯碼性能。Turbo碼的解碼[2-3]通常以迭代方式完成，一個譯碼器處理過的信息被迭代地饋送到另一個譯碼器，直到達到一定程度的收斂為止。

譯碼器中實現解碼有各種各樣的方法，其中基于BCJR(Bahl，Cocke，Jelinek and Raviv)算法的最大后驗概率(Maximum A Posteriori Probability,MAP)譯碼算法[4]被廣泛采用。MAP算法的目的是使得輸出正確碼字的概率最大化，包括系統信息和外信息的概率。在進行下一次迭代期間，其他譯碼器會用到外信息。這種算法采用的是迭代的譯碼過程，外信息在兩個分量譯碼器之間進行迭代，以逼近香農極限。雖然采用MAP算法的Turbo 碼的性能指標已經接近了最優[5]，但采用MAP算法具體實現的集成電路還存在著兩個主要問題：時延和存儲需求。在每一次迭代中，來自另一個分量譯碼器的外信息以累積的形式呈現在當前譯碼器狀態信息和外信息更新中。為了降低譯碼器狀態信息和外信息保存的存儲開銷，MAP譯碼器的狀態信息和外信息都采用有限字長來表示；為了避免在累加過程中有限字長出現溢出的情況，MAP譯碼器可以采用歸一化來進行處理。歸一化方法就是通過尋找更新后的狀態信息的最大值，并將該最大值作為基準進行歸一化處理。因此，這種算法會帶來一定的處理時延和計算復雜度。

本文提出了一種免歸一化的MAP算法，避免了傳統算法中最大值搜索和處理的相關過程及計算[6]。利用二進制補碼的基本原理，將有限字長的二進制補碼表示的數值映射到一個歸一化圓上，這樣以二進制補碼表征的狀態信息和外信息也映射到該歸一化圓上。利用二進制補碼運算的基本原理，MAP算法中的狀態信息和外信息的更新計算過程轉換為相關數值點在圓周上的運動。如果能夠通過這些數值在該圓周上的相對位置關系，獲得這些數值的相對大小關系，根據MAP算法的基本原理，就可以獲得正確的概率信息，且沒有性能的損失。這就是免歸一化MAP算法的基本思想。本文還給出歸一化圓半徑的確定方法。性能仿真和電路實現驗證了本文所提出的算法不會損失譯碼性能；與傳統方法相比關鍵路徑時延降低了17.4%，復雜度降低了36.2%。因此，本文提出的算法能有效地改善MAP譯碼器的時延和復雜度。

1 MAP算法原理及其歸一化處理

為了便于陳述，表1列舉出了本文使用的一些主要符號和其定義。

表1 本文所用符號匯總

Turbo編碼器將信息符號及根據碼約束關系獲得的校驗符號一起發送出去。接收器接收到發送過來的帶有噪聲的數據后，MAP譯碼器從頭至尾掃描接收到的數據來識別前向可能的譯碼路徑關系，然后又從尾到頭獲得后向可能的譯碼路徑關系；最后根據大量前向和后向的搜索結果，從所有可能的路徑中尋找出最佳的譯碼路徑。最優路徑是對所有輸入數據的最佳推測。例如，一個長度為 15 的數據幀被送入MAP譯碼器，Turbo碼的狀態空間S為8，譯碼路徑如圖1所示。

圖1 譯碼路徑

譯碼過程中，αk=(αk(0),αk(1),…,αk(s-1))從前向由αk-1獲得，βk=(βk(0),βk(1),…,βk(s-1))從后向由βk+1獲得。根據MAP算法，狀態信息表示從一個步驟到下一個步驟的狀態轉移概率，表示狀態信息的字長或者位寬在實現過程中會受到一定的限制。如果在狀態信息變化過程中發生溢出，就會產生誤碼，而且誤碼會擴大，導致MAP譯碼器無法正常工作。因此，狀態信息必須歸一化[7]。

αk和βk-1的計算方法如下：

(1)

(2)

當s∈S-1、s′∈S時，γk(s′,s)這樣定義：

γk(s′,s)=p(sk=s/sk-1=s′)=

(3)

這樣，外信息的計算方法是

(4)

為了簡化計算，在大多數實現中采用了log_MAP算法[8-9]，將乘法和除法轉換為加法和減法。簡化計算如下：

(5)

ln(ea+eb)=LOG_SUM(a,b)=

max(a,b)+ln(1+exp(-|b-a|))。

(6)

在實現過程中，ln(1+exp(-|b-a|))可以通過查表法來實現。根據之前的研究，大小為8的表就可以提供足夠的精度。

Log_MAP中的歸一化可以修改為

(7)

(8)

在Log_MAP中，外信息是

(9)

因此在執行歸一化算法時每一步都要做S-1次比較和S次減法。如果在歸一化期間不需要估計狀態信息的最大值，那么在譯碼器實現過程中就會降低解碼延遲并減小計算復雜度，達到提高計算速度的目的。

本文提出的免歸一化算法，目的就是省略在歸一化中尋找最大狀態信息的過程。因為在MAP譯碼算法中，重要的不是獲得各狀態信息的絕對值，而是正確計算和表征各狀態信息之間大小的相對關系，即在迭代過程中，具有相對大的狀態信息比相對小的狀態信息對于算法的正確收斂貢獻更大。

2 免歸一化MAP算法

根據Log_MAP算法的思想[6]，每一步更新后的狀態信息是一組介于0和負無窮(實際上是0到負數的界限)之間的數字。如果一種狀態信息越趨近于0，那就表明該狀態越有可能在最優譯碼路徑上的狀態是正確的。假如αk(s)是最大值，αk(s)=0，那么s就是在前向搜索的第k步中概率最高的正確狀態。假如βk(s)是最大值，βk(s)=0，那么s就是在后向搜索的第k步中概率最高的正確狀態。

在公式(9)中，{αk-1(s′)}的最大值和{βk(s)}的最大值對LLek起主要作用。如果在編碼器的輸出端dsk=+1 并且解碼器的推測是正確的，則LLek為正；如果在編碼器的輸出端dsk=-1并且解碼器的推測是正確的，則LLek為負。如果LLek的絕對值越大，那么在第k步的推測可信度就會越高。如果狀態信息的最大值遠大于狀態信息的次最大值，則LLek將更快地收斂于正確的推測。因此，在譯碼過程中知道哪個狀態具有最大的狀態信息對我們來說很重要，但最大值是否必須為0并不重要。

圖2 歸一化圓

如果狀態信息更新期間發生溢出，則投影點將從上半圓逆時針移動到下半圓；如果發生下溢出，投影點將逆時針從下半圓移動到上半圓；如果歸一化圓的半徑，即表示狀態信息的位寬足夠大，每個計算步驟的所有狀態信息都可以保持在同一個半圓中。也就是說，從最小狀態信息到最大狀態信息的弧上逆時針運動掃過的角度小于π。

我們可以將αk看作比賽中的跑步者，用比較通俗的描述來解釋該原理。如果所有跑步者間的距離始終在半圈內(競爭非常激烈的比賽)，則很容易確定誰是領先者。因此，如果αk之間的差值總是小于歸一化圓的一半，可以不用去管圓上的絕對位置就能很容易地找到αk的最大值。

在免歸一化算法中，可以通過二進制補碼加法器和減法器來實現模運算。假設免歸一化中使用的二進制補碼數據范圍為(-C,C)，根據Log_MAP算法中的公式(7)和(8)，如果滿足以下關系，則說明已經進行了歸一化：

maxAk(s)-minAk(s)

(10)

maxBk(s)-minBk(s)

(11)

免歸一化算法的Log_MAP中的歸一化修改為

(12)

(13)

圖3 免歸一化處理的實現框圖

如果用免歸一化方法得到{αk-1(s′)}和{βk(s)}，則{αk-1(s′)}的最大值和{βk(s)}的最大值的作用將會得到體現。與公式(9)結果相同，如果使用二進制補碼進行計算，當

則會滿足以下關系：

(14)

(15)

(16)

因此，我們不需要尋找狀態信息的最大值，Log_MAP的計算過程在每一步都得到了簡化，也加快了信息更新。由于譯碼器的樣點位寬和信道信噪比是預先定義的，就確定了最大狀態信息和最小狀態信息之間的差異。因此，即使本文的算法發生溢出時，在Log_MAP計算期間也可以保持狀態信息之間的正確關系?？梢?，免歸一化算法對于不同狀態信息的更新和外信息的更新效果與傳統的Log_MAP 譯碼算法相同。因此，本文算法在保證不損失譯碼性能的情況下，能加快狀態信息的更新速度并降低計算的復雜度。

本文的免歸一化算法的不足之處是在執行模塊歸一化時需要增加額外的比特位。免歸一化MAP算法的位寬可以通過Log_MAP算法中的|maxP+-maxP-|

3 性能分析

采用仿真實驗來分析免歸一化算法的性能。仿真中采用了符合LTE(Long Term Evolution)標準的Turbo碼，仿真參數如表2所列。

表2 仿真參數

仿真實驗中我們將傳統的Log_MAP算法與免歸一化算法進行了比較，結果如圖4所示。圖4(a)顯示了Turbo譯碼器在AWGN通道上譯碼器的數據幀長度為1 146時的性能，圖4(b)顯示了Turbo譯碼器在AWGN通道上譯碼器的數據幀長度為3 066時的性能。Turbo碼的譯碼有一個明顯的特點，就是“瀑布”效益，即在信噪比(Signal-to-Noise Ratio,SNR)增量很小的范圍內，如圖4(b)中SNR在-1.3～-0.6 dB范圍內，誤碼率(Bit Error Rate,BER)從10-1迅速降低到10-6。Turbo譯碼的另一個特點是有誤碼平層，當達到一定的誤碼率后，如圖4(b)中SNR高于-0.6 dB后，BER性能基本保持穩定而不會提升。

(a)數據幀長度為1 146

(b)數據幀長度為3 066圖4 不同數據幀長度下Turbo譯碼器在AWGN通道上的性能

從圖4中可以看到，采用免歸一化技術的Log_MAP算法的譯碼性能與傳統算法的譯碼性能基本相同。

對于免歸一化算法和傳統算法，采用Synopsys公司的EDA工具來實現Log_MAP譯碼器，在綜合仿真中進行了速度優化，表3列出了仿真結果。從表3中的數據發現，與傳統方法相比，采用免歸一化的Log_MAP算法可以降低36.2%的計算復雜度和17.4%的關鍵路徑延遲。因此，譯碼器可以以比傳統方法更低的復雜度和更高的速度運行。

表3 不同算法的仿真性能對比

4 結 論

本文提出的一種新技術——免歸一化MAP算法，通過簡化狀態信息歸一化過程來加速MAP譯碼器的狀態信息更新，可以使Turbo譯碼器變得更快、更小。這種歸一化算法可用于實現ASIC或FPGA技術中的Log_MAP和Max-Log-MAP譯碼器。