Polar Code（18）比特信道的选择

发表于 2017-08-24 更新于 2017-08-26 分类于 Polar Code 阅读次数：

前言

本文源于《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$ 定义为：

\[\begin{align} Z\left( W \right)=\sum\limits_{y\in Y}{\sqrt{W\left( y|0 \right)W\left( y|1 \right)}} \end{align}\]

$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$ 下，有结论：

\[\begin{align} Z\left( W_{2N}^{\left( 2i-1 \right)} \right)\le 2Z\left( W_{N}^{\left( i \right)} \right)-Z{ {\left( W_{N}^{\left( i \right)} \right)}^{2}} \end{align}\]

\[\begin{align} Z\left( W_{2N}^{\left( 2i \right)} \right)\text{=}Z{ {\left( W_{N}^{\left( i \right)} \right)}^{2}} \end{align}\]

当且仅当$W$是BEC时，式（2）等号成立。

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

\[\begin{align} \varepsilon _{2k}^{\left( 2j-1 \right)}=2\varepsilon _{k}^{\left( j \right)}-{ {\left[ \varepsilon _{k}^{\left( j \right)} \right]}^{2}} \end{align}\]

\[\begin{align} \varepsilon _{2k}^{\left( 2j \right)}\text{=}{ {\left[ \varepsilon _{k}^{\left( j \right)} \right]}^{2}} \end{align}\]

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

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

只有在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）。

高斯近似

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

\[\begin{align} m_{2N}^{\left( 2i\text{-}1 \right)}={ {\varphi }^{-1}}\left( 1-{ {\left[ 1-\varphi \left( m_{N}^{\left( i \right)} \right) \right]}^{2}} \right) \end{align}\]

\[\begin{align} m_{2N}^{\left( 2i \right)}=2m_{N}^{\left( i \right)} \end{align}\]

\[\begin{align} m_{1}^{\left( 1 \right)}={2}/{ { {\sigma }^{2}}}\; \end{align}\]

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

前面说巴氏参数计算的时候，$$就需要自己给定；而高斯近似法，${ {}^{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有如下定义：

\[\begin{align} design-snr=R\cdot \frac{ { {E}_{b}}}{ { {N}_{0}}}=\frac{K}{N}\cdot \frac{ { {E}_{b}}}{ { {N}_{0}}} \end{align}\]

文献[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.

前言