码字比较 倍源符号 信源符号 等长偏码 变长编码 信息熵 出现概率 CI C2 A 0.6 00 0 H(X)=-∑P(s)Iog,(P()月 2 0.25 01 10 0.1 10 110 =1.4905bit/符号 D 0.05 11 1110 平均码字长度 E1=2×0.6+2×0.25+2×0.1+2×0.05=2 2=1×0.6+2×0.25+3×0.1+4×0.05=1.6 ·编码效率， =H0=74.52% %=I0=93.16% K 6
6 码字比较 信源符号 信源符号 出现概率 等长编码 C1 变长编码 C2 A 0.6 0 0 0 B 0.25 0 1 1 0 C 0.1 1 0 1 1 0 D 0.05 1 1 1 1 1 0 1 2 2 0.6 2 0.25 2 0.1 2 0.05 2 1 0.6 2 0.25 3 0.1 4 0.05 1.6 K K • 平均码字长度 • 信息熵 2 1 log 1.4905 bit/ n i i i H X P x P x 符号 • 编码效率 1 2 ( ) 74.52% ( ) 93.16% H X K H X K
变长编码 冬最佳编码： ■对于某一信源和某一码符号集来说，若有一唯一 可译码，其平均码长小于所有其他唯一可译码的 平均长度。 冬三种变长编码 香农(Shannon)编码 ■费诺(Fano)编码 ■哈夫曼(Huffma)编码
7 变长编码 v最佳编码： § 对于某一信源和某一码符号集来说,若有一唯一 可译码,其平均码长小于所有其他唯一可译码的 平均长度。 v三种变长编码 § 香农(Shannon)编码 § 费诺(Fano)编码 § 哈夫曼(Huffma)编码
香农编码 冬二进制香农码的编码步骤如下： 1.将信源符号按概率从大到小的顺序排列， p(a1)≥p(a2)≥.≥p(an) 2.确定满足下列不等式的整数K, -log2 p(ai)<Ki<1-log2 p(aj) 3.令p(a1)=0,用P表示第个码字的累加概率， 1-1 P->p(a.) k= 4.将P用二进制表示，并取小数点后K位作为符号a的编 码
8 v二进制香农码的编码步骤如下： 1.将信源符号按概率从大到小的顺序排列, p(a1)≥ p(a2)≥…≥ p(an) 2.确定满足下列不等式的整数Ki , -log2 p(ai)≤ Ki <1-log2 p(ai) 3.令p(a1)=0,用Pi 表示第i个码字的累加概率, 4.将Pi 用二进制表示,并取小数点后Ki 位作为符号ai 的编 码。 香农编码 1 1 ( ) i i k k P p a
香农编码 ·例：有一单符号离散无记忆信源 x X2 X3 X4 X5 0.40.30.20.050.05 对该信源进行二进制香农编码，其过程如表所示： 信源符号 累加 码 以i=3为例 符号 機率 機率 -log p(x 长 码字长度： 码字 K3=[l0g0.2]=3 X P(xi) P K 累加视Q X 0.4 0 1.32 2 00 =0ζ9-9 .10110. X2 0.3 0.4 1.73 2 01 X3 0.2 0.7 2.32 3 101 101 11100 X4 0.05 0.9 4.3 5 11100 X5 0.05 0.95 这些码字没有占满所有树叶， 11110 所以不是最佳变长编码
9 • 例: 有一单符号离散无记忆信源 • 对该信源进行二进制香农编码，其过程如表所示： 以i = 3为例: 码字长度： K3 = [-log0.2] = 3 累加概率 Pi=0.70 → 0.10110… 00 01 101 11100 11110 信源 符号 xi 符号 概率 p(xi) 累加 概率 Pi -log p(xi) 码 长 Ki 码字 x1 0.4 0 1.32 2 00 x2 0.3 0.4 1.73 2 01 x3 0.2 0.7 2.32 3 101 x4 0.05 0.9 4.3 5 11100 x5 0.05 0.95 4.3 5 11110 1 2 3 4 5 ( ) 0.4 0.3 0.2 0.05 0.05 X x x x x x p x 香农编码 这些码字没有占满所有树叶, 所以不是最佳变长编码
香农编码 ·平均码长： K=∑px)K,=0.4x2+0.3×2+0.2×3+0.05x5x2=2.5 i=1 ·信源熵： H(X)=-0.4log0.4-0.3log0.3-0.2log0.2-2×0.05l0g0.05 =1.95 ·编码效率 H(X)1.95 =78% 2.5 10
10 • 平均码长： 5 1 ( ) 0.4 2 0.3 2 0.2 3 0.05 5 2 2.5 i i i K p x K • 信源熵： ( ) 0.4log0.4 0.3log0.3 0.2log0.2 2 0.05log0.05 1.95 H X • 编码效率 ( ) 1.95 78% 2.5 H X K 香农编码