一種帶有交織器的Polar碼串行級聯(lián)算法研究

陸艷銘 方勇

摘 要： Polar碼是較新提出的一種理論上能夠達(dá)到香農(nóng)極限的信道編碼，但其在中短碼字譯碼性能不如LDPC碼。為了讓Polar碼達(dá)到更好的譯碼性能，文中主要采用將Polar碼、塊交織器和LDPC碼進(jìn)行串行級聯(lián)的方法來提高譯碼性能。在高斯信道環(huán)境下對這種級聯(lián)碼的仿真結(jié)果表明，碼長、碼率相同的情況下，這種級聯(lián)碼的譯碼性能優(yōu)于單獨的Polar碼、LDPC碼和不帶有交織器的Polar?LDPC級聯(lián)碼的譯碼性能。

關(guān)鍵詞： Polar碼; LDPC碼; 交織器; 串行級聯(lián); 信道編碼; 譯碼性能

中圖分類號： TN911.2?34 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2018）12?0071?04

Abstract： Polar code is a relative new channel coding that can achieve the Shannon limit theoretically， but its performance is not as good as that of LDPC codes in decoding middle and short codewords. The method of cascading the Polar code， block interleaver and LDPC code serially is adopted in this paper to make the Polar code achieve better decoding performance. The simulation was carried out for the concatenated code in the Gauss channel environment. The results show that the decoding performance of the concatenated code is better than that of the sole Polar code， LDPC code， and Polar?LDPC concatenated code without interleaver when the code length and code rate are the same.

Keywords： Polar code; LDPC code; interleaver; serial cascade; channel coding; decoding performance

0 引 言

1948年，Shannon在“A mathematical theory of communication”中證明了噪聲信道編碼定理，而后，編碼領(lǐng)域的研究人員就一直在努力尋找一種信道容量能夠達(dá)到香農(nóng)極限的編碼方式。但是信道編碼理論直到20世紀(jì)90年代以后才發(fā)展起來，其中研究比較熱門并被應(yīng)用于多個領(lǐng)域的是Turbo碼和低密度校驗碼（Low?Density?Parity?Check Codes，LDPC）。在2008年，Arikan提出信道極化現(xiàn)象，在2009年，提出新的信道編碼方案，也就是基于信道極化現(xiàn)象的Polar碼[1]。雖然Polar碼被證明在二進(jìn)制離散無記憶信道下的對稱容量理論上可以達(dá)到香農(nóng)極限，并且在編譯碼方面較其他的編碼方式有較低的計算復(fù)雜度，但是在中短碼字的譯碼方面與LDPC碼相比，其譯碼性能不夠理想[2]。對于LDPC碼而言，雖然在低信噪比的信道中有著比較低的誤比特率（Bit Error Ratio，BER），但是在高信噪比的信道中會有錯誤平層的出現(xiàn)。于是有研究者就提出將Polar碼與LDPC碼進(jìn)行級聯(lián)[3?7]，以期得到更好的譯碼效果，但其結(jié)果還不夠理想。Polar碼和LDPC碼進(jìn)行級聯(lián)時，已有的方法都是直接將Polar碼和LDPC碼進(jìn)行簡單的串行級聯(lián)，沒有考慮到在編譯碼過程中可能出現(xiàn)的連續(xù)錯誤，而塊交織器恰恰能夠解決這一問題。所以本文主要是在級聯(lián)的基礎(chǔ)上，將塊交織器加入到Polar碼與LDPC碼的級聯(lián)碼中，來提高抗突發(fā)差錯能力，使級聯(lián)碼能夠達(dá)到更好的譯碼性能。

1 基礎(chǔ)背景

1.1 塊交織

在Polar碼與LDPC碼進(jìn)行級聯(lián)時，為了防止信息在編碼傳輸過程中發(fā)生突發(fā)性的連續(xù)錯誤，從而引入了塊交織器。在對信息進(jìn)行交織時，將信息按列寫入一個[t]行[h]列的矩陣。其中[th=N]，[N]表示輸入信源長度，[t]為[N]開平方后取整的值。然后將信息按行讀出，作為交織好的信息輸出。而解交織就是把交織方法按照反方向進(jìn)行，即先按行寫入矩陣，然后按列讀出信息。信息經(jīng)過交織后即使發(fā)生了連續(xù)的錯誤，在解交織時也會變成隨機獨立的差錯。這樣就會使級聯(lián)碼的性能達(dá)到更好。

1.2 LDPC碼

Polar碼的編碼過程其實就是信道組合的過程。已知給定的碼塊長度為：[xN1=uN1GN]，假設(shè)[A]是[{1，2，…，N}]的子集，[Ac]是[A]的補碼，則極化碼的編碼方式為：[xN1=uAGN（A）⊕uAcGN（Ac）]。Polar碼基本的譯碼算法有連續(xù)消除（Successive Cancellation，SC）譯碼算法[1]和置信傳播（Belief Propagation，BP）譯碼算法[7]。而在大多數(shù)文章中都采用了SC譯碼算法，并且學(xué)者們對Polar碼進(jìn)行研究時大多數(shù)也都是基于SC譯碼算法進(jìn)行的[9?10]，所以本文主要采用SC譯碼算法進(jìn)行下面的研究。

2 Polar碼的級聯(lián)方案

由于LDPC碼也是能夠逼近香農(nóng)極限的一種編碼，而且它有著非常好的誤碼性能;所以本文考慮將LDPC碼與Polar碼級聯(lián)成為以Polar碼為外碼，以LDPC碼為內(nèi)碼，中間以塊交織器連接的級聯(lián)碼，即Polar?LDPC級聯(lián)碼。這種級聯(lián)方案既可以使這兩種碼的缺點得到互補，也可以將其優(yōu)點進(jìn)一步強化：LDPC碼雖然對中短碼有著較好的誤碼性能，但是在高信噪比的信道中會有錯誤平層的出現(xiàn)，而Polar碼雖然對中短碼的性能沒有LDPC性能佳，但是不會有錯誤平層的出現(xiàn)。因而這兩種碼結(jié)合而成的Polar?LDPC級聯(lián)碼既有較好的誤碼性能，又不會產(chǎn)生錯誤平層。此外，本級聯(lián)碼又引入了塊交織器，使其具有更好的抗突發(fā)噪聲和抗衰落性能。下面主要介紹Polar?LDPC級聯(lián)碼的具體設(shè)計思路和設(shè)計方案，最后對該級聯(lián)碼的譯碼部分做出了簡單介紹。

2.1 Polar?LDPC級聯(lián)碼的具體設(shè)計方案

Polar?LDPC級聯(lián)碼是以Polar碼作為外碼，LDPC碼為內(nèi)碼，中間以塊交織器連接構(gòu)成的級聯(lián)碼。本文在做研究和仿真時都是以二進(jìn)制的Polar碼和LDPC碼進(jìn)行的。Polar?LDPC級聯(lián)碼的具體結(jié)構(gòu)框圖如圖1所示。

由圖1可知，在信源輸入端將一個長度為[k]的信源輸入后，經(jīng)過Polar編碼器編碼，得到一個長度為[N]的Polar碼碼字;對得到的這個長度為[N]的碼字進(jìn)行塊交織，塊交織的長度單位應(yīng)滿足小于長度[N]，并且[N]能夠被整除。經(jīng)過塊交織后的長度為[N]的編碼作為信源進(jìn)行LDPC編碼，此時，[N]等于[k]，編碼后的信息碼長為[m]。編碼完成以后信息經(jīng)過高斯信道傳輸，信息輸出后首先經(jīng)過LDPC譯碼器進(jìn)行譯碼，譯碼后經(jīng)過解交織器進(jìn)行解交織，解交織后的信息傳輸?shù)絇olar譯碼器進(jìn)行譯碼，譯碼后就完成了整個過程并得到信源的估計值。

Polar?LDPC級聯(lián)碼級聯(lián)過程中具體的編碼級聯(lián)過程如圖2所示。

由圖2可知，級聯(lián)碼在級聯(lián)時由于加入了塊交織器，所以每一個Polar碼的前[t]個比特位就成為了LDPC碼的第一個碼字塊，而Polar碼在接下來的[t]個比特位就成了LDPC碼的第二個碼字塊，以此類推，Polar碼的最后[t]個比特位就成了LDPC碼的末位的碼字塊。由上述可知，Polar碼的碼率[R1=KN]，LDPC碼的碼率[R2=Km]，由于[N=K]，所以Polar?LDPC級聯(lián)碼的碼率為[R12=（kN）*（Km）=km]。

2.2 Polar?LDPC級聯(lián)碼的譯碼方法

在Polar碼與LDPC碼進(jìn)行級聯(lián)時，外碼Polar碼采用的譯碼算法是SC譯碼算法，而內(nèi)碼LDPC碼的譯碼算法采用的是BP譯碼算法。兩次譯碼后就得到了信源的估計值。

具體的級聯(lián)碼譯碼方法步驟如下：

1） 初始化

信源經(jīng)過編碼后，經(jīng)過高斯信道得到一個含有[N]個[yi（i=1，2，…，N）]碼元的信息[Y]。

2） Polar碼譯碼

經(jīng)過初始化后，對得到的信息[Y]進(jìn)行Polar碼譯碼。首個碼元的似然比由式（4）計算得出[L（1）1（yi）]，然后將得到的[L（1）1（yi）]由式（5）計算得出該碼元的估計值[u11]，剩下碼元的估計值[uN1]用式（6）和式（7）進(jìn)行遞歸調(diào)用，每次遞歸調(diào)用后都用式（5）進(jìn)行譯碼判決得出信息[Y]的估計值[Y′]，Polar碼譯碼結(jié)束。

2.3 譯碼時間復(fù)雜度分析

由上文可知，在Polar?LDPC級聯(lián)碼的級聯(lián)方案中，Polar碼采用的是SC譯碼算法，其譯碼方法結(jié)構(gòu)比較簡單，時間復(fù)雜度為[O（Nlog N）]。其中[N]為Polar碼的碼長。LDPC碼采用的是BP譯碼算法，該算法的時間復(fù)雜度為[O（n）]，其中[n]為LDPC碼的碼長。所以當(dāng)[L=N×n]時，Polar?LDPC級聯(lián)碼的譯碼時間復(fù)雜度為[O（Llog L）]。

3 仿真結(jié)果與分析

本節(jié)將利用Matlab平臺對上面提出的帶有交織器的Polar?LDPC級聯(lián)碼進(jìn)行仿真，并對Polar碼、LDPC碼以及沒有加交織器的Polar?LDPC級聯(lián)碼進(jìn)行仿真，對其結(jié)果進(jìn)行對比和分析。仿真的具體參數(shù)設(shè)置如表1所示。

如圖3所示，給出Polar碼、LDPC碼、沒有帶交織器的Polar?LDPC級聯(lián)碼和帶有交織器的Polar?LDPC級聯(lián)碼的性能曲線。其中碼長均為1 024，碼率都為[16]，級聯(lián)碼的外碼Polar碼的碼率為[12]，內(nèi)碼LDPC碼的碼率為[13]。由圖3可知，在相同的參數(shù)下，在信噪比為0～1.6時，LDPC碼的性能均優(yōu)于其他的幾個編碼，但是當(dāng)信噪比增大時，LDPC碼的性能曲線趨平，而其他的幾個編碼曲線則變得更陡峭些。當(dāng)信噪比為0～0.6時，級聯(lián)碼的性能不如Polar碼的性能，但是當(dāng)信噪比大于0.6時，隨著信噪比的增大，帶有交織器的Polar?LDPC級聯(lián)碼的BER下降趨勢更快些。當(dāng)誤碼率為10-4時，帶有交織器的Polar?LDPC級聯(lián)碼與無交織器的Polar?LDPC級聯(lián)碼的譯碼性能相比較，有大約0.25 dB的性能增益;與Polar碼的譯碼性相比較，有大約0.75 dB的性能增益。因此，加入交織器的Polar?LDPC級聯(lián)碼在譯碼時能夠避免更多的錯誤產(chǎn)生，有很好的誤碼性能。

4 結(jié) 語

為了提高Polar碼的譯碼性能，綜合Polar碼和LDPC碼的優(yōu)點，本文主要研究分析了帶有交織器的Polar?LDPC級聯(lián)碼，詳細(xì)介紹了這種級聯(lián)方法的具體方案、譯碼過程，并且對該級聯(lián)碼的時間復(fù)雜度和仿真結(jié)果進(jìn)行了分析。通過仿真結(jié)果可知，在相同的編碼長度、碼率和信道下，這種帶有交織器的Polar?LDPC級聯(lián)碼比Polar碼和不帶有交織器的Polar?LDPC級聯(lián)碼的性能更優(yōu)。

注：本文通訊作者為方勇。

參考文獻(xiàn)

[1] ARIKAN E. Channel polarization： a method for constructing capacity?achieving codes for symmetric binary?input memoryless channels [J]. IEEE transactions on information theory， 2009， 55（7）： 3051?3073.

[2] MENG Ya， LI Liping， HU Yanjun. A novel interleaving scheme for polar codes [C]// Proceedings of 84th IEEE Vehicular Technology Conference. Montreal： IEEE， 2016： 1?5.

[3] ESLAMI A， PISHRO?NIK H. A practical approach to Polar codes [C]// Proceedings of International Symposium on Information Theory. St. Petersburg： IEEE， 2011： 16?20.

[4] ESLAMI A， PISHRO?NIK H. On finite?length performance of Polar codes： stopping sets， error floor， and concatenated design [J]. IEEE transactions on communications， 2013， 61（3）： 919?929.

[5] ZHANG Y， LIU A， GONG C， et al. Polar?LDPC concatenated coding for the AWGN wiretap channel [J]. IEEE communications letters， 2014， 18（10）： 1683?1686.

[6] GUO J， QIN M， F?BREGAS A G I， et al. Enhanced belief propagation decoding of Polar codes through concatenation [C]// Proceedings of IEEE International Symposium on Information Theory. Honolulu： IEEE， 2014： 2987?2991.

[7] ARIKAN E. A performance comparison of Polar codes and Reed?Muller codes [J]. IEEE communications letters， 2008， 12（6）： 447?449.

[8] LIVA G， RYAN W E， CHIANI M. Quasi?cyclic generalized LDPC codes with low error floors [J]. IEEE transactions on communications. 2008， 56（1）： 49?57.

[9] TAL I， VARDY A. List decoding of polar codes [J]. IEEE transactions on information theory， 2012， 61（5）： 2213?2226.

[10] NIU K， CHEN K. Stack decoding of polar codes [J]. Electronics letters， 2012， 48（12）： 695?697.