第5章 信源编码2.ppt

信源编码（主要内容） 信源编码定理 信源编码基本概念 定长信源编码 变长信源编码 信源编码方法 离散信源编码 连续信源编码 相关信源编码 变换编码 变长编码 特点： 在码符号序列长度L不很大的时候，就能达到很高的编码效率。 完全无失真的编码。 要求： 变长码要满足唯一可译码的条件，它必须是非奇异码，而且任意有限长L次扩展码也应该是非奇异码。 为了能够即时译码，变长码必须是即时码。 克拉夫特不等式（1949年） 克拉夫特不等式描述了信源符号数和码字长度之间应满足什么条件才能构成即时码。 麦克米伦不等式（1956年） 可将克拉夫特不等式的结果推广到唯一可译码的情况： 定理 在前一定理所给定的条件下，唯一可译码存在的充要条件是 此不等式称为麦克米伦不等式 说明 如果码字长度和码符号数满足克拉夫特（或麦克米伦）不等式时，必可构造出即时码（或唯一可译码），否则不能构造出即时码（或唯一可译码）。 但是，该定理并不能作为判别一种码是否为即时码（或唯一可译码）的判据。 例如：码字中有两个码字长度相同，则这两个码字无论是否相同，都可能使不等式成立。但是，当这两个码字相同时，显然不可能是唯一可译码。 唯一可译码的判断 用唯一可译码的定义来判断：如果一种码不是唯一可译码，则必然存在有争议码符号序列，可以被解释成两种或两种以上的码字序列 判断方法：对码C中的每一个码字，求其它码字对这个码字的所有尾随后缀，如果尾随后缀中存在码字或码字序列，则不是唯一可译码；如果遍历完所有的码字，尾随后缀中都没有码字或码字序列，那么就是唯一可译码 唯一可译码的判断 【例1】 对于0，因为0不是其它码字的前缀，所以其它码字对于0没有尾随后缀 再对于10，求尾随后缀 唯一可译码的判断 【例2】 00虽然不是码字，但是码字序列 唯一可译码的判断 【例3】 01虽然不是任何码字，但是可以分解成0和尾随后缀1 唯一可译码的判断 【例4】 是唯一可译码 平均码长 定义 设有信源 编码后的码字分别为W1 ，W2，…，Wn，各码字相应的码长分别为k1，k2，…，kn。因为是唯一可译码，信源符号xi和码字Wi是一一对应的，则这个码的平均长度为： 变长无失真信源编码定理 变长无失真信源编码定理即香农第一定理 定理 设离散无记忆信源为 变长无失真信源编码定理（续） 变长无失真信源编码定理－理解 推广到普通信源 变长无失真信源编码定理可以推广到平稳遍历的有记忆信源，一般离散信源或马尔可夫信源，有 其中，H∞为有记忆信源的极限熵 定长编码是变长编码的一个特例，定长编码定理也可以统一到香农第一定理。 变长编码的编码信息率R’ 定义变长编码的编码信息率为： 它表示编码后平均每个信源符号能载荷的最大信息量。 香农第一定理又可以表述为： 若H(X)≤R’H(X)+ε，就存在唯一可译的变长编码。 若R’H(X)，则不存在唯一可译的变长编码。不能实现无失真的信源编码。 编码效率和剩余度 变长编码举例 变长编码举例—续 变长编码举例—续 变长编码举例—续 用同样方法可进一步对信源X的三次和四次扩展信源进行编码，并求出其编码效率为： η1=0.811比特/二元码符号 η2=0.961比特/二元码符号 η3=0.985比特/二元码符号 η4=0.991比特/二元码符号 对于同一信源，要求编码效率都达到96％，比较 变长码只需对二次扩展信源（L = 2）进行编码； 而等长码则要求L大于4.13X107 . 很明显，用变长码编码时，L不需很大就可以达到相当高的编码效率，而且可实现无失真编码。 信源与信道的匹配 从定量的角度，分析信源编码是如何实现信源与信道的匹配的 研究信源编码时，只考虑信息传输的有效性，所以可以把信道编解码和信道看做无噪无损信道 信源与信道的匹配 从信道的角度分析，对于无噪无损信道，噪声熵和损失熵都为0， ，最佳输入分布为等概率分布 信道的输入是码符号序列Y，信息传输率： 信源与信道的匹配 再从信源编码的角度分析，根据香农第一定理，当编码效率 时（即编出最佳码时），平均码长达到最短的极限值 将（2）代入到（1）中，有 信息传输率达到了最大值，即信道容量 信源与信道的匹配 信源与信道匹配的分析中，得到了两点结论： 在信源编码中，编码效率越高，编出来的码在信道中传输时信息传输率越高 ，实现了信源与信道的匹配 信源编码后满足信道的最佳输入分布，实际上是码符号满足信道的最佳输入分布，码符号集中的各码符号等概率分布，满足了无噪无损信道的最