李莉萍，侯妍妍

(安徽大學(xué) 計(jì)算智能與信號(hào)處理教育部重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230039)

0 引言

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

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

1 極化碼基本原理

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

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

xN1=uN1GN，

(1)

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

(2)

(3)

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

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

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

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

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

(4)

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

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

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

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

而此隨機(jī)變量，就是文獻(xiàn)[3]中提出的復(fù)雜度為O(NlogN)的串行抵消譯碼算法(Successive Cancellation, SC)計(jì)算的判決值。因此，用一個(gè)SC譯碼器，可以用蒙特卡洛仿真的方式，預(yù)測(cè)出各比特信道的巴氏參數(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]方法使用低密度奇偶校驗(yàn)碼(Low Density Parity Check, LDPC)中的密度進(jìn)化方法，對(duì)極化碼因子圖中的節(jié)點(diǎn)，遞歸計(jì)算其對(duì)數(shù)似然比(Log Likelihood Ratio, LLR)的密度函數(shù)。在獲得每個(gè)根節(jié)點(diǎn)(對(duì)應(yīng)于相應(yīng)的比特信道)密度函數(shù)后，可計(jì)算出每個(gè)比特信道對(duì)應(yīng)的錯(cuò)誤概率。那么，極化碼的構(gòu)造可以通過(guò)選擇錯(cuò)誤概率之和最小的K=NR個(gè)比特信道作為信息位集合A。

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

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

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

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

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

(5)

(6)

(7)

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

3.3 Tal-Vardy構(gòu)造

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

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

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

在Tal-Vardy構(gòu)造中，因每一級(jí)輸出符號(hào)個(gè)數(shù)為μ，最終的比特信道輸出符號(hào)個(gè)數(shù)也是μ，比如μ=256。對(duì)于輸出符號(hào)一定的比特信道，可以直接算出錯(cuò)誤概率，選擇錯(cuò)誤概率之和最小的K個(gè)比特信道構(gòu)成信息位集合。Tal-Vardy構(gòu)造復(fù)雜度可控，給定輸出符號(hào)個(gè)數(shù)μ，其復(fù)雜度為O(Nμ2log2μ)，且適合任何B-DMC信道。對(duì)Tal-Vardy算法，文獻(xiàn)[13]進(jìn)行了推廣，對(duì)原始的N個(gè)相同的底層信道W，推廣為N個(gè)任意的底層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]被提出。對(duì)于比特信道i，對(duì)應(yīng)的極化重量定義為：

(8)

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

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

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

3.6 極化譜構(gòu)造

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

(9)

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

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

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

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

4 結(jié)束語(yǔ)

本文指出了極化碼編碼構(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)域，比如，除了目前已知的兩個(gè)部分序，是否還存在其他類(lèi)型的部分序？除了SC譯碼，其他譯碼方式下(比如SCL和BP譯碼)的極化碼構(gòu)造，理論上的支持仍然未知，目前只能通過(guò)極化譜構(gòu)造或者人工智能的方式進(jìn)行搜索。極化碼的構(gòu)造理論與技術(shù)實(shí)現(xiàn)，需要更多的突破。