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

王 璇，杜 軍

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

0 引 言

數(shù)據(jù)傳輸?shù)目煽啃允菬o線通信系統(tǒng)設(shè)計(jì)中一個非常重要的指標(biāo)。Turbo編碼[1]可以獲得逼近香農(nóng)信道容量的譯碼性能。Turbo碼的解碼[2-3]通常以迭代方式完成，一個譯碼器處理過的信息被迭代地饋送到另一個譯碼器，直到達(dá)到一定程度的收斂為止。

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

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

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

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

表1 本文所用符號匯總

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

圖1 譯碼路徑

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

αk和βk-1的計(jì)算方法如下：

(1)

(2)

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

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

(3)

這樣，外信息的計(jì)算方法是

(4)

為了簡化計(jì)算，在大多數(shù)實(shí)現(xiàn)中采用了log_MAP算法[8-9]，將乘法和除法轉(zhuǎn)換為加法和減法。簡化計(jì)算如下：

(5)

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

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

(6)

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

Log_MAP中的歸一化可以修改為

(7)

(8)

在Log_MAP中，外信息是

(9)

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

本文提出的免歸一化算法，目的就是省略在歸一化中尋找最大狀態(tài)信息的過程。因?yàn)樵贛AP譯碼算法中，重要的不是獲得各狀態(tài)信息的絕對值，而是正確計(jì)算和表征各狀態(tài)信息之間大小的相對關(guān)系，即在迭代過程中，具有相對大的狀態(tài)信息比相對小的狀態(tài)信息對于算法的正確收斂貢獻(xiàn)更大。

2 免歸一化MAP算法

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

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

圖2 歸一化圓

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

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

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

maxAk(s)-minAk(s)

(10)

maxBk(s)-minBk(s)

(11)

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

(12)

(13)

圖3 免歸一化處理的實(shí)現(xiàn)框圖

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

則會滿足以下關(guān)系：

(14)

(15)

(16)

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

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

3 性能分析

采用仿真實(shí)驗(yàn)來分析免歸一化算法的性能。仿真中采用了符合LTE(Long Term Evolution)標(biāo)準(zhǔn)的Turbo碼，仿真參數(shù)如表2所列。

表2 仿真參數(shù)

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

(a)數(shù)據(jù)幀長度為1 146

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

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

對于免歸一化算法和傳統(tǒng)算法，采用Synopsys公司的EDA工具來實(shí)現(xiàn)Log_MAP譯碼器，在綜合仿真中進(jìn)行了速度優(yōu)化，表3列出了仿真結(jié)果。從表3中的數(shù)據(jù)發(fā)現(xiàn)，與傳統(tǒng)方法相比，采用免歸一化的Log_MAP算法可以降低36.2%的計(jì)算復(fù)雜度和17.4%的關(guān)鍵路徑延遲。因此，譯碼器可以以比傳統(tǒng)方法更低的復(fù)雜度和更高的速度運(yùn)行。

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

4 結(jié) 論

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