“太極混一”——極化碼原理及5G應用

牛凱

摘要：極化碼是第一種達到信道容量的構造性編碼，已列入5G移動通信的控制信道編碼標準，這是信道編碼領域近年來的重大突破。旨在闡述極化碼的基本原理與5G中的應用。基于信道極化觀點，分析了極化碼蝶形編碼結構與基本的串行抵消譯碼算法，提出了級聯極化編碼結構，并歸納了高性能譯碼算法的特點。另外，還深入分析了5G移動通信中極化碼設計的基本思想，概括了極化碼實用編碼的3種方式：鑿孔、縮短與重復。最后，指出極化信息處理是未來通信系統優化的新型方法。

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

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年，信息論創始人C. E. Shannon在經典文獻[1]中，提出了著名的信道編碼定理。70年來，構造逼近信道容量的編碼是信道編碼理論的中心目標。近20年來，雖然以Turbo與低密度校驗碼（LDPC）為代表的信道編碼具有優越的糾錯性能，但難以從理論上證明這些碼漸近可達信道容量。2009年，土耳其學者E. Ar?kan在文獻[2]中提出了極化碼的設計思想，首次以構造性方法證明信道容量漸近可達。由于在編碼理論方面的杰出貢獻，該論文獲得了2010年電子和電氣工程師協會（IEEE）信息論分會的最佳論文獎，引起了信息論與編碼學術界的極大關注。

極化碼發明近10年來，成為信道編碼領域的熱門研究方向，其理論基礎已經初步建立，人們對極化碼的漸近性能有了深入理解。特別是2016年底，極化碼入選5G移動通信的控制信道編碼候選方案，并最終寫入5G標準[3]，極大推動了極化碼的應用研究。

1 極化碼原理

本節我們將詳細介紹極化碼的基本原理，包括信道極化原理、極化碼構造算法以及極化碼的基本譯碼算法與增強型譯碼算法。

1.1 信道極化與編碼

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

（1）信道極化。

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

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

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

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

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

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

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

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

由于[IW-=0.25

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

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

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

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

（2）極化編碼。

極化碼有2種基本編碼結構，即非系統碼與系統碼。下面我們簡述各自的結構特點。

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

[xN1=uN1GN]， （6）

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

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

（3）實用化極化編碼。

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

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

筆者在文獻[6]中提出了準均勻鑿孔（QUP）適配方案，并進一步在文獻[7]中提出了反向準均勻縮短（RQUS）適配方案。其中，QUP是鑿孔方案，適用于低碼率的情況;RQUS是縮短方案，適用于高碼率的情況。可以證明，QUP與RQUS方案是理論最優的速率適配方案[7]，并且RQUS與文獻[8]中提到的縮短方案等價。

1.2 極化碼構造

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

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

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

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

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

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