上一节我们了解了tal-vardy算法的大致原理，对所要研究的二元输入无记忆对称信道进行了介绍，并着重介绍了能够避免输出爆炸灾难的合并操作，这一节我们来关注信道弱化与强化操作。
【1】《Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels》Erdal Arıkan
【2】《How to Construct Polar Codes》Ido Tal, Alexander Vardy
Part1.信道弱化与信道强化
信道弱化：
我们给出一个信道。对于信道
，如果存在一个中间信道
使得对于所有的
都有：
那么我们记：，指代信道Q相对于信道W是弱化的。
很容易证明下面这些性质：
1） 这种“弱化”是具有传递性的，类似a≤b，b≤c，则a≤c。
2） 我们定义“弱化”操作中的恒等性质，类似a≤b，b≤a，则a≡b。
3） 这种恒等性质具有对称性，类似a≡b，则b≡a。
对于信道的强化操作，这里就不再解释了。实际上，只需要把上式中的信道W和信道Q调换一下位置，就能够的得到信道强化的操作，以及类似的公式和下面的性质。
通过弱化操作后得到的弱化信道Q，我们重点关注它的三个参数。不过，在那之前我们先来看一下原始信道W的参数情况。
对于一个二元无记忆对称信道W：
<1> 信道错误概率Pe：
我们假设Pe(W)为最大似然判决下的错误概率，如果输入服从等概率分布（即传输0和1的概率都为1/2），那么我们可以得到：
<2> 巴氏参数Z(W)：
<3> 信道容量I(W)：
由W得到的弱化信道的参数变化情况如下：
论文中并没有直接给出后两个结论的导出，第二个结论在论文的参考文献中已经被严格证明，第三个结论在第二个结论的基础上可以被证明。这两个证明超出了我的能力范围，需要证明的可以从论文参考文献给出的引用目录里面去找。我们重点来关注第一个公式，以及它的证明。
如上为证明过程，由第一步到第二步很好理解，直接把定义公式代入就行。从第二步到第三步需要稍稍解释一下。
我们可以先忽略掉最外层的1/2倍乘和对z的求和，对比后面的内容。
- 第二步的运算逻辑顺序为，先求和、再挑选最小值；
- 第三步的运算逻辑顺序为，先挑选最小值、再求和。
这两种操作造成差异的原因就在于运算的逻辑顺序问题。
第二步的式子中，我们把W(y|0)和W(y|1)看做两个整体，忽略整体中每一个加数的细节，关注整体的大小，再取两个整体的最小值。
第三步的式子中，我们将W(y|0)和W(y|1)拆开来看，我们逐项拿出数对进行对比，只留下较小的那一项，这样最后相加的加数项的每一项，都是它所对应的那一对数中的较小者，这样的一组加数相加得到的和一定是小于等于第二步的。
当然，这只是一种定性的分析，我们也可以用数学语言去描述它，让它在形式上更加严谨。
弱化操作
在介绍信道弱化操作前，让我们先来回顾一下Arikan递推公式。tal-vardy算法每一步只操作两个信道，因此我们关注Arikan对单步信道转化的描述。
【1】-I-E中明确指出，两个独立的二元输入信道副本W:X→Y能够通过单步信道转化，变成一对二元输入信道：和
。其中输出字符集的映射关系为：
。信道转移概率之间的关系为：
【2】中对这两种信道操作进行了重新定义。【2】提出了两种符号分别用来表征这两种信道转化操作。第一种操作记为：，第二种操作记为：
。因此，我们得到：
从【1】中的介绍，我们发现，原始信道副本的输入字符集为{0,1}，长度为2；假设输出字符集长度为 “2L”，则通过第一种信道操作得到的信道 W' 的输出字符集长度为“2L×2L”，通过第二种信道操作得到的信道 W'' 的输出字符集长度为 “(2L)×2”。这个结论很重要，与接下来的信道操作有关。
这个现象很好说明，两个W信道副本都只有两个输出字符，分别为y1、y2和它们的共轭，2L=2。假设我们简记y→0，→1。则第一种信道操作的输出字符集有2L×2L=4，四种可能——{00,01,10,11}；第二种信道有2×(2L)=8，八种可能——{000,001,010,011,100,101,110,111}。可以看到，随着单步信道转化的进行，信道的输出字符集长度将随着转化次数的增加爆炸增长。在码长较大时，这将使得极化码的构造计算复杂度变得不可控制，我们之前介绍的合并函数就是为了解决这个问题而存在的。
【2】中的引理5是信道弱化操作的核心理论。
引理5的证明位于【2】Page6。
引理5告诉我们，一个弱化信道，即使对它进行信道转化操作后，它依然是一个弱化信道。
【2】中对信道弱化操作部分做了与合并函数同样的描述方式，将信道弱化操作视为一个函数。函数的输入为原始BMS信道W，以及指定输出字符集长度μ；函数输出为一个弱化BMS信道Q，Q的输出字符集最大不超过μ。
信道极化操作
在信道极化过程中，对于信道转化方法的选择问题（即在每一个节点判断进行信道操作1，还是信道操作2），可以视为一个二进制树的生成。在【1】中Arikan为我们展示了这样一张图：
我们暂且称其为“码树”。
码树的根为原始的信道副本，在每一级code_level上都会产生两个分支，上分支使用第一个信道转化公式，下分支使用第二个信道转化公式。我们以上图为例，N=2^n=8，n=3。n即code_level，表示树的深度；N即code_length，表示树的广度。借助二进制数，我们可以很容易的找到从树根到树梢的路径。例如，当 i 取5时，我们将 i-1 转化为位数为 n=3 的二进制数：(5-1)→(100)对应到码树中，从树根开始，三级分支分别取下、上、上分支，使用相应的信道操作，就能够得到这一极化信道。
因此，在信道操作中，我们可以将信道指数（channel index）转化为二进制数，通过逐位读取并进行判断，使用相应的信道操作，就能够实现信道极化。【2】中给出了一个非常清晰的算法思路：
算法复杂度
在上面的算法中，我们假设每次执行合并函数的时间为，遵循上述算法A中的符号使用规则，对于n个信道来说，由于每个信道指数有m位，因此总共调用合并函数的次数为n·m次，用时
。但是，由于许多中间信道的计算是在做重复性的工作，因此，实际计算不同信道的次数为（2n-1-1）次，因此总的时间复杂度应该为
，也即
。
实际上，我们能够利用对称信道的特点，进一步降低计算复杂度。
还记得我们在上一节强调过的Arikan给出的定理13吗？
由于我们的信道操作是单步进行的，每一次只进行两个信道的合并，在上图的（58）式中，取N=2，i=1，我们可以得到第一种信道操作的对应公式： 其中，G2=[1 0; 1 1]。不失一般性的，我们假设发送的比特为0，即u1=0，并且，我们令等式右端的发送端等于1（即令a1=1），可以得到：
【我们为什么要这么做？】
【回忆一下对称信道的定义之中，有这样一条：】 【显然，我们这样做的目的是为了得到字符对（y1，y2）的共轭对。】
当a2分别取0、1时，有：
也即，有两个共轭对，一个是
，另一个是
。对上式进一步的转化，我们可以发现，容易得到：
以及：
通俗来说，上面这一番计算的意义在于，在信道转化操作之后，我们没有必要计算输出字符集中每一个字符的转移概率。实际上，我们只需要对一半字符进行计算。
类似的，我们可以对第二种信道操作进行类似的计算，令i=2，则输出字符集共有3个字符，可以组成8中不同的组合，最后实际上只需要计算4种组合。
本节的内容就是这样，下一节我们将讨论如何对BAWGN信道使用tal-vardy算法。