高維核矩陣極化碼的蒙特卡洛設計方法＊

黃志亮，張施怡，周水紅

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

0　引言

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

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

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

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

本文安排如下。第二節給出文章中所使用的符號和定義，描述了極化碼構造的本質。第三節描述了本文的研究動機。第四節首先描述了如何利用MC構造方法來設計高維核矩陣極化碼，然后給出MC構造方法的性能和復雜度分析。第五節給出仿真結果。第六節總結了文章。

1　準備工作

1.1　符號

對于一個給定的核矩陣Gm，定義為：

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

1.2　極化碼構造

實質上，構造一個k維的極化碼就是找到k個最可靠的位信道。Arikan[1]使用巴氏參數來評價位信道，從所有N個位信道中挑選k個有著最小的位信道作為信息位集合。Tal和Vardy[4]使用更易操作的對位信道進行排序，表示在最大似然判決下第i個位信道的差錯概率。本文采用來評價位信道。

1.3　基于W-表達式的SC譯碼

Korada等人[5]指出一個高維的Gm核矩陣極化碼的直接SC譯碼復雜度為。Huang等人[7]提出一個W-表達式方法簡化遞歸公式fk0和的計算。當m≤16時，基于W-表達式，SC譯碼復雜度降低為。因此，本文采用基于W-表達式的SC譯碼。

2　研究動機

由于GA-DE和Tal-Vardy方法推廣至高維核矩陣的困難，本研究采用MC構造方法來設計高維核矩陣極化碼。下面將詳細介紹推廣GA-DE和Tal-Vardy方法構造高維核矩陣極化碼的難點。

2.1　GA-DE方法

下面用一個簡單的例子闡述GA-DE方法構造的高維核矩陣極化碼會有一定程度失真。

例1（一個G6核矩陣的-表達式）[7]：

2.2　Tal-Vardy方法

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

然而對于高維核矩陣，Tal-Vardy方法是不實際的。Tal-Vardy方法可以分解為兩步：①構造信道；②輸出字母集大小從μ2減少到μ。給定一個Gm核矩陣，遞歸公式⑸變為：

3　蒙特卡洛構造方法

MC構造方法模擬SC譯碼過程：首先，對每一位重復執行SC譯碼；其次，通過大量的仿真，并基于每一位的差錯概率來評估每個位信道；最后，對所有位信道的差錯概率排序，選擇具有最低差錯概率的K個位信道作為信息位集合。

3.1　蒙特卡洛構造方法

重復執行SC譯碼，MC構造方法用每一位的差錯概率評估每個位信道，并選擇具有最低差錯概率的最佳K個位信道作為信息位。令M表示SC譯碼的重復執行次數。算法2描述了MC構造方法。在算法2中，第8步采用基于W-表達式的SC譯碼算法進行譯碼，對于給定的信息位ui，如果其譯碼結果為1，則；否則不變。在MC構造方法中（和是成正比的）用來評價位信道。

3.2　蒙特卡洛構造方法的分析

令：

有：

令：

實際上，[1，Corollary 1]證明了等式⑻。

因此，根據⑺，⑻，⑼，有：

3.3　M的值

根據⑽式，通過使用更大的樣本的M，MC構造方法可以任意準確地估計。然而，一個更大的M意味著更高的復雜度。由于的值趨向于0或1，所以MC構造方法受益于極化現象，并不需要太大。實驗結果表明最優的M不需要太大。

4　仿真

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

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

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

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

仿真結果證明了以下兩點：①對于高維核矩陣，用MC構造的極化碼明顯優于GA-DE方法構造的極化碼;②相比于G2核矩陣極化碼，高維核矩陣極化碼獲得明顯的性能提升。

5　結論

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

參考文獻(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