高維核矩陣極化碼的蒙特卡洛設(shè)計(jì)方法＊

黃志亮，張施怡，周水紅

(浙江師范大學(xué)數(shù)理與信息工程學(xué)院，浙江 金華 321004)

0　引言

由Arikan提出的極化碼，被證明了在連續(xù)消去（SC）譯碼算法下，其可以達(dá)到二進(jìn)制輸入對(duì)稱離散無(wú)記憶信道（B-DMCs）的對(duì)稱容量，并且有著多項(xiàng)式級(jí)數(shù)的編譯碼復(fù)雜度[1]。盡管極化碼的構(gòu)造是明確的，但只有在二進(jìn)制刪除信道（BEC）下的構(gòu)造是有效的[1]。Mori和Tanaka表明在一般信道下，密度進(jìn)化（DE）[2]方法是一種有效構(gòu)造極化碼的工具[3]。基于密度進(jìn)化方法，研究者主要[3-4]提出兩類方法用于原2×2維核矩陣極化碼的構(gòu)造：高斯近似DE（GA-DE）方法[3]和Tal-Vardy方法[4]。GA-DE方法有著線性的復(fù)雜度，并且其構(gòu)造的極化碼有著優(yōu)異的性能。Tal-Vardy方法是一種量化的DE方法[4]。Tal-Vardy方法提供兩種信道升級(jí)和降級(jí)的近似量化方法，原始的位信道夾在這兩種方法構(gòu)造的位信道之間。由于這兩種方法是構(gòu)造出的極化碼是極其接近的[4]，因此Tal-Vardy方法被認(rèn)為是最優(yōu)的極化碼構(gòu)造方法。

構(gòu)造高維核矩陣極化碼最直接的方法就是將GA-DE和Tal-Vardy方法從G2推廣到高維核矩陣。然而，在推廣這兩種方法時(shí)存在一些問(wèn)題。①GA-DE方法：Huang等人[7]提出了一種-表達(dá)式方法用來(lái)獲得任意高維核矩陣在似然比域中SC譯碼算法的簡(jiǎn)化遞歸公式。基于-表達(dá)式，可以利用GA-DE方法構(gòu)造相應(yīng)高維核矩陣極化碼[7]。然而，對(duì)于高維核矩陣極化碼，由于-表達(dá)式中引入了相關(guān)，其違背了高斯假設(shè)（多個(gè)獨(dú)立同分布的隨機(jī)變量相加的分布近似位高斯分布），因此GA-DE方法產(chǎn)生一定的失真。②Tal-Vardy方法：由于單步遞歸位信道輸出集合的元素個(gè)數(shù)，隨著核矩陣的維數(shù)m指數(shù)地增長(zhǎng)，所以直接將Tal-Vardy方法推廣至高維核矩陣極化碼是不實(shí)際的。

另一種用來(lái)構(gòu)造極化碼方法是Arikan在其原始文章中提出的基于蒙特卡洛（MC）的極化碼構(gòu)造方法[1]。然而，后續(xù)僅僅少數(shù)的研究者[8]利用這種方法來(lái)構(gòu)造極化碼。文獻(xiàn)[8]關(guān)于MC構(gòu)造方法設(shè)計(jì)極化碼是針對(duì)G2核矩陣的。本文深入分析了基于MC的極化碼構(gòu)造方法，將其進(jìn)一步推廣至了高維核矩陣極化碼的設(shè)計(jì)中，表明了MC構(gòu)造方法對(duì)于高維核矩陣極化碼也是一種快速而有效的方法。

本文主要有三個(gè)方面的貢獻(xiàn)。首先，分析了MC構(gòu)造方法，從理論上表明了其有效性；第二，對(duì)于高維核矩陣極化碼，在連續(xù)消去（SC）譯碼和列表SC（LSC）下，MC構(gòu)造方法比GA-DE方法有著更優(yōu)的性能；第三，與原G2核矩陣相比，高維核矩陣極化碼獲得相當(dāng)大的性能提升。

本文安排如下。第二節(jié)給出文章中所使用的符號(hào)和定義，描述了極化碼構(gòu)造的本質(zhì)。第三節(jié)描述了本文的研究動(dòng)機(jī)。第四節(jié)首先描述了如何利用MC構(gòu)造方法來(lái)設(shè)計(jì)高維核矩陣極化碼，然后給出MC構(gòu)造方法的性能和復(fù)雜度分析。第五節(jié)給出仿真結(jié)果。第六節(jié)總結(jié)了文章。

1　準(zhǔn)備工作

1.1　符號(hào)

對(duì)于一個(gè)給定的核矩陣Gm，定義為：

對(duì)于SC譯碼，基本的遞歸計(jì)算公式（單步位信道計(jì)算公式）為：

1.2　極化碼構(gòu)造

實(shí)質(zhì)上，構(gòu)造一個(gè)k維的極化碼就是找到k個(gè)最可靠的位信道。Arikan[1]使用巴氏參數(shù)來(lái)評(píng)價(jià)位信道，從所有N個(gè)位信道中挑選k個(gè)有著最小的位信道作為信息位集合。Tal和Vardy[4]使用更易操作的對(duì)位信道進(jìn)行排序，表示在最大似然判決下第i個(gè)位信道的差錯(cuò)概率。本文采用來(lái)評(píng)價(jià)位信道。

1.3　基于W-表達(dá)式的SC譯碼

Korada等人[5]指出一個(gè)高維的Gm核矩陣極化碼的直接SC譯碼復(fù)雜度為。Huang等人[7]提出一個(gè)W-表達(dá)式方法簡(jiǎn)化遞歸公式fk0和的計(jì)算。當(dāng)m≤16時(shí)，基于W-表達(dá)式，SC譯碼復(fù)雜度降低為。因此，本文采用基于W-表達(dá)式的SC譯碼。

2　研究動(dòng)機(jī)

由于GA-DE和Tal-Vardy方法推廣至高維核矩陣的困難，本研究采用MC構(gòu)造方法來(lái)設(shè)計(jì)高維核矩陣極化碼。下面將詳細(xì)介紹推廣GA-DE和Tal-Vardy方法構(gòu)造高維核矩陣極化碼的難點(diǎn)。

2.1　GA-DE方法

下面用一個(gè)簡(jiǎn)單的例子闡述GA-DE方法構(gòu)造的高維核矩陣極化碼會(huì)有一定程度失真。

例1（一個(gè)G6核矩陣的-表達(dá)式）[7]：

2.2　Tal-Vardy方法

不失一般性，考慮G2核矩陣的遞歸信道轉(zhuǎn)化如下：

然而對(duì)于高維核矩陣，Tal-Vardy方法是不實(shí)際的。Tal-Vardy方法可以分解為兩步：①構(gòu)造信道；②輸出字母集大小從μ2減少到μ。給定一個(gè)Gm核矩陣，遞歸公式⑸變?yōu)椋?/p>

3　蒙特卡洛構(gòu)造方法

MC構(gòu)造方法模擬SC譯碼過(guò)程：首先，對(duì)每一位重復(fù)執(zhí)行SC譯碼；其次，通過(guò)大量的仿真，并基于每一位的差錯(cuò)概率來(lái)評(píng)估每個(gè)位信道；最后，對(duì)所有位信道的差錯(cuò)概率排序，選擇具有最低差錯(cuò)概率的K個(gè)位信道作為信息位集合。

3.1　蒙特卡洛構(gòu)造方法

重復(fù)執(zhí)行SC譯碼，MC構(gòu)造方法用每一位的差錯(cuò)概率評(píng)估每個(gè)位信道，并選擇具有最低差錯(cuò)概率的最佳K個(gè)位信道作為信息位。令M表示SC譯碼的重復(fù)執(zhí)行次數(shù)。算法2描述了MC構(gòu)造方法。在算法2中，第8步采用基于W-表達(dá)式的SC譯碼算法進(jìn)行譯碼，對(duì)于給定的信息位ui，如果其譯碼結(jié)果為1，則；否則不變。在MC構(gòu)造方法中（和是成正比的）用來(lái)評(píng)價(jià)位信道。

3.2　蒙特卡洛構(gòu)造方法的分析

令：

有：

令：

實(shí)際上，[1，Corollary 1]證明了等式⑻。

因此，根據(jù)⑺，⑻，⑼，有：

3.3　M的值

根據(jù)⑽式，通過(guò)使用更大的樣本的M，MC構(gòu)造方法可以任意準(zhǔn)確地估計(jì)。然而，一個(gè)更大的M意味著更高的復(fù)雜度。由于的值趨向于0或1，所以MC構(gòu)造方法受益于極化現(xiàn)象，并不需要太大。實(shí)驗(yàn)結(jié)果表明最優(yōu)的M不需要太大。

4　仿真

考慮二進(jìn)制相移鍵控（BPSK）調(diào)制和一個(gè)加性高斯白噪聲（AWGN）信道。特別的，二進(jìn)制碼字x=(x0,…,xN-1)基于sn=1-2xn映射到一個(gè)傳輸序列s=(s0,…，sN-1)。在接收端，獲得接收向量y=(y0,…,yN-1)，其中yn=sn+zn，z=(z0,…，zN-1)是獨(dú)立同分布隨機(jī)變量，它們都滿足均值為0和方差為N0/2的高斯分布。

圖2　MC構(gòu)造方法和Tal-Vardy方法構(gòu)造的極化碼在LSC譯碼下的FER

圖3　MC構(gòu)造方法和Tal-Vardy方法構(gòu)造的極化碼在LSC譯碼下的FER

圖2表明在SC和LSC譯碼下，用MC方法構(gòu)造的極化碼明顯優(yōu)于GA-DE方法構(gòu)造的極化碼，也表明在SC譯碼（L=1）下，相比于極化碼，用MC構(gòu)造方法構(gòu)造的極化碼獲得相當(dāng)大的性能提升。所有的碼在SNR=2.0dB構(gòu)造。圖3表明在SC和LSC譯碼下，相比于Tal-Vardy方法構(gòu)造的極化碼，MC方法構(gòu)造的極化碼有著明顯的性能提升。

仿真結(jié)果證明了以下兩點(diǎn)：①對(duì)于高維核矩陣，用MC構(gòu)造的極化碼明顯優(yōu)于GA-DE方法構(gòu)造的極化碼;②相比于G2核矩陣極化碼，高維核矩陣極化碼獲得明顯的性能提升。

5　結(jié)論

為了有效地構(gòu)造高維核矩陣的極化碼，提出一個(gè)基于蒙特卡洛方法的極化碼構(gòu)造方。本文從理論上分析了蒙特卡洛方法計(jì)算的位信道差錯(cuò)概率是實(shí)際差錯(cuò)概率的準(zhǔn)確估計(jì)。仿真結(jié)果表明：①對(duì)高維核矩陣極化碼，MC構(gòu)造方法明顯優(yōu)于GA-DE方法；②相比于G2核矩陣極化碼，MC構(gòu)造方法構(gòu)造的高維核矩陣極化碼獲得明顯的性能提升。因此，本文研究表明MC構(gòu)造方法是一個(gè)有效的高維核矩陣極化碼構(gòu)造方法。

參考文獻(xiàn)(References):

[1]Arikan E.Channel Polarization:A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input MemorylessChannels[J].IEEETransactions on Information Theory,2009.55(7):3051-3073

[2]Mori R and Tanaka T.Performance of polar codes with the construction using density evolution[J].IEEE Communications Letters,2009.13(7):519-521

[3]Trifonov P.Efficient Design and Decoding of Polar Codes[J].IEEETransactions onCommunications,2012.60(11):3221-3227

[4]Tal I and Vardy A.How to Construct Polar Codes[J].IEEE Transactions onInformation Theory,2013.59(10):6562-6582

[5]Korada S B, ?a?oglu E,and Urbanke R.Polar Codes:Characterization ofExponent,Bounds,and Constructions[J].IEEETransactions onInformation Theory,2010.56(12):6253-6264

[6]Lin H P,Lin S,Abdel-Ghaffar K A S.Linear and NonlinearBinaryKernelsofPolarCodesofSmall DimensionsWithMaximumExponents[J].IEEE Transactions on Information Theory,2015.61(10):5253-5270

[7]Huang Z,Zhang S,Zhang F,Duan C,and Chen M.On the Successive Cancellation Decoding of Polar Codes with ArbitraryLinearBinaryKernels[J].CornellUniversity Library,http://arxiv.org/abs/1701.03264,accessed Dec.3.2017.

[8]Wu D,Li Y,and Sun Y.Construction and Block Error Rate Analysis of Polar Codes Over AWGN Channel Based onGaussianApproximation[J].IEEECommunications Letters,2014.18(7):1099-1102