“太極混一”——極化碼原理及5G應(yīng)用

牛凱

摘要：極化碼是第一種達(dá)到信道容量的構(gòu)造性編碼，已列入5G移動(dòng)通信的控制信道編碼標(biāo)準(zhǔn)，這是信道編碼領(lǐng)域近年來的重大突破。旨在闡述極化碼的基本原理與5G中的應(yīng)用?；谛诺罉O化觀點(diǎn)，分析了極化碼蝶形編碼結(jié)構(gòu)與基本的串行抵消譯碼算法，提出了級(jí)聯(lián)極化編碼結(jié)構(gòu)，并歸納了高性能譯碼算法的特點(diǎn)。另外，還深入分析了5G移動(dòng)通信中極化碼設(shè)計(jì)的基本思想，概括了極化碼實(shí)用編碼的3種方式：鑿孔、縮短與重復(fù)。最后，指出極化信息處理是未來通信系統(tǒng)優(yōu)化的新型方法。

關(guān)鍵詞：極化碼;信道極化;串行抵消譯碼;串行抵消列表譯碼;串行抵消堆棧譯碼;極化信息處理

Abstract： Polar code is the first error control code achieving the channel capacity and has been accepted as the coding scheme of the control channels of the 5G wireless communication systems， which is the great breakthrough of the channel coding field in recent years. In this paper， the primary principle of the polar code and the application in 5G systems are surveyed. First， based on the viewpoint of channel polarization， the butter-fly structure of polar coding and successive cancellation decoding are analyzed. Then， the concatenated polar code is proposed and the characteristics of high-performance decoding algorithms are summarized. Furthermore， the design of polar codes in 5G systems is addressed and three practical coding schemes of polar codes are overviewed， which is puncturing， shortening and repetition. In the end， it is pointed out that polar coded information processing will become the new diagram of the communication system optimization in the future.

Key words： polar code; channel polarization; successive cancellation decoding; successive cancellation list decoding; successive cancellation stack decoding; polar coded information processing

1948年，信息論創(chuàng)始人C. E. Shannon在經(jīng)典文獻(xiàn)[1]中，提出了著名的信道編碼定理。70年來，構(gòu)造逼近信道容量的編碼是信道編碼理論的中心目標(biāo)。近20年來，雖然以Turbo與低密度校驗(yàn)碼（LDPC）為代表的信道編碼具有優(yōu)越的糾錯(cuò)性能，但難以從理論上證明這些碼漸近可達(dá)信道容量。2009年，土耳其學(xué)者E. Ar?kan在文獻(xiàn)[2]中提出了極化碼的設(shè)計(jì)思想，首次以構(gòu)造性方法證明信道容量漸近可達(dá)。由于在編碼理論方面的杰出貢獻(xiàn)，該論文獲得了2010年電子和電氣工程師協(xié)會(huì)（IEEE）信息論分會(huì)的最佳論文獎(jiǎng)，引起了信息論與編碼學(xué)術(shù)界的極大關(guān)注。

極化碼發(fā)明近10年來，成為信道編碼領(lǐng)域的熱門研究方向，其理論基礎(chǔ)已經(jīng)初步建立，人們對(duì)極化碼的漸近性能有了深入理解。特別是2016年底，極化碼入選5G移動(dòng)通信的控制信道編碼候選方案，并最終寫入5G標(biāo)準(zhǔn)[3]，極大推動(dòng)了極化碼的應(yīng)用研究。

1 極化碼原理

本節(jié)我們將詳細(xì)介紹極化碼的基本原理，包括信道極化原理、極化碼構(gòu)造算法以及極化碼的基本譯碼算法與增強(qiáng)型譯碼算法。

1.1 信道極化與編碼

極化碼的構(gòu)造依賴于信道極化現(xiàn)象，我們首先介紹信道極化的基本原理，然后概述極化碼的編碼過程。

（1）信道極化。

所謂信道極化，最早由E.Ar?kan引入[2]，是指將1組可靠性相同的二進(jìn)制對(duì)稱輸入離散無記憶信道（B-DMC）采用遞推編碼的方法，變換為1組有相關(guān)性的、可靠性各不相同的極化子信道的過程，隨著碼長(zhǎng)（即信道數(shù)目）的增加，這些子信道呈現(xiàn)兩極分化現(xiàn)象。圖1給出了二元?jiǎng)h余信道（BEC）的信道極化演進(jìn)示例。

令B-DMC信道轉(zhuǎn)移概率為[Wyx]，則信道互信息與可靠性度量（Bhattacharyya參數(shù)，簡(jiǎn)稱巴氏參數(shù)）定義如公式（1）：

[ZW=y∈YWy0Wy1]。 ?（2）

圖1 a）給出了刪余率為0.5的BEC信道的映射關(guān)系[W：X∈0，1→Y]，其信道互信息為[IW=0.5]，巴氏參數(shù)[ZW=0.5]。

圖1 b）是2信道極化過程，[u1，u2∈0，1]是輸入信道的兩比特，[x1，x2∈0，1]是經(jīng)過模2加編碼后的兩比特，分別送入信道后得到[y1，y2∈Y]2個(gè)輸出信號(hào)。對(duì)應(yīng)的編碼過程可以表示為：

[x1，x2=u1，u21011=u1，u2F]。 ?（3）

通過矩陣[F]的極化操作，將一對(duì)獨(dú)立信道[W，W]變換為2個(gè)相關(guān)子信道[W-，W+]。其中，[W-：X→Y2]，[W+：X→Y2×X]，其信道輸入輸出關(guān)系分別如圖1 b）中綠線和粉線所示。這2個(gè)子信道的信道互信息與可靠度量滿足公式（4）的關(guān)系：

[IW-≤IW≤IW+ZW-≥ZW≥ZW+]。 ?（4）

由于[IW-=0.25

上述編碼過程可以推廣到4信道極化，如圖1 c）所示。此時(shí)，每2個(gè)[W-]信道極化為[W--]與[W-+]2個(gè)信道，每2個(gè)[W+]信道極化為[W+-]與[W++]2個(gè)信道。這樣原來可靠性相同的4個(gè)獨(dú)立信道變換為可靠性差異更大的4個(gè)極化信道。

信道極化變換可以遞推應(yīng)用到[N=2n]個(gè)信道，給定信源序列[UN1]與接收序列[YN1]，序列互信息可以分解為多個(gè)子信道互信息之和，即滿足公式（5）中的關(guān)系：

其中，[IUi;YN1Ui-11]是第[i]個(gè)極化子信道的互信息，相應(yīng)的信道轉(zhuǎn)移概率為[WiNYN1Ui-11Ui]。這就是信道極化分解原理，其本質(zhì)是通過編碼約束關(guān)系，引入信道相關(guān)性，從而導(dǎo)致各個(gè)子信道的可靠性或容量差異。圖1 d）給出了碼長(zhǎng)[N=20～28]時(shí)，極化子信道互信息的演進(jìn)趨勢(shì)。其中，每個(gè)節(jié)點(diǎn)的上分支表示極化變換后相對(duì)好的信道（紅線標(biāo)注），下分支表示相對(duì)差的信道（藍(lán)線標(biāo)注）。顯然，隨著碼長(zhǎng)增長(zhǎng)，好信道集聚到右上角（互信息趨于1），差信道集聚到右下角（互信息趨于0）。

E. Ar?kan證明了當(dāng)信道數(shù)目充分大時(shí)，極化信道的互信息完全兩極分化為無噪的好信道（互信息趨于1）與完全噪聲的差信道（互信息趨于0），并且好信道占總信道的比例趨于原始B-DMC信道[W]的容量[IW]，而差信道比例趨于[1-IW][2]。

（2）極化編碼。

極化碼有2種基本編碼結(jié)構(gòu)，即非系統(tǒng)碼與系統(tǒng)碼。下面我們簡(jiǎn)述各自的結(jié)構(gòu)特點(diǎn)。

首先，根據(jù)信道極化的遞推過程，可以得到非系統(tǒng)極化碼的編碼結(jié)構(gòu)。令[uN1=u1，u2，...，uN]表示信息比特序列，[xN1=x1，x2，...，xN]表示編碼比特序列，E. Ar?kan證明[2]編碼滿足公式（6）：

[xN1=uN1GN]， （6）

其中，編碼生成矩陣[GN=BNF?n]，[BN]是排序矩陣，完成比特反序操作，[F?n]表示矩陣[F]進(jìn)行[n]次Kronecker積操作。

圖2給出了碼長(zhǎng)[N=8]，碼率[R=0.5]的極化碼編碼器的示例。由圖2可知，對(duì)于非系統(tǒng)極化碼，根據(jù)巴氏參數(shù)選擇可靠性高的[u4，u6，u7，u8]作為信息比特，信息位長(zhǎng)度為4，而可靠性較差的[u1，u2，u3，u5]作為固定比特，取值為0。經(jīng)過3級(jí)蝶形運(yùn)算，可以得到編碼比特序列[x81]。對(duì)于系統(tǒng)極化碼，則需要將信息位承載在[x4，x6，x7，x8]，對(duì)應(yīng)的編碼器左側(cè)輸入（信源側(cè)）比特則通過代數(shù)運(yùn)算[4]確定取值。由于采用蝶形結(jié)構(gòu)編碼，極化碼的編碼復(fù)雜度則可表示為[ONlogN][2]。

（3）實(shí)用化極化編碼。

筆者在文獻(xiàn)[5]中提出了循環(huán)冗余校驗(yàn)（CRC）-Polar級(jí)聯(lián)方案，如圖3所示。由[k]個(gè)信息比特組成的序列首先送入CRC編碼器，級(jí)聯(lián)[m]個(gè)CRC校驗(yàn)比特后送入極化碼編碼器，產(chǎn)生[N]比特碼字。這種級(jí)聯(lián)編碼方案，以CRC編碼作為外碼，極化碼作為內(nèi)碼，具有顯著的性能增益，目前已經(jīng)成為極化碼的主流編碼方案。

由于極化碼原始碼長(zhǎng)限定為2的冪次，即[N=2n]，而實(shí)際通信系統(tǒng)往往要求任意碼長(zhǎng)編碼。為了滿足這一要求，需要設(shè)計(jì)極化碼的速率適配方案，主要包括鑿孔、縮短、重復(fù)3種操作。假定速率適配后的碼長(zhǎng)為[M

筆者在文獻(xiàn)[6]中提出了準(zhǔn)均勻鑿孔（QUP）適配方案，并進(jìn)一步在文獻(xiàn)[7]中提出了反向準(zhǔn)均勻縮短（RQUS）適配方案。其中，QUP是鑿孔方案，適用于低碼率的情況;RQUS是縮短方案，適用于高碼率的情況?？梢宰C明，QUP與RQUS方案是理論最優(yōu)的速率適配方案[7]，并且RQUS與文獻(xiàn)[8]中提到的縮短方案等價(jià)。

1.2 極化碼構(gòu)造

極化碼構(gòu)造算法的目的是精確計(jì)算各個(gè)子信道的互信息或可靠性，然后從大到小排序，選擇其中好的子信道集合承載信息比特;因此，構(gòu)造算法是極化碼編碼的關(guān)鍵。

E. Ar?kan最早提出基于巴氏參數(shù)的構(gòu)造算法[2]。假定初始信道的巴氏參數(shù)為[ZW]，則從[N]擴(kuò)展到[2N]個(gè)極化信道的迭代計(jì)算過程如公式（7）：

[ZW2i-12N=2ZWiN-ZWiN2ZW2i2N=ZWiN2]。（7）

這種構(gòu)造算法復(fù)雜度較低，但只適用于BEC信道，對(duì)于其他信道，例如二元對(duì)稱信道（BSC）、加性白噪聲信道（AWGN）等，該方法并非最優(yōu)。

Mori基于密度進(jìn)化（DE）方法，得到了BSC、AWGN信道下最優(yōu)的子信道選擇準(zhǔn)則[9]，但由于涉及到變量與校驗(yàn)節(jié)點(diǎn)比特LLR概率分布計(jì)算，計(jì)算復(fù)雜度很高，限制了其應(yīng)用。更好的方法是I. Tal與A. Vardy提出的迭代算法[10]，通過引入極化子信道的上下界近似，該方法能以中等復(fù)雜度保證較高的計(jì)算精度，但碼長(zhǎng)很長(zhǎng)時(shí)，其計(jì)算復(fù)雜度也會(huì)變大。

P. Trifonov所提出的高斯近似（GA）算法[11]是目前較流行的構(gòu)造方法。給定AWGN信道的接收信號(hào)模型為[yi=si+ni，i=1，2，…，N]，噪聲功率為[σ2]，則接收比特的LLR[Lyi?N2σ2，4σ2]服從高斯分布。信道極化的LLR均值迭代公式為：