極化碼編碼理論綜述

李莉萍，侯妍妍

(安徽大學(xué) 計算智能與信號處理教育部重點實驗室，安徽 合肥 230039)

0 引言

當(dāng)前，第五代移動通信(5G)正在被學(xué)術(shù)界、工業(yè)界積極研究，很多國家及地區(qū)亦在進(jìn)行5G服務(wù)的部署；與此同時，世界范圍內(nèi)也開始了對第六代移動通信(6G)的新理論、新技術(shù)的調(diào)查研究[1-2]。在5G通信中，目前已確定使用極化碼(polar code)[3]作為增強(qiáng)移動寬帶場景(eMBB)控制信道編碼方案[4-5]。

本文先對極化碼的編碼原理進(jìn)行簡單介紹，然后重點描述極化碼編碼構(gòu)造方案的研究進(jìn)展，并對各個構(gòu)造方案進(jìn)行介紹，以展示極化碼的編碼構(gòu)造理論與技術(shù)的全面圖景。

1 極化碼基本原理

文獻(xiàn)[3]給出了極化碼的基本理論，本節(jié)介紹文獻(xiàn)[3]中的相關(guān)內(nèi)容，以引出極化碼的編碼構(gòu)造問題。

對于任意碼長N(N=2n，n≥0)，極化碼的編碼可以表示為：

xN1=uN1GN，

(1)

對于任意一個B-DMC信道W:x→y，其中x表示輸入字符集，y表示輸出字符集，則信道轉(zhuǎn)移概率可以表示為W(y|x),x∈x={0,1},y∈y。極化碼編碼后的碼字xN1在N個底層信道W上進(jìn)行傳輸，得到輸出信號yN1，這個過程產(chǎn)生向量信道WN，其轉(zhuǎn)移概率為：

(2)

(3)

在文獻(xiàn)[3]中已證明，當(dāng)N趨于無窮大時，這N個比特信道，一部分是完美的無噪聲信道，另一部分是純噪聲信道，且無噪聲信道所占的比率是底層信道W的信道容量。這個現(xiàn)象就是信道極化的現(xiàn)象，也是極化碼名稱的由來。

圖1 極化碼編碼示意圖(N=8，信息位集合：A={4,6,7,8}，左側(cè)白色節(jié)點表示固定位信息)Fig.1 An encoding example of polar codes

實際碼長N是有限的，中短碼長的極化碼，信道不會充分極化，比特信道中有些信道，其信道質(zhì)量在無噪聲信道與純噪聲信道之間。極化碼的構(gòu)造問題，就是對于給定的底層信道W、碼長N、碼率R，如何確定哪些比特信道質(zhì)量相對較好，也就是要確定信息比特信道集合A，在這些信道上傳輸信息位比特。下面將對極化碼的構(gòu)造問題進(jìn)行闡述，詳細(xì)介紹目前的構(gòu)造算法。

2 極化碼構(gòu)造問題

如上所述，極化碼的構(gòu)造，其實質(zhì)是確定傳輸信息位比特的比特信道集合A，這些信道相對于固定位比特信道，應(yīng)具備更好的信道質(zhì)量。除了比特信道容量，也可以通過巴氏參數(shù)(Bhattacharyya parameter)來衡量比特信道質(zhì)量。巴氏參數(shù)是最大似然估計下，傳輸一次時的錯誤估計概率上限，因此，巴氏參數(shù)值越小，錯誤估計上限越小。極化碼第i個比特信道的巴氏參數(shù)定義為：

(4)

文獻(xiàn)[3]中，作者給出了二進(jìn)制刪除信道(Binary Erasure Channel, BEC)的信道容量及巴氏參數(shù)的遞推公式，依據(jù)遞推公式，可以確定地算出每個比特信道的信道容量或者巴氏參數(shù)，進(jìn)而可以選擇信道容量大(巴氏參數(shù)小)的比特信道作為傳輸信息位的信道，這些信道構(gòu)成了集合A。因此，對于BEC信道，極化碼具有確定的構(gòu)造方法；而對于其他類型的B-DMC信道，沒有確定的公式來進(jìn)行構(gòu)造。

3 編碼構(gòu)造方案

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

極化碼的構(gòu)造，可以通過計算各個比特信道的巴氏參數(shù)，上文提到，由于輸出符號個數(shù)巨大而無法精確計算。文獻(xiàn)[3]提出可以使用近似的方法來計算巴氏參數(shù)，其中一種方法就是使用蒙特卡洛(Monte Carlo)方法來進(jìn)行巴氏參數(shù)的估計。作者證明了巴氏參數(shù)是如下隨機(jī)變量的期望：

而此隨機(jī)變量，就是文獻(xiàn)[3]中提出的復(fù)雜度為O(NlogN)的串行抵消譯碼算法(Successive Cancellation, SC)計算的判決值。因此，用一個SC譯碼器，可以用蒙特卡洛仿真的方式，預(yù)測出各比特信道的巴氏參數(shù)，進(jìn)而進(jìn)行極化碼的構(gòu)造。

3.2 密度進(jìn)化構(gòu)造及高斯近似構(gòu)造

極化碼的編碼與解碼圖，可以等效轉(zhuǎn)換為因子圖(factor graph)[3]。極化碼的密度進(jìn)化(Density Evolution, DE)構(gòu)造[6-7]方法使用低密度奇偶校驗碼(Low Density Parity Check, LDPC)中的密度進(jìn)化方法，對極化碼因子圖中的節(jié)點，遞歸計算其對數(shù)似然比(Log Likelihood Ratio, LLR)的密度函數(shù)。在獲得每個根節(jié)點(對應(yīng)于相應(yīng)的比特信道)密度函數(shù)后，可計算出每個比特信道對應(yīng)的錯誤概率。那么，極化碼的構(gòu)造可以通過選擇錯誤概率之和最小的K=NR個比特信道作為信息位集合A。

在遞歸計算密度函數(shù)過程中，需要計算密度函數(shù)的卷積。在卷積運(yùn)算中，需要合理選擇精度以避免量化誤差對結(jié)果的影響。在文獻(xiàn)[8-9]中，針對加性高斯白噪聲信道(Additive Gaussian Noise Channel，AWGN),作者提出使用高斯近似的方法來降低密度函數(shù)的計算復(fù)雜度。假設(shè)傳輸全零信息位，那么信道接收到的信號以及遞歸計算過程中的中間節(jié)點的LLR，都服從高斯分布，且高斯分布的方差是均值的2倍。所以，在計算過程中，只需要遞歸計算LLR的均值即可。遞歸計算的過程中，基本計算單元如圖2所示。

圖2 LLR遞歸計算基本單元Fig.2 Basic unit of LLR calculation

假設(shè)一個高斯分布的LLR的均值為m, 則此高斯分布是N(m,2m)。在遞歸計算中，用高斯近似可以計算出下一級兩個LLR的均值，分別為：

m1=f1(m),m2=f2(m)；

其中，f1(x)和f2(x)分別為：

(5)

(6)

(7)

通過上述方法，在極化碼的因子圖中進(jìn)行LLR的遞歸計算，即可求出最終每個比特信道的誤碼率。極化碼的構(gòu)造，可以通過選擇誤碼率之和最小的K個信道作為信息位集合。最后需要說明的是，文獻(xiàn)[11]中發(fā)現(xiàn)，式(7)中的兩段近似方案，不能滿足碼長稍大時的精度要求。比如，在碼長N≥214時，兩段的高斯近似方法構(gòu)造結(jié)果誤差較大。因此，在文獻(xiàn)[11]中，提出了改進(jìn)的近似函數(shù)，使得極化碼高斯近似的構(gòu)造，在碼長為N=218時，仍能提供高精度的構(gòu)造結(jié)果。

3.3 Tal-Vardy構(gòu)造

在第2節(jié)的討論中，可以看出極化碼構(gòu)造的難點在于每個比特信道的輸出符號個數(shù)太多，無法精確計算比特信道的信道容量或者巴氏參數(shù)。在文獻(xiàn)[12]中，作者合并每級比特信道輸出符號的個數(shù)，使得最終的比特信道符號是一個固定的值，這樣一來，輸出符號個數(shù)不隨碼長增大而增大，進(jìn)而可以方便計算比特信道的錯誤概率。文獻(xiàn)[12]的作者是Tal和Vardy，因此這個構(gòu)造被稱為Tal-Vardy構(gòu)造。

碼長N=8時，極化碼每一級比特信道的演進(jìn)情況如圖3所示。從最右側(cè)的底層信道W起始，每一級信道的輸出符號個數(shù)，至少都是前一級輸出符號個數(shù)的平方。在文獻(xiàn)[12]中，作者提出兩種方案，每種方案的核心都是限制每個級別比特信道的符號個數(shù)，比如限制最終的輸出符號個數(shù)為μ。限制的方式是通過合并輸出符號，直到輸出符號的個數(shù)是μ為止。以其中一種方案為例，此方案在每次合并輸出符號時，具有一定的質(zhì)量損失，而每次合并的準(zhǔn)則是使得合并前后互信息損失最小。

圖3 每一級比特信道演進(jìn)(N=8)Fig.3 Bit channel transformation in each level(N=8)

在Tal-Vardy構(gòu)造中，因每一級輸出符號個數(shù)為μ，最終的比特信道輸出符號個數(shù)也是μ，比如μ=256。對于輸出符號一定的比特信道，可以直接算出錯誤概率，選擇錯誤概率之和最小的K個比特信道構(gòu)成信息位集合。Tal-Vardy構(gòu)造復(fù)雜度可控，給定輸出符號個數(shù)μ，其復(fù)雜度為O(Nμ2log2μ)，且適合任何B-DMC信道。對Tal-Vardy算法，文獻(xiàn)[13]進(jìn)行了推廣，對原始的N個相同的底層信道W，推廣為N個任意的底層B-DMC信道(可以不同)，使得Tal-Vardy算法能支持極化碼在廣義底層信道條件的構(gòu)造。

3.4 部分序構(gòu)造

部分序(Partial Order, PO)在文獻(xiàn)[7,14]中被提出，在文獻(xiàn)[15-16]中使用部分序進(jìn)行了極化碼的具體構(gòu)造。

3.5 極化重量構(gòu)造

極化重量(Polarization Weight, PW)在文獻(xiàn)[17-19]被提出。對于比特信道i，對應(yīng)的極化重量定義為：

(8)

式(8)在數(shù)學(xué)上稱為β展開，其中β為一個常數(shù)。在文獻(xiàn)[17]中，β的值根據(jù)經(jīng)驗選擇為21/4。對每個比特信道都可以算出其對應(yīng)的極化重量，極化重量越大，表示信道質(zhì)量越好，最終可以選擇極化重量最大的K個信道作為傳輸信息位的比特信道。

用極化重量的方法進(jìn)行信道排序，在計算信道質(zhì)量時，與底層信道類型無關(guān)，可以事先算出給定碼長N的所有比特信道質(zhì)量。并且，極化重量還具有對稱性及嵌套性(nesting)[18]。極化重量的嵌套性，可以用來支持在給定最大碼長N的情況下，任意碼長N'≤N與任意碼率R的組合。以此為基礎(chǔ)，在5G標(biāo)準(zhǔn)中文獻(xiàn)[5]給出的信道序列，是碼長最大為1 024時，比特信道按照質(zhì)量從差到好的排序列表：對任意碼長與碼率，只需從列表中從前到后選擇出固定位的比特信道即可。

利用極化重量對極化碼的構(gòu)造，計算復(fù)雜度低且對任意信道適用，對任意碼長碼率的支持靈活，因而在5G標(biāo)準(zhǔn)中得到了應(yīng)用。需要指出的是，對于具體的某一個底層信道、碼長和碼率，極化重量的構(gòu)造方法不一定會產(chǎn)生最優(yōu)的排序結(jié)果。在實際系統(tǒng)設(shè)計時，需根據(jù)具體場景進(jìn)行合適的選擇。

3.6 極化譜構(gòu)造

極化譜(polarization spectrum)在文獻(xiàn)[20]中被提出，是近期極化碼構(gòu)造方面的新進(jìn)展。在文獻(xiàn)[20]中，對第i個極化信道，定義一個子碼，其生成矩陣是原始生成矩陣第i行至最后一行對應(yīng)的矩陣，那么第i個信道對應(yīng)的極化子碼(polar subcode)，則是編碼序列的第i位是1時，通過子碼編碼矩陣編碼后對應(yīng)的所有碼字。極化譜是極化子碼的重量分布。第i個比特信道的巴氏參數(shù)聯(lián)合界(Union Bhattacharyya Bound, UB)，與極化譜分布相關(guān)，也與底層信道巴氏參數(shù)相關(guān)，具體如下所示：

(9)

重量譜的計算通常比較復(fù)雜且沒有閉合公式，在文獻(xiàn)[20]的工作中，通過對極化子碼的對偶碼的研究，運(yùn)用MacWilliams 等式，作者提出了計算極化譜的遞歸算法，總體復(fù)雜度為O(N3)。構(gòu)造結(jié)果表明，在SC譯碼下，極化譜構(gòu)造方法略差于GA及Tal-Vardy構(gòu)造算法，但是在SC的列表譯碼(SC List Decoding, SCL)時[21-22]，優(yōu)于GA、Tal-Vardy和PW構(gòu)造方法。

3.7 人工智能構(gòu)造

如以上討論，極化碼構(gòu)造計算復(fù)雜且沒有一個統(tǒng)一的公式。并且，前文所述的構(gòu)造方法(除了極化譜)，理論上都是基于SC譯碼進(jìn)行的優(yōu)化，而現(xiàn)有的SCL譯碼以及BP譯碼(Belief Propagation)，沒有針對性的優(yōu)化構(gòu)造。此類問題比較適合人工智能方法的應(yīng)用，典型工作參見文獻(xiàn)[23-24]。

在文獻(xiàn)[23-24]中，針對極化碼的構(gòu)造，作者提出使用遺傳學(xué)習(xí)(genetic learning)的方法進(jìn)行構(gòu)造。構(gòu)造過程中，不提供極化碼構(gòu)造的已知方法，比如前文提到的巴氏參數(shù)、高斯近似及Tal-Vardy構(gòu)造等。遺傳學(xué)習(xí)構(gòu)造的極化碼，通過現(xiàn)有的SC或者SCL譯碼器進(jìn)行譯碼，譯碼的錯誤概率作為遺傳學(xué)習(xí)算法下次構(gòu)造的輸入，這個循環(huán)一直進(jìn)行，直到構(gòu)造出符合性能指標(biāo)的極化碼(或者最大構(gòu)造次數(shù)到達(dá))。通過遺傳學(xué)習(xí)算法構(gòu)造的極化碼，在SCL及BP譯碼下，比現(xiàn)有的構(gòu)造方式具有更好的性能。在文獻(xiàn)[24]中，還對嵌套的極化碼構(gòu)造進(jìn)行了優(yōu)化，以對任意碼長碼率的極化碼進(jìn)行支持。人工智能的構(gòu)造，計算量比較大，可以采用線下構(gòu)造好之后再使用的方式。

4 結(jié)束語

本文指出了極化碼編碼構(gòu)造的難題，進(jìn)而引出極化碼構(gòu)造方面的主要構(gòu)造方法，除了BEC信道的確定構(gòu)造方案，主要介紹了蒙特卡洛構(gòu)造、密度進(jìn)化構(gòu)造、高斯近似構(gòu)造、Tal-Vardy構(gòu)造、部分序構(gòu)造、極化重量構(gòu)造、極化譜構(gòu)造以及基于人工智能的構(gòu)造。極化碼構(gòu)造理論仍然有未知的領(lǐng)域，比如，除了目前已知的兩個部分序，是否還存在其他類型的部分序？除了SC譯碼，其他譯碼方式下(比如SCL和BP譯碼)的極化碼構(gòu)造，理論上的支持仍然未知，目前只能通過極化譜構(gòu)造或者人工智能的方式進(jìn)行搜索。極化碼的構(gòu)造理論與技術(shù)實現(xiàn)，需要更多的突破。