Polar Code(4)编码之极化信道可靠性估计

前言


由Arikan发明的Polar Code经典编码算法已在《Polar Code(2)编码原理》中阐明,《Polar Code(3)编码实例》则是对前文的举例。在编码实例中,有两个前提假设:

  1. 假设一个二进制删除信道(BEC);
  2. 假设采用计算巴氏参数来评估各分裂子信道的可靠性。

Arikan在讨论信道极化时,针对的是二进制离散无记忆信道(B-DMC),然而在构造极化码时需要计算的巴氏参数\(Z\left( W \right)\)的适用范围是二进制删除信道。BEC是B-DMC的子集。因此在Polar Code编码时只能回落的BEC来进行构造。

当信道不是BEC信道时,比如二元对称信道(BSC)或二进制高斯白噪声信道(BAWGNC),则超出了\(Z\left( W \right)\)的适用范围,各个分裂信道的\(Z\left( W{}_{N}^{\left( i \right)} \right)\)无法精确得到。为了更精确地估计信道极化中各分裂信道的可靠性,Mori等人提出了密度进化(Density Evolution,DE)的构造方法。该方法适用于所有类型的B-DMC。

定义错误概率:对信道\(W\)\(N\)个独立时隙上进行信道极化以后,得到极化信道\(W_{N}^{\left( i \right)}\),其中\(i=1,2,...,N\)。令事件\({ {A}_{i}}\)表示序号为\(i\)的极化信道\(W_{N}^{\left( i \right)}\)所承载的比特经过传输后接收发生错误,即

\[{ {A}_{i}}=\left\{ u_{1}^{N},y_{1}^{N}:W_{N}^{\left( i \right)}\left( y_{1}^{N},u_{1}^{i-1}|{ {u}_{i}} \right)<W_{N}^{\left( i \right)}\left( y_{1}^{N},u_{1}^{i-1}|{ {u}_{i}}\oplus 1 \right) \right\}\]

则极化信道\(W_{N}^{\left( i \right)}\)的错误概率为\(P\left( { {A}_{i}} \right)\)

Marshall:关于事件\({ {A}_{i}}\)的理解详见《Answer-Polar Code-定义错误概率》

密度进化(DE)


类似LDPC码等信道编码,信道极化也可以用Tanner图的结构来表示。下图给出了一个\(N=8\)的例子,图中圆圈表示变量节点,每个变量节点代码一个比特,同时也存储了该比特取值为0或1时的概率;而方框则表示校验节点,表示与之相连的各变量节点比特值的检验和为零。

由于变量节点的比特值仅可能有0或1两种取值,因此,存储与变量节点的消息往往用对数似然比(LLR)值来表示。

\[\begin{equation} L_{N}^{\left( i \right)}\left( y_{1}^{N},\hat{u}_{1}^{i-1} \right)=\ln \left( \frac{W_{N}^{\left( i \right)}\left( y_{1}^{N},\hat{u}_{1}^{i-1}|0 \right)}{W_{N}^{\left( i \right)}\left( y_{1}^{N},\hat{u}_{1}^{i-1}|1 \right)} \right) \end{equation}\]

根据《Polar Code(2)编码原理》中递归式\(W_{N}^{\left( 2i-1 \right)}\left( y_{1}^{N},u_{1}^{2i-2}|{u_{2i-1}} \right)\)与式\(W_{N}^{\left( 2i \right)}\left( y_{1}^{N},u_{1}^{2i-1}|{u_{2i}} \right)\),Tanner图中各个变量节点的LLR值可以递归地计算得到

\[\begin{align} & L_{N}^{\left( 2i-1 \right)}\left( y_{1}^{N},\hat{u}_{1}^{2i-2} \right)=2{\tanh ^{-1}}\left( \tanh \left( \frac{L_{N/{2}\;}^{\left( i \right)}\left( y_{1}^{N/{2}\;},\hat{u}_{1,o}^{2i-2}\oplus \hat{u}_{1,e}^{2i-2} \right)}{2} \right) \right) \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \nonumber \cdot \tanh \left( \frac{L_{N/{2}\;}^{\left( i \right)}\left( y_{N/{2}\;+1}^{N},\hat{u}_{1,e}^{2i-2} \right)}{2} \right) \\ \end{align}\]

\[\begin{align} & L_{N}^{\left( 2i \right)}\left( y_{1}^{N},\hat{u}_{1}^{2i-1} \right)=L_{ {N}/{2}\;}^{\left( i \right)}\left( y_{ {N}/{2}\;+1}^{N},\hat{u}_{1,e}^{2i-2} \right)+{ {\left( -1 \right)}^{ { { {\hat{u}}}_{2i-1}}}} \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \nonumber \cdot L_{ {N}/{2}\;}^{\left( i \right)}\left( y_{1}^{ {N}/{2}\;},\hat{u}_{1,o}^{2i-2}\oplus \hat{u}_{1,e}^{2i-2} \right) \\ \end{align}\]

若最终得到的\(L_{N}^{\left( i \right)}\left( y_{1}^{N},\hat{u}_{1}^{i-1} \right)\ge 0\),则判决为\({\hat{u}_{i}}=0\);否则,判决\({\hat{u}_{i}}=1\)

将某一个变量节点的LLR值视为一个随机变量,用\(\mathbf{a}\left( z \right)\)表示该随机变量的概率密度函数(PDF)。由于信道满足对称性,可以假设发送的比特为全零。从而该变量节点的比特判决值错误的概率为

\[\begin{equation} {P_{e}}=\int_{-\infty }^{0}{\mathbf{a}\left( z \right)}dz \end{equation}\]

在对第\(i\)个信道进行可靠性计算时,如上图中加粗线条所示,以比特\({u_{i}}\)对应的变量节点为根节点,逐层扩展,直至最右侧一列变量节点,构成译码树。

\({\mathbf{a}_{w}}\)表示信道输入到最右侧一列变量节点的LLR值的PDF;用\(\mathbf{a}_{N}^{\left( i \right)}\)表示\(L_{N}^{\left( i \right)}\left( y_{1}^{N},\hat{u}_{1}^{i-1} \right)\)值的PDF。根据密度进化理论以及式(2)和式(3),假设发送序列为全零比特序列,在\(u_{1}^{i-1}\)值已知的条件下,序号为\(i\)的极化信道LLR值可以递归第计算如下

\[\begin{equation} \mathbf{a}_{2N}^{\left( 2i-1 \right)}=\mathbf{a}_{N}^{\left( i \right)}\odot \mathbf{a}_{N}^{\left( i \right)} \end{equation}\]

\[\begin{equation} \mathbf{a}_{2N}^{\left( 2i \right)}=\mathbf{a}_{N}^{\left( i \right)}*\mathbf{a}_{N}^{\left( i \right)} \end{equation}\]

\[\begin{equation} \mathbf{a}_{1}^{\left( 1 \right)}\text{=}{\mathbf{a}_{w}} \end{equation}\]

其中,运算$\(与\)*\(分布表示校验节点与变量节点上的卷积操作。通过概率密度函数\){N}^{( i )}\(与式(4)可以得到各个极化信道\)W{N}^{( i )}\(的可靠性度量\)P( {A_{i}} )$。

高斯近似(GA)


通过密度进化对极化信道\(W_{N}^{\left( i \right)}\)的可靠性度量\(P\left( {A_{i}} \right)\)进行计算,可以适用于任意类型的B-DMC信道。然而,在实际算法实现时,需要维护一个高维的向量以存储(量化后的)概率密度函数\(\mathbf{a}_{N}^{\left( i \right)}\)。为保证计算结果精确,该向量的维度常取到\({10^{6}}\),对如此高维的向量进行式(5)和式(6)的卷积操作,计算复杂度非常高。

在大多数研究场景下,信道编码的传输信道模型均为BAWGNC信道。在BAWGNC信道下,可以将密度进化中的LLR值的概率密度函数用一族方差为均值2倍的高斯分布来近似,从而简化成了对一维的均值的计算,大大降低计算量,这种对DE的简化计算即为高斯近似(Gaussian Approximation,GA)。

对噪声方差为\({\sigma ^{2}}\)的BAWGNC信道,调制方式采用BPSK,若从信道获取的接收信号为\(y\)

\[\begin{equation} y=\left( 1-2x \right)+z \end{equation}\]

其中发送比特\(x\in \left\{ 0,1 \right\}\)\(z\sim N\left( 0,{\sigma ^{2}} \right)\)

假设发送比特为全零序列,则对应的LLR值为

\[\begin{equation} LLR\left( y \right)=\ln \frac{p\left( y|x=0 \right)}{p\left( y|x=1 \right)}=\frac{2}{\sigma ^{2}}y \end{equation}\]

其中\(y\sim N\left( 1,{\sigma ^{2}} \right)\)。因此式(9)中所得的LLR值符合均值为\(2/{\sigma ^{2}}\;\)、方差为\(4/{\sigma ^{2}}\;\)的高斯分布。根据已有的高斯近似理论,若输入的消息\(\mathbf{a}_{N/{2}\;}^{\left( i \right)}\)服从独立的高斯分布,对如式(6)所示的变量节点上的操作,则其输出\(\mathbf{a}_{N}^{\left( i \right)}\)也服从高斯分布;对如式(5)所示的变量节点上的操作,其输出\(\mathbf{a}_{N}^{\left( 2i-1 \right)}\)也非常接近高斯分布。由于高斯分布可以有其均值和方差完全决定,因此在概率密度函数的计算过程中值需要考虑均值和方差,但必需满足密度进化的对称条件。如果用\(f\left( z \right)\)表示LLR的概率密度,则对称条件表示为\(f\left( z \right)\text{=}f\left( -z \right){e^{z}}\)。对于均值为\(m\)、方差为\({\sigma ^{2}}\)的高斯分布,该对称条件可以简化为\({\sigma ^{2}}=2m\)。因此,在高斯近似中,仅需要考虑一维的变量,即均值\(m\)。设\(\mathbf{a}_{N}^{\left( i \right)}\)可以用\(N\left( m_{N}^{\left( i \right)},2m_{N}^{\left( i \right)} \right)\)表示,则式(5)、式(6)和式(7)中所示的LLR计算过程可以用高斯近似成为

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

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

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

其中函数

mark

\[\begin{equation} \varphi \left( x \right)=\left\{ \begin{matrix} 1-\frac{1}{\sqrt{4\pi x}}\int_{-\infty }^{\infty }{\tanh \frac{u}{2}\cdot \exp \left( -\frac{ { {\left( u-x \right)}^{2}}}{4x} \right)du,x>0} \\ 1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ,x=0 \\ \end{matrix} \right. \end{equation}\]

注:文献[2]中的公式有误。

\(\varphi \left( x \right)\)\(\left[ 0,\infty \right)\)上连续单调递减,\(\varphi \left( 0 \right)\text{=}1\)\(\varphi \left( \infty \right)\text{=0}\),其反函数用\({ {\varphi }^{-1}}\left( x \right)\)表示。一般情况下,函数\(\varphi \left( x \right)\)可以使用如下的近似形式计算

mark

\[\begin{equation} \varphi \left( x \right)=\left\{ \begin{matrix} \sqrt{\frac{\pi }{x}}\left( 1-\frac{10}{7x} \right)\exp \left( -\frac{x}{4} \right),x\ge 10 \\ \exp \left( -0.4527{ {x}^{0.86}}+0.0218 \right),0<x<10 \\ \end{matrix} \right. \end{equation}\]

注:文献[2]中的公式有误。

在得到\(m_{N}^{\left( i \right)}\)后,各极化信道\(W_{N}^{\left( i \right)}\)在发送全零时对应的接收信号LLR值服从分布\(N\left( m_{N}^{\left( i \right)},2m_{N}^{\left( i \right)} \right)\),于是可靠性度量\(P\left( { {A}_{i}} \right)\)即可计算如下

\[\begin{equation} P\left( { {A}_{i}} \right)\text{=}\int\limits_{-\infty }^{0}{\frac{1}{2\sqrt{\pi m_{N}^{\left( i \right)}}}\cdot \exp \left( \frac{-{ {\left( x-m_{N}^{\left( i \right)} \right)}^{2}}}{4m_{N}^{\left( i \right)}} \right)}dx \end{equation}\]

总结


巴氏参数、密度进化和高斯近似法都是计算各分裂信道错误概率\(P\left( { {A}_{i}} \right)\)的方法,不同的方法有各自的适用范围。巴氏参数法仅适用于BEC,密度进化法适用于所有类型的B-DMC,而高斯近似法则适用于更加实际的BAWGNC。

参考文献


[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] 陈凯. 极化编码理论与实用方案研究[D]. 北京邮电大学, 2014.

相关链接


《Polar Code(17)高斯近似(2)》 《Polar Code(8)高斯近似》