一種多元極化碼速率分配的低復雜度方法

袁遼， 倪衛明

(復旦大學 信息科學與工程學院， 上海 200433)

?

一種多元極化碼速率分配的低復雜度方法

袁遼， 倪衛明

(復旦大學 信息科學與工程學院， 上海 200433)

研究多元離散無記憶信道下速率分配問題。在碼長有限時，極化現象不完全，子信道并沒有完全極化到它的理想信道容量階次。設計子信道速率方案使得其恰好契合不同子信道多樣化的信道容量得以實現。當子信道傳輸信息比特溢出于子信道容量時，錯誤將會發生。對于有限碼長下多元極化信道下的塊錯誤概率(block error rate, BLER)進行線性建模，并提出了一種線性優化算法來實現多元極化碼速率分配。對比窮舉算法碼長指數級的復雜度，線性優化算法復雜度隨碼長線性增長。仿真結果表明低碼長情況下線性優化算法具有和窮舉算法一致的最優BLER。對比二元速率分配方案，線性優化算法對BLER優化有顯著增益。四元刪除信道下的四元極化碼用作例子，給出詳細說明。

多元極化碼； 塊錯誤概率； 碼速率分配； 線性優化算法

0 引言

極化碼[1]是由Arikan在信道極化的基礎上首次提出，在保證信道總容量不變[2]的情況下，二元離散無記憶信道產生極化現象。信道極化從整體上提高信道傳輸的可靠性。而在一些通信條件下，多元極化碼具有更好性能。Erena提出，當離散無記憶信道輸入符號個數為質數時，子信道仍然存在極化現象，與二元極化碼有著類似的構造方法，并且能達到信道容量[3]。Park和Barg則證明了子信道在輸入符號為q=2r,r=2,3…n的情況下，可以轉化為q元信道，對應的信道容量為0,1,2…r比特[4]。更進一步的，Sahebi和Pradhan提出，在輸入符號數量為合數時，可以將合數分解為質數的表示，進而將多元離散無記憶信道在不同階次上極化[5]。

在多元極化碼的有限碼長構造中，面臨兩個問題：各個子信道的錯誤概率的測量，以及碼速率一定情況下的子信道速率分配。本文采用給定子信道信息比特情況下的塊錯誤概率(block error rate, BLER)[6]的參數來描述錯誤概率，著重關注碼速率固定時的子信道速率分配問題的優化求解。

本文將速率分配問題分為兩個部分。第一部分，先把子信道分為m類，每一類子信道分配相同信道容量階次的信息比特，使得滿足總速率要求，稱為速率分類。第二部分，各個子信道分配m類中的速率，使得BLER最小，稱為速率分配。本文的核心工作是將BLER參數進行線性建模，把最小化BLER參數的目標函數，速率分類和子信道速率分配的約束條件描述為標準的線性規劃問題。在線性模型中，本文引入線性優化中的指派問題思想，采用低復雜度的線性優化算法求解分配方案，實現速率最優分配。對比窮舉算法，線性優化算法復雜度優化顯著。仿真結果顯示兩種算法在低碼長的BLER的計算上保持一致。對比二元速率分配算法，線性優化算法對于BLER的性能提升有顯著效果，顯示合適速率分配方案對于通信可靠性的重要意義。

1 多元極化信道概述

以4-ary刪除信道為例描述多進制信道極化現象。4-ary刪除信道的參數λ和ε滿足λ+ε≤1(λ,ε≥0)。任意輸入符號以1-λ-ε的概率正確傳輸。輸入符號0和2傳輸為E1的概率為ε，同樣的，符號3和1傳輸為E2的概率為ε。所有符號傳輸為E3的概率為λ。易知4-ary刪除信道的信道容量為C=2-2λ-ε。則第i個子信道的刪除概率的遞歸公式如式(1)、(2)。

bj=1,

(1)

bj=0,

(2)

其中εb0=ε,λb0=λ,(b0b1,…bj)為i的二進制表示。當碼長為無窮時，子信道的容量將分布在3個信道容量階次上，分別在ε=0和λ=0，以及兩者同時為0取到。則子信道可以分為C1=0，C2=1，C3=2三組理想的信道容量。

下面考慮速率分配問題：考慮碼率為0.5，碼長為4的4-ary極化碼，需要傳輸的信息比特為4。對此，顯然有多種分配方式。一種為選擇2個子信道，其熵為2，即2個子信道使得符號從{0 1 2 3}中等概率傳輸，而剩下2子信道傳輸固定比特。對此，本文將這一種分配方案描述為(2,0,2)，其中第i個參數表示選取的符號數量。那么，(1,2,1)的分配方案顯然也滿足要求。

針對固定碼長和一定的碼率，有多樣的碼速率分配方案，不同的碼速率分配方案有著不同BLER。因此，設計有效算法快速找到適合的碼速率分配方案使得BLER最小具有研究價值。

2 多元極化碼的碼速率分配

2.1 BLER分析

(3)

以4-ary刪除信道為例，其BLER如式(4)。

1-∏k∈C2(1-0.5λk)∏l∈C3(1-0.75λl-0.5εl)

(4)

2.2 碼速率分配算法

2.2.1 線性規劃模型

CEij=-10Log10(pij),i=1,2,…n,j=1,2,…m

(5)

(6)

目標函數即轉化為式(7)。

(7)

顯性約束條件為碼速率K的約束，滿足式(8)。

(8)

隱形條件為每一個子信道有且只能選擇一個Cj：為式(9)。

(9)

則線性規劃模型為式(10)。

(10)

2.2.2 線性優化算法

線性規劃問題求解具有相當的復雜度，考慮將其分成兩部分：第一部分為速率分類，先將碼速率分配到不同的信道容量的Cj上，即先給定K=(K1,K2,…Km)。第二部分為求解給定K情況下的使得BLER最小的碼速率分配方案。顯然，速率分類可以通過簡單的遍歷得到所有的情況，重點是優化選擇BLER并使得BLER到達最優。將問題重新描述如式(11)。

(11)

顯然，碼長n將遠大于子信道容量階次m，線性問題退化為非平衡0-1的指派問題的求解。對此，采用一種差額法進行求解：

步驟1: 列出價值系數矩陣CEij，求出系數矩陣中任意兩列對應元素之差，將其差額以矩陣的形式列于系數矩陣右側。

步驟2: 在差額矩陣中尋找最大元素，用符號標記出來，劃去該元所在行的其他元素。在差額矩陣中將該行所有元素置為-1，保證不參與之后的運算。目的是保證每一個子信道只分配一個Cj。若有幾個元素同為最大，則需在原系數矩陣中查到產生這些最大差額的對應元素，選擇最小元素對應的那個最大差額。

步驟3: 在原系數矩陣中找出產生此最大差額的兩個對應元素，在兩者中選出較小者。當原系數矩陣中某一列選取的元素到達Kj/Cj時，將該列有關的差額矩陣中所有行置為-1。其目的是保證滿足碼速率分配K=(K1,K2,…Km)的要求。

步驟4: 再在差額矩陣中尋找最大元素，其余操作同上，以尋求最優解。

特別地，當Kj中有且只有一個不為0，則全部選取CEij，i=1,2,…n。如表1所示。

表1 不同子信道CE參數

下面以4進制刪除信道的4-ary極化碼為例，取ε=0.4,λ=0.2，詳細描述本文的算法。

選取碼長n=8，碼速率為K=8的情況，給定K的分配方案(3,2,3)為例，描述線性優化算法。

步驟1：在系數矩陣右側列出差額矩陣。步驟2：選取差額矩陣中最大的元素CE13-CE11，并將i=1差額矩陣置為-1，即在之后的最大值尋找中，不在考慮第一行。步驟3：在原系數矩陣中，找到CE11，判第一列選取元素小于3，則進行下一步。步驟4：繼續在差額矩陣中尋找最大值，不斷迭代。顯然，第2循環選取CE21，第3循環選取CE31。此時，第一列選取元素等于3。將差額矩陣中和第一列有關列的全部置為-1，則實際只剩下第三列進行判斷。而后依次選出CE42，CE52，CE63，CE73，CE83，取到最小的目標函數CEij的和為1.818 2。

2.3 復雜度分析

算法復雜度分析中，選取窮舉算法進行對比。選擇窮舉算法進行對比，由于窮舉算法在一定時間必能得出最優解的方案，亦可驗證線性優化算法的正確性。下面就在給定分配時，對兩種算法的復雜度進行簡單的分析。

對于窮舉算法，其基本的步驟是在m容量階次上選取不同CE進行計算目標函數的操作，易得窮舉算法的歸一化復雜度,如式(12)。

(12)

對于本文提出的線性優化算法，首先選取所有列的差額進行減法運算,如式(13)。

(13)

在獲取差額矩陣之后，需要的是遍歷行列選取最值為式(14)。

(14)

那么，對于線性優化算法的，其歸一化的復雜度為式(15)。

(15)

線性優化算法的歸一化復雜度將是碼長n的線性級的復雜度。在一般情況下，碼長將是遠大于子信道容量階次數量m的，此時線性優化算法將具有復雜度上的較大優勢。

3 仿真結果

如圖1所示。

圖1 不同碼率下窮舉算法和線性優化算法全局最優BLER對比

在不同碼率下，4-ary極化碼下窮舉算法和線性優化算法的BLER結果對比。選用4-ary刪除信道參數固定為ε=0.4,λ=0.2，碼長n=16,碼率覆蓋范圍從0.062 5到1。從圖中可以看到，兩條曲線重合，窮舉法和線性優化算法的全局BLER最優解保持一致。

如圖2所示。

圖2 Binary-like算法和線性優化算法全局最優BLER對比

不同碼率下binary-like算法和線性優化算法全局最優BLER對比。同樣的，采用的是4-ary極化碼和4-ary刪除信道的固定參數ε=0.4,λ=0.2。采用碼長為128和256分別進行測試。此處采用binary-like算法與線性優化算法進行對比。具體地說，binary-like算法即將子信道分配為信道容量C3=2的值取到最大值，即K3為K/2的值取整數，K2為K-K3。換言之，將信道盡可能地分配到容量階次最大和最小的子信道上，模仿二元極化碼現象。從圖2中可以看到，線性優化算法的全局最優的BLER對比于binary-like算法具有明顯的增益。這種現象表明在多元極化碼中，合適的碼速率分配對于通信性能的提升具有重要意義。

4 總結

對于多元離散無記憶信道，本文提出了一種針對有限碼長的多元極化碼的速率分配算法。將BLER參數進行線性建模，把最小化BLER參數的目標函數，速率分類和子信道速率分配的約束條件描述為標準的線性規劃問題。該模型是線性優化算法提出的基礎。4-ary的刪除信道下的4-ary極化碼在文中詳細描述算法，并作為仿真模型。仿真結果和分析發現，線性優化算法具有碼長線相關的復雜度，在低碼長的情況下和窮舉算法保持一致BLER。在碼長較長的情況下，線性優化算法對于BLER的優化有顯著增益效果。

[1] Arikan E. Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels[J]. IEEE Transactions on Information Theory, 2008, 55(7):3051-3073.

[2] Arikan E. Channel Combining and Splitting for Cutoff Rate Improvement[J]. IEEE Transactions on Information Theory, 2006, 52(2):628-639.

[4] Park, W., Barg, Polar Codes for Q-Ary Channels, q=2^{r}[J]. IEEE Transactions on Information Theory, 2013, 59(2):955-969.

[5] Aria G. Sahebi, S. Sandeep Pradhan. Multilevel Channel Polarization for Arbitrary Discrete Memoryless Channels[J]. IEEE Transactions on Information Theory, 2013, 59(12): 7839-7857.

[6] Daolong Wu, Ying Li, Yue Sun. Rate assignment for multi-level polarised non-binary polar codes[J]. IET Communications, 2016, 10(10):1151-1155.

Methods for Enhancing Successive Cancellation Decoding of Polar Codes

Yuan Liao, Ni Weiming

(Department of Information Science and Technology， Fudan University， Shanghai 200433, China)

In this paper, we study methods to enhance successive cancellation decoding of polar codes. We propose two improved algorithms, which are two-path decision delay decoding and variable path decision delay decoding with threshold. Conventional successive cancellation decoding is greedy algorithm in code tree, which means that successive cancellation decoding can't correct errors from the former nodes. In this paper, the decision delay decoding is used to provide opportunity to correct previous error for the current node. The proposed two-path and variable path decision delay decoding can improve the decoding performance by increasing the computing nodes and increasing the storage space. The simulation results show that compared to successive cancellation decoding, the two-path decision delay decoding has 1.1dB gain on decoding performance. In addition, variable path decision delay decoding has more gain.

Polar multi-code; Successive cancellation decoding; Decision delay decoding; Two-path decision delay decoding

袁遼(1993-)，男，寧波人，碩士研究生，研究方向:信道編碼、通信算法優化。 倪衛明(1970-)，男，上海市人，博士，副教授，研究方向:無線通信和無線網、通信信號處理、編碼技術等。

1007-757X(2017)07-0062-03

TN911.22

A

2017.04.07)