信息论与编码课件第四章

信息论与编码课件第四章第一页，共三十五页，编辑于2023年，星期六第四章作业

教材第116页~117页

4.2， 4.8(1)(3)第二页，共三十五页，编辑于2023年，星期六编码器S=（s1，s2，…，sq）

C=（W1，W2，…，Wq）

X=（x1，x2，…，xr

）信源符号码字码符号编码器第三页，共三十五页，编辑于2023年，星期六码：特定的符号集合。编码：建立在源符号与码符号或码符号组之间的变换。

3547——>011101100111信源编码：从信源输出符号序列到码符号序列的一种映射，其逆映射称译码。信源编码的目的：适合于信道传输，提高输出效率编码器第四页，共三十五页，编辑于2023年，星期六编码器同价码

非同价码非奇异码奇异码不等长码等长码信源符号si

出现概率pi

码A码B码Cs1p10000s2p20101s3p310100s4p4111011第五页，共三十五页，编辑于2023年，星期六等长编码及其定理唯一可译码：一个码的任意一串有限长的码符号序列只能被唯一地译成所对应的信源符号序列。akp(ak)码A码Ba10.50000a20.250101a30.1251000a40.1251110等长非奇异码一定是唯一可译码第六页，共三十五页，编辑于2023年，星期六对信源S的N次扩展信源SN进行等长编码若S={s1,s2,…,sq}，则N次扩展信源SN={a1,a2,…,aqN}，共有qN个符号序列。设码符号集为X={x1,x2,…,xr}，长度为l的码符号序列Wi=(xi1xi2…xil),xi1,xi2,…,xil∈X。若要求编得的等长码是唯一可译码则必须满足

qN≤rl等长编码及其定理第七页，共三十五页，编辑于2023年，星期六对qN≤rl两边取对数，则得Nlogq≤llogr

或例如英文电报有32个符号（26个英文字母加上6个字符），即q=32。若r=2，N=1(即对信源的逐个符号进行二进制编码)，则等长编码及其定理第八页，共三十五页，编辑于2023年，星期六定理4.1（等长信源编码定理）

对于上述编码，对于任意，只要N充分大，且满足不等式则译码错误概率任意小（可以进行无失真编码）。反之，若则不可能进行无失真编码，且N充分大时，译码错误概率近似等于1。第九页，共三十五页，编辑于2023年，星期六实现无失真编码存在问题：N充分大使存储和处理难度大。解决办法：采用变长编码。等长信源编码定理的意义：

信源的信息熵是（信源冗余度的可压缩性）无失真数据压缩的理论极限。压缩到小于这个极限值，则无失真做不到。等长编码定理第十页，共三十五页，编辑于2023年，星期六不等长编码及其定理不等长编码的基本思想——“量体裁衣”出现概率大的信源符号用较短码字表示，出现概率小的信源符号用较长码字表示。这样平均每个信源符号所需的码符号数降低，提高编码效率。唯一可译码：一个码的任意一串有限长的码符号序列只能被唯一地译成所对应的信源符号序列。即时码：唯一可译码，译码时无需参考后续的码符号就能立即作出译码判断。异前缀码：码中没有码字是任意其他码字的前缀。可以在无延时的情况下解码。异前缀码等价于即时码第十一页，共三十五页，编辑于2023年，星期六不等长编码及其定理第十二页，共三十五页，编辑于2023年，星期六例：

p(ak)码A码B码C码Da10.50000a20.250100110a30.125100011110a40.125100101111110

码A：奇异，非唯一；码B：非奇异，非唯一；码C：唯一，非异前缀；码D：唯一，异前缀，即时码。不等长编码及其定理第十三页，共三十五页，编辑于2023年，星期六异前缀码是唯一可译码中的一类子码，易于构造。异前缀码等价于即时码。即任何一种唯一可译码都可找到相应、同样有效的异前缀码。不等长编码及其定理树图法是构造即时码（异前缀码）的一种简单方法。

22022122210111220210一级节点二级节点三级节点120树根中间节点不能作为码字的终点第十四页，共三十五页，编辑于2023年，星期六定理4.2设信源S={s1,s2,…,sq}，码符号集X={x1,x2,…,xr}，又设码字为（W1，W2，…，Wq），其分别对应的码长为l1，l2，…，lq，则存在唯一可译码的充要条件为Kraft不等式

定理给出了码字长度的下界的限制。第十五页，共三十五页，编辑于2023年，星期六例：

p(ak)码A码B码C码Da10.50011a20.2511101101a30.1250000100001a40.125110110100001r＝2，码A，码B：l1=1,l2=l3=l4=2,这样码A，码B不可能是唯一可译码。r＝2，码C，码D：l1=1,l2=2,l3=3,l4=4,码C不是唯一可译码，码D是唯一可译码。第十六页，共三十五页，编辑于2023年，星期六信源编码有关概念（1）平均码长单位：码符号/信源符号意义：每个源符号平均需要的码符号数。编码后每个信源符号平均用个码符号表示。（2）信息传输率（平均每个码符号携带的信息量）

越短，信息传输率就越高。第十七页，共三十五页，编辑于2023年，星期六（3）最佳码（紧致码）最佳码：对于某一信源和某一码符号集，若有一唯一可译码，其平均码长小于等于所有其他唯一可译码的平均码长，则该码称为最佳码。（最短唯一可译码）

无失真信源编码的基本问题就是找到最佳码，最佳码的平均码长为理论极限。

理论极限是多少呢？第十八页，共三十五页，编辑于2023年，星期六定理4.3（单符号信源的变长编码定理）若有一离散无记忆信源S具有熵H（S），并有r个码符号的符号集X={x1,x2,…,xr}，则总可以找到一种无失真编码方法，构成唯一可译码，使其平均码长满足证明：第十九页，共三十五页，编辑于2023年，星期六第二十页，共三十五页，编辑于2023年，星期六定理4.4（变长无失真信源编码定理----

香农第一定理）离散无记忆信源S的N次扩展信源SN={a1,a2,…,aqN

}，共有qN个符号序列，具有熵H（SN），并有r个码符号的符号集X={x1,x2,…,xr}。若对信源SN（即信源输出的是N长的符号序列）进行编码，总可以找到一种编码方法，构成唯一可译码，使信源S中每个信源符号所需的码字平均长度满足香农第一定理第二十一页，共三十五页，编辑于2023年，星期六由香农第一定理得到平均码长的理论极限：H(S)/logr香农第一定理第二十二页，共三十五页，编辑于2023年，星期六由香农第一定理得到平均码长的理论极限：H(S)/logr香农第一定理的物理意义R等于无噪无损信道的信道容量C。无失真信源编码的实质：对离散信源进行适当的变换，使变换后新的码符号信源（信道的输入信源）尽可能等概率分布，以使新信源的每个码符号平均所含的信息量达到最大，从而使信息传输率R达到信道容量C，实现信源与信道理想的统计匹配。

第二十三页，共三十五页，编辑于2023年，星期六〖例4.1〗有一离散无记忆信源其熵为H(S)=0.811

比特/信源符号，用二进制符号{0，1}来构造一个即时码。s1→0，s2→1。码的效率为η1=0.811信息传输率为R1=0.811比特/二进制符号。对信源S的长为2、3、4的符号序列的符号序列（即N=2、3、4）分别进行变长编码。η2=0.961 R2=0.961比特/二进制符号η3=0.985 R3=0.985比特/二进制符号η4=0.991 R4=0.991比特/二进制符号可见编码复杂一些，使信息传输率提高。第二十四页，共三十五页，编辑于2023年，星期六变长码的编码方法霍夫曼(Huffman)

码Huffman码是异字头码，是一种最佳码。1952年提出，应用于数据压缩，文件传输、语音处理、图象处理。

费诺（Fano）码Fano码不一定是最佳码，但有时也可能是最佳码。

第二十五页，共三十五页，编辑于2023年，星期六霍夫曼码的编码方法二进制霍夫曼码的的编码方法，它的编码步骤如下：（1）将q个信源符号按概率值的大小以递减次序排列起来，设

p1≥p2≥…≥pq（2）用0和1码符号分别代表概率最小的两个信源符号，并将这两个概率最小的信源符号合并一个符号，从而得到包含q－1个符号的新信源--------缩减信源S′。（3）把缩减信源S′的符号仍按概率值大小以递减次序排列，再将其最后二个概率最小的符号合并成一个符号，并分别用0和1码符号表示，这样又得到q－2个符号的新缩减信源S〞。（4）依次继续下去，直至信源最后只剩两个符号为止。将这最后两个信源符号分别用0和1码符号表示。然后从最后一级缩减信源开始，向前返回，就得出各信源符号所对应的码符号序列，即得到对应的码字。第二十六页，共三十五页，编辑于2023年，星期六缩减信源（辅助信源）设信源S，取值于集合其概率分布满足,码为缩减信源S’码为第二十七页，共三十五页，编辑于2023年，星期六例：对下列离散无记忆稳恒信源进行Huffman编码源字母概率码字编码过程a10.4a20.2a30.2a40.1a50.1霍夫曼码编码举例第二十八页，共三十五页，编辑于2023年，星期六霍夫曼码编码举例0001001110101010110010

0011

01100010101010第二十九页，共三十五页，编辑于2023年，星期六霍夫曼码说明：（1）如果出现相同概率的情况，合并后的概率尽量安排处于最高的位置，减少合并元素被重复编码的次数，使短码字充分利用。（2）不同编码后，平均码长相等，取码长偏离平均码长的方差较小的，即

（3）缩减时源符号不够时，补零（概率）后编码。即：信源符号个数应满足

q=θ(r–1)

+r第三十页，共三十五页，编辑于2023年，星期六例：对下列离散无记忆稳恒信源进行4进制Huffman编码源字母概率码字编码过程a10.22a20.20a30.18a40.15a50.10a60.08a70.05a80.02r进制霍夫曼码编码举例第三十一页，共三十五页，编辑于2023年，星期六霍夫曼码的最佳性定理4.5对于给定信源，存在有最佳唯一可译二元码，其最小概率的两个码字Wq-1和Wq