信道容量及信道编码原理学习1. 引言2. 离散信道（discret channel）3. 联合典型序列4. 信道编码定理5. 汉明码6. 信源和信道分离定理7. Turbo码本质和贝叶斯网络的置信度传播的关系

1. 引言

0x1：什么是通信

当我们说“A与B通信”时，我们本质意思是在说A的物理行为使B产生一种需要的物理状态。信息的传输是一个物理过程，因此，必然受到无法控制的周边噪声以及信号处理本身缺陷的影响。如果接受者B与传输者A就所传输的内容是一致的，那么说这次通信是成功的。

1. 数据压缩与数据传输的对偶性

在数据压缩和数据传输之间存在对偶性：

• 在数据压缩过程中，去除数据中所有的冗余以使其得到最大程度的压缩
• 在数据传输过程中，以一种受控的方式加入冗余以抵抗信道传输中可能发生的错误

这么看起来，数据压缩和数据传输的目标是彼此对抗的，无法同时达到最优。一般地，通信系统可以分为两部分，而且数据压缩与数据传输问题可以分开单独考虑和设计，通信系统设计的目标就是让这两个目标整体达到最优。

0x2：什么是信道容量

假设A与B在通过某种物理渠道（或抽象物理结构）进行通信，在n次使用信道下，我们可以计算出可区分的信号的最大数目。该数与n成指数增长关系，这个指数就是所说的信道容量。信道容量（可区分的信号数目的对数值）被特征化为最大互信息，是信息论中一个关键问题。

下图给出了一个物理发送信号系统的数学模拟。

• 来自某个有限字母表的信源字符被编码器映射成一系列信道字符串，通过信道向译码器传输信道的输出序列。
• 从概率与数理统计的角度来说，输出序列虽然是随机的（符合某种随机变量），但它的分布由输入序列决定，每个可能的输入序列将导出一个关于输出序列的概率分布，即p(y|x)。但是由于两个不同的输入序列可以产生相同的输出序列，于是根据输出序列不一定能100%反向确定输入序列具体是什么（贝叶斯概率公式），译码器的任务就是凭借这些输出序列来恢复出信源传输的信息。

信道容量理论研究的问题，并不是讨论一个物理通道最大能传输的极限信息，而是在保证非常低误差的情况下，能达到的理论传输率。有明确的理论可以支撑证明，我们能够以很高的概率从输入序列中挑选出一个“不会混淆”的子集，使得对于每一个特定的输出序列，只存在唯一的一个输入最有可能导致该输出。于是，在可忽略的误差概率情况下，可以在输出端重构输入序列。

将信源映射到适合于输入信道的“足够分散的”输入序列集合，我们能够以非常低的误差概率传输一条消息，并且在信道的输出端重构出这个信源消息。可实现的最大的码率称作该信道的容量。

0x3：信道容量的几个例子

这个小节，我们通过几个典型例子，来从不同角度看一下信道容量的决定因素。

1. 无噪声二元信道

如下图所示，它的二元输入在输出端能精确地重现：

无噪声二元信道，C=1比特

在这种情况下，任何一个传输的比特都能被无误差地接收到。因此，每次使用该信道，都可以毫无误差地传输一个比特，信道容量就是1比特。

另一方面，也可以计算得到信息容量C=maxI(X；Y)=1比特，且在p(x)=(1/2，1/2)时达到。  

2. 无重叠输出的有噪声信道

这种信道对于两个输入中的每一个，均有两个可能的输出，如下图所示：

无重叠输出的有噪声信道，C=1比特

这种信道虽然有噪声，但是依然可以根据输出精确确定输入，只是需要更多的信息。

因此，该信道的容量仍然是1比特/传输，也可以计算出该信道的信息容量C=maxI(X；Y)=1比特，且在p(x)=(1/2，1/2)时达到。

3. 有噪声的打字机信道

在这种信道中，信道输入以概率1/2在输出端精确接收，或以1/2概率转变为下一个字母，如下图所示：

有噪声信道

从上图可以看到，从输出端存在彼此交叠重合，无法从输出端精确地还原出输入端。为了解决这个问题，可以参考上一节的例子，将输出端以间隔的方式进行编码映射，以此得到独立同分布的无噪声输出端概率分布。

若输入端有26个字符，并以间隔的方式使用输入字符，如下图所示，

那么在每次传输过程中，可以毫无误差地传输其中的13个字符。因此，该信道的容量为log13比特/传输，也可以计算得到信道的容量：

C=maxI(X；Y) = max[H(Y) - H(Y|X)] = max(H(Y)) - 1 = log26 - 1 = log13比特，且当p(x)为整个输入字母表上的均匀分布时达到该最大容量

4. 二元对称信道

考虑下图所示的二元对称信道（binary symmetric channel，BSC），这个二元信道的输入字符以概率p互补，这是一个有误差信道的最简单典型模型。

在出现错误时，0作为1收到，或者正好相反。从接收到的比特中我们并不能看出哪里发生了错误。从某种意义上说，所有接收到的比特都不可靠。但是信道噪声定理告诉我们，我们仍然可以使用这样的通信信道以非0的传输码率发送信息，并且误差概率任意小。

这里给出互信息的一个界，

最后一个不等式成立是因为Y是一个二元随机变量，当输入分布是均匀分布时等号成立。因此，参数为p的二元对称信道的信息容量是：C = 1 - H(p)比特。

从公式中可以看到，信道输出端的概率分布越均匀，则信道容量越小。

5. 二元檫除信道

有一种信道类似于二元对称信道，会直接损失一些比特（丢失信息），这种信道称作二元檫除信道（binary erasure channel）。在二元檫除信道中，比例为a的比特被檫除掉，并且接受者知道哪些比特已经被檫除掉了，如下图所示：

二元檫除信道，两个输入，三个输出

计算二元檫除信道的容量如下：

从公式上咋一看，似乎H(Y)的的最大值是log3，但无论选择什么输入分布p(x)，都无法达到这个值。设E代表事件{Y=e}，并使用表达式：

设Pr(X=1)=π，我们有，

因此，

，其中，当π=1/2时，达到该信道容量 

这个信道容量的表达式有很强的直观意义：由于比例为α的比特在信道中损失，因而我们至多能够恢复比例为1-α的比特输入信息。因此，信道容量最多为1-α。

从上面的几个例子讨论可以得到一个概括性的结论，信道容量由两部分组成：

• 信道结构：输入源和输出源之间的映射关系（输入输出概率分布）
• 信道噪声：信噪比（本质也是输入输出之间的映射结构）

笔者思考：

从信道容量这个视角来看机器学习模型的训练和拟合过程，我们可以将一个训练集抽象理解为一个通信信道，训练集信道的目的是通过抽样方法，得到一个目标函数的典型集，典型集中包含了目标函数的信源信息。对于训练集自身来说，我们的目的总是希望训练集中包含的有用信息尽量多，也就说，我们的目标是”让训练集信道的信道容量尽量大“，那如何让信道容量尽量大呢？由前面的结论我们可以得到几点启发：

• 优化信道结构：训练样本中，不同类别的样本分布要尽量保持均匀，这样可以让训练集中的信息熵最大。
• 减小信道噪声：在信号输出侧减小不同信号码之间的交叠，尽量保证不同的信号码之间是彼此独立的。简单来说就是，不要让同一类样本出现label交叠的情况，在实际工程中这是一个常见问题误区，常常是因为打标系统的漏报导致。

Relevant Link: 

《信息论基础》阮吉寿著 - 第七章

 

2. 离散信道（discret channel）

离散信道是数字通信中，最常用的抽象模型，我们本文的讨论对象也是针对离散信道。

0x1：离散信道形式化定义

离散信道是由：

• 输入字母表X
• 输出字母表Y
• 概率转移矩阵p(y|x)

三部分构成的系统，如下图所示，

取自下标集的消息W，产生信号，这个信号以随机序列的方式被接受者收到。然后，接受者使用适当的译码规则猜测消息W。如果与所传输的消息W不同，则表明接受者出错。下面我们用数学符号严格定义这些概念，

用表示的离散信道由两个有限集X和Y以及一簇概率密度函数p(y|x)构成，其中对任意的x与y，有p(y|x)>=0，以及对任意的x，有，而X和Y分别看做信道的输入与输出。

值得注意的是，如果输出的概率分布仅依赖于它所对应的输入，而与先前通信的输入或者输出条件独立，就称这个信道是无记忆的（memoryless），值得注意的是，马尔科夫过程也是一种无记忆过程。本文在讨论离散无记忆信道时，如无特别说明，一般都是指不带反馈的离散无记忆信道。

0x2：离散无记忆信道的信道容量

离散无记忆信道的“信息”信道容量（channel capacity）定义为：

，这里最大值取所有可能的输入分布p(x)

从随机过程熵率的角度来看，信道容量定义为信道的最高码率（比特/信道使用），在此码率下，信息能够以任意小的误差概率被传输。香农第二定理表明，信道容量等于这个可操作的信道容量。 

0x3：离散无记忆信道（DMC）的n次扩展

离散无记忆信道（DMC）的n次扩展是指信道，其中，即进行n次通信的通信过程。

因为是无记忆的，离散无记忆信道的n次扩展的信道转移函数可以简化为，

信道的(M，n)码由以下部分构成：

• 下标集
• 编码函数，生成码字。所有码字的集合称作码簿（codebook）
• 译码函数，它是一个确定性规则，为每个收到的字符向量指定一个源码猜测

0x4：离散信道容量的性质 

这个小节，我们来讨论下信道容量的几个典型性质，

• 由于 I(X；Y) >= 0，所以 C>=0
• 由于 C=max I(X；Y) <= maxH(X) <= log |X|，C <= log |X|
• C <= log |Y|
• I(X；Y)是关于p(x)的一个连续函数
• I(X；Y)是关于p(x)的凹函数。由于I(X；Y)是闭凸集上的凹函数，因而局部最大值也是全局最大值，所以最大值是有界的，也即信道容量是有界的

0x5：离散信道的误差

1. 条件误差概率

设，

为已知下标 i 被发送的条件下，接受者译码错误的条件概率（conditional probability of error），其中 I(.) 为示性函数。

2. 最大误差概率

(M，n)码的最大误差概率λ⁽ⁿ⁾（maximum probability of error）定义为，

 

3. 平均误差概率

(M，n)码的（算术）平均误差概率P_e⁽ⁿ⁾（average probability of error）定义为，

显然有， 

0x6：离散信道的码率

(M，n)码的码率R(rate)为，

进一步的，如果存在一个码序列，满足当时，最大误差概率，则称码率R是可达的（achievable）。

信道的容量定义为：所有可达码率的上确界。

于是，对于充分大的分组长度，小于信道容量的码率对应的误差概率可以任意小。

Relevant Link: 

《信息论基础》阮吉寿著 - 第七章

 

3. 联合典型序列

所谓联合典型序列，简单地说，就是如果码字与接收到的信号是”联合典型“的话，就将信道输出译为第 i 个下标。

0x1：联合典型序列定义

服从分布p(x，y)的联合典型序列所构成的集合是指其经验熵与真实熵ε接近的n长序列构成的集合，即：

 

其中，

0x2：联合AEP

设(Xⁿ，Yⁿ)为服从的i.i.d.的n长序列，那么，

• 当n->∞时，
• 
• 如果，即与是独立的且与p(xⁿ，yⁿ)有相同的边际分布，那么，而且对于充分大的n，有，由此，n长序列的联合典型集的上界和下界都是可以确定的

下图是关于联合典型集的示意图，

大约有2^nH(X)个典型的X序列和大约2^nH(Y)个典型的Y序列。但是，联合典型序列只有2^nH(X，Y)个，所以并不是所有典型的Xⁿ与典型的Yⁿ构成的序列对都是联合典型的。

随机选取的序列对是联合典型的概率大约为2^-nI(X；Y)。因此，我们可能需要考虑约2^nI(X；Y)这样的序列对，才可能遇到一个联合典型对，这表明存在大约2^nI(X；Y)个可区分的信号Xⁿ。

着眼于上述问题的另一种方式是考虑固定输出序列Yⁿ下的联合典型序列集，这里假定该输出序列来自真实的输入信号Xⁿ。对于序列Yⁿ，大约存在2^nH(X|Y)个条件典型的输入信号。某个随机选取的（其他）输入信号Xⁿ与Yⁿ为联合典型的概率大约等于。

这再次表明，我们可能选取出大约2^nI(X；Y)个码字Xⁿ(W)，才能使其中的一个码字与产生输出Yⁿ的对应码字混淆起来。

Relevant Link: 

《信息论基础》阮吉寿著 - 第七章

 

4. 信道编码定理

0x1：信道容量的直观理解

前面的章节中我们已经讨论了离散无记忆信道的信息容量定义，即容量可以视为能够在该信道中可靠传输的比特数。我们这小节将尝试给出一个直观思路，解释为什么能通过信道来传输C比特的信息。

基本的思路是，对于大的分组长度，每个信道可以看作是有噪声打字机信道（前面章节提到），由此每个信道都有一个输入子集，使得在输出端接收到的序列基本互不相交。

对于输入的每个n长序列，会有大约2^nH(Y|X)个可能的Y序列与之对应，并且所有这些序列是等可能的（AEP定理），如下图所示，

我们希望确保没有两个X序列能够产生相同的Y输出序列，否则，将无法判断到底传输的是哪个X序列。

所有可能的Y序列的总数约等于2^nH(Y)，对应于不同的输入X序列，这个集合分割成大小为2^nH(Y|X)的小集合。所以不相交集的总数小于等于。因此，我们至多可以传输个可区分的n长序列，这就是所谓的信道容量。

0x2：香农证明信道编码定理的主要思路

信道编码定理最初的证明由香农在1948年的开创性论文中给出。该结果与直观感觉正好相反，如果在信道传输过程中存在误差，那么如何纠正所有误差？任何纠错过程本身也受到误差的影响，这样将无穷无尽地进行下去。

香农证明，只要码率小于信道容量，信息就可以通过该信道可靠地传输，香农在证明中使用了很多精妙的思考，包括：

• 允许任意小的非0误差概率存在
• 连续使用信道多次，以保证可以使用大数定律
• 在随机选择的码簿上计算平均误差概率，这样可以使概率对称，而且可以用来证明至少存在一个好的编码

香农的概述性证明基于典型序列、随机码选择的思想（计算随机选择的码字的平均误差概率）等等。

即寻找一个与收到的序列是联合典型的码字，如果找到唯一满足该性质的码字，我们则认为这就是被发送的码字。

依据前面所讨论的联合典型性的性质，由于发送的码字与接收到序列是概率相关的，所以他们以很高的概率成为联合典型。并且，任意其他码字与接收到的序列是联合典型的概率是2^-nl，因此，如果码字个数小于2^nI，那么可以以很高的概率断定不会有其他的码字能够与被传输的码字相混淆，并且误差概率很小。

虽然联合典型译码是次优的，但是它便于分析而且可以达到小于信道容量的任何码率。

0x3：信道编码定理形式化定义

对于离散无记忆信道，小于信道容量C的所有码率都是可达的。具体来说，对任意码率R<C，存在一个(2^nR，n)码序列，它的最大误差概率为。反之，任何满足的(2^nR，n)码必定有R<=C。

值得注意的是，虽然这个定理说明了对于大的分组长度，存在误差概率任意小的好码，但它并没有提供一种构造最佳码的方法。如果使用定理证明中的方法，根据适当的分布随机地生成一个码，那么对于充分大的分组长度，这样构造出来的编码可能是最好的。

然而，由于该编码中缺乏某个结构，译码将是非常困难的，因此，这个定理并不能提供一个实际的编码方案，而仅仅只是一个方法论，我们后面会具体讨论具体的易于编和译的构造性编码，例如汉明（Hamming）码，它在每个比特分组中纠正一个错误。

0x4：零误差码

在允许完全无误差的情况下，我们来重新论证一次信道编码定理。首先证明蕴含结论R<=C。

假定有一个零误差概率的(2^nR，n)码，也就是说，译码器输出的g(Yⁿ)以概率1等于输入的下标W。那么，输入下标W完全由输出序列决定，即。

为了获得更强的界，随意假定W服从上的均匀分布，于是，H(W) = nR。从而，我们有如下不等式推导过程， 

其中，

• （a）由数据处理不等式推出，由于形成马尔柯夫链
• （b）由离散无记忆假设证明推出
• （c）直接由信息容量的定义推出

因此，对任何零误差的(2^nR，n)码及所有的n，有：

0x5：费诺不等式与编码定理的逆定理

下面将零误差码的证明过程推广到具有非常小误差概率的编码，证明需要用到的新工具就是费诺不等式，它依据条件熵给出误差概率的下界。

这里先给出费诺不等式的定义，下标W服从集合上的均匀分布，序列Yⁿ与W是概率相关的。通过Yⁿ来估计被发送的下标W。设为其估计，那么，W->Xⁿ(W)->Yⁿ->W‘行程马尔柯夫链，注意到误差概率为：

我们给出下面的引理， 

【费诺不等式】设离散无记忆信道的码簿为C，且输入消息W服从2^nR上的均匀分布，则有，

【信道容量不变定理】设Yⁿ为Xⁿ经过容量C离散无记忆信道传输所得到的输出信号，则，

，对于任意的p(xⁿ)

上式说明多次使用信道并不增加每次传输的信心容量比特。

笔者总结：

本质上讲，当R<C时，可以以任意低的误差概率传输信息；而当R>C时，误差概率将远离0。最佳的码率就是信道容量。

Relevant Link: 

《信息论基础》阮吉寿著 - 第七章

  

5. 汉明码

信道编码定理使用分组码的方案，如果分组长度足够大的话，当码率小于信道容量时，可以用分组码以任意低的误差概率传输信息。香农在其开创性论文中提出了得到这种码的一种概述性方法，此后人们一直在寻找这样的码。除了要达到低的误差概率之外，还需要具备简单的特性，以保证可以大规模进行有效编码和译码。我们本章介绍由汉明开发的一种最简单的方案，它可以说明大多数码所共有的一些基本思想。

0x1：从简单编码方案说起

编码的目的是通过增加冗余使得在一些信息损失或者损坏的情况下，扔可能由接受者恢复出原始的消息。

一种最显而易见的编码方案是重复信息，例如，为了发送一个1，我们发送11111，为了发送一个0，我们发送00000。这一方案使用5个字符来传输1比特，因此码率为1/5比特/字符。如果在二元对称信道中使用这样的码，最优的译码方案就是将接收到的每个5比特分组译为其中占多数的比特。显然，当且仅当超过3/5的比特发生错误时，才会导致译码错误。通过使用更长的重复码，可以达到任意小的误差概率。但是，随着分组长度的增加，码率也趋于0，因此，一个”最简单的“编码，不一定是一个非常实用的编码。

替代这种简单的重复比特方法，可以用某种巧妙的方式将比特联合起来，使得每一个额外的比特都可以用来检验某个信息比特子集中是否发生错误。

一个简单的例子就是奇偶校验码，从n-1个信息比特的分组出发，选取第n个比特，使得整个分组的奇偶校验数为0。这样，如果在传输过程中发生了奇数次错误，那么接受者能够注意到奇偶性的变化，并察觉到错误，这就是检错码（error-detecting code）最简单的例子。但是要注意的是，该编码既不能察觉到出现偶数次错误，也不能提供任何有关纠正这些错误的信息。

我们可以推广奇偶校验的思想，允许存在多个奇偶校验位，也可以允许奇偶校验依赖于各种各样的信息比特子集。

接下来要讨论的汉明码就是奇偶校验码的一个例子，我们会利用线性代数中的一些简单思想来描述它。

0x2：汉明码基本思想

为了说明汉明码的基本思想，考虑分组长度为7，单个码字长度为3的非0二元向量的集合，以它们为列向量构成一个矩阵：

考虑H的零空间（与H相乘得到000的向量）中长度为7的向量的集合。由线性空间理论，因为H的秩为3，故期望H的零空间的维数为4，这2⁴个码字如下：

由于这个码字集是矩阵的零空间，所以从任意两个码字的和扔是一个码字的意义上看，这是一个线性空间。因此，码字集形成7维向量空间中的一个4维线性子空间。

观察这些码字，不难注意到除了全是0的码字外，任何码字中1的最小数目为3，该最小数称为码的最小重量（minimum weight）。可以看出，由于H的所有列互不相同，没有两列的和可以为000，因此码的最小重量至少为3。

基于任意两列的和必然为该矩阵中某一列的事实，我们可以推出最小距离恰好为3。由于该码是线性的，任意两个码字的差仍是一个码字，因此，任意两个码字之间至少在3个位置上有所不同。

两个码字不同的最小位置数称为该码的最小距离（minimum distance）。码的最小距离是用来表示码字之间相隔多远的一个度量，并且可以决定在信道的输出端码字之间差异的程度。对线性码来说，最小距离等于最小重量，我们的目的是设计出最小距离尽可能大的码（信道编码定理）。

上述码的最小距离是3，因此，如果码字c仅占一个位置损坏，那么产生新字符串将与其他任何码字之间至少存在两个位置上是不用的，它与c更加接近。根据香农给出的联合典型码思想，依然可以根据似然译码得到码字c。但是，是否可以通过穷举搜索就发现哪一个是距离最近的码字呢？

回答是肯定的！可以利用矩阵H的结构译码！

矩阵H称作奇偶校验矩阵（parity check matrix），具有如下性质：

对任意码字c均有Hc = 0，设e_i是第 i 个位置为1其余位置为0的向量。如果码字的第 i 个位置损坏，则接收到的向量为 r=e+e_i，如果将矩阵H与接收到的向量相乘，则得到，

这正好是H的第 i 列向量。因此，通过计算Hr，就可以发现接收向量的哪一个位置损坏的，还原该位置上的值就得到一个码字。这样就有了一个简单的程序用来纠正接收序列中的一个错误。

我们已经构造出分组长度为7的16个码字组成的码簿，它能纠正至多一个错误，这个码就是汉明码（Hamming code）。

至此，我们还没有给出明确的编码程序，我们继续明确定理汉明码，

• 所有码字的前4位，构成了2⁴种组合，将这4个比特看做是要发送消息的4个比特
• 而另外3个比特由编码决定

一般地，让码字的前k个比特代表消息，而后面n-k个比特留作奇偶校验位，这样得到的编码称作系统码（systematic code）。该码往往由它的分组长度n，信息比特数k，以及最小距离d三个参数来决定。例如，上述编码称作（7，4，3）汉明码。

可以用简单的文氏图表示来解释汉明码的工作原理，为了发送信息序列1101，将序列中的4个信息比特分别放在图中4个相交的区域中，然后在剩余的区域中各放置一个校验位使得每个圈中的校验结果为偶数（即每个圆中有偶数个1），如下图，

 

现在不妨假设其中的一个比特被改变了，如下图中，有一个信息比特从1变成了0，

此时，有两个圆违背了原先的校验约束（图中加黑部分）。因而，当我们知道了这两个约束违背，不难看出，导致产生约束违背的这个单一的比特错误只可能在两圆的相交部分发生。

类似地，通过分析其他情形，可以看出，这种码可以检测并纠正发生在接收码字中的任何单个比特错误 

很容易推广这一程度来构造更大的矩阵H。一般来说，如果使用矩阵H中的 l 行，那么所得编码的分组长度为 n=2^l-1，k=2^l-l-1，以及最小距离为3。所有这些码都称作汉明码，并可以纠正一个错误。

汉明码是所有线性奇偶校验码中最简单的例子，通过汉明码说明了构造其他线性码的基本原则，即分组码（block code）---- 将一组信息比特映射成一个信道码字，且不依赖于过去的信息比特。

Relevant Link: 

《信息论基础》阮吉寿著 - 第七章

 

6. 信源和信道分离定理

这章我们来讨论一个问题，为了节省传输进行了数据压缩（R>H）和用户信道传输的信道编码（R<C）是彼此独立的还是互相依赖的呢？

例如，考虑通过离散无记忆信道传输数字语音或音乐，设计一个码，将语言样本序列直接映射成信道的输入信号，或者先将语音压缩成最有效的格式，然后使用适当的信道编码从该信道将他发送出去。由于数据压缩不依赖于信道，而信道编码又不依赖于信源分布。

在这章中，我们将证明：在有噪声信道中，数据压缩和信道编码这两个步骤是彼此独立的。这意味着，可以将通信系统的设计转化成信源编码与通信编码两个部分的组合。这种组合的方法与将两个问题一起考虑所能设计出的任何方法一样有效。

数据的通常表示是二元字母表，最现代的通信系统是数字化通信系统，并且为了能在通常的信道上传输，数据简化为二进制表示。这使复杂度大大减小，像ATM和因特网这样的网络系统允许语音、视频和数字数据共用相同的通信信道。

现在对上述讨论问题做一个严格的定义，假设有一个信源V，从字母表V中生成字符。对于由V生成的随机过程，除了要求其取值于有限字母表且满足AEP之外，不做任何假设。这种过程的例子包括独立同分布的随机变量序列和平稳不可约马尔柯夫链的状态序列。任何平稳遍历信源均满足AEP。

现在想通过信道发送字符序列，并且保证接受者可以重构序列。为了达到这个目的，将序列映射成码字，通过信道发送这个码字。接受者观察接收到的序列Yⁿ后，给出发送序列Vⁿ的估计。如果，则接受者犯了错误，我们定义误差概率为：

其中 I 为示性函数，为译码函数，这个系统如下图所示，

0x1：联合信源信道编码定理

如果V₁，V₂，....，V_n为有限字母表上满足AEP和H(v)<C的随机过程，则存在一个信源信道编码使得误差概率。反之，对任意平稳随机过程，如果H(v)>C，那么误差概率远离0，从而不可能以任意低的误差概率通过信道发送这个过程。

证明：可达性。

证明前半部分的重点就是此前描述的两步骤编码，由于已经假定随机过程满足AEP，所以必然存在一个元素个数<=2^n(H(v)+ε)的典型集A_ε⁽ⁿ⁾，它拥有概率的绝大部分。仅对属于这个典型集的信源序列进行编码，其余所有序列将产生一个错误，它对误差概率的贡献不会超过ε。

给A_ε⁽ⁿ⁾中的所有序列加上下标，由于至多有2n(Hv+ε)个这样的序列，n(H+ε)比特足以给出它们的下标了，如果

 

我们能以小于ε的误差概率将需要的下标发送给接收者，接收者可以通过穷举典型集A_ε⁽ⁿ⁾，选择与被估计下标相应的序列，从而重构出Vⁿ。这个序列将以很高的概率与传输序列相一致。具体来说，对充分大的n，我们有，

 

因此，如果

那么对于充分大的n，我们能够以低的误差概率重构出序列。

联合信源信道分离定理促使我们将信源编码问题从信道编码问题中独立出来考虑，

• 信源编码起试图找到信源的最有效表示
• 信道编码器需要让编码消息，具备能够对抗信道中产生的噪声和错误的能力

分离定理表明，分离编码器与联合编码器能够达到相同的码率，我们可以独立地涉及信源码和信道码，然后结合两者达到最优的效果，

总结一下，

• 数据压缩定理来源于AEP，表明全部信源序列存在一个拥有了绝大部分概率的”小型“的子集（大约为2^nH），根据这个子集使用H比特/字符并以很小的误差概率来表示这个信源
• 数据传输定理基于联合的AEP，它依据的事实是，对于大的分组长度，信道的输出序列非常有可能与输入码字是联合典型的，而任何其他码字是联合典型的概率约为2^-nI。因而，我们可以使用大约2^nI个码字而保持可忽略的误差概率。

Relevant Link: 

《信息论基础》阮吉寿著 - 第七章

 

7. Turbo码本质和贝叶斯网络的置信度传播的关系

TODO