第5章_无失真信源编码定理-2005-9汇编.ppt

而其依赖关系为： 传递矩阵 理解 若不考虑符号间的依赖关系，可得码长l＝2 若考虑符号间的依赖关系，则对此信源作二次扩展 可见，由于符号间依赖关系的存在，扩展后许多符号出现的概率为0，此信源只有4个字符，可得码长 ，平均每个信源符号所需码符号为 理解 考虑到英文字母间的相关性，对信源作N次扩展，在扩展后的信源(也就是句子）中，有些句子是有意义的，而有些句子是没有意义的，可以只对有意义的句子编码，而对那些没有意义的句子不进行编码，这样就可以缩短每个信源符号所需的码长。 等长信源编码定理给出了进行等长信源编码所需码长的极限值。 例：英文电报 了解 5.4 等长信源编码定理 信源编码有等长和变长两种方法。 等长编码：码字长度是固定的，相应的编码定理称为 定长信源编码定理，是寻求最小码字长度 的编码方法。 变长编码：码字长度是变值，相应的编码定理称为变 长编码定理。这里的码字长度最小意味着 数学期望最小。 理解 了解 定理中的公式改写成 不等式左边表示长为L的码符号序列能载荷的最大信息量， 右边代表长为N的信源序列平均携带的信息量。 所以定长编码定理告诉我们：只要码字传输的信息量大于信源携带的信息量，总可实现几乎无失真编码。 了解 最佳编码效率为： 编码效率： 编码后信源的信息传输率： 了解 当允许错误概率小于δ时，信源符号序列的长度N： 为自信息的方差 如果为最佳编码，则 由式5.32 了解 例5-1：设离散无记忆信源 求信源序列的长度。 对S采取等长二元编码，要求编码效率 允许错误概率 了解 5.5 变长码 5.5.1 唯一可译变长码与即时码 优点： 变长码往往在N不很大时就可编出效率很高而且无失真的码。 5.5 变长码 5.5.1 唯一可译变长码与即时码 变长码的要求： 变长码必须是唯一可译码，才能实现无失真编码。 变长码不但码本身必须是非奇异的，而且其任意有限长N次扩展码也都必须是非奇异的。所以唯一可译变长码的任意有限长N次扩展码都是非奇异的。 了解 信源符号ai 符号出现概率p(ai) 码1 码2 码3 码4 a1 1/2 0 0 1 1 a2 1/4 11 10 10 01 a3 1/8 00 00 100 001 a4 1/8 11 01 1000 0001 观察表中的各个码。 表5.4 掌握 码2二次扩展 掌握 掌握 掌握 5.5.2 即时码的树图构造法 即时码的一种简单构造方法是树图法。 对于给定码字的全体集合C，可用码树来描述它。 所谓树，既有根、枝，又有节点。 图中最上端A点为根，从根出发向下伸出树枝，树枝的数目等于码符号的总数r。 树枝的尽头为节点，从节点出发再伸出树枝，每次每个节点伸出r枝，依次下去构成一棵树。 了解 在下图中，当某一个节点被安排为码字后，就不再继续伸枝，此节点称为终端节点(用粗黑点表示)。 其他节点称为中间节点，不安排为码字(用空心圈表示)，给每个节点所伸出的树枝分别从左向右标上码符号0，1，…，r。 了解 任一即时码都可用树图法来表示。 当码字长度给定时，即时码不是唯一的。 在每个节点上都有r个分枝的树称为整树（满树），否则称为非整树（非满树）。 了解 了解 5.5.3 克拉夫特（Kraft)不等式 掌握 例：设二进制码树中X={ ， ， ， } ，对应的 ， ， ， ，由上述定理，可得 因此不存在满足这种码长的唯一可译码。 掌握 a1=1 0 1 0 1 0 1 a2=01 a3=001 a4=000 {1，01，001，001} 惟一可译码； {1，01，010，000} 不是惟一可译码； 均满足克劳夫特不等式 掌握 注意：不满足克拉夫特不等式的码，一定不是唯一可译码。码长满足克拉夫特不等式的码，也不一定是唯一可译码。 克拉夫特不等式只是说明唯一可译码是否存在，并不能作为一种码制是否是唯一可译码的判断依据。 了解 第5章 无失真信源编码定理 邹小林 2015.11. 通信的实质是信息的传输。 高效率、高质量传送信息是信息传输的基本问题！ 需要解决两个问题： 第一，在不失真或允许一定失真的条件下，如何