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

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

0 引 言

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

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

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

1 極化碼基本原理

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

1.1 信道極化

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

1.2 極化碼編碼

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

2 極化碼的譯碼

2.1 BP譯碼算法

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

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

式中，s、t∈R。

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

圖1 N=8時(shí)的BP譯碼因子圖

2.2 BPF譯碼算法

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

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

圖2 單BPF譯碼流程圖

(1) 進(jìn)行普通BP譯碼，所有非凍結(jié)比特的先驗(yàn)LLR設(shè)置為0；

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

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

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

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

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

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

3 BER-BPF-ω譯碼算法

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

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

式中，φ(x)為

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

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

(1) 進(jìn)行普通BP譯碼，所有非凍結(jié)比特的先驗(yàn)LLR設(shè)置為0；

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

(3) 對步驟(2)進(jìn)行M(此處M取值為50)次迭代操作，同時(shí)記錄迭代結(jié)束前S(此處S取值20)次的左信息值，并計(jì)算其平均值A(chǔ)VE_S以及方差VAE_S；

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

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

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

4 結(jié)果與分析

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

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

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

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

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

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

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

5 結(jié)束語

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