信息论课件chap以第一定理为指导无失真信源压缩的

上次课q 及相关概 qKraft不等

r i 码

H(S)1LNH(Slog log log (i1, ,q p(s

Pi pk码 码的编码步骤1）将个信源符号按概率递减的方式进行排列p1p2 第一定理计算出每个信源符号的码长 iPi k1将累加概率Pi用二进制数表示取Pi对应二进制数的小数点后符号的二进制码

位构成该3码的编码步骤如下信源符号以概率递减的次序排列起来将排列好的信源符号按概率值划分成两大，使每组的概率之和接近于相等，并对每予一个二元码符号“0”和5信源符号所对应的码字即 码4 1952年，（Huffman）提出了一种符号的编码方法，一般称作码。设编码对象为离散S{s1,s2,...,其对应的概率分p(si){p1,p2,...,pq}则对二 码而言，其编码步骤如下5编码步骤（对二元系统将q个信源符号按概率递减的方式排列起来用“0”,1”得到只包含1；S0，“缩减信源；0，“1”;从最后一级缩减信源开始，向前返回，得出各信源所对应的码符号序列，即得出对应的码字 例:对离散 信

s2s3s4s50s2s3s4s50. 0. 0. 0. 0.1 进 编码为下面的信源符号为“1”上面的信源符号为“0”。从概率等于“1.0”端沿合并路线逆行至对应消息编码78信源的熵为：H(S2.12(比特／符号从li123,45

p(ai)li

2.编码效率为： H(S) 0.96L9[例]将下列消息按二 方法编

a7p(a

01

0.61

a5a2

a5 l1a2 l11a6 1 0

a6

llla30.100 0.011

a3→0110la7→0111l：

a7p(a 7可求出信源的熵7H(Sp(ailogp(ai2.61(比特/符号i

a5 l从：l=(2,2,3,3,3,4,4)可求得平均码长为a2

l7Lp(ai)li2.72(二元码符号/信源符号7i编码效率H(S)

a6

lll

a3→0110la7→0111l1 码的编码方法，可知这种码有如下特征①它是一种分组码：各个信源符号都被映射成一组固定次序的码符号；②它是一种即时码：一串码符号中的每个码字都可不考其后的符号解③它是一种惟一可译码：任何码符号串只能以码

式 la2 la6 码串可通过从左到右检查各个

ll符号进行译码。本例中000110110101011可译

l

a3→0110la7→0111l码是一种即时码，可用码树形式来表示“1”码是可以任意的，所以可得到不同的码，码长li对给定信源，编码方法得到的码并非但平均码长不[例]离散 信

s5p(s

信 编

概

缩减信源 0.4

00.4

0.20.1 10.1

1按概率分布的大小递减次

将概率最小的两个信源符号分别用“个符

从最后一级缩 s5p(s)

4所 码的平均码长为5Lp(si)li0.410.220.230.140.152.2（二元符号信源符号编码效率

H(S)L对应的码树

信源

曼编码所得的码一定时码0

第二 码信 编 概 0

缩减信源

0.6

0.4

0.4

0.2

源开始向前返回缩减信源中合并的概率排列在这时各码字长度分别为2，2，2，3，35

得出各信源符号应的码平均码长为：Lp(si)li0.40.20.2)20.10.12.2（二元信源符号上述编上述编码的码树如图

同样可得

信 编 概

两种编码方法比较 树结构如右图所示 ；平均码长相同→编码效率相；每个信源符号的码长却不编码选择依据：码长li偏离平均长度L的方差q2E[(lL)2]p(s)(lL 2本例中，第一种编码2＝1.366，第二种编码2＝0.16，后 编码过程中，当缩减信源的概率分布重新排列时，使合并得来的概率和尽量处于最高的位置，这样可使合元素重复编码次数减少，使短码得到充分利用 码的 码，概率小的符号对应于长码，即pj＞pk→ljlk同，前面各位码元相同(二元编码情况)。每次缩减信源的最长两个码字有相r 不同的只是每次把r个符号(概率最小的)合并成一个新的信源符号，并分别用0，1，…，(r-1)等码元表示。r因此对于r元编码，信源S的符号个数q必须满足q＝n(r-1)+n表示缩减的次数，(r-1)为每次缩减所减少的信源符数对于二元码(r＝2)，信源符号个数q必须满足q＝n+因此q可等于任意整正数 而对于r元码（r2）时，不一定能找到一个nq＝n(r-1)r成立。q不满足上式时，可设一sq1,sq2,...,sqtpq1

...pqt

虚拟的信qt＝n(r-1r能成立这样得到的r 码一定 码

方法及其对应的码字 q＝n(r-1)+表中s9s10假设的信源符号，这样q+t=10，能找到n=2。该四 码的码树，如图所示q＝n(r-1)+r时，所得从图可知，当信源符号个数qq＝n(r-1r，则得到r元码树一定是整树。所以，二元码树一定节点，。至此讨论的三种编码方法中 编码方法所求得的二进制码组集合是唯一的，即有信源符号