Polar Code（5）编码之信道转移概率

前言

极化信道的可靠性估计是Polar Code编码的第一步，对于BEC信道，若计算巴氏参数，转移概率是绕不开的一步。此外对于译码判决来说，计算转移概率也是必须的。本文就尝试梳理一下极化信道的转移概率\(W_{N}^{\left( i \right)}\left( y_{1}^{N},u_{1}^{i-1}|{ {u}_{i}} \right)\)。

离散信道的数学模型

信道是信号传输的媒介，是传送信息的通道。在信息论研究中不考虑信道的物理特性，而只是考虑它的概率特性。研究信道的目的主要是为了解决信息如何通过信道实现有效和可靠传输的问题。香农第二定理指出，信息传输速率小于信道容量是实现可靠传输的充分与必要的条件。信道容量是信息能够可靠传输的最大信息传输速率，是信道研究中的一个重要内容。信道容量定义为信道输入与输出平均互信息的最大值，它是信道本身固有特性的反映，仅与信道的转移概率有关，与信道的输入概率无关，但是信道输人概率必须与信道匹配才能达到容量。

设信道的输入符号集合\(X\)为随机变量集合，则输出符号集合\(Y\)也为随机变量集合。因为信道有随机噪声干扰，使\(Y\)在\(X\)给定条件下为随机变量，所以用条件概率或转移概率\(P\left( y|x \right)\)描述\(Y\)与\(X\) 之间的关系，其中\(x\in X,y\in Y\)。信道模型如图1所示。

一般的信道输入与输出均为随机矢量，设输入集合为\({ {X}^{N}}={ {X}_{1}},{ {X}_{2}},...,{ {X}_{N}}\)，集合中的矢量\(\mathbf{x}={ {x}_{1}},{ {x}_{2}},...{ {x}_{N}},\mathbf{x}\in { {X}^{N}}\)，输入单符号集为\(A=\left\{ { {a}_{1}},{ {a}_{2}},...,{ {a}_{r}} \right\}\)，其中\({ {a}_{1}},{ {a}_{2}},...,{ {a}_{r}}\)的概率分别是\({ {p}_{1}},{ {p}_{2}},...{ {p}_{r}}\)，且\({ {x}_{n}}\)取自\(A\)，\(1\le n\le N\)，输入矢量的符号集为\({ {A}^{N}}\)。输出集合为\({ {Y}^{N}}={ {Y}_{1}},{ {Y}_{2}},...,{ {Y}_{N}}\)，集合中的矢量为\(\mathbf{y}={ {y}_{1}},{ {y}_{2}},...,{ {y}_{N}},\mathbf{y}\in { {Y}^{N}}\)，输出单符号集为\(B=\left\{ { {b}_{1}},{ {b}_{2}},...,{ {b}_{s}} \right\}\)，其中\({ {b}_{1}},{ {b}_{2}},...,{ {b}_{s}}\)的概率分别是\({ {q}_{1}},{ {q}_{2}},...,{ {q}_{s}}\)，且\({ {y}_{n}}\)取自\(B\)，\(1\le n\le N\)，输出矢量的符号集为\({ {B}^{N}}\)。这种信道模型表示为\(\left\{ { {X}^{N}},p\left( \mathbf{y}|\mathbf{x} \right),{ {Y}^{N}} \right\}\)，其中\(p\left( \mathbf{y}|\mathbf{x} \right)=p\left( { {y}_{1}},...,{ {y}_{N}}|{ {x}_{1}},...,{ {x}_{N}} \right)\)。

二进制离散无记忆信道

设信道的输入和输出分别是长为\(N\)的序列，若信道的转移概率满足

\[p\left( \mathbf{y}|\mathbf{x} \right)=\prod\limits_{n=1}^{N}{p\left( { {y}_{n}}|{ {x}_{n}} \right)}\]

则称此信道为离散无记忆信道（DMC），其数学模型为：\(\left\{ X,p\left( { {y}_{n}}|{ {x}_{n}} \right),Y \right\}\)。若输入单符号集为\(A=\left\{ { {a}_{1}},{ {a}_{2}} \right\}\text{=}\left\{ 0,1 \right\}\)，则此信道为二进制离散无记忆信道（B-DMC）。

二进制对称信道

二进制对称信道，简记为BSC（Binary Symmetric Channel），输入与输出符号集分别为\(A=\left\{ 0,1 \right\}\)，\(B=\left\{ 0,1 \right\}\)，信道转移概率满足\({ {P}_{Y|X}}\left( 0|0 \right)={ {P}_{Y|X}}\left( 1|1 \right)=p\)，\({ {P}_{Y|X}}\left( 1|0 \right)={ {P}_{Y|X}}\left( 0|1 \right)=1-p\)。BSC转移概率图如图2所示。

二进制删除信道

二进制删除信道，简记为BEC（Binary Erasure Channel），输入与输出符号集分别为\(A=\left\{ 0,1 \right\}\)，\(B=\left\{ 0,2,1 \right\}\)，信道转移概率满足${ {P}{Y|X}}( 0|0 )={ {P}{Y|X}}( 1|1 )=1-\(，\){ {P}{Y|X}}( 2|0 )={ {P}{Y|X}}( 2|1 )=\(，\)$称为错误率。BEC转移概率图如图3所示。

极化信道

Arikan在研究极化信道和极化码时是基于B-DMC的。原始信道\(W:X\to Y\)如图4（a）所示，其转移概率为\(W\left( y|u \right),u\in X,y\in Y\)。将原始信道\(W\)的\(N\)个独立副本经过联合与分裂操作之后就形成了新的极化信道\(W_{N}^{\left( i \right)}:X\to { {Y}^{N}}\times { {X}^{i-1}}\)，如图4（b）所示，其转移概率为\(W_{N}^{\left( i \right)}\left( y_{1}^{N},u_{1}^{i-1}|{ {u}_{i}} \right)\)。

极化信道转移概率

对任何\(n\ge 0,N={ {2}^{n}},1\le i\le {N}/{2}\;\)，有递归式

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

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

递归计算过程中对于任意\(a_{i}^{j}\)，只有\(i\le j\)的情况，如遇到\(a_{i}^{j},i>j\)的情况则视为无效，并定义\(W_{1}^{\left( 1 \right)}\triangleq { {W}_{1}}=W\)，\(y_{1}^{1}\triangleq { {y}_{1}}\)，\(u_{1}^{1}\triangleq { {u}_{1}}\)。下面以\(N=4\)为例详细说明。

下面以BSC信道为例，计算各极化信道转移概率。

\(W_{1}^{\left( 1 \right)}\)

当\(N=1,i=1\)时，利用式（1）计算信道\(W_{1}^{\left( 1 \right)}\text{=}W\)的转移概率：

\[\begin{align} W_{1}^{\left( 1 \right)}\left( y_{1}^{1},u_{1}^{0}|{ {u}_{1}} \right)=W\left( { {y}_{1}}|{ {u}_{1}} \right)=p \end{align}\]

此时的信道即为如图4（a）所示的原始信道。类似的有\(W\left( { {y}_{2}}|{ {u}_{2}} \right)=W\left( { {y}_{N}}|{ {u}_{N}} \right)=p\)。

\(W_{2}^{\left( 1 \right)}\)

当\(N=2,i=1\)时，利用式（1）计算信道\(W_{2}^{\left( 1 \right)}\)的转移概率：

\[\begin{align} \nonumber W_{2}^{\left( 1 \right)}\left( y_{1}^{2},u_{1}^{0}|{ {u}_{1}} \right)=\sum\limits_{ { {u}_{2}}}{\frac{1}{2}}W_{1}^{\left( 1 \right)}\left( y_{1}^{1},u_{1,o}^{0}\oplus u_{1,e}^{0}|{ {u}_{1}}\oplus { {u}_{2}} \right)\cdot W_{1}^{\left( 1 \right)}\left( y_{2}^{2},u_{1,e}^{0}|{ {u}_{2}} \right) \\ \downarrow \\ \nonumber W_{2}^{\left( 1 \right)}\left( y_{1}^{2}|{ {u}_{1}} \right)=\sum\limits_{ { {u}_{2}}}{\frac{1}{2}}W\left( { {y}_{1}}|{ {u}_{1}}\oplus { {u}_{2}} \right)\cdot W\left( { {y}_{2}}|{ {u}_{2}} \right) \\ \end{align}\]

此时的信道即为如图4（b）所示的第1个极化信道。考察对\({ {u}_{1}}\)的译码可知，根据运算关系有\({ {u}_{1}}={ {y}_{1}}\oplus { {y}_{2}}\)，当\(\left\{ { {y}_{1}},{ {y}_{2}} \right\}\)中有一个是错误符号时，\({ {u}_{1}}\)的值便无法获得，此时\({ {u}_{1}}\)译码失败，可以计算\(W_{2}^{\left( 1 \right)}\)的转移概率为

\[\begin{align} W_{2}^{\left( 1 \right)}\left( y_{1}^{2}|{ {u}_{1}} \right)=p\times p={ {p}^{2}} \end{align}\]

两个原始信道\(W\)的副本经过信道极化构成极化信道\({ {W}_{2}}\)。如图5所示，\({ {W}_{2}}\)的一个分裂子信道\({ {v}_{1}}\)的转移概率即为\(W_{2}^{\left( 1 \right)}\)，\({ {v}_{2}}\)是\({ {W}_{2}}\)的另一个分裂子信道。下面求\({ {v}_{2}}\)的转移概率。

\(W_{2}^{\left( 2 \right)}\)

当\(N=2,i=1\)时，利用式（2）计算信道\(W_{2}^{\left( 2 \right)}\)的转移概率：

\[\begin{align} \nonumber W_{2}^{\left( 2 \right)}\left( y_{1}^{2},u_{1}^{1}|{ {u}_{2}} \right)=\frac{1}{2}W_{1}^{\left( 1 \right)}\left( y_{1}^{1},u_{1,o}^{0}\oplus u_{1,e}^{0}|{ {u}_{1}}\oplus { {u}_{2}} \right)\cdot W_{1}^{\left( 1 \right)}\left( y_{2}^{2},u_{1,e}^{0}|{ {u}_{2}} \right) \\ \downarrow \\ \nonumber W_{2}^{\left( 2 \right)}\left( y_{1}^{2},{ {u}_{1}}|{ {u}_{2}} \right)=\frac{1}{2}W\left( { {y}_{1}}|{ {u}_{1}}\oplus { {u}_{2}} \right)\cdot W\left( { {y}_{2}}|{ {u}_{2}} \right) \\ \end{align}\]

此时的信道即为如图4（b）所示的第2个极化信道。考察对\({ {u}_{2}}\)的译码可知，根据运算关系有\({ {u}_{2}}={ {y}_{1}}\oplus { {u}_{1}}\)或\({ {u}_{2}}={ {y}_{2}}\)，只要这两个式子的任意一个提供了正确符号，那么\({ {u}_{2}}\)将必定被正确译码。即当\({ {u}_{1}}\)被正确译码时，只有\(\left\{ { {y}_{1}},{ {y}_{2}} \right\}\)全部是错误符号时，\({ {u}_{2}}\)才会译码失败。可以计算\(W_{2}^{\left( 2 \right)}\)的转移概率为

\[\begin{align} W_{2}^{\left( 2 \right)}\left( y_{1}^{2},{ {u}_{1}}|{ {u}_{2}} \right)=1-{ {\left( 1-p \right)}^{2}} \end{align}\]

两个极化信道\({ {W}_{2}}\)的副本又进一步经过信道极化构成了极化信道\({ {W}_{4}}\)。\({ {v}_{1}}\)和\({ {v}_{3}}\)的转移概率相同，\({ {v}_{2}}\)和\({ {v}_{4}}\)的转移概率相同，如图6所示。

\(W_{4}^{\left( 1 \right)}\)

当\(N=4,i=1\)时，利用式（1）计算信道\(W_{4}^{\left( 1 \right)}\)的转移概率：

\[\begin{align} \nonumber W_{4}^{\left( 1 \right)}\left( y_{1}^{4},u_{1}^{0}|{ {u}_{1}} \right)=\sum\limits_{ { {u}_{2}}}{\frac{1}{2}W_{2}^{\left( 1 \right)}\left( y_{1}^{2},u_{1,o}^{0}\oplus u_{1,e}^{0}|{ {u}_{1}}\oplus { {u}_{2}} \right)\cdot W_{2}^{\left( 1 \right)}\left( y_{3}^{4},u_{1,e}^{0}|{ {u}_{2}} \right)} \\ \downarrow \\ \nonumber W_{4}^{\left( 1 \right)}\left( y_{1}^{4}|{ {u}_{1}} \right)=\sum\limits_{ { {u}_{2}}}{\frac{1}{2}W_{2}^{\left( 1 \right)}\left( y_{1}^{2}|{ {u}_{1}}\oplus { {u}_{2}} \right)\cdot W_{2}^{\left( 1 \right)}\left( y_{3}^{4}|{ {u}_{2}} \right)} \\ \end{align}\]

利用递归思想，将（4）式\(W_{2}^{\left( 1 \right)}\left( y_{1}^{2}|{ {u}_{1}} \right)\)的计算结果作为新的“原始信道”的转移概率，即根据\(\left\{ \begin{matrix} { {y}_{1}}=v{}_{1}\oplus { {v}_{3}} \\ { {y}_{2}}={ {v}_{3}} \\ \end{matrix} \right.\)递归计算\(W_{4}^{\left( 1 \right)}\left( y_{1}^{4}|{ {u}_{1}} \right)\)的转移概率为\({ {\left( { {p}^{2}} \right)}^{2}}\)，如图7所示。

\(W_{4}^{\left( 2 \right)}\)

当\(N=4,i=1\)时，利用式（2）计算信道\(W_{4}^{\left( 2 \right)}\)的转移概率：

\[\begin{align} \nonumber & W_{4}^{\left( 2 \right)}\left( y_{1}^{4},{ {u}_{1}}|{ {u}_{2}} \right)=\frac{1}{2}W_{2}^{\left( 1 \right)}\left( y_{1}^{2}|{ {u}_{1}}\oplus { {u}_{2}} \right)\cdot W_{2}^{\left( 1 \right)}\left( y_{3}^{4}|{ {u}_{2}} \right) \\ & =1-{ {\left( 1-{ {p}^{2}} \right)}^{2}} \\ \end{align}\]

\(W_{4}^{\left( 3 \right)}\)

当\(N=4,i=2\)时，利用式（1）计算信道\(W_{4}^{\left( 3 \right)}\)的转移概率：

\[\begin{align} \nonumber & W_{4}^{\left( 3 \right)}\left( y_{1}^{4},u_{1}^{2}|{ {u}_{3}} \right)=\sum\limits_{ { {u}_{4}}}{\frac{1}{2}W_{2}^{\left( 2 \right)}\left( y_{1}^{2},{ {u}_{1}}\oplus { {u}_{2}}|{ {u}_{3}}\oplus { {u}_{4}} \right)\cdot W_{2}^{\left( 2 \right)}\left( y_{3}^{4},{ {u}_{2}}|{ {u}_{4}} \right)} \\ & ={ {\left( 1-{ {\left( 1-p \right)}^{2}} \right)}^{2}} \\ \end{align}\]

\(W_{4}^{\left( 4 \right)}\)

当\(N=4,i=2\)时，利用式（2）计算信道\(W_{4}^{\left( 4 \right)}\)的转移概率：

\[\begin{align} \nonumber & W_{4}^{\left( 4 \right)}\left( y_{1}^{4},u_{1}^{3}|{ {u}_{4}} \right)=\frac{1}{2}W_{2}^{\left( 2 \right)}\left( y_{1}^{2},{ {u}_{1}}\oplus { {u}_{2}}|{ {u}_{3}}\oplus { {u}_{4}} \right)\cdot W_{2}^{\left( 2 \right)}\left( y_{3}^{4},{ {u}_{2}}|{ {u}_{4}} \right) \\ & =1-{ {\left( { {\left( 1-p \right)}^{2}} \right)}^{2}} \\ \end{align}\]

小结

经过以上运算得到了极化信道\({ {W}_{4}}\)的各个分裂子信道的转移概率：

\[\begin{align} \left\{ \begin{matrix} W_{4}^{\left( 1 \right)}\left( y_{1}^{4}|{ {u}_{1}} \right)={ {\left( { {p}^{2}} \right)}^{2}} \\ W_{4}^{\left( 2 \right)}\left( y_{1}^{4},{ {u}_{1}}|{ {u}_{2}} \right)=1-{ {\left( 1-{ {p}^{2}} \right)}^{2}} \\ W_{4}^{\left( 3 \right)}\left( y_{1}^{4},u_{1}^{2}|{ {u}_{3}} \right)={ {\left( 1-{ {\left( 1-p \right)}^{2}} \right)}^{2}} \\ W_{4}^{\left( 4 \right)}\left( y_{1}^{4},u_{1}^{3}|{ {u}_{4}} \right)=1-{ {\left( { {\left( 1-p \right)}^{2}} \right)}^{2}} \\ \end{matrix} \right. \end{align}\]

若信道为BSC，则\({ {W}_{4}}\)的各分裂子信道的转移概率即为式（12）。若信道为BEC，只需将\(p\)替换为$1-$，即

\[\begin{align} \left\{ \begin{matrix} W_{4}^{\left( 1 \right)}\left( y_{1}^{4}|{ {u}_{1}} \right)={ {\left( { {\left( 1-\varepsilon \right)}^{2}} \right)}^{2}} \\ W_{4}^{\left( 2 \right)}\left( y_{1}^{4},{ {u}_{1}}|{ {u}_{2}} \right)=1-{ {\left( 1-{ {\left( 1-\varepsilon \right)}^{2}} \right)}^{2}} \\ W_{4}^{\left( 3 \right)}\left( y_{1}^{4},u_{1}^{2}|{ {u}_{3}} \right)={ {\left( 1-{ {\varepsilon }^{2}} \right)}^{2}} \\ W_{4}^{\left( 4 \right)}\left( y_{1}^{4},u_{1}^{3}|{ {u}_{4}} \right)=1-{ {\left( { {\varepsilon }^{2}} \right)}^{2}} \\ \end{matrix} \right. \end{align}\]

验证

假设对于删除概率为\(\varepsilon =0.5\)的BEC，原始信道\(W\)的对称容量\(I\left( W \right)=0.5\)，利用式（13）可得各分裂信道转移概率

\[\begin{align} \left\{ \begin{matrix} W_{4}^{\left( 1 \right)}\left( y_{1}^{4}|{ {u}_{1}} \right)={ {\left( { {\left( 1-\varepsilon \right)}^{2}} \right)}^{2}}=0.0625 \\ W_{4}^{\left( 2 \right)}\left( y_{1}^{4},{ {u}_{1}}|{ {u}_{2}} \right)=1-{ {\left( 1-{ {\left( 1-\varepsilon \right)}^{2}} \right)}^{2}}=0.4375 \\ W_{4}^{\left( 3 \right)}\left( y_{1}^{4},u_{1}^{2}|{ {u}_{3}} \right)={ {\left( 1-{ {\varepsilon }^{2}} \right)}^{2}}=0.5625 \\ W_{4}^{\left( 4 \right)}\left( y_{1}^{4},u_{1}^{3}|{ {u}_{4}} \right)=1-{ {\left( { {\varepsilon }^{2}} \right)}^{2}}=0.9375 \\ \end{matrix} \right. \end{align}\]

进而求得各分裂信道的对称容量

\[\begin{align} \left\{ \begin{matrix} I\left( W_{4}^{\left( 1 \right)} \right)=0.0625 \\ I\left( W_{4}^{\left( 2 \right)} \right)=\text{0}\text{.4375} \\ I\left( W_{4}^{\left( 3 \right)} \right)=\text{0}\text{.5625} \\ I\left( W_{4}^{\left( 4 \right)} \right)=\text{0}\text{.9375} \\ \end{matrix} \right. \end{align}\]

从式（15）可以看出原始信道\(W\)的4个独立副本经过信道极化以后，各分裂信道的容量呈现两极分化趋势。一部分子信道容量开始趋近于0，另一部分子信道容量开始趋近于1。并且信道总容量不变：\(I\left( W_{4}^{\left( 1 \right)} \right)\text{+}I\left( W_{4}^{\left( 2 \right)} \right)\text{+}I\left( W_{4}^{\left( 3 \right)} \right)\text{+}I\left( W_{4}^{\left( 4 \right)} \right)\text{=}4\times I\left( W \right)\)。

总结

本文首先引入离散信道的数学模型，进而定义二进制对称信道和二进制删除信道的转移概率，并延伸出极化信道的转移概率。之后以\(N=4\)为例，推导了极化信道\({ {W}_{4}}\)各分裂子信道的转移概率。最后由各分裂信道的转移概率计算相应的对称容量，验证了信道极化现象。

参考文献

[1] 田宝玉. 信息论基础.第2版[M]. 人民邮电出版社, 2016. [2] 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.