研究生 信息论课件

《研究生 信息论课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、5.2.2变长编码定理31256005张文娜知识点回顾：（1）每个符号输出的码长是（2）编码效率为什么对符号进行变长编码呢？对同一编成同一码符号的即时码或一维可译码有多种。究竟哪一种好呢？从高效传输信息的的观点来考虑，当然希望由短的码符号组成的码字，这就是用码长作为选择的准则，为此我们引入了码的平均长度。变长编码定理也称香农第一定理。在变长编码中，码长K是变化的，根据信源各个符号的统计特性，如概率大的符号用短码，概率小的用较长的码，使得编码后平均码长降低，从而提高编码效率。设信源为编码后的码字为其码字长度为因为对唯一可译码来说，信源符号与码字是一一对应的，所以有则这个码的平均长

2、度为的单位是码符号或信源符号。它是每个信源符号平均需用的码元数。从工程观点来看，总希望通信设备经济，简单，并且单位时间内传输的信息量越大越好。当信源给定时，信源的熵就确定了，而编码后每个信源符号平均用个码元来变换。那么平均每个码元携带的信息量即编码后信道的信息传输率为（比特

3、码符号）若传输一个码符号平均需要t秒，则编码后信道每秒钟传输的信息量为（比特

4、秒）由此可见越短，越大，信息传输效率越高。为此，我们感兴趣的码是使平均长度为最短的码。对于某一信源和某一符号集来说，若有一个唯一可译码，其平均长度小于所有其他一维可译码的平均长度，则该码称为紧致码，或称最佳码。无失真信源编码的基本

5、问题就是要找紧致码。现在我们找紧致码的平均长度可能达到的极限理论。单个符号变长编码定理：若离散无记忆信源的符号熵为H(X)，每个信源符号用m进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式上式找了紧致码的平均码长可能达到的极限。定理告诉我们平均长度不能小于极限值否则唯一译码器不存在。定理又给出了平均编码的上界。但不是说大于这个上界不能构成唯一可译码，而是因为我们希望尽可能短。定理说明，当平均码长小于上界时唯一可译码也存在。而且这个最短平均码长与信源熵是有关的。另外我们还可以看出，这个极限值与等长编码定理的极限值是一致的。定理证明：分为两部分，首先证

6、明下界，然后证明上界。[1]下界证明根据平均长度定义及熵的定义得推倒中的不等式是根据詹姆森不等式得出的。因为总可以找到一种唯一可译码，它的码长满足克拉夫特不等式，所以于是证得由证明过程知，上述等式成立的条件是取对数得可见，只有当我们能够选择每个码长等于时，才能达到这个下界值。由于必须是正整数，所以必须是正整数。这也就是说，当等式成立时，每个信源符号的概率必须呈现的形式。如果这个条件满足则只要选择等于，然后根据这些码长，就可以按照树图法构造出一种唯一可译码，而且所得的码一定是紧致码。[2]下界证明只需证明可以构造一种唯一可译码满足不等式即可。首先令然后选取每个码字的长度的原则是，

7、若是整数，取；若不是整数，选取满足的整数，即选择码长满足[x]表示不小于x的最小正整数。因此得码长满足将上式对所有的i求和，左边的不等式既是克拉夫特不等式。因此，用这样选择的码长满足克拉夫特不等式，可构造一维可译码。但所得码并不一定是紧致码。式右边不等式为两边乘以并对i求和可得因而由此得到证明，平均码长小于上界的一维可译码存在。[证毕]式中熵H（X）与logm的信息量单位必须一致。若以m进制为单位，则上式可写成从单位来看的单位仍是码符号

8、信源符号，与平均长度是一致的。单个符号离散平稳无记忆序列变长编码定理变长编码定理证明：单符号变长编码定理：设用m进制码元做变长编码，序列长度为

9、L个信源符号的平均码字长度为已知平均输出信息率为则当L足够大时，可得离散平稳无记忆序列变长编码定理：对于平均符号熵为HL(X)的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息率满足不等式其中为任意小正数。离散平稳无记忆序列变长编码定理是香农信息论的主要定理之一。定理指出，要做到无失真的信源编码，变换每个信源符号平均所需最少的r元码元数就是信源的熵值。若编码的平均长度小于信源的熵值，则唯一可译码不存在，在译码或反变换时必然要带来失真或差错。同时，定理还指出，通过对信源进行变长编码，当N趋于无穷时，平均码长可达到这个极限值。可见，信源的信息熵是无失真信源压缩的极限值。也

10、可认为，信源的信息熵是描述信源每个符号平均所需最少的比特数。为了衡量各种编码矩极限压缩值的情况，我们定义变码长的编码效率。设对信源S进行编码所得到的平均长度为，因为一定是大于或等于所以定义编码效率为平均码长与极限值之比，一般对于平稳有记忆信源有对于无记忆信源则有式中是小于或等于1的数。对同一信源来说，若码的平均长度越短，越接近极限值，信道的信息传输率就越高，就越接近无噪无损信道容量，这时也就越接近于1，所以可以用码的效率来衡量各种编码的优劣。另外，未了衡量各种编码与最佳码的差距，定义码的剩余