Polar Code(20)Beta-expansion

前言


高斯近似(GA)终将成为历史,取而代之的是β-expansion算法。β-expansion与GA性能等价,但复杂度极低。

文献[1]首先揭示了极化码合成信道(synthesized channels)之间的偏序(Partial Order,PO)关系。2016年8月22-26日,在瑞典哥德堡举行的3GPP RAN1 #86次会议上,华为提出了用极化权重(Polarization Weight,PW)来表征AWGN信道下极化码合成信道可靠性的算法[2]。这两项独立的研究似乎不谋而合,促使华为进一步进行理论扩展,追求AWGN信道下极化码的快速构造方法。这就是本博文所要介绍的β-expansion[3]。

文献[3]首先介绍了通用偏序(Universal Partial Order,UPO)的两个重要性质:嵌套和对称。这两个性质是能够采用递归方式构造极化码序列的基础。然后介绍了PW方法,其中β参数需要慎重地选择,其值的大小直接决定了合成信道的顺序。最后用大量的篇幅论证了β的最佳取值为1.1892,即$\beta ={ {2}^{ {1}/{4}\;}}$。无论是渐进性分析,还是数值仿真结果都证实β-expansion方法以低复杂度获得了与GA相同的性能。

预备知识

极化码策略


策略:将信息比特放置于好的信道位置上,将冻结比特放置于差的信道位置上。

关键:如何有效地识别信道位置的好坏并按可靠性排序,是极化码序列构造的关键。

不幸:有效地序列构造仅存在于二进制删除信道(BEC)上。

挑战:5G无线通信系统要求极化码至少能够适用于AWGN信道。

已有方法:高斯近似(GA)。

已有方法缺点:GA的缺点是计算量大,其计算量随着码块长度成比例增加,这对于码长和码率变化的实际系统是不可接受的。不仅如此,对于低延迟的编译码器,也无法实现在线地处理。

通用偏序(UPO)


文献[1]证明了任意二进制输入对称信道下的可靠性测量存在偏序(Partial Order)关系。给定一对合成信道索引$\left( x,y \right)$,它们的可靠性关系取决于下列规则:

Addition:若一个合成信道索引用二进制表示为$\left( a,b,1,c \right)$,那么它的可靠性一定大于合成信道$\left( a,b,0,c \right)$。$’’1\succ 0’’$模式对于1比特或多比特同样适用。例如:

2(0, 1 ,0) $\prec $ 3(0, 1, 1)

9(1, 0, 0, 1) $\prec $ 15(1, 1, 1, 1)

在此例中(1, 0, 0, 1)是合成信道索引9的二进制表示。

Left-swap:若合成信道索引为$\left( a,0,b,1,c \right)$,那么它的可靠性一定小于合成信道$\left( a,1,b,0,c \right)$。$’’0…1\prec 1…0’’$模式可以出现多次,并且0,1不需要彼此相邻。例如:

2(0, 1 ,0) $\prec $ 4(1, 0, 0)

12(0, 1, 1, 0, 0) $\prec $ 24(1, 1, 0, 0, 0)

但这两个规则也不是万能的,对于某些索引对$\left( x,y \right)$则无能为力。Addition、Left-swap或它们的联合都不能确定顺序。例如:

3(0, 1, 1)and 4(1, 0, 0)

7(0, 1, 1, 1)and 12(1, 1, 0, 0)

我们称这些序对于UPO是未知的

UPO的性质


Proposition 1. (嵌套和对称)极化码通用偏序有两个重要性质:

嵌套:码长为$N$的序可在码长为$2N$的序中保持不变。

对称:在码长为$N$的极化码中,$x\prec y$的序和$\left( N-1-x \right)\prec \left( N-1-y \right)$的序对称。

现在讨论UPO的递归结构。定义$\mathbf{UP}{ {\mathbf{O}}_{n}}$为极化码码长$N$的偏序关系$x\prec y$的最小集合,其中$x\prec y$记为$\left\{ x,y \right\}$,$x,y$是$\left[ 0,N-1 \right]$内的整数。关系链$x\prec y\prec z$可以用若干子链表示最临近节点之间的关系,即$x\prec y$和$y\prec z$。例如:

mark

其中$\mathbf{UP}{ {\mathbf{O}}_{n}}$中黑色字体的序来源于它的上一级$\mathbf{UP}{ {\mathbf{O}}_{n-1}}$,对应于Proposition 1的嵌套性质;蓝色字体的序表示与黑色字体的序对称的部分,对应于Proposition 1的对称性质;红色字体的序表示从$\mathbf{UP}{ {\mathbf{O}}_{n-1}}$到$\mathbf{UP}{ {\mathbf{O}}_{n}}$构造过程中出现的新序,这些新出现的序对于UPO来说是未知的

β-expansion:PW算法原理


定义:(PW 算法)考虑一个合成信道索引$x$,其$n$比特二进制扩展为$B=\left( { {b}_{n-1}},…,{ {b}_{1}},{ {b}_{0}} \right)$,最左边为最高有效位。极化权重定义为

其中$\beta $的值需要慎重选择。文献[2]建议$\beta ={ {2}^{ {1}/{4}\;}}$。

在数学上,这种表示方法被称为β-expansion,是十进制扩展的推广,可以看作是对于任意实数$y$的基于β的非整数表示。

例1:令$\beta ={ {2}^{ {1}/{4}\;}}$,极化码码长为$N={ {2}^{n}}=16$。则对于合成信道索引3,即${ {B}_{3}}=\left( 0,0,1,1 \right)$,其β-expansion可计算为

同理,我们可以写出所有合成信道的β-expansion

${ {w}_{x}}$值越大表示合成信道索引$x$的可靠性越高。将$w$按可靠性增序排列,就得到了极化码序列

PW算法的优点是,对合成信道可靠性,提供了一种简洁、低复杂度的全排列算法,并且当码长${ {2}^{n}}$从$n=1$到$n\to +\infty $增加时,能够始终保持一种嵌套性质。

Proposition 2. (嵌套结构)PW算法维持了极化码的嵌套码构造的特性。

Proposition 3. 当$\beta >1$,任何由PW算法得到的序列都遵循极化码的通用偏序(UPO)关系。

Theorem 1. 对于长度为${ {2}^{n}}\left( n\ge 3 \right)$的极化码,存在一个升序集合${ {A}_{n}}=\left\{ { {a}_{0}},{ {a}_{1}},{ {a}_{2}},…,{ {a}_{ { {i}_{\max }}}},+\infty \right\}$,其中${ {a}_{0}}=1$和${ {a}_{1}},{ {a}_{2}},…,{ {a}_{ { {i}_{\max }}}}$都是代数。任意$\beta $落入区间$\left( { {a}_{i}},{ {a}_{i+1}} \right),\forall i\ge 0$内,β-expansion都是唯一的,并且$\beta $落入不同区间可导致不同的顺序序列。此外,集合${ {A}_{n}}$是嵌套的,即${ {A}_{n}}\subset { {A}_{n+1}}$。

Marshall:通过上述Proposition和Theorem,初步地把β-expansion和偏序建立起联系,β-expansion获得了偏序的理论支撑。两者的共性在于,它们都具有嵌套结构。然而$\beta $的值究竟取何值呢?这还需要在具体的用例中去分析和确定。

AWGN信道下的快速构造


现在UPO已经成为极化码序列构造的基础,而极化码序列的构造决定了合成信道的可靠性顺序。但UPO无法做到对整个序列进行全排列,正如在UPO的性质一节所看到的,从$\mathbf{UP}{ {\mathbf{O}}_{n-1}}$到$\mathbf{UP}{ {\mathbf{O}}_{n}}$的构造中,总会有一些新的序是UPO无法判断的。而高斯近似虽然能够对整个序列进行全排序,但由于其高复杂度而不适用于实际应用。为了克服两者的缺点,本节呈现了一种基于UPO和β-expansion的快速构造方法。

Marshall:根据高斯近似的结果,一步一步缩小$\beta $的取值范围,最终的序列不仅满足UPO性质,而且与高斯近似的结果保持一致。换句话说,没有条件,就去创造条件。

解释一下为什么$\beta $的取值会影响序列顺序,如图1所示。

根据定理1,是默认为$\beta >1$,所以今后只考虑$\beta >1$。

当$n=3$时,只有一对未定关系,即$\left( \beta +1,{ {\beta }^{2}} \right)$。为了区分它们的关系,需要多项式方式${ {x}^{2}}-x-1=0$,取其大于1的根为$x=\frac{1+\sqrt{5}}{2}=1.618$,因此升序集合为

当$\beta \in \left( 1,1.618 \right)$时,有$\beta +1>{ {\beta }^{2}}$,则相应的序列为

mark

当$\beta \in \left( 1.618,+\infty \right)$时,有$\beta +1<{ {\beta }^{2}}$,则相应的序列为

mark

这就是定理1所说的,当$\beta $落入${ {A}_{3}}$的任意区间内,β-expansion是唯一的,且导致不同的顺序序列。

当$n=4$时,有4对未定关系,包括之前提到的$\left( \beta +1,{ {\beta }^{2}} \right)$及其两个等价形式,即

为了区分它们的关系,需要求解4个多项式方程

得到

其中1.325,1.466,1.618,1.839分别是多项式方程(2~5)的根。

$\beta $分别落入${ {A}_{4}}$的5段子区间内,将导致5种不同的序,如图2所示。

$\beta $取哪个值?此时高斯近似法开始派上用场。对于码长$N={ {2}^{4}}=16$,$n=4$的极化码,AWGN信道下,高斯近似法对合成信道索引的排序为

将这个序与图2对比,发现当$\beta \in \left( 1,1.325 \right)$时,两个序一致。

由此,我们将$\beta $的取值范围由$n=3$时的$\left( 1,1.618 \right)$缩小到$n=4$时的$\left( 1,1.325 \right)$。

进一步,当$n=5$时,有5对未定关系,即$\left( 28,15 \right),\left( 14,19 \right),\left( 24,13 \right),\left( 24,11 \right),\left( 24,7 \right)$。根据高斯近似的可靠性结果,呈现出与$\beta $的对应关系

对于序$\left\{ 7,24 \right\}$,虽然依赖于SNR的可靠性结果为$7\succ 24$,但大量仿真结果表明$7\prec 24$具有更好的性能。因此选择

此时,$\beta $的取值范围进一步缩小到$\left( 1.179,1.221 \right)$。

对于$n>5$($N>32$)的情况,继续重复这一搜索过程,得到如下表中所示的结果。随着$N$的增加,$\beta $的取值范围不断缩小,并接近于$1.1892\approx { {2}^{ {1}/{4}\;}}$。新的序对小于合成信道总数的20%。

mark

渐进性分析与数值仿真结果


β-expansion可以转化为贝努力卷积(Bernoulli Convolution)概念。贝努力卷积定义了概率测度

假设$B=\left( …,{ {b}_{1}},{ {b}_{0}} \right)$是二进制独立随机序列,满足

测度${ {v}_{\lambda }}$要么是绝对连续的,要么是奇异的。我们需要的正是${ {v}_{\lambda }}$的绝对连续,使得在无限长的序列上能够进行全排列。令$\beta ={ {2}^{ {1}/{k}\;}}$,已经证明当$k=4$时,即$\beta \text{=}1.1892$时,满足绝对连续的必要条件。这与上表中的观察一致。

图3则从仿真结果上表明β-expansion与高斯近似的性能相同。

至此,从理论分析到仿真结果,充分论证了β-expansion算法的可行性和优越性。

参考文献


[1] C. Schurch, “A partial Order for the Synthesized Channels of a Polar Code, ISIT 2016.
[2] 3GPP, R1-167209, Polar code design and rate matching, Huawei, HiSilicon.
[3] β-expansion A Theoretical Framework for Fast and Recursive Construction of Polar Codes, Huawei.