Polar Code(18)比特信道的选择

前言


本文源于《Polar Code(6)SC译码算法》评论区的讨论,受到启发后重新梳理了关于巴氏参数法、高斯近似、degign-snr的认识。

极化码构造原则


Arikan在论文[1]指出极化码构造原则:

Polar code construction rule. To construct an $\left( N,K \right)$ polar code for a B-DMC $W$, we select $A$ as the subset of indices $A\subset \left\{ 1,…,N \right\}$ such that $\left| A \right|=K$ and for each $i\in A$, the value $Z\left( W_{N}^{\left( i \right)} \right)$ is among the smallest $K$ values in the set $\left\{ Z\left( W_{N}^{\left( i \right)} \right):j=1,…,N \right\}$. The choice of the frozen vector $f_{1}^{\left| { {A}^{c}} \right|}$ is unspecified; any choice $\left( A,f_{1}^{\left| { {A}^{c}} \right|} \right)$ defines a polar code.

巴氏参数$Z\left( W \right)$,对任意B-DMC $W$ 定义为:

$Z\left( W \right)$与信道容量$I\left( W_{N}^{\left( i \right)} \right)$成反比,$I\left( W_{N}^{\left( i \right)} \right)$越大,$Z\left( W_{N}^{\left( i \right)} \right)$越小。信道极化的特性是,一部分子信道的容量趋于1,一部分子信道的容量趋于0。构造极化码时自然要选择容量较大的子信道来放置信息比特,也就是选择$Z\left( W_{N}^{\left( i \right)} \right)$最小的$K$个子信道。这就是Arikan定义的极化码构造原则。但问题是巴氏参数如何计算?

巴氏参数的计算


在B-DMC $W$ 下,有结论:

当且仅当$W$是BEC时,式(2)等号成立。

在BEC下,信道转移概率$W_{N}^{\left( i \right)}$可由BEC的删除概率得到:

递归初始值为$\varepsilon _{1}^{\left( 1 \right)}=\varepsilon $。

注意此时信道条件已经由B-DMC缩小到BEC。$Z\left( W_{N}^{\left( i \right)} \right)$由$W_{N}^{\left( i \right)}$得到,而$W_{N}^{\left( i \right)}$由$\varepsilon $得到。那么$\varepsilon $从何而来?答案是自己给定。这和实际不相符啊,在实际的信道编码中怎么自己给定?这个问题先存疑,先叙述后面的内容。

只有在BEC时,才能按照式(1)求解巴氏参数。不是BEC的情况下,式(2)是不等式,没办法精确求解。这就是为什么说巴氏参数法不适用于非BEC信道。但此路不通,可以绕着走。

巴氏参数界


观察不等式(2),$Z\left( W_{2N}^{\left( 2i-1 \right)} \right)$的上界是$2Z\left( W_{N}^{\left( i \right)} \right)-Z{ {\left( W_{N}^{\left( i \right)} \right)}^{2}}$,只有当BEC信道时达到上界。换句话说,式(2~3)表达的是巴氏参数界。式(1~5)是按正向思维的推导,得出了巴氏参数界。下面就是逆向思维的应用了。巴氏参数界有如此良好的特性,这正是我们所需要的。

不用搭梯子,直接空降。直接利用巴氏参数界的结论,是对巴氏参数计算的一种简化,跳出了BEC的限制条件,让它适用于更广泛的信道。这就是论文[2]关于PCC-0所说的:

A pair of upper bounds on the Bhattacharyya parameters of bit-channels evolve as simply as $\left\{ z,z \right\}\to \left\{ 2z-{ {z}^{2}},{ {z}^{2}} \right\}$ at each polarizing transform $F$. Due to its simplicity, this construction has been widely used, and produced good polar codes.

看来重要的是利用这个结论,使计算得到简化。否则,按正向思维从式(1)到式(5),对于其他信道而言,计算不等式将是非常麻烦的。

有文献说“巴氏参数”只适用于BEC信道,这是对的。脱离了BEC,等号就是不能成立,就是不能计算。正向思维受阻。

有文献说“巴氏参数界”适用于BWAGN信道,这也是对的。直接利用结论,对巴氏参数的计算进行简化,照样可以计算。简化思维突破限制。

这两种说法都对,但说的不是一回事。后者是前者的演进(evolution)。

高斯近似


比特信道的选择,除了利用巴氏参数,更广泛采用的是高斯近似法。三个递归式:

这里有两个高斯随机变量,一个是原始信道,一个LLR。LLR是所要构造的高斯随机变量,满足方差是均值的2倍。即LLR的方差由其均值m得到,其均值m由式(6~8)递归得到。其中${ {\sigma }^{2}}$是原始信道的方差。那么${ {\sigma }^{2}}$从何而来?答案是自己给定。

前面说巴氏参数计算的时候,$\varepsilon $就需要自己给定;而高斯近似法,${ {\sigma }^{2}}$也需要自己给定。这些参数共同点,都是原始信道的参数。极化码必须要事先假定原始信道参数,在每个瞬间,无线信道参数都可能不同,使用不同原始信道参数得到的极化码也不同。这就是极化码的特点。因此论文[2]说:

An important characteristic of polar codes is their non-universality. That is, different polar codes are generated depending on the specified value of signal-to-noise ratio (SNR), known as the design-SNR. A change in operating SNR is possible in practice but a change in code according to SNR is not desirable. Therefore we wish to construct a polar code at one design-SNR and use it for a range of possible SNRs.

在实际信道中SNR就是变化的,但根据每一种SNR来改变编码则是困难的。我们不希望由于无线信道的不断变化而在编码时做出频繁地调整,因此作者提出在design-SNR的框架下,能够实现“一对多”,即一个design-SNR值能够适用于在一定范围内变化的SNR。这篇论文的目的就是找到最优的design-SNR值。

design-snr


design-snr用于极化码的设计,它和实际信道的SNR不是一回事,而是“一对多”的关系。希望用一个design-snr适配于一定范围的SNR。design-snr有如下定义:

文献[2]在design-snr的框架下,分别对以下4种算法重新进行了定义:

Algorithm PCC-0 : The Bhattacharyya bounds
Algorithm PCC-1 : The Monte-Carlo estimation
Algorithm PCC-2 : The full TPM estimation
Algorithm PCC-3 : The Gaussian approximation

design-snr不是通过计算得来的,而是直接给定。作者指出,最优design-snr是码率、码长和构造算法的函数。得到最优design-snr并不容易,作者是通过搜索算法进行大量的仿真试验,得到了这四种构造算法分别对应的最优design-snr:

PCC-0 @ 0dB
PCC-1 @ 1dB
PCC-2 @ -1.5917dB
PCC-3 @ -1.5917dB

也就是说,design-snr是基于大量仿真的经验值。在各自最优的design-snr下,四种算法的BER性能非常接近,性能都非常好。根据这个经验值,使用不同的构造方法,选择对应的最优design-snr值即可。

这是个“一劳永逸”的办法,一次性完成比特信道的选择,此后无论信道SNR环境如何变化(当然也是在一定范围内变化),都按照这个最优design-snr来安排比特位置。当选用其中一种算法后,决定design-snr的因素就只剩下码率和码长。在实际编码中,可在发送端和接收端都建立一张二维列表,根据不同的码率和码长,选用相应的design-snr。当然这张表格中的值都是基于大量仿真结果的经验值。

把SNR与编码的强相关变成弱相关,直至变成不相关。把极化码的非通用性向着通用性方向改造。这是对极化编码非常重要的简化。

总结


design-snr和高斯近似是一个比较好的极化码构造方案。你只需要考虑把${ {\sigma }^{2}}$构造为design-snr的函数,设定了一个design-snr,就意味着设定了${ {\sigma }^{2}}$。

论文[2]的重要意义在于,design-snr可以与实际信道的SNR解耦。起初极化码的确要考虑实际信道的SNR,但现在有了design-snr,那么在比特信道选择阶段就可以不必过于关注SNR的变化。这张design-snr表格的值只与码率和码长有关,但这些值是基于大量仿真的经验值。论文[2]仅给出了一种码率和码长(R=0.5,N=2048)条件下的最优design-snr。不同的码率和码长,其值应该是有所不同的。

design-snr已经是相当程度上的简化操作,让编码和译码器不必每时每刻都关注SNR,而只关注design-snr。

参考文献


[1] Arikan E. Channel polarization: A method for constructing capacity-achieving codes[C]//Information Theory, 2008. ISIT 2008. IEEE International Symposium on. IEEE, 2008: 1173-1177.
[2] Vangala H, Viterbo E, Hong Y. A comparative study of polar code constructions for the AWGN channel[J]. arXiv preprint arXiv:1501.02473, 2015.

相关链接


Polar Code(6)SC译码算法
Polar Code(8)高斯近似
Polar Code(19)当我们谈论design-snr时我们在谈论什么