#
前言
许多年前，在知乎上偶然刷到关于极化码的讨论，答主谈到极化码构造了一个鞅， 然后利用鞅的收敛定理证明极化码可以逼近信道容量。那时我正在学习随机分析理论， 已经知道鞅的收敛定理是鞅理论的核心之一，但当了解到其能够运用于编码理论中时， 我还是吃了一惊。
去年，我利用闲散的时间，学习了一些信息论的一些基本概念。 遂想通过极化码验收下学习成果，也看看鞅是否真能在编码理论中发挥作用。
#
信道容量
信道容量被定义为最大互信息，𝐶=max𝑋∼𝑃𝐼(𝑋;𝑌), 香农的信道逼近定理表明， 随着编码长度加长，在错误概率被控制的情况下，通信速率能够不断逼近信道容量。
对于BEC信道，LDPC已经理论证明能够逼近信道容量，但是对于一般的对称信道则没有答案。 而极化码能够在理论上给出逼近一般二元无记忆对称信道（B-DMC）的方案。
#
信道极化
对于一般的编码方案，数据以block为单位，输入一个block，输出一个block，而一个 block是若干个bit拼接而成。或者说，许多个单bit信道被拼接在一块组成一个并行的矢量信道。 这个矢量信道发送的是编码后的结果。
极化码从另一个角度看待这一问题。输入的bit信息不做任何变换被直接拼接在一起， 组成矢量信道的输入。但是信道不再是多个子信道的拼接，而是经过了极化码的变换。也就是说, 通过极化变换，若干个独立的信道被变化为一个特殊的矢量信道。在这个矢量信道中， 有些信道容量大，有些信道容量小，极化码的宗旨是将信息放在信道容量较大的子信道中， 而信道容量较小的子信道只发送无意义的比特。
上图就是所说的信道极化变换。考虑一个二元信道𝑊(𝑦|𝑥), 信道极化后给出两个 一元信道，分别被定义为：
𝑊12(𝑦21|𝑢1)=∑𝑢212𝑊(𝑦2|𝑢2)𝑊(𝑦1|𝑢1⊕𝑢2)
𝑊22(𝑦21,𝑢1|𝑢2)=12𝑊(𝑦2|𝑢2)𝑊(𝑦1|𝑢1⊕𝑢2)
(1)
观察可知变换后的信道输入是1bit，输出是一个矢量𝑦21,甚至还可能包含𝑢1. 将 本来独立的信道如此拆分是有意义的：
𝐼(𝑈21;𝑌21)=𝐼(𝑌21;𝑈1)+𝐼(𝑌21,𝑈1;𝑈2)=2𝐼(𝑊)
(2)
𝐼(𝑌21,𝑈1;𝑈2)≥𝐼(𝑊)≥𝐼(𝑌21;𝑈1)
(3)
上述公式说明信道极化后一个容量变大，一个容量变小，而总的容量不变。其证明是比较 简单的:
𝐼(𝑌21;𝑈1)+𝐼(𝑌21,𝑈1;𝑈2)=
𝐻(𝑈1)−𝐻(𝑈1|𝑌1,𝑌2)+𝐻(𝑈2)−𝐻(𝑈2|𝑌1,𝑌2,𝑈1)
=𝐻(𝑈1)+𝐻(𝑈2)−𝐻(𝑈1,𝑈2|𝑌1,𝑌2)
=𝐼(𝑈21;𝑌21)=2𝐼(𝑊)
(4)
𝐼(𝑌21,𝑈1;𝑈2)=𝐻(𝑈2)−𝐻(𝑈2|𝑈1,𝑌1,𝑌2)≤𝐻(𝑈2)−𝐻(𝑈2|𝑌2)
=𝐼(𝑊)
(5)
如此假设我们有很多个信道，那么信道极化会递归下去，那么有一些信道它的信道容量将会不断变小， 一些信道容量将不断变大。而极化码的核心定理表明，这一过程不仅正确，而且发生了两极分化的现象。 也就是说，大部分子信道要么信道容量为1要么信道容量为0。介于二者之间的非常少。
于是极化码编码便是找到信道容量为1的信道将要编码的信息通过这些信道发送即可， 其他信道发送0或者其他任何信息均可。
#
信道极化的定理
假设有𝑁=2𝑛个信道, 使用2进制对这𝑁个信道进行编码：1+(𝑏1…𝑏𝑛−1𝑏𝑛)2。1 现在要在这𝑁个信道构造随机变量与概率空间。这个概率空间的基本事件是1,2,…𝑁, 概率测度为均匀测度。于是子信道的互信息构成了一组随机变量，假设信道的编号为随机变量 𝐵𝑛, 那么有：
ℙ(𝐵𝑛+1|𝐵𝑛=(𝑎1𝑎2…𝑎𝑛)2)={12if𝐵𝑛+1=(𝑎1𝑎2…𝑎𝑛0)12if𝐵𝑛+1=(𝑎1𝑎2…𝑎𝑛1)
(6)
那么编号为𝐵𝑛 对应的信道容量为 𝐼𝑛=𝐼(𝑊𝐵𝑛2𝑛) 随机过程 𝐼𝑛 构成了鞅,因为
𝔼(𝐼𝑛+1|𝐼𝑛)=12𝐼(𝑊𝑎1𝑎2…𝑎𝑛02𝑛)+12𝐼(𝑊𝑎1𝑎2…𝑎𝑛12𝑛)=𝐼𝑛
(7)
等式成立的依据是公式 2 , 即极化变换导致的分叉保持总的互信息不变。
#
严密化
上述的构造是直觉性的，还不够严密，构造鞅需要构造嵌套的𝜎 代数和概率空间。 首先需要将信道编号，1,2,…∞,构成基本事件，即 Ω={(𝑎1,𝑎2,…):𝑎𝑘∈𝔽2,𝑘= 1,2,3,…}
𝜎代数被定义为：
ℱ𝑛+1=𝜎({{(𝑏1,𝑏2,…,𝑏𝑛,𝑏𝑛+1,…):𝑏𝑛+2,𝑏𝑛+3,…∈𝔽2}:𝑏1,𝑏2,…,𝑏𝑛+1∈𝔽2})
∪ℱ𝑛
ℱ0={∅,Ω}
(8)
显然这个𝜎代数就是由二进制编码后的索引构成的并包含了所有的低维的𝜎代数， 即有ℱ𝑛⊂ℱ𝓃+1。
概率测度即是均匀测度，定义为
ℙ({(𝑏1,𝑏2,…,𝑏𝑛,𝑏𝑛+1,…):𝑏𝑛+1,𝑏𝑛+2,…∈𝔽2})=12𝑛
(9)
在该概率空间上子信道的互信息构成了一个随机变量，𝐼𝑛((𝑎1…𝑎𝑛−1𝑎𝑛)2)= 𝐼(𝑊(𝑎1…𝑎𝑛−1𝑎𝑛)22𝑛)， 按照公式 2, 所有子信道容量只和为 𝑁𝐼(𝑊),从而有
•
𝔼(𝐼𝑛)=𝐼(𝑊),
上述的构造只为说明𝐼𝑛 构成了鞅：
𝔼(𝐼𝑛+1|ℱ𝑛)=𝐼𝑛
(10)
这个证明可以在基本集𝑆(𝑏1,𝑏2,…,𝑏𝑛){(𝑏1,𝑏2,…,𝑏𝑛,𝑏𝑛+1,…):𝑏𝑛+1,𝑏𝑛+2,…∈𝔽2}上积分证明:
∫𝑆(𝑏1,…,𝑏𝑛)𝔼(𝐼𝑛+1|ℱ𝑛)dℙ
=12∫𝑆(𝑏1,…,𝑏𝑛,1)𝐼𝑛+1dℙ+12∫𝑆(𝑏1,…,𝑏𝑛,0)𝐼𝑛+1dℙ
=12𝐼(𝑊𝑎1𝑎2…𝑎𝑛02𝑛)+12𝐼(𝑊𝑎1𝑎2…𝑎𝑛12𝑛)=𝐼𝑛
(11)
从而𝐼𝑛 构成了鞅，最终会收敛到稳定值，并且因为是一致有界的从而收敛也是𝐿1意义上的 [1]。
上述的收敛性说明，极化后的信道容量在编号上形成了稳定的分布，其实还可以更进一步， 这种分布还是简单函数，也就是说在一个编号集上，信道容量为1, 在其补集上信道容量为0. 这需要引入Bhattacharyya 参数，由于名字太长，这里称之为为Z参数好了
#
Z 参数
Z 参数被定义为
𝑍(𝑊)=∑𝑦√𝑊(𝑦|0)𝑊(𝑦|1)
(12)
由基本不等式可以发现𝑍(𝑊)∈[0,1], 并且
𝑍(𝑊)=1⇔𝑊(𝑦|0)=𝑊(𝑦|1)⇔𝐼(𝑊)=0
𝑍(𝑊)=0⇔𝐼(𝑊)=1
(13)
第一个公式是显然的，应为它意味这𝑋,𝑌是独立的。第二个意味这几乎处处有𝑊(𝑦|0)𝑊(𝑦|1)=0, 这意味着这两个测度是奇异的，也就是说可以把y的取值空间划成 不相交的两个部分𝐴 和𝐴𝑐，在𝐴𝑐中𝑊(𝑦|1)=0, 在𝐴中𝑊(𝑦|0)=0。于是 可以构造函数𝜉(𝑦)=𝟙𝐴, 从而有
𝑋⟶𝑊(𝑦|𝑥)𝑌⟶𝟙𝐴𝜉
(14)
于是
𝜉={1if𝑋=10if𝑋=0
(15)
从而𝐼(𝜉;𝑋)=1, 由信息不等式知道𝐼(𝑌;𝑋)>𝐼(𝜉;𝑋), 从而𝐼(𝑌;𝑋)=1
#
Z 参数收敛
变换后
𝑍(𝑊22)=∑𝑢1,𝑦1,𝑦212√𝑊(𝑦1|1⊕𝑢1)𝑊(𝑦2|1)𝑊(𝑦1|0⊕𝑢1)𝑊(𝑦2|0)
=𝑍(𝑊)2
(16)
而对于𝑍(𝑊12)的结果则更困难一些, 我想不出除了照抄Arıkan的证明外还有什么办法[2] 。
𝑍(𝑊12)≤2𝑍(𝑊)−𝑍(𝑊)2
(17)
于是可以发现
𝑍(𝑊12)+𝑍(𝑊22)≤2𝑍(𝑊)
(18)
通过上述公式可以构造出一个上鞅，证明和𝐼𝑛 类似， 记𝑍𝑛=𝑍(𝑊𝐵𝑛2𝑛),𝐵𝑛= (𝑎1𝑎2…𝑎𝑛)2 从而
𝔼(𝑍𝑛+1|ℱ𝑛)≤𝑍𝑛
(19)
于是它将收敛，并且是𝐿1收敛，其结果记作𝑍∞ 从而
lim𝑛→∞𝔼(|𝑍𝑛+1−𝑍𝑛|)=0
(20)
而
𝔼(|𝑍𝑛+1−𝑍𝑛|)≥12𝔼(|𝑍𝑛(𝑍𝑛−1)|)
(21)
于是可以得到几乎处处有 𝑍∞(1−𝑍∞)≡0
从而𝑍∞ 是简单函数，要么是1 要么是0. 进一步互信息𝐼∞ 要么是1 要么是0
#
参考文献
[1]
钱忠民，应坚刚, 随机分析引论（复旦大学数学研究生教学用书）, 1st edition. 复旦大学出版社, 2017.
[2]
E. Arikan, “Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels,” IEEE Transactions on Information Theory, vol. 55, no. 7, pp. 3051–3073, Jul. 2009, doi: 10.1109/TIT.2009.2021379.
1由于极化码的递归结构，这里的2进制表示是bitreverse后的。
quaerat voluptatem. Ut enim aeque doleamus animo, cum corpore dolemus, fieri tamen permagna accessio
potest, si aliquod aeternum et infinitum impendere malum nobis opinemur. Quod idem licet transferre
in voluptatem, ut postea variari voluptas distinguique possit, augeri amplificarique non possit.
At etiam Athenis, ut e patre audiebam facete et urban