袁辽， 倪卫明

(复旦大学 信息科学与工程学院， 上海 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)