極化碼的原理及分析

［］

1 引言

信道編碼技術是無線通信物理層的最核心的基礎技術之一，它的主要目的是使數字信號進行可靠的傳遞。信道編碼技術通過在發送信息序列上增加額外的校驗比特，并在接收端采用譯碼技術對傳輸過程中產生的差錯進行糾正，從而實現發送信息序列的正確接收。為了實現可靠的信號傳輸，編碼學家在過去的半個多世紀提出多種糾錯碼技術如RS碼、卷積碼，Turbo碼等，并在各種通信系統中取得了廣泛的應用[1]。我們知道LDPC是碼長足夠長時，是逼近香農極限的。香農極限即香農第二定理通俗來說就是，在碼長R不大于信道容量C的情況下，存在一種能夠實現信息的絕對可靠傳輸的編碼方案。而所謂香農限就是同時滿足絕對可靠、R逼近C的理想情況。香農第二定理并沒有告訴我們如何進行信道編碼，但是它指導著我們去尋找更加符合這種理想狀態的編碼方案，從turbo碼到LDPC碼，越來越逼近這一理想，而極化碼的出現，在理論上實現了這一理想。2008年在國際信息論ISIT會議上，Arikan首次提出了信道極化的概念[2]，這種理想的編碼方案使我們能夠在一個噪聲信道中以理論上最小的差錯率和最快的速度進行信息傳輸。極化碼的編碼長度設計都是2的N次方，而目前航天器與地面計算機系統都是32位的比特計算與存儲，所以極化碼的特性也適合應用于未來的衛星領域。Polar碼具有明確而簡單的編碼及譯碼算法。該編碼因為擁有結構簡單，譯碼復雜度低，而被國際移動通信標準化組織3GPP確定為5G eMBB(增強移動寬帶)場景的信道編碼技術方案，其中，Polar碼作為控制信道的編碼方案。本文將對極化碼的原理進行闡述，研究其在二進制信道下碼長，信道索引和信道極化現象的關系，并對連續刪除SC譯碼基于matlab下進行了仿真實現，同時引入LDPC碼中BP譯碼和最小和BP譯碼，將這三種譯碼方式進行了仿真對比。

2 信道極化

2.1 信道的參數與符號

極化碼是基于二進制GF（2）構造的，其中Px表示X的概率分布，Px,y表示聯合概率分布。表示行向量；表示由N個合成信道；表示將分解成N個子信道第i個子信道；信道轉移概率W(y|x)[3-4]。定義在二進制DMC下信道容量和巴氏參數分別為I（W）和Z(W):

I(W)表示無錯誤傳輸的最大信息速率，Z(W)表示信道的可靠性。

2.2 信道的組合

信道組合就是將二進制DMC信道遞歸操作組合起來形成WN,其中N=2n，n>=0。

當n=0時，信道復制一次，有W1=W。當n=1時，信道進行組合得到信道W2，如圖1所示：

圖1 W2的信道組合

當n=2時，信道進行組合得到W4,如圖2所示：

圖2 W4的信道組合

當n=3時，信道進行組合得到W8，如圖3所示：

圖3 W8的信道組合示意圖

以此類推可以得到n=n-1時，組合信道WN,如圖4所示：

圖4 WN的信道組合示意圖

對輸入序列u進行線性變換后可得到編碼序列x，其變換過程可用生成矩陣GN來表示

此時其信道的轉移概率為：

2.3 信道分裂

信道分裂是信道組合的逆過程，將合成信道WN再分解成N個二進制輸入信道，其對應的轉換概率為：

2.4 信道極化

信道極化是信道合并與信道分裂兩種信道操作的結果[4]。在上述兩種操作下，原本相同的N個W信道產生了極化現象，其中一部分信道容量趨于1，另一部分信道容量趨于0。

從圖可以看出當刪除概率為0.5時，隨著編碼長度N的增加，信道極化形象越加明顯，圖中所有點呈中心對稱，當信道索引號很小時，對稱信道容量趨近0；當信道索引號很大時，對稱信道容量趨近于1。

由柱狀統計圖（6）中可以看出，當N比較小時，趨于0或1的個數占總個數比例不高，當N=32768時，信道容量0和1的數目比例都分別占到了大約49%。這就是信道極化現象。

3 極化碼的原理

3.1 極化碼編碼

首先聲明定義Kronecker(克羅內克積)：

圖5 N=64，1024，32768時的信道容量

將式（8）帶入，可得：

3.2 SC譯碼

圖6 信道極化現象的柱狀統計圖

設定第i個信息比特ui對應分裂信道為，通過該信道發出的信息，在接收端宜采用軟判決譯碼，計算對數似然比：

從上面推導過程中可以看出似然值的復雜度為N（1+logN）。

3.3 BP 譯碼

極化碼生成矩陣可以 用因子圖來表示，這樣就可以使用BP譯碼算法對其進行譯碼【6,7,8】。BP譯碼就是通過節點之間相互傳遞信息，每個節點的更新公式如下：

其中g(x,y)=ln((1+xy)/(x+y))，從信源端發出的信息,與信息集和固定比特值選取有關：

最后一層信道端的信息，接收到的信息設置為：

達到最大迭代值時，停止迭代，并做出判決：

由以上譯碼過程可以看出，極化碼的BP譯碼算法作為一種并行的譯碼算法具有不錯的譯碼性能。

3.4 最小和BP譯碼

雖然BP譯碼具有不錯的性能，但在LDPC碼中我們可知其復雜度還是相對較高，因此，我們引入BP譯碼的改進方式，最小和BP譯碼。其譯碼時的節點更新公式依舊如式（15）一樣。只是令其中g(x,y)=sign(x)sign(y)min(|x|,|y|),當y時，sign(y)=0,否則sign(y)=1。其譯碼算法迭代過程如下：

輸入：接收矢量y;

迭代更新：對式15進行迭代更新每個節點先從右向左進行更新，到達最左側后再從左向右進行更新，到達迭代最大值時停止更新。

最小和BP譯碼與BP譯碼方式最大的區別，在于判決處，BP的判決條件是否則。

4 仿真結果分析

圖7 不同碼長下極化碼的性能

在AWNG信道下，選取碼率為0.25，采用SC譯碼方式，分別選取不同碼長的極化碼，在matlab下對其進行仿真，得到圖4.7.其中黑色的為碼長256，綠色為碼長512，紅色為碼長1024，藍色為碼長2048.從圖中可以看出，碼長越長性能越好。隨著SNR的逐漸增加，越加明顯。這是因為碼長越長，有前面信道極化仿真可知，信道極化越加明顯，無躁信道的個數和比例都會顯著提高，所以性能就越加好。

在AWNG信道下，選取碼長為512，采用SC譯碼方式，分別選取不同碼率的極化碼，在matlab下對其進行仿真，得到圖4.8.其中綠色為碼率0.25，黑色為碼率為0.5，紅色為碼率0.75。從圖中可以看出，碼率越小，極化碼的性能就越好，說明編碼效率直接影響碼字的好壞。因為碼率越低，信道編碼對信道信息增加的冗余就越多，使得信息受到的保護就越多，因而性能就越好。所以編碼速率不同時，發送的信息越多性能越差，因為信道極化，其中一部分信道是完美的無噪信道，當發送的信息多于好的信道個數時，就會導致其余部分信息在完全噪聲信道下發送，最終出現這種情況。所以，信息位的選擇很大程度上也與編碼速率有關，碼率越高，有效性越高，但可靠性就低；碼率越低，有效性就低，但信息傳輸可靠性就高。

圖8 不同碼率下極化碼的性能

圖9 不同碼長下極化碼的性能

在AWNG信道下，對極化碼采取不同譯碼方式，將LDPC碼中的BP譯碼和最小和譯碼方式引入，分別對其仿真，得到如圖4.9所示。在SNR約小于3.5時，SC譯碼性能好于兩種BP譯碼方式。當SNR大于3.5時，兩種BP譯碼性能優于SC譯碼。而BP譯碼性能始終優于最小和BP譯碼方式。因為SC譯碼是一種串行譯碼，而BP譯碼方式是一種并行譯碼方式，在碼長較大時，BP性能會優越一些。但BP譯碼一般在硬件上實現比較復雜，所以一般都用最小和BP譯碼來近似，雖然降低了BP復雜度，但譯碼性能卻打了折扣。

5 總結

從代數編碼和概率編碼的角度來說，極化碼具備了兩者各自的特點。首先，只要給定編碼長度，極化碼的編譯碼結構就唯一確定了，而且可以通過生成矩陣的形式完成編碼過程，這一點和代數編碼的常見思維是一致的。其次，極化碼在設計時并沒有考慮最小距離特性，而是利用了信道聯合（Channel Combination）與信道分裂（Channel Splitting）的過程來選擇具體的編碼方案，而且在譯碼時也是采用概率算法，這一點比較符合概率編碼的思想。

SC譯碼算法以LLR為判決準則，對每一個比特進行硬判決，按比特序號從小到大的順序依次判決譯碼。當碼長趨近于無窮時，由于各個分裂信道接近完全極化（其信道容量或者為0或者為1）， 個消息比特都會獲得正確的譯碼結果，可以在理論上使得極化碼達到信道的對稱容量,而且SC譯碼器的復雜度僅為O(NlogN)和碼長呈近似線性的關系。然而，在有限碼長下，由于信道極化并不完全，依然會存在一些消息比特無法被正確譯碼。當前面i-1個消息比特的譯碼中發生錯誤之后，由于SC譯碼器在對后面的消息比特譯碼時需要用到之前的消息比特的估計值，這就會導致較為嚴重的錯誤傳遞。因此，對于有限碼長的極化碼，采用SC譯碼器往往不能達到理想的性能。

為進一步提高有限碼長極化碼的性能，相繼也提出了很多其它譯碼算法，SCL譯碼，CRC輔助SCL譯碼。通過多保留候選路徑篩選來保證譯碼的正確性，但相對SC譯碼，其復雜度會提高很多，消耗更多存儲空間?；诓⑿凶g碼的置信傳播（BP）譯碼，在低時延條件下可以獲得比SC更好的性能。

極化碼想要得到更多應用還要克服高速率通信下的時延和吞吐率問題，這是polar codes應用上最大的問題。