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

袁遼， 倪衛(wèi)明

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

?

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

袁遼， 倪衛(wèi)明

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

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

多元極化碼； 塊錯(cuò)誤概率； 碼速率分配； 線性優(yōu)化算法

0 引言

極化碼[1]是由Arikan在信道極化的基礎(chǔ)上首次提出，在保證信道總?cè)萘坎蛔僛2]的情況下，二元離散無記憶信道產(chǎn)生極化現(xiàn)象。信道極化從整體上提高信道傳輸?shù)目煽啃?。而在一些通信條件下，多元極化碼具有更好性能。Erena提出，當(dāng)離散無記憶信道輸入符號(hào)個(gè)數(shù)為質(zhì)數(shù)時(shí)，子信道仍然存在極化現(xiàn)象，與二元極化碼有著類似的構(gòu)造方法，并且能達(dá)到信道容量[3]。Park和Barg則證明了子信道在輸入符號(hào)為q=2r,r=2,3…n的情況下，可以轉(zhuǎn)化為q元信道，對(duì)應(yīng)的信道容量為0,1,2…r比特[4]。更進(jìn)一步的，Sahebi和Pradhan提出，在輸入符號(hào)數(shù)量為合數(shù)時(shí)，可以將合數(shù)分解為質(zhì)數(shù)的表示，進(jìn)而將多元離散無記憶信道在不同階次上極化[5]。

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

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

1 多元極化信道概述

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

bj=1,

(1)

bj=0,

(2)

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

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

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

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 線性規(guī)劃模型

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

(5)

(6)

目標(biāo)函數(shù)即轉(zhuǎn)化為式(7)。

(7)

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

(8)

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

(9)

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

(10)

2.2.2 線性優(yōu)化算法

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

(11)

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

步驟1: 列出價(jià)值系數(shù)矩陣CEij，求出系數(shù)矩陣中任意兩列對(duì)應(yīng)元素之差，將其差額以矩陣的形式列于系數(shù)矩陣右側(cè)。

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

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

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

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

表1 不同子信道CE參數(shù)

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

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

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

2.3 復(fù)雜度分析

算法復(fù)雜度分析中，選取窮舉算法進(jìn)行對(duì)比。選擇窮舉算法進(jìn)行對(duì)比，由于窮舉算法在一定時(shí)間必能得出最優(yōu)解的方案，亦可驗(yàn)證線性優(yōu)化算法的正確性。下面就在給定分配時(shí)，對(duì)兩種算法的復(fù)雜度進(jìn)行簡單的分析。

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

(12)

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

(13)

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

(14)

那么，對(duì)于線性優(yōu)化算法的，其歸一化的復(fù)雜度為式(15)。

(15)

線性優(yōu)化算法的歸一化復(fù)雜度將是碼長n的線性級(jí)的復(fù)雜度。在一般情況下，碼長將是遠(yuǎn)大于子信道容量階次數(shù)量m的，此時(shí)線性優(yōu)化算法將具有復(fù)雜度上的較大優(yōu)勢(shì)。

3 仿真結(jié)果

如圖1所示。

圖1 不同碼率下窮舉算法和線性優(yōu)化算法全局最優(yōu)BLER對(duì)比

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

如圖2所示。

圖2 Binary-like算法和線性優(yōu)化算法全局最優(yōu)BLER對(duì)比

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

4 總結(jié)

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

[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-)，男，寧波人，碩士研究生，研究方向:信道編碼、通信算法優(yōu)化。 倪衛(wèi)明(1970-)，男，上海市人，博士，副教授，研究方向:無線通信和無線網(wǎng)、通信信號(hào)處理、編碼技術(shù)等。

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

TN911.22

A

2017.04.07)