極化碼基于比特翻轉改進的BP譯碼算法

王華華，秦 紅，方澤圣，李平安，陳 博

(重慶郵電大學 通信與信息工程學院，重慶 400065)

0 引 言

由Arikan E提出的極化碼是世界上第一種能夠被嚴格證明香農(nóng)門限可達的編碼方案[1]。同時，Arikan E還提出了兩種針對極化碼的譯碼算法，分別是連續(xù)消除(Successive Cancellation,SC)[1]和置信傳播(Belief Propagation,BP)譯碼算法[2]。

SC譯碼算法及其衍生的算法，如SC翻轉(SC Flip,SCF)[3]和列表SC(SC List,SCL)譯碼算法[4-5]已成為大多數(shù)人的關注點。與之相反的是BP譯碼算法[6]，與串行SC譯碼算法相比，BP譯碼算法通過并行迭代計算，在高吞吐量的應用場景中具有更大的優(yōu)勢。然而，BP譯碼算法的性能不如SCL譯碼算法，因此，在文獻[7]中，作者提出了一個固定的臨界集作為翻轉集的譯碼方法，即BP比特翻轉(Bit-Flip,BF) (BPF)譯碼，通過對數(shù)似然比(Log-Likelihood-Ratios, LLR)的值來選擇錯誤概率更大的比特進行翻轉，由此來達到提升譯碼性能的目的，然而這種算法會因為翻轉集的不準確而導致譯碼性能的提升有限；此外，在文獻[8]中，一種增強型BPF(Enhanced BPF,EBPF)譯碼算法被提出，它通過減少不可靠比特的范圍從而降低譯碼復雜度，并且具有比文獻[7]更高的譯碼性能。

本文提出了一種構建翻轉集的新方法，先用文獻[9-10]中所描述的方差方法基于LLR的BPF(BPF-LLR)譯碼算法來構建粗翻轉集FS，再使用誤碼率(Bit Error Rate,BER)的差值構建精翻轉集FS′，從而實現(xiàn)了BER-BPF譯碼算法(BER-BPF-ω，ω為階數(shù)，單比特時ω=1)。仿真結果表明，新算法降低了譯碼迭代次數(shù)，且性能較文獻[8]和[10]有很大提升。

1 極化碼基本原理

極化碼的設計核心理念便是對信道進行極化處理，在這個過程中使得一部分信道的容量趨近于1，而另一部分信道容量趨近于0。信道極化包含兩個過程：信道聯(lián)合和信道分裂。

1.1 信道極化

信道聯(lián)合：對已知的二進制離散無記憶信道W進行N次復制WN：XN→YN(式中：X和Y分別為輸入和輸出矩陣；N必須為2的整數(shù)次冪。)，并對復制所得信道進行信道組合。其中WN為信道聯(lián)合前的原始信道，信道聯(lián)合后的復合信道為WN，其轉移概率為

1.2 極化碼編碼

極化碼編碼一般有3個過程，一是對極化信道可靠性的估計；二是進行比特混合；三是構造生成矩陣。

2 極化碼的譯碼

2.1 BP譯碼算法

BP譯碼算法相比其他譯碼算法的一個最大特點是可以并行譯碼，由此可提高譯碼速度，其主要通過因子圖的左右循環(huán)迭代來實現(xiàn)譯碼。圖1所示為N=8時的BP譯碼因子圖，其中紅色部分為一個長度為2的極化碼因子圖的運算過程，其計算過程為

式中：L和R分別為從右到左和從左到右的LLR值。g(s,t)為

式中，s、t∈R。

BP與SC譯碼算法的很大區(qū)別就在于BP譯碼算法需要經(jīng)過多次迭代最終得出LLR值。如圖1所示，紅色部分箭頭方向向左迭代算半次迭代，向右迭代也算半次迭代，兩者合二為一便為一次迭代，本文中統(tǒng)一將迭代次數(shù)M設置為200。當?shù)瓿珊髮⒆筮叺腖LR值經(jīng)式(7)得出最終譯碼結果：

圖1 N=8時的BP譯碼因子圖

2.2 BPF譯碼算法

極化碼中的BF譯碼最早被應用于單個BF的SC譯碼，被稱之為SCF譯碼。在單比特譯碼之后，SCF譯碼器將譯碼中出錯率最高的非凍結比特收集并建立了一個大小為T的翻轉集，且最多翻轉次數(shù)為T。在極化碼傳輸過程中，出現(xiàn)譯碼錯誤的主要原因便是差錯傳播，通過翻轉第一個錯誤，能夠提升譯碼的性能。但翻轉集的最大缺陷在于，如果沒有找到第一個錯誤的比特，那么性能幾乎不會有提升，而且大多數(shù)時候，錯誤比特不止一個，所以單BF對譯碼性能提升有限。

BPF譯碼算法的譯碼流程如圖2所示，其基本步驟如下：

圖2 單BPF譯碼流程圖

(1) 進行普通BP譯碼，所有非凍結比特的先驗LLR設置為0；

(2) 若達到最大迭代次數(shù)M，選出不可靠信息比特，構建一個大小為T的翻轉集；

(3) 對LLR信息進行判決，然后進行循環(huán)冗余校驗(Cyclic Redundancy Check， CRC)；

(4) 若CRC正確，則結束譯碼，否則判斷翻轉次數(shù)是否

(5) 將不可靠信息比特ui進行翻轉，將ui<0的LLR設置為-∞，反之則為+∞，即LLRui=(1-2ui)×∞；

(6) 對更新后的LLR值進行BP譯碼，若達到M次迭代則進入第(3)步。

在上述步驟(2)中，如何選擇出不可靠信息比特，構建出正確的翻轉集是最大的難點，在文獻[9]中，作者提出了利用因子圖最左端連續(xù)S個LLR迭代信息的方差來選擇出最不穩(wěn)定的T個點。由于一個數(shù)據(jù)的方差可以顯示出該數(shù)據(jù)的穩(wěn)定性，所以如果某個數(shù)據(jù)的似然比信息方差越大，那么其穩(wěn)定性越差，即為不可靠點。首先將每個比特的連續(xù)S個左信息求均值AVE_S，然后根據(jù)均值求出每個比特的方差VAE_S，計算公式為

3 BER-BPF-ω譯碼算法

文獻[9]中所提算法為了降低最終迭代次數(shù)，對翻轉集的大小進行了約束，使得部分錯誤比特并未進入到翻轉集中，最終性能提升有限。所以本文提出了BER-BPF-ω譯碼算法，它可以更準確地找出不可靠點。相比文獻[9]，本文所提算法迭代次數(shù)有所下降且性能明顯提升。本文所提算法借鑒了文獻[9]中的方差確定翻轉集的方法，但與之不同的是擴大了翻轉集的大小T，同時還使用了一種新的方法來縮小翻轉集的大小再進行多比特翻轉。

假設本文中所有碼字經(jīng)BPSK調制并在高斯信道中傳輸。那么碼字x經(jīng)過調制傳輸后，接收到的y所對應的LLR值為

式中，φ(x)為

因此，我們可以根據(jù)文獻[11]得到碼字通過高斯信道的BER為

式中：PE為經(jīng)高斯信道后得到的估計值；erfc()為互補誤差函數(shù)，與此同時，我們可以得出經(jīng)過BP譯碼后信息比特的BER為

(1) 進行普通BP譯碼，所有非凍結比特的先驗LLR設置為0；

(2) 根據(jù)式(5)從右向左依次更新每一列的左信息，直到最左邊；再反方向更新至最右側；

(3) 對步驟(2)進行M(此處M取值為50)次迭代操作，同時記錄迭代結束前S(此處S取值20)次的左信息值，并計算其平均值AVE_S以及方差VAE_S；

(4) 由式(7)得出譯碼后的ui，并對所得結果做CRC校驗，若未通過，則選取VAE_S最大的T(此處T取值為信息比特的1/2)個值構建粗翻轉集FS；

(5) 將FS的T個比特進行BER計算，再比較PE與PBP的大小，構建精翻轉集FS′={i∈A|PBP(i)>PE(i)}(A為信息比特索引集合)，大小為T′，并以BER差值的降序排列；

(6) 先對精翻轉集FS′做單BPF譯碼，其基本步驟如2.2節(jié)所示，如果最終所有CRC均未通過，則進行多BPF譯碼，將翻轉集FS′中的比特以ω個組合形成新的翻轉集FS″，ω按順序依次遞增，直到CRC校驗通過或者ω>T′。

4 結果與分析

本節(jié)中，在AWGN信道下，采用的調制方式為BPSK，對提出的BER-BPF-ω譯碼算法仿真結果進行分析。

為了驗證本文所提算法的可行性，分別對256和1 024碼長進行了仿真分析，同時也對BP、EBPF和BPF-LLR譯碼算法進行了仿真，用以對比驗證本文所提算法的性能。圖3(a)和3(b)所示分別為對(256,128)和(1 024,512)型極化碼的BER仿真波形，由于本文的重心不在于翻轉集的設定，故根據(jù)文獻[9]將翻轉集大小分別暫定為T=10和20，且CRC校驗類型為CRC-16。

注：SNR為信噪比。 圖3 兩種碼長時幾種譯碼算法的BER

由圖3可知，本文所提算法與BP、EBPF和BPF-LLR算法相比，其BER有明顯提升，例如在BER為10-3時，圖3(a)中分別約有0.495、0.175和0.280 dB的性能提升。同時，由圖3 (b)可知，隨著碼長的增加，譯碼性能有更高的提升，在SNR=3 dB時，本文所提算法就可以達到完全譯碼。

表1所示為對上述幾種算法迭代次數(shù)的統(tǒng)計，其中BP譯碼因為沒有翻轉過程，所以經(jīng)過M次迭代后便會結束譯碼(M=50)。由表1可知，本文所提譯碼算法相比EBPF譯碼算法減少了約10%的迭代次數(shù)，相比BPF-LLR譯碼算法減少了約25%的迭代次數(shù)，由此可知，本文所提譯碼算法在迭代次數(shù)上有所降低。

表1 碼長為256和1 024時不同SNR下的總迭代次數(shù)

通過對本文所提算法進行BER和復雜度的分析可知，本文所提算法優(yōu)于現(xiàn)行的BPF譯碼算法，雖然復雜度降低不是特別明顯，但其性能有很大提升。

5 結束語

本文所提BPF譯碼算法主要在于翻轉集的構建，提出了粗翻轉集和精翻轉集的概念，通過數(shù)據(jù)的方差可以判斷數(shù)據(jù)穩(wěn)定性的特點來構建粗翻轉集，再通過高斯信道后的BER與譯碼后的BER差值比較來構建精翻轉集。在仿真分析中可以看出，本文所提譯碼算法在性能和復雜度上都有所提升。接下來的研究重點是將該算法通過硬件平臺(如現(xiàn)場可編程門陣列(Field Programmable Gate Array，F(xiàn)PGA))實現(xiàn)。