第5章有噪信道编码

第5章有噪信道编码

前一章已经从理论上讨论了在无噪无损信道上，只要对信源进行适当的编码,总能以最大信息传输率C（信道容量）无差错的传输信息。但是一般信道总存在噪声或干扰,信息传输会造成损失，那么在有噪信道中怎么能使消息通过传输后发生的错误最少？在有噪信道中无错误传输的可达的最大信息传输率是多少？这就是本章所要研究的问题，即研究通信的可靠性问题。第5章有噪信道编码

内容提要本章介绍了信道编码和译码的基本概念，介绍了两种常用的译码准则：最大后验概率译码准则和极大似然译码准则,还介绍了在这两种译码准则下错误概率的计算方法。本章还介绍了信道编码定理以及信息论中的一个重要不等式Fano不等式。5．1信道编码的基本概念

将信道用图5-1所示的模型表示。信道编码器信道信道译码器uxy图5-1信道模型

信源输出序列u，经信道编码器编成码字x=f(u)并输入信道，由于干扰，信道输出y，信道译码器对y估值得

=F(y)。

信源编码以提高传输效率作为主要考虑因素，信道编码以提高传输可靠性作为主要考虑因素。这一章讨论信道编码的一些基本概念及信道编码定理。【例】给定二元对称信道，信道固有错误概率为p（p<0.5）编码规则：为提高可靠性，每个信道符号重复三次发送。

译码规则：择多译码，即信宿方收到的三个符号中有两个或三个为1，就将此次接收符号判决为1；若三个符号中有两个或三个为0，就将此次接收符号判决为0。

下面为重复编码传输示意图，计算错误概率pe。书上例题5.1信源输出序列为：

信道输入序列为：

由于p的存在，使得传输出错，故信道输出为：

根据译码规则，信道估值输出：

信道错误概率：假设信道离散无记忆，即

错误概率为：

重复编码的结果使错误概率下降。

书5-1式有问题书上例题5.2【例5.3】逆重复码离散无记忆二进制对称信道，固有误码率为p(p<0.5)，信源输出序列为三位二进制数字。编码规则：为提高传输效率，仅向信道发送一位，预先将信源输出序列进行择多编码:图5-3逆重复编码传输示意图

译码规则：将接收的一位符号重复三次译出，即若接收到1就译码为111，即若接收到0就译码为000。信源输出的三位符号中有两位或3位是1，信源序列编码为1，若三位符号中有两位或3位是0，就将此信源序列编码为0。1-p0

p

1011-p

p

计算差错概率pe：分二步进行：（1）先设p=0，计算这种编码方法带来的固有错误p1信道输入符号集X={000,001,010,011,100,101,110,111}判决输出符号集Y={000,111}译码规则因为后验概率则出错概率

假设8组输入序列是等概发送的，由于信道的对称性，两个估值序列也是等概分布的，则每个序列的平均错误概率为，误比特率。（2）再设p≠0，计算由于信道噪声引起的错误概率p2因为每个序列有三位二进制数字，但只发送一位，这一位的出错概率为p，故序列差错概率为p，误比特率。（3）总差错概率（误比特率）：

【例5.4】奇偶校验码在信息序列后面加上一位校验位，使之模2和等于1，这样的编码称为奇校验码；若使模2和等于0，这样的编码就称为偶校验码，即每个码矢中1的个数固定为奇数或偶数。关于奇偶校验

奇偶校验原理：通过计算数据中“1”的个数是奇数还是偶数来判断数据的正确性。在被校验的数据后加一位校验位或校验字符用作校验码实现校验。校验位的生成方法奇校验：确保整个被传输的数据中“1”的个数是奇数个，即载荷数据中“1”的个数是奇数个时校验位填“0”，否则填“1”；偶校验：确保整个被传输的数据中“1”的个数是偶数个，即载荷数据中“1”的个数是奇数个时校验位填“1”，否则填“0”。

使用奇偶校验码校验的特点：奇偶校验能够检测出信息传输过程中的部分误码（1位误码能检出，2位及2位以上误码不能检出），同时，它不能纠错。在发现错误后，只能要求重发。但由于其实现简单，仍得到了广泛使用。校验处理过程简单，但如果数据中发生多位数据错误就可能检测不出来，更检测不到错误发生在哪一位；主要应用于低速数字通信系统中，一般异步传输模式选用偶校验，同步传输模式选用奇校验。信道编码的目的：提高传输可靠性。有噪信道编码定理，即香农第二定理，是信道编码的理论基础。本章重点介绍通过信道编码通信系统所能达到的极限性能，不涉及编码技术的具体实现，以及两种常用的译码准则。信道编码就是按一定的规则给信源输出序列增加某些冗余符号，使其变成满足一定数学规律的码序列（或码字），再经信道进行传输。（具有纠错能力）信道译码就是按与编码器同样的数学规律去掉接收序列中的冗余符号，恢复信源消息序列。传输信道插入冗余信息抽出冗余信息编码译码还原序列发送序列编码译码发送序列还原序列传输信道插入冗余信息抽出冗余信息编码译码第5.1节错误概率与译码规则第5.2节错误概率与编码方法第5.3节有噪信道编码定理主要内容

前一章已经从理论上讨论了,对于无噪无损信道只要对信源进行适当的编码,总能以信道容量无差错的传递信息。

但是一般信道总会存在噪声和干扰,那么在有噪信道中进行无错传输可以达到的最大信息传输率是多少呢？这就是本章所要讨论的问题。

本章的核心是香农第二定理。第五章有噪信道编码第5.1节错误概率与译码规则

有噪信道传输消息是会发生错误的.为了减少错误,提高通信可靠性,就必须1)分析错误概率与哪些因素有关;2)有没有办法控制,如何控制;3)能控制到什么程度等问题.

前边已经讨论过,错误概率与信道的统计特性有关,但并不是唯一相关的因素,译码方法的选择也会影响错误率。信道统计特性信道统计特性用信道传递矩阵来描述,该矩阵确定了哪些是正确传递概率,哪些是错误传递概率.

译码规则通信过程并非到信道输出端就结束,还要经过译码过程(或判决过程)才到达消息的终端(收信者).第5.1节错误概率与译码规则例:有一个BSC信道,如右图01011/31/32/32/3若收到“0”译作“0”,收到“1”译作“1”,则平均错误概率为:反之,若收到“0”译作“1”,收到“1”译作“0”,则平均错误概率为1/3.可见,错误概率与译码准则有关.第5.1节错误概率与译码规则极端的例子---书P103，图5.4-强噪信道译码规则定义译码规则:输入符号集:A={ai},i=1,2,…,r;输出符号集:B={bj},j=1,2,…,s;译码规则:设计函数F(bj),它对于每个输出符号bj确定一个唯一的输入符号ai与其对应(单值函数).即F(bj)=ai译码规则的选择依据由于任何输出符号bj都可以译成任何输入符号ai,即s个输出符号中的每一个都可以译成r个输入符号中的任一个，所以有rs种译码规则.译码规则的选择应该根据什么准则？译码规则的选择依据:使平均错误概率最小.译码准则可以为:A:和B:例5.1:有一离散单符号信道，信道矩阵为平均错误概率有了译码规则F(bj)=ai以后,条件正确概率:收到bj译码为ai的概率p[F(bj)|bj]=p(ai|bj)条件错误概率:收bj后推测发出除ai之外符号的概率p(e|bj)=1-p(ai|bj)=1-p[F(bj)|bj]平均错误译码概率:最小错误概率译码准则问题:如何选择p(ai|bj)?使p(e|bj)最小,就应选择p[F(bj)|bj]为最大,即选择译码函数F(bj)=a*，并使之满足条件:p(a*|bj)≥p(ai|bj)ai≠a*

如果采用这样一种译码函数，它对于每一个输出符号均译成具有最大后验概率的那个输入符号，则信道错误概率就能最小；即收到符号bj以后译成具有最大后验概率的输入符号a*.该译码准则称为“最大后验概率译码准则(MAP，MaximumaPosteriori)

”或“最小错误概率译码准则”.也叫最大联合概率译码准则。对每个输出符号均译成具有最大后验概率的那个输入符号，则信道错误概率就能最小。

（1）联合概率其中称为前向概率，描述信道的噪声特性有时也把称为先验概率，把称为后验概率（2）输出符号的概率（3）后验概率表明输出端收到任一符号，必定是输入端某一符号输入所致我们一般已知信道传递概率p(bj|ai)与输入符号先验概率p(ai),所以根据贝叶斯定律,上式也可以写成一般p(bj)≠0.这样最大后验概率准则就表示为:选择译码函数F(bj)=a*, 使满足p(bj|a*)p(a*)≥p(bj|ai)p(ai),也即p(a*bj)≥p(aibj).—最大联合概率译码准则p(a*|bj)≥p(ai|bj)等效于最大联合概率译码准则最大似然译码准则(maximumlikelihoodML准则)

前面介绍的最大后验概率译码准则等同于最小传输错误概率准则，从错误概率最小角度，该译码准则是最好的。

在实际应用中，通常用同一信道去传输各种不同的信源，只知道信道的转移概率，而不知道信源的分布，故无法计算全概率，故无法采用最大后验概率译码准则进行译码。

如果输入符号等概发生,则选择译码函数F(bj)=a*,并满足p(bj|a*)≥p(bj|ai) 该译码规则称为:最大似然译码准则.该准则表示收到bj后,在信道矩阵的第j列,选择最大的值对应输入符号a*作为译码输出.平均错误概率

根据译码规则,可进一步写出平均错误概率PE,即而平均正确概率为平均错误概率也可写成:如果先验概率p(ai)相等,则:平均错误概率先对行求和，除去译码规则中所对应的概率，然后是各行之和几点说明1）当输入符号等概时，最大似然准则等价于最大后验概率准则。2）该准则可直接从信道传递矩阵中选定译码函数，即收到bj后，译成信道矩阵p中第j列中最大那个元素所对应的信源符号。3）该准则本身不再依赖于先验概率p(ai)，但当输入符号等概时，它使平均错误概率PE最小。4）当输入符号等概或先验概率未知时，采用此准则。复习和捋顺关系信道编码就是按一定的规则给信源输出序列增加某些冗余符号，使其变成满足一定数学规律的码序列（或码字），再经信道进行传输。（具有纠错能力）信道译码就是按与编码器同样的数学规律去掉接收序列中的冗余符号，恢复信源消息序列。平均错误概率与两个因素有关1、信道的统计特性（传递矩阵）2、译码规则主要内容和捋顺关系：一、译码规则；二、如何选择译码规则；三、两种译码准则-最大后验概率译码准则四、两种译码准则-最大似然译码准则一、译码规则；定义译码规则:输入符号集:A={ai},i=1,2,…,r;输出符号集:B={bj},j=1,2,…,s;译码规则:设计函数F(bj),它对于每个输出符号bj确定一个唯一的输入符号ai与其对应(单值函数).即F(bj)=ai由于任何输出符号bj都可以译成任何输入符号ai,即s个输出符号中的每一个都可以译成r个输入符号中的任一个，所以有rs种译码规则.译码准则可以为:A:和B:例5.1:有一离散单符号信道，信道矩阵为二、如何选择译码规则；译码规则的选择应该根据什么准则？译码规则的选择依据:使平均错误概率最小.平均错误概率如何计算？平均错误概率有了译码规则F(bj)=ai以后,条件正确概率:收到bj译码为ai的概率p[F(bj)|bj]=p(ai|bj)条件错误概率:收bj后推测发出除ai之外符号的概率p(e|bj)=1-p(ai|bj)=1-p[F(bj)|bj]平均错误译码概率:三、两种译码准则-最大后验概率译码准则最小错误概率译码准则问题:如何选择p(ai|bj)?使p(e|bj)最小,就应选择p[F(bj)|bj]为最大,即选择译码函数F(bj)=a*，并使之满足条件:p(a*|bj)≥p(ai|bj)ai≠a*

如果采用这样一种译码函数，它对于每一个输出符号均译成具有最大后验概率的那个输入符号，则信道错误概率就能最小；即收到符号bj以后译成具有最大后验概率的输入符号a*.该译码准则称为“最大后验概率译码准则(MAP，MaximumaPosteriori)

”或“最小错误概率译码准则”.也叫最大联合概率译码准则。对每个输出符号均译成具有最大后验概率的那个输入符号，则信道错误概率就能最小。

我们一般已知信道传递概率p(bj|ai)与输入符号先验概率p(ai),所以根据贝叶斯定律,上式也可以写成一般p(bj)≠0.这样最大后验概率准则就表示为:选择译码函数F(bj)=a*, 使满足p(bj|a*)p(a*)≥p(bj|ai)p(ai),也即p(a*bj)≥p(aibj).—最大联合概率译码准则p(a*|bj)≥p(ai|bj)四、两种译码准则-最大似然译码准则最大似然译码准则(maximumlikelihoodML准则)

前面介绍的最大后验概率译码准则等同于最小传输错误概率准则，从错误概率最小角度，该译码准则是最好的。

在实际应用中，通常用同一信道去传输各种不同的信源，只知道信道的转移概率，而不知道信源的分布，故无法计算全概率，故无法采用最大后验概率译码准则进行译码。

如果输入符号等概发生,则选择译码函数F(bj)=a*,并满足p(bj|a*)≥p(bj|ai) 该译码规则称为:最大似然译码准则.该准则表示收到bj后,在信道矩阵的第j列,选择最大的值对应输入符号a*作为译码输出.平均错误概率

根据译码规则,可进一步写出平均错误概率PE,即而平均正确概率为平均错误概率也可写成:如果先验概率p(ai)相等,则:平均错误概率先对行求和，除去译码规则中所对应的概率，然后是各行之和几点说明1）当输入符号等概时，最大似然准则等价于最大后验概率准则。2）该准则可直接从信道传递矩阵中选定译码函数，即收到bj后，译成信道矩阵p中第j列中最大那个元素所对应的信源符号。3）该准则本身不再依赖于先验概率p(ai)，但当输入符号等概时，它使平均错误概率PE最小。4）当输入符号等概或先验概率未知时，采用此准则。两种准则使用要点MAP准则-最大后验概率准则

1）由转移概率矩阵的每行分别乘p(x)，得到联合概率矩阵；

2）对于每一列（相当于y固定）找一个最大的概率对应的X作为译码结果；

3）所有译码结果所对应的联合概率的和为正确概率，其他矩阵元素的和为错误概率。ML准则--最大似然译码准则1）对转移概率矩阵中每列选择最大的一个元素对应的x作为译码结果；2）所有译码结果所对应的转移概率的和再乘以1/r（或pi）为正确概率,其他矩阵元素的和再乘以1/r（或pi）为错误概率。当输入分布等概时，最大似然译码准则和最大后验概率准则是等价的。根据最大似然译码准则，我们可以直接从信道矩阵的传递概率中去选定译码函数：就是说，收到后，译成信道矩阵的第j列中最大的那个元素所对应的信源符号。最大似然译码准则本身不再依赖于先验概率。但是当先验概率为等概时，它使错误概率PE最小。如果先验概率不相等或不知道时，仍可以采用这个准则，但不一定能使PE最小。如果知道先验概率，应该使用最大后验概率准则;如果不知道先验概率，则只能用最大似然准则.例题5.2.2已知信道的转移概率矩阵为现有两种译码规则：规则A：规则B：设输入等概，求两种译码规则的错误概率。解：设判决函数为，根据平均错误概率公式得Thefourteenthclass--2014书上P104可见这两种方法得到同一结果，因为要得到后验概率，计算步骤更多，所以可直接应用最大联合概率译码准则译码。【例】信源分布

信道转移概率矩阵

，信道输出符号Y={y1，y2，y3}。（1）计算按最大后验概率准则译码的平均错误概率；（2）若信源等概分布，对其按极大似然译码准则译码，并求平均错误概率。

【解】（1）最大后验概率准则译码

前面同一例子求平均错误概率平均错误概率：

（2）当信源等概分布，按极大似然函数译码准则译码，已给出信道转移概率矩阵为

在矩阵的每列中选一最大值(矩阵中带下划线的值)，译码为

平均错误概率：

第5.1节错误概率与译码规则例5.3:

根据最大似然准则可选择译码函数为B:若采用前述译码函数A,则平均错误率为:可见第5.1节错误概率与译码规则若输入不等概,仍可采用最大似然译码准则,其概率分布为:第5.1节错误概率与译码规则输入不是等概分布时，比较最大似然译码准则和最小错误概率译码准则若采用最小错误概率译码准则,其联合矩阵{p(aibj)}为:所得译码函数为:C:第5.1节错误概率与译码规则平均错误率为:可见,.所以输入非等概分布时最大似然译码准则获得的平均错误概率不是最小的.第5.1节错误概率与译码规则§5.3费诺(Fano)不等式1.信道疑义度（损失熵）2.费诺(Fano)不等式平均错误概率Pe与译码规则(译码函数)有关，而译码规则又由信道特性来决定。由于信道中存在噪声，导致输出端发生错误，并使接收端输出符号后，对发送的是什么符号还存在不确定性。可以，Pe与信道疑义度具有一定的关系，就是下面要讲的费诺不等式5.3.1信道疑义度（回忆）设信道的输入与输出分别为X、Y，定义条件熵H(X/Y)为信道疑义度。信道疑义度的含义：信道疑义度表示接收到Y条件下X的平均不确定性；根据I(X;Y)=H(X)-H(X/Y)，信道疑义度又表示X经信道传输信息量的损失；8－2Fano不等式证明：倒数？(2)如果判决出错（概率为）,错在r-1个符号中的哪一个，其疑义度不会超log(r-1)。

物理意义进行一次判决后，关于X的疑义度可分成两项：(1)是否判对，疑义度为H

()费诺不等式示意图信道疑义度是信源熵H(X)超过平均互信息I(X;Y)的部分。若以H(X|Y)为纵坐标，PE为横坐标，则函数H(PE)+PElog(n-1)随PE变化的曲线如图所示。由图可知，当信源、信道给定时，信道疑义度H(X|Y)就给定了译码平均错误概率PE的下限。

注释第5.2节错误概率与编码方法

一般信道传输时都会产生错误,而选择译码准则并不会消除错误,那么如何减少错误概率呢?下边讨论通过编码方法来降低错误概率.第5.2节错误概率与编码方法a1=0a2=1b1=0b2=10.990.990.010.01例:对于如下二元对称信道若选择最佳译码规则F(b1)=a1F(b2)=a2对于一般传输系统(如数字通信),这个概率已经相当大了.一般要求系统的错误概率在10-6~10-9范围内,甚至更低.简单重复编码如何提高信道传输的正确率呢？可尝试下面的方法实际经验告诉我们：只要在发送端把消息重复发几遍，也就是增加消息的传输时间，就可使接收端接收消息时错误减小，从而提高了通信的可靠性。如在二元对称信道中，当发送消息（符号）0时，不是只发一个0而是连续发三个0，同样发送消息（符号）1时也连续发送三个1，这是一种最简单的编码方法，他它将长度n=1的两个二元序列变换为两个长度n=3的二元序列，我们称这两个长度为3的二元序列为码字，于是信道输入端有两个码字000和111，但在输出端，由于信道干扰的作用，码字中各个码元（码符号）都可能发生错误，则有8个可能的输出序列，如下面简单重复编码

如何提高信道传输的正确率呢？可尝试下面的方法没有使用的码字001010011100101110用作消息的码字000111输出端接收序列000001010011100101110111二元对称信道的三次扩展信道重复编码(n=3次)：信道看成是3次扩展，输出端由于各个干扰，各个码元都可能发生错误，则有8个可能的输出序列。根据最大似然译码准则(假设输入时等概率的),可得简单重复编码的译码规则为F(β1)=F(β2)=F(β3)=F(β5)=α1F(β4)=F(β6)=F(β7)=F(β8)=α8信道矩阵简单重复编码根据这个规则计算得译码后的错误概率为简单重复编码简单重复编码也可以采用“择多译码”,即根据接收序列中0多还是1多,0多就判作0,1多就判作1.可得译码函数为：F(000)=000,F(001)=000,F(010)=000,F(011)=111F(100)=000,F(101)=111,F(110)=111,F(111)=111根据择多译码规则,同样可得到可见,择多译码准则与最大似然译码准则是一致的.

简单重复编码与原来PE=10-2比较,这种简单重复的编码方法已把译码错误概率降低了近两个数量级.结论：重复编码使PE减小原因:这种编码可以纠正码字中的一位码元出错,译错的可能性变小了,因此错误概率降低.简单重复编码若重复更多次可进一步降低错误率.可算得可见,当n很大时,使PE很小是可能的.但这又带来了一个新问题,n很大时,信息传输率会降低很多.简单重复编码编码后信息传输率为在上例中：M=2当n=1时R=1当n=3时R=1/3当n=5时R=1/5............由此得PE和R的关系,如右图.它表明:尽管PE降低很多,但也使信息传输率降得很低.M为输入信息（许用码字）的个数。logM表示消息集在等概率条件下每个消息（码字）携带的平均信息量（比特）。n是编码后码字的长度（码元的个数）Thefifteenthclass--2014复习上一次课主要内容一、费诺(Fano)不等式二、降低错误概率的方法§5.3费诺(Fano)不等式1.信道疑义度2.费诺(Fano)不等式平均错误概率Pe与译码规则(译码函数)有关，而译码规则又由信道特性来决定。由于信道中存在噪声，导致输出端发生错误，并使接收端输出符号后，对发送的是什么符号还存在不确定性。可以，Pe与信道疑义度具有一定的关系，就是下面要讲的费诺不等式香农第二定理这显然是一个矛盾,有没有解决的办法,能不能找到一种更好的编码方法,使PE相当低,而R却保持在一定水平呢？这就是香农第二定理,即有噪信道编码定理.在上图中,也给出了香农第二定理的PE和R的关系值,其中ε为任意小的数.设离散无记忆信道[X,p(y|x),Y]，其信道容量为C。当信息传输率R<C时，只要码长n足够长，总可以在输入符号集中找到个码字组成的一组码和相应的译码规则，使译码的错误概率任意小。与信源编码定理的证明类似，构造编码方法。第三节有噪信道编码定理(香农第二定理)基本思路—证明有噪信道编码定理香农对有噪信道编码定理证明方法的基本思路是：连续使用信道多次，即在n次无记忆扩展信道中讨论，以便使大数定律有效；随机地选取码书，也就是在Xn的符号序列集中随机地选取经常出现的高概率序列作为码字；采用最大似然译码准则，也就是将接收序列译成与其距离最近的那个码字；在随机编码的基础上，对所有的码书计算其平均错误概率。当n足够大时，此平均错误概率趋于零，由此证明得至少有一种好码存在。证明：离散无记忆信道[X,p(y|x),Y]，输入序列为输出序列：转移概率：编码速率为R，则消息的标号集为编码函数可看作下述映射：译码函数为：发送m的条件下译码错误概率为：译码的平均误组率为（消息等概）具体的证明过程----了解从中独立随机地选取个序列作为码字，这相当于每个码字出现的概率为消息序列出现的概率:X中任一元素独立等概地出现，这种编码方法称作随机编码。译码规则：（典型序列准则—译为联合典型序列的x）对给定的接受序列y，若存在唯一的使就将y译为m'，即D(y)=m'。当或者有两个以上m’和y构成联合典型序列时，就认为译码出错。就是任意特定消息被错误译码的概率。所以不失一般性可假设发送的是第一个消息。译码错误概率为因为随机码具有对称性，所以译码错误概率与送出的消息编号无关，也就是随机码集合的平均错误概率再具体一些说，就是：为了使R大，可使I(X:Y)极大化，即以C代替。若R<C-3，随着n趋于无穷大，上面的错误概率趋于0。因为R<C-3，上面的错误概率趋于0，所以必定存在一种码，当n足够大时，其译码错误概率为0。

Shannon第二定理另一种形式！有噪信道编码定理，即Shannon第二定理。--书上的证明方法！P1065．3信道编码定理定理5.1对于任何离散无记忆信道DMC，存在信息传输率为R，长为n的码，当n→∞时，平均差错概率pe<exp{-nE(R)}→0，式中E(R)为可靠性函数，E(R)在0<R<C的范围内为正。

1．随机编码方法信道输入符号集A={a1,a2,…,ak},选用长为n的定长码，共可构成kn个矢量，设有M个消息待传（M<kn），每次随机地从kn个矢量中抽出M个矢量构成一个码集C（允许重复取）C

={x1,…,xm,…,x

M}共可构成knM个这样的码集。由随机编码的构造方法，得到任何一个码字的概率相同，且相互独立。

上述定理也称有噪信道编码定理，即Shannon第二定理。

2．Gallager上界因为上述按随机编码方法构成的码集是等概分布的，按照最大似然译码准则译码，在发送码矢xk时，要得到正确译码须满足

，即

（5-5）

定义示性函数则发送码矢xk判错的概率为

（5-6）

书上错的根据式(5-5)，当0

,

1时，下式成立用示性函数Ik(y)表示上式，即

（5-7）

将式(5-7)代入式(5-6)，得式中0

,

1，因为,

都是任意数，可取，则有

（5-8）

Gallager上界3．随机编码错误概率上界

Gallager限仅给出发送码矢xk时的错误概率上界，还要对全部码矢求平均，下面对上述的随机编码集合求平均。

对于随机编码，各码字等概且独立，有，对式(5-8)求统计平均值，得平均错误概率上界

(5-9)

后面一项，因为0

1，而x是x的∩型凸函数，由∩型凸函数的定义知：函数均值均值函数，即有(5-10)因为xm(m=1,2,…,M)都通过同一信道传输，故p(y︱xm)值相同，记为p(y︱x)，代入式（5－10）得

(5-11)

将式(5-11)代回式(5-9)，得

（5－12）

平均错误概率的一个上界4．离散无记忆信道DMC的错误概率上界

对于n维离散无记忆信道DMC，有，对于随机编码，将这两个关系式代入式(5-12)，有（5－13）

序列x=x1,…,xi,,…,xn中的

xi,取自同一符号A={a1,a2,…,ak}，故分布q(xi)相同,（5－14）

将式（5－14）代入式（5－13），得

（5－15）

5．可靠性函数E(R)信息传输率，则式(5－15)可写为： (5-16)

记则式(5-16)可写成

pe

<exp{-n[-R+E0(,q)]}(5-17)

对式(5-17)右边求极小值，即对指数-R+E0(,q)求极大值,记这个极大值为则式(5-17)可写为pe<exp{-nE

(R)}称E

(R)为可靠性函数,也称随机编码指数，它与信道转移概率p(y︱x)有关。

在0

R

C的范围内，E

(R)是下降的、下凹的正值函数，说明E

(R)有界，这样，当时，有exp{-nE

(R)}→0，从而pe

<exp{-n

E

(R)}→0。

2、有噪信道编码逆定理如一离散无记忆信道,其容量为C.当信息传输率R>C时,则无论码长n多长,总找不到一种编码(2nR,n)使信道输出端的平均错误译码概率达到任意小.第三节有噪信道编码定理

这个定理是信道编码的理论依据,可以看出:

信道容量是一个明确的分界点,当取分界点以下的信息传输率时,PE以指数趋进于0;

当取分