信息论 基础理论与应用第三版(傅祖芸) 第六章 讲义（课堂PPT）

第6章有噪信道编码定理,6.1错误概率与译码规则,6.2错误概率与编码方法,6.4有噪信道编码定理,6.5联合信源信道编码定理,1,前面已经从理论上讨论了，对于无噪无损信道只要对信源进行适当的编码，总能以信道容量无差错的传递信息。但是一般信道总会存在噪声和干扰，信息传输会造成损失。那么在有噪信道中怎样能使消息传输发生的错误最少？进行无错传输的可达的最大信息传输率是多少呢？这就是本章所要讨论的问题。本章的核心是香农第二定理。,2,6.1错误概率与译码规则,为了减少传输错误，提高通信的可靠性，就必须分析错误概率与哪些因素有关，有没有办法控制？能控制到什么程度？一般地，错误概率与如下因素相关：信道的统计特性译码规则,3,例：有一个BSC信道，如图所示,若收到“0”译作“0”，收到“1”译作“1”，则平均错误概率为：,反之，若收到“0”译作“1”，收到“1”译作“0”，则平均错误概率为可见错误概率与译码规则有关。,4,译码规则：输入符号集输出符号集译码规则,例：某信道转移矩阵,可以设计译码准则：A：和B：,5,总的译码规则数目信道的s个输出符号的每一个译码输出有r种选择，因此，总的译码规则总数为译码规则的选择依据一个自然的依据就是使平均错误概率最小。为了选择译码规则，需要计算平均错误概率。,平均错误概率分析：译码规则确定后，设信道输出端收到时一定译为。如果发送端刚好发送的就是，则为正确译码，译码的条件正确概率为：,6,而错误译码的概率为收到后翻译为，但发送端实际上发送的却不是，则为错误译码，其条件错误概率为：,e表示：除了以外的所有输入符号的集合。,则可得平均错误译码概率：,它表示经过译码后平均每收到一个符号所产生错误的大小，也称平均错误概率。,7,条件正确概率,如何设计译码规则，使平均错误概率最小？,最小错误概率准则（最大后验概率准则）,条件错误概率,满足关系：,因此应选择译码规则,也即收到一个符号以后译成具有最大后验概率的那个输入符号。,决定于译码规则,i为待定,8,根据贝叶斯定理，上式可写成,当信源等概分布时，则最小错误概率准则变为,这称为最大似然译码准则，方法是收到一个后，在信道矩阵的第j列元素中选择最大的值所对应的输入符号作为译码输出。,最大似然译码准则,即,9,当译码规则确定后，可进一步计算平均错误概率：,平均错误概率的计算,信道传递概率,平均正确概率,上式中，平均错误概率计算是在联合概率矩阵P(ai)P(bj|ai)中：1）先求每一列除去F(bj)=a*所对应的P(a*bj)以外的元素之和；2）然后，对所有列求和。,10,（选讲）当然，也可以对联合概率矩阵P(ai)P(bj/ai)中：1）先求每一行中除去F(bj)=ai*所对应的P(aibj)以外的元素之和;2）然后，对各行的和求和。,如果先验概率相等，则：,某个输入符号ai传输引起的错误概率,即：,具体计算如下：,11,例：某信道,1）若根据最大似然准则选择译码函数为B：,若输入等概率，则平均错误概率为,若输入不等概分布，则错误概率为：,12,2）采用最小错误概率译码准则，则联合矩阵为：,所得译码函数为：C：,平均错误概率：,13,6.2错误概率与编码方法,一般信道传输时都会产生错误，而选择译码准则并不会消除错误，那么如何减少错误概率呢？下边讨论通过编码方法来降低错误概率。,例：对于如下二元对称信道,按照最大似然准则译码，,14,如何提高信道传输的正确率呢？可用重复消息的方法，即尝试扩展信道的方法。,未用的码字（禁用码字）001010011100101110,用作消息的码字（许用码字）000（表示0）111（表示1）,输出端接收序列000001010011100101110111,二元对称信道的三次扩展信道,15,则信道矩阵为：,根据最大似然译码准则，当p=0.01，可得译码函数为：F(000)=000F(001)=000F(010)=000F(011)=111F(100)=000F(101)=111F(110)=111F(111)=111,一位错误,当000、111等概时，平均错误概率变小了：,16,现在码元个数n=3，已经将错误概率降低了两个数量级；若重复更多次，n=5，7，还可以进一步降低错误概率，上例中：,当n=5时当n=7时当n=9时当n=11时,但是n很大时，信道的信息传输率会降低很多：（M为许用码字的个数，即输入消息个数，n为编码后码字的长度）,在上例中：M=2当n=1时R=1当n=3时R=1/3当n=5时R=1/5,（比特/码符号）,（比特/码符号）,（比特/码符号）,17,分析前边的例子，只用了扩展信源的两个字符，因此信息率降低了，如果把8个字符全用上，信息传输率就会回到1，但是此时错误率更大了：一般地，有如下规律：在二元信道的n次扩展信道中，选取其中的M个作为消息，则M大一些，跟着大，R也大；M小一些，跟着小，R也小。,如果上例中，取M4，如：取000011101110为消息，则与M=8比较，错误率降低了，而信息率也降低了。,18,另外一个问题，消息数固定而编码选取方法不同，错误率也不同。比较两种选取方法：第一种：000011101110第二种：000001010100可以计算得第一种方法的错误率为第二种方法的错误率为,比较可知，第一种方法好。仔细观察发现：在第一种方法中，如果000有一位出错，就可以判定出错了；而在第二种方法中，如果000中任何一位出错，就变成了其他的合法的码字，我们无法判断是否出错。再仔细观察，发现第二种方法中，码字之间太相似。,19,码字距离：长度为n的两个码字对应位置上不同码元的个数。通常称为汉明距离：在二元码中，码字的汉明距离：,如：,则,在某一码中，任意两个码字Ci、Cj的汉明距离的最小值称为该码C的最小距离。,20,很明显，越大，越小，在M相同时也如此。码C中最小距离越大，受到干扰后，越不容易成为另一码字，因而错误概率小；相反，则容易干扰后变成另一码字。所以：应尽量设法使选取的M个码字中任意两两不同码字的距离尽量大。,讨论4种码的距离和错误概率（码长=3）：,21,二元信道的译码规则可以如下规定：,选择,使之满足条件：,它称为最小距离译码准则，也就是收到一个码字后，把它译成与它距离（汉明距离）最近的输入码字。这样可以使平均错误率较小。,最小距离译码准则,即：,22,最小距离译码准则与最大似然准则的关系在二元无记忆对称信道中，最小距离译码准则等于最大似然译码准则。（略）证明：n次扩展信道传递概率为：,错误位数,正确位数,N长接收序列,N长发送序列,信道转移概率,23,在任意信道中，也可以采用最小距离译码准则，但它不一定等于最大似然准则。,由此，按照最大似然准则，应选择传递概率最大者对应的输入序列作为译码输出。选择译码函数：使满足：即满足：,24,小结在消息数M和码长n不变的时，信息传输率R=logM/n。采用不同的编码可获得的不同的码字距离和最小码字距离，并导致不同的平均错误概率。且最小码字距离越大，平均错误概率越小。因此：应尽量设法使选取的M个码字中任意两两不同码字的距离dmin尽量大。,总之，在有噪信道中，除了信道本身的统计特性外，传输的平均错误概率与各种编译码方法相关。编码：可选择M个消息所对应得码字之间最小距离dmin尽可能大的编码方法。译码：则将接收序列译成与之最近的那个码字。只要码长n足够大，合适地选择M个消息的对应码字，就可以使错误概率很小，而信息传输率保持一定。,25,6.3有噪信道编码定理,1、有噪信道编码定理（香农第二定理）,设一个离散无记忆信道，为信道传递概率，信道容量为C。当信息传输率RC时，则无论码长n多长，总找不到一种编码使信道输出端的平均错误译码概率达到任意小。,26,这个定理是信道编码的理论依据，可以看出：信道容量是一个明确的分界点，当取分界点以下的信息传输率时，以指数趋进于0；当取分界点以下的信息传输率时，以指数趋进于1。因此在任何信道中，信道容量都是可达的、最大的可靠信息传输率。这个定理是一个存在定理，它说明错误概率趋于0的好码是存在的。但它没有给出一个具体可构造的编码方法，在它的证明过程中，码是随机的选取的。然而，它有助于指导各种通信系统的设计，有助于评价各种系统及编码的效率。,意义,27,从香农第一、第二定理可以看出，要做到有效和可靠的传输信息，可以将通信系统设计成两部分的组合，即信源编码和信道编码两部分：1）首先通过信源编码，用尽可能少的信道符号来表达信源，尽可能减少编码后信源的数据的剩余率；2）然后针对信道，对信源编码后的数据独立的进行信道编码，适当增加一些剩余度，使能纠正和克服信道中引起的错误和干扰。理论分析表明，只要满足香农第一定理和第二定理，用两步编码的方法传输信息和一步编码的方法传输信息其效果是一样的。,（选讲）6.5联合信源信道编码定理,28,两步编码分析：其信源压缩编码只与信源有关，不依赖于信道；信道编码只与信道有关，不依赖于信源。如果信源编码是一一对应的无失真编码(RH)，则编码、译码都是一一对应的映射，不会带来信息的损失；信道会导致信息有一些损失。但通过适当的信道编码（RC），可使信道引起的损失或错误尽可能小。因此，两步处理不会带来信息的损失。,29,若是有限符号集的随机序列，并满足AEP(渐进等分性)，信源S的极限熵，则存在信源与信道编码，其。反之，对于任意平稳随机序列，若极限熵，则错误概率远离0，即不可能以任意小的错误概率发送随机序列。,信源-信道编码定理,因此，信源通过信道传输，有效和可靠地传输的充要条件是HC。,30,可见，当且仅当信源极限熵H信道容量C，在信道上无错误地传输平稳信源。由于两步