04统计编码.doc

Entropy Coding CUI HUIJUAN 第四讲 统计编码 ? 讲课 i?1,?,M ? 信源的熵(平均信息量)： H(X)??pilog2(1/pi) i?1 MM ???pilog2pi i?1 H(X)是信源的平均信息量，叫做信源的熵，它的单位是比特 (若式中的对数以2为底)。 例：4符号信源，a1,a2,a3,a4出现的概率分别为0.5, 0.25, 0.125和0.125，其熵为 H(X)??(0.5log20.5?0.25log20.25?2?0.125log20.125)=1.75比特/符号 当4个符号出现概率等概时（0.25），可以算出信源熵为2比特/符号。 ? 当信源各符号出现概率相等时，信源具有最大熵。 ? 熵的范围为： 1 Entropy Coding CUI HUIJUAN 0?H(X)?log2N ? 在编码中用熵值衡量是否为最佳编码。若以 表示编码器输出码字的平均码长，则当 gt;gt;H(X)：有冗余，不是最佳编码； lt;H(X)：不可能； ?H(X)：最佳编码 (稍大于H(X))。 ? 无损编码定理 离散信源X无损编码所能达到的最小速率不能低于该信源的信源熵，即： min{R}?H(X)?? ? 信源编码定理（有损编码定理） ? 对于给定的信源，在允许一定的失真D情况下，存在一失真率函数R(D)，当编码速率R不低于R(D)时，编码失真能够不大于D。 ? R(D)一般不容易计算。 ? 该定理也没有给出编码方法。 R H(Xmax率失真函数 图4－1率失真示意图 2. 定长编码 ? 定长编码对每个符号使用等长码字编码，而不考虑其概率。 例：5电平量化器，a1,a2,a3,a4,a5代表5个量化电平， ? 若用000，001，010，011和100表示， ? 设它们出现概率相同，那么信源熵为：H(X)?5?0.2log2(1/0.2)?? 如果每3个信源符号合成一组进行编码，那么共有125种组合符号，可以用7bit编码，平均每个信 源符号用2.33比特/每个信源符号。 ? 随着分组长度加长，平均每信源符号所需编码比特数将趋向信源熵，编码复杂度和延时也增加。 3．霍夫曼编码 ? 变字长编码的最佳编码定理：在变字长码中，对于概率大的信息符号编以短字长的码；对于概率小的 信息符号编以长字长的码。如果码字长度严格按照符号概率的大小的相反顺序排列，则平均码字长度一定小于按任何其他符号顺序排列方式得到的码字长度。 证明：设最佳排列方式的码字平均长度为，则有 ??nip?ai? 式中Mp?ai?为信源符号ai出现的概率，ni是ai的编码长度。规定p?ai??p?as?，ni?ns，i?1 2 Entropy Coding CUI HUIJUAN i?1,2,?,m，s?1,2,?,m。如果将ai的码字与as的码字互换，其余码字不变，其平均码字 长度变为，即 ‘ ‘???nip?ai??nsp?as????nsp?ai??nip?as?? ???ns?ni??p?ai??p?as??’ 因为ns?ni，p?ai??p?as?，所以?，也就是说是最短的。 霍夫曼编码就是利用了这个定理，将等长分组的信源符号，根据其概率采用不等长编码。概率大的分组，使用短的码字编码；概率小的分组，使用长的码字编码。霍夫曼编码把信源符号按概率大小顺序排列，并设法按逆次序分配码字的长度。在分配码字的长度时，首先将出现概率最小的的两个符号的概率相加，合成一个概率；第二步把这个合成的概率看成是一个新组合符号的概率，重复上述做法，直到最后只剩下两个符号的概率为止。完成以上概率相加顺序排列后，再反过来逐步向前进行编码。每一步有两个分支，各赋予一个二进制码，可以对概率大的编为0码，概率小的编为1码。反之亦然。 霍夫曼编码的具体步骤归纳如下： (1) 统计概率，得n 个不同概率的信息符号。 (2) 将 n 个信源信息符号的 n 个概率，按概率大小排序。 (3) 将n 个概率中，最后两个小概率相加，这时概率个数减为n －1 个。 (4) 将n－1个概率， 按大小重新排序。 (5) 重复(3)，将排序后的最后两个小概率再相加，相加和与其余概率再排序。 (6) 如此反复重复n－2 次， 最后只剩两个概率。 (7) 分配码字。由最后一步开始反向进行，依次对“最后”两个概率一个赋予“0”码，一个赋予“1”码。 构成霍夫曼编码字。编码结束。 ? 霍夫曼编码产生最佳整数前缀码，即没有一个码字是另一个码字的前