研究生信息论课件.pptVIP

5.2.2 变长编码定理张文娜 知识点回顾： （1）每个符号输出的码长是 （2）编码效率 为什么对符号进行变长编码呢？ 对同一编成同一码符号的即时码或一维可译码有多种。究竟哪一种好呢？从高效传输信息的的观点来考虑，当然希望由短的码符号组成的码字，这就是用码长作为选择的准则，为此我们引入了码的平均长度。 变长编码定理也称香农第一定理。在变长编码中，码长K是变化的，根据信源各个符号的统计特性，如概率大的符号用短码，概率小的用较长的码，使得编码后平均码长降低，从而提高编码效率。 设信源为 编码后的码字为 其码字长度为 因为对唯一可译码来说，信源符号与码字是一一 对应的，所以有 则这个码的平均长度为 的单位是码符号或信源符号。它是每个信源符号平均需用的码元数。 从工程观点来看，总希望通信设备经济，简单，并且单位时间内传输的信息量越大越好。 当信源给定时，信源的熵就确定了，而编码后每个信源符号平均用 个码元来变换。那么平均每个码元携带的信息量即编码后信道的信息传输率为 （比特|码符号） 若传输一个码符号平均需要t秒，则编码后信道每秒钟传输的信息量为 （比特|秒） 由此可见 越短， 越大，信息传输效率越高。为此，我们感兴趣的码是使平均长度 为最短的码。 对于某一信源和某一符号集来说，若有一个唯一可译码，其平均长度 小于所有其他一维可译码的平均长度，则该码称为紧致码，或称最佳码。无失真信源编码的基本问题就是要找紧致码。 现在我们找紧致码的平均长度 可能达到的极限理论。 单个符号变长编码定理：若离散无记忆信源的符号熵为H(X)，每个信源符号用m进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式 上式找了紧致码的平均码长 可能达到的极限。 定理告诉我们平均长度不能小于极限值 否则唯一译码器不存在。 定理又给出了平均编码的上界。但不是说大于这个上界不能构成唯一可译码，而是因为我们希望 尽可能短。定理说明，当平均码长小于上界时唯一可译码也存在。而且这个最短平均码长 与信源熵是有关的。 另外我们还可以看出，这个极限值与等长编码定理的极限值是一致的。 定理证明：分为两部分，首先证明下界，然后证明 上界。 [1]下界证明 根据平均长度定义 及熵的定义得 推倒中的不等式是根据詹姆森不等式得出的。 因为总可以找到一种唯一可译码，它的码长满足克拉夫特不等式，所以 于是证得 由证明过程知，上述等式成立的条件是 取对数得 可见，只有当我们能够选择每个码长 等于 时， 才能达到这个下界值。 由于 必须是正整数，所以 必须是正整数。这也就是说，当等式成立时，每个信源符号的概率 必须呈现 的形式。 如果这个条件满足则只要选择 等于 ，然后根据这些码长，就可以按照树图法构造出一种唯一可译码，而且所得的码一定是紧致码。 [2]下界证明只需证明可以构造一种唯一可译码满足 不等式 即可。 首先令 然后选取每个码字的长度 的原则是，若 是整数，取 ；若 不是整数，选取 满足 的整数，即选择码长满足 [x]表示不小于x的最小正整数。因此得码长满足 将上式对所有的i求和，左边的不等式既是克拉夫特不等式。 因此，用这样选择的码长 满足克拉夫特不等式，可构造一维可译码。但所得码并不一定是紧致码。 式 右边不等式为 两边乘以 并对i求和可得 因而 由此得到证明，平均码长小于上界的一维可译码存在。[证毕] 式中熵H（X）与logm的信息量单位必须一致。若以m进制为单位，则上式可写成 从单位来看 的单位仍是码符号|信源符号，与平均长度是一致的。 单个符号 离散平稳无记忆序列 变长编码定理 变长编码定理 证明：单符号变长编码定理： 设用m进制码元做变长编码，序列长度为L个信源符号 的平均码字长度为 已知平均输出信息率为 则 当L足够大时，可得 离散平稳无记忆序列变长编码