信息论与编码课件第五章.ppt

第五章第五章 信道编码定理信道编码定理 错误概率与译码规则错误概率与译码规则 错误概率与编码方法错误概率与编码方法 信道编码定理信道编码定理 第五章 作业 教材第141页142页 5.1，5.3 信道编码信道编码 目的：提高抗干扰能力，使差错率最小。目的：提高抗干扰能力，使差错率最小。 实质：增加冗余度，扩大信号空间，增大信实质：增加冗余度，扩大信号空间，增大信 号间距离。号间距离。 重要意义：通过信道编码的方法，可以用不重要意义：通过信道编码的方法，可以用不 可靠的信道实现可靠的传输。可靠的信道实现可靠的传输。 信信 源源 编编 码码 器器 信信 源源 译译 码码 器器 信信 道道 编编 码码 器器 信信 道道 译译 码码 器器 信源信源 信宿信宿 信道信道 u u y y x x 干扰干扰 编码器：编码函数，完成映射编码器：编码函数，完成映射 编码器的输入：编码器的输入： 码字分别为：码字分别为： 编码后的信息传输率：码字长为编码后的信息传输率：码字长为 n n 物理意义：每个码元所能携带的最大信息量。物理意义：每个码元所能携带的最大信息量。 好码：在相同的差错控制（纠错能力）下，好码：在相同的差错控制（纠错能力）下， 越大，则相应的码越好。越大，则相应的码越好。 问题：问题：R R 能否无限制提高能否无限制提高? ? 如何衡量纠错能力？如何衡量纠错能力？ 例：二元对称信道例：二元对称信道 译码规则对错误概率的影响译码规则对错误概率的影响 译码器译码器A A 译码规则：译码规则： 接收符号接收符号译码译码 0 0 0 0 1 1 1 1 错误概率与译码规则错误概率与译码规则 分析分析 则在此译码器下，平均错误概率为（设输入为等概则在此译码器下，平均错误概率为（设输入为等概 ） 发发发发出符号出符号接收符号接收符号译码译码译码译码正确概率正确概率错误错误错误错误 概率概率 0 0 0 0 0 0 1/31/3 0 0 1 1 1 1 p pe e (0)(0) = 2/3 = 2/3 1 1 1 1 1 1 1/31/3 1 1 0 0 0 0 p pe e (1)(1) = 2/3 = 2/3 译码器译码器B B 译码规则：译码规则： 分析分析 则在此译码器下，平均错误概率为（设输入为等概则在此译码器下，平均错误概率为（设输入为等概 ） 接收符号接收符号译码译码译码译码 0 0 1 1 1 1 0 0 发发发发出符号出符号接收符号接收符号译码译码译码译码正确概率正确概率错误错误错误错误 概率概率 0 0 0 0 1 1 p pe e (0)(0) = 1/3 = 1/3 0 0 1 1 0 0 p(0)= 2/3p(0)= 2/3 1 1 1 1 0 0 p p e e (1)(1) = 1/3 = 1/3 1 1 0 0 1 1 p(1)= 2/3p(1)= 2/3 结论：错误概率不仅与信道的统计特性有关，而且与结论：错误概率不仅与信道的统计特性有关，而且与 译译 码规则有关。码规则有关。 我们来定义译码规则我们来定义译码规则 设信道的输入符号集为设信道的输入符号集为X X= a a i i ，i i =1=1，2 2，r r ； 输出符号集为输出符号集为Y Y= = b b j j ，j j =1 =1，2 2，s s。 制定译码规则就是设计一个单值函数制定译码规则就是设计一个单值函数F F（b b j j ），），它对于它对于 每一个输出符号每一个输出符号b b j j 确定一个唯一的输入符号确定一个唯一的输入符号a a i i 与其对应与其对应 。 即即 F F（b b j j ）= = a a i i i i =1=1，2 2，r r j j =1 =1，2 2，s s 注：对于同一有噪信道共有注：对于同一有噪信道共有 r r s s 种种译码规则可供选择。译码规则可供选择。 例例5.15.1： 可设计译码准则可设计译码准则 译码准则译码准则 A A： 译码准则译码准则 B B： 译码规则总数为：译码规则总数为： r r s s = = 2727 目标：在目标：在 r r s s 个规则中找到理想的一个。个规则中找到理想的一个。 原则：使平均错误概率最小。原则：使平均错误概率最小。 平均错误概率平均错误概率 P PE E 如何计算？ 如何计算？ 收到符号收到符号b b j j 条件下译码正确的条件概率为条件下译码正确的条件概率为 平均错误概率平均错误概率P PE E ： ： 条件错误概率条件错误概率 对输出空间对输出空间Y Y 取统计平均取统计平均 物理意义：译码后平均收到一个符号所产生的错误的大物理意义：译码后平均收到一个符号所产生的错误的大 小小 要使要使P PE E 最小就应该选择 最小就应该选择p p F F( (b b j j )| )|b b j j 为最大为最大 。 最大后验概率准则（最小错误概率准则）最大后验概率准则（最小错误概率准则） 选择译码函数：选择译码函数： 译码：将每一个输出符号译成具有最大后验概率译码：将每一个输出符号译成具有最大后验概率 的的 输入符号，则信道的错误概率此时最小。输入符号，则信道的错误概率此时最小。 分析：分析： 则则最大后验概率准则可另表述为最大后验概率准则可另表述为 选择译码函数选择译码函数 使成立使成立 最大似然译码准则最大似然译码准则（最大后验概率准则最大后验概率准则特例）特例） 设输入符号的先验概率等概，选择译码函数设输入符号的先验概率等概，选择译码函数 使成立使成立 译码：当收到译码：当收到 b b j j 后后，译成信道矩阵中第，译成信道矩阵中第 j j 列中最大列中最大 的元素所对应的信源符号。的元素所对应的信源符号。 最大后验概率准则最大后验概率准则：依赖于先验概率：依赖于先验概率p p( (a a i i ) )和信道和信道 传递概率传递概率p p( (b b j j | |a a i i ) )选定译码函数。选定译码函数。 最大似然译码准则最大似然译码准则：直接从信道矩阵的传递概：直接从信道矩阵的传递概 率中去选定译码函数。率中去选定译码函数。 当先验概率当先验概率p p( (a a i i ) )为等概率分布时，最大似然译码为等概率分布时，最大似然译码 准则与最大后验概率准则等价。准则与最大后验概率准则等价。 平均错误概率平均错误概率P P E E 与译码规则（译码函数）有关。与译码规则（译码函数）有关。 而译码规则又由信道特性来决定。而译码规则又由信道特性来决定。 费诺不等式费诺不等式 HH（X X | | Y Y） HH（P P E E ）+ + P PE E log ( log (r r1)1) 重复发送重复发送大数判决规则大数判决规则 信息数据 编码1编码2 000000000000000000000 001000000111001001001 010000111000010010010 011000111111011011011 100111000000100100100 101111000111101101101 110111111000110110110 111111111111111111111 错误概率与编码方法错误概率与编码方法 编码编码1 1：将每个码元重复三次：将每个码元重复三次 纠正任一位上的错误纠正任一位上的错误 设码字记为设码字记为 由编码方法知由编码方法知 “择多译码择多译码”规则的依据规则的依据： 连续出现两个错误的连续出现两个错误的 概率概率 远远小于出现一个错误的概率。远远小于出现一个错误的概率。 编码编码2 2：将每个码字重复三次：将每个码字重复三次 纠正任一位上的错误纠正任一位上的错误 纠正连续三位和三位以下码元的错误纠正连续三位和三位以下码元的错误 由编码方法知由编码方法知 例例 发送的码字为发送的码字为 0 1 0 0 1 0 0 1 00 1 0 0 1 0 0 1 0 干扰后收到为干扰后收到为 0 1 1 1 0 0 0 1 00 1 1 1 0 0 0 1 0 此时此时 以上这两种重复码编码后的信息传输率相同为以上这两种重复码编码后的信息传输率相同为 但纠错能力不同，平均但纠错能力不同，平均错误概率错误概率不同。不同。 如何选择编码规则呢？如何选择编码规则呢？ 例：对例：对 4 4个等概消息编码个等概消息编码 M = 4 第种M = 4 第种 0 0 0 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 1 0 1 0 0 M = 4 第种 0 0 0 0 1 1 1 0 1 1 1 0 最大似然译码规则下，计算平均错误概率最大似然译码规则下，计算平均错误概率P P E E = =？ 0.01 0.99 0.99 0.01 M = 4 第种 0 0 0 0 0 1 0 1 0 1 0 0 在选择编码规则时，要使码字之间的最小距离在选择编码规则时，要使码字之间的最小距离D Dmin min越 越大大 越好。越好。 结论：错误概率与编码方法有关。结论：错误概率与编码方法有关。 码码 A码码 B码码 C码码 D码码 E 码码字 000 111 000 011 101 110 000 001 010 100 00000 01101 10111 11010 000 001 010 011 100 101 110 111 码码字长长度 n 33353 消息数 M 24448 码码的最小距离 Dmin 32131 信息传输传输 速率R （比特/符号） 1/32/32/32/51 错误错误 概率PE （最大似然译码译码 ） 310-4210-22.2810-27.810-4310-2 能不能找到一种编码方法使能不能找到一种编码方法使P P E E 相当低（可靠性高），而相当低（可靠性高），而R R却保持在却保持在 一定水平（有效性较高）呢？一定水平（有效性较高）呢？ 定理定理5.1 5.1 香农第二定理（信道编码定理）香农第二定理（信道编码定理） 设某信道有设某信道有r r个输入符号，个输入符号，s s个输出符号，信道容量为个输出符号，信道容量为C C。 当信息传输率当信息传输率R RC C时，只要码长时，只要码长n n足够长，总可以在输入足够长，总可以在输入 的集合中找到的集合中找到MM个码字（代表个码字（代表MM个等可能性的消息）组成个等可能性的消息）组成 的一个码（的一个码（ MM22n n( (C - C -) )，而 ，而 是一任意小的正数是一任意小的正数 ）和相应的）和相应的 译码规则，使信道输出的错误概率译码规则，使信道输出的错误概率P P E E 任意小。任意小。 定理定理5.2 5.2 （信道编码逆定理）设某信道有（信道编码逆定理）设某信道有r r个输入，个输入，s s个输个输 出，信道容量为出，信道容量为C C，令