Kraft 不等式的证明
这其实是一个引理
引出最优信源符号编码定理与编码方法( Huffman,Shannon-Fano )。
( Kraft不等式 ) 给定正整数
而且,在式 (
证明:
充分性(
[1]中的方法:
把所有可能的码字列出来构成一个码树,所示如下:
由于是前缀码,一旦大的被选择了,后面小的就不能被选了,蓝色的加在一起的高度不能超过 1。每一个被选择的块的高度为
[2]中的方法:
难点就是从大到小对码长排序依次放缩。
必要性(
利用不同的码字组合在一起得到的序列也是不同的这个性质既可以得到。