《第四章-无失真信源编码ppt课件.ppt》由会员分享，可在线阅读，更多相关《第四章-无失真信源编码ppt课件.ppt（96页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、信息论基础 李富年 武汉科技大学信息传输系统 第二章第二章:信息量信息量第三章信道第三章信道与信道容量与信道容量第四章第四章:无失无失真信源编码真信源编码信息论基础 李富年 武汉科技大学第四章 无失真信源编码q信源编码的概念 q信源编码的模型q等长编码q变长编码l香农费诺艾利斯编码l霍夫曼编码l费诺编码信息论基础 李富年 武汉科技大学信源编码的概念 要把信源的信息高速度、高质量地通过信道传送给信宿，一般要通过信源编码和信道编码来完成。 研究信源编码：只考虑有效性，不考虑可靠性信息论基础 李富年 武汉科技大学信源编码的概念 信源编码的作用p 符号变换：用信道能传输的符号来代表信源发出的消息，使信
2、源适合于信道的传输。信息论基础 李富年 武汉科技大学信源编码的概念 例：电报： 1：母亲患癌症，情况危急，请速归。 2：母病危速归p 有效传输(冗余度压缩)减少信源的剩余度 在不失真的条件下，用尽可能少的符号来传送信源信息，提高信息传送率。信息论基础 李富年 武汉科技大学信源编码的概念 一般而言，编码就是用数字形式表示消息的过程。编码实质上是对要处理的源数据按一定的规则进行变换。这些数学方法和变换策略的目的都是力图用尽可能少的符号或位来表示较多、较长的符号及消息。信息论基础 李富年 武汉科技大学信源编码的概念 对于离散信源，如果信源的统计特性已知，便可直接进行编码。信息论基础 李富年 武汉科技
3、大学无失真信源编码的基本概念 根据能否在解码后完全准确的恢复出原始消息(信息熵是否变换)，将信源编码分为无失真信源编码和率失真信源编码.否：率失真信源编码能：无失真信源编码号？能否完全恢复出原始信错有差错，没必要没有差不可能没编码，语音、图像，率失真编码：连续信源据，不能有差错文字、数编码，无失真编码：离散信源信息论基础 李富年 武汉科技大学信源编码模型设信源概率空间为1234:0.5 0.25 0.125 0.125ssssS对此信源进行二进制编码。 1234,ss s s s0 ,1B 编码的过程就是建立 之间元素的对应关系。 和信息论基础 李富年 武汉科技大学编码的定义 如果一种编码方案
4、0011 xs0122xs3310sx4411sx 如果信源连续发送S1S2S3三个符号，则该信源编码的输出为信息论基础 李富年 武汉科技大学编码的定义 假定这样的码经信道传输，在接收端收到以“0”“1”为符号的序列。如 如果一种编码方案110sx2210sx33110sx44111sx 将此序列进行译码，能唯一地恢复原来的消息序列。信息论基础 李富年 武汉科技大学信源编码模型 信源空间为：)(.)()(.2121qqspspspsssS12 ,.rXx xx 编码符号表为，用 的符号对消息 进行编码。Xis信息论基础 李富年 武汉科技大学isX消息 与由 的符号组成的符号序列相对应，用公式表
5、示为12.iiiiiinsWx xx1,2,.ikixXkn信源编码模型叫做对应消息 的码字。isiW称为码元。 ikxiniW称为 的字长。 信息论基础 李富年 武汉科技大学无失真信源编码的基本概念信息论基础 李富年 武汉科技大学码的分类q 二元码：码符号集为 ，所有码字都是由0、1组成的二元符号序列。100,1,.1r q r进制码元：码元符号集为 ， 所有码字都是由0、1.r-1组成的r进制数字序列。信源符号码1码2S1000S2111S3102S4113信息论基础 李富年 武汉科技大学码的分类q 根据编码后码字的长度等长码变长码：码字集合中各码字的码长都相等：码字集合中各码字的码长不完
6、全相等信源符号码1码2码3码4S1000001S21101110S310000100S41111111000信息论基础 李富年 武汉科技大学码的分类q 根据码字的情况ijijSSWW：所有码字都不相同，信源符号与码字之间唯一对应：码字集合中有相同的码字，即存在但非奇异码奇异码信源符号码1码2码3码4S1000001S20101110S310000100S41111111000信息论基础 李富年 武汉科技大学q根据译码恢复出的序列的情况l唯一可译码（UDC） 任意有限长的码字序列，只能被唯一地分割成一个个的码字，且任一码字只与唯一一个信源符号对应，便称为唯一可译码。又称单义码。 l非唯一可译码码
7、的分类信息论基础 李富年 武汉科技大学0 1 0 1 0 1 0例：10,11, 0X码的分类例：0,01,10X 要保证无失真编码，必须采用唯一可译码。0 1 0 1 0 1 01 3 3 3SS S S1333S S S S2221S S S S信息论基础 李富年 武汉科技大学码的分类信源符号码1码2S10000S20101S31000S41111001110q等长非奇异码一定是唯一可译码。信息论基础 李富年 武汉科技大学q根据码字相互关联的情况l非续长码 任意一个码字都不是另一个码字的续长，称为非续长码。换句话说，不能在任意一个码字后边，添上一些码元构成一个新的码字。 因此，当非续长码码
8、字的最后一个码字出现时，译码器能立即判断一个码字已经结束，可以立即译码，又称即时码或立即码。码的分类l续长码信息论基础 李富年 武汉科技大学码的分类信源符号码4码5S101S20101S3011001S41110001结论： 非续长码一定是单义码，而单义码却不一定是非续长码。 0011101011信息论基础 李富年 武汉科技大学码的分类非奇异码、唯一可译码、非续长码的关系信息论基础 李富年 武汉科技大学树图法树图法树图法：所有码字用码树描述出来。码树是一棵倒置的树，最上端是根节点，从根节点出发不断向下伸出树枝，分支与码符号一一对应。一个节点继续分支，称为中间节点；一个节点不再继续分支，称为终端
9、节点。 将信源符号对应的节点用实心圆表示，从根节点到这个节点经过的分支对应的码符号序列就是码字；没有与信源符号对应的节点用空心圆表示信息论基础 李富年 武汉科技大学对于码 和用码树表示如下：00010010111000100101树图法树图法信息论基础 李富年 武汉科技大学编码：用树图法构造非续长码，只要将信源符号全部对应于终端节点，而不是中间节点即可。这样就可以保证任何一个码字都不是其它码字的前缀 解码：按照码符号的顺序，从根节点依次查询到终端节点，就得到对应的信源符号。再从根节点对剩下的码符号序列做相同的处理，直到处理完码符号序列中所有的码符号。非续长码非续长码 -树图构造树图构造信息论基
10、础 李富年 武汉科技大学例：给定编码符号表X=0，1，码字W=W1，W2，W3，W4,字长分别是n1=1，n2=2 ，n3=n4=3，求非续长码。 非续长码非续长码 -树图构造树图构造信息论基础 李富年 武汉科技大学非续长码非续长码 -树图构造树图构造非续长码不是唯一的。全部终端节点都代表码字，这种情况叫做用尽的非续长码。信息论基础 李富年 武汉科技大学单义码存在定理 设信源S的符号集为 ，码符号集 ，又设码字为 ，其码长分别为 。则存在单义码的必要条件是： 满足Kraft不等式，即 其中，q是码字的个数，r是编码符号表的码元个数，ni 是字长。若上式成立，就一定能构造一个r进制的唯一可译码。
11、,., :21qsssS12: , ,. rXx xxqWWW,.,21qnnn,.,21),.,2 ,1(,qinrqi11qinir信息论基础 李富年 武汉科技大学例：给定编码符号表X=0，1，码字W=W1，W2，W3，W4 = 0，01，10，011,分别由1，2，2，3个码元构成的码字单义码存在定理按照不等式可知，q=4，r=2，n1=1，n2=2 ，n3=2 ，n4=3 ，代入Kraft不等式左边得189814141212411inqiniir信息论基础 李富年 武汉科技大学单义码存在定理 如W改为为0，10，110，111， 即n1=1，n2=2 ，n3=3 ，n4=3 18181
12、41212411inqiniir 如W改为为0，01，110，011， 即n1=1，n2=2 ，n3=3 ，n4=3 1818141212411inqiniir信息论基础 李富年 武汉科技大学单义码存在定理 码字不满足克拉夫特不等式，则肯定不是唯一可译码。码字满足克拉夫特不等式，并不一定是唯一可译码，只是说存在这样的码长条件的唯一可译码。信息论基础 李富年 武汉科技大学等长编码等长码：各个码字码长都相等的码 10否是11100010111000 可以编码成 有效性： 更好 可靠性： 更好，提供纠错功能对于等长码，如果是非奇异码，那么一定是唯一可译码信息论基础 李富年 武汉科技大学等长编码 信源
13、符号集有2个符号，可以用 编码，码长为1； 信源符号有4个，码长为1就不行了，必须用码长为2的等长码 设信源符号集中有符号q个；用二元码进行编码，码长为 ，能够提供的最多码字为 个，因此要满足1011100100ll2qlqllog2等长码码长不能无限制缩短。信息论基础 李富年 武汉科技大学 用 准则编解码过程非常简单，但是编码效率非常低，有效性很差。主要原因是没有考虑到信源符号间的相关性。qllog等长编码 信息论基础 李富年 武汉科技大学等长编码1231:0.455 0.001 0.544sssS1232:111333sssS00 01 10131:0.455 0.544ssS01信息论基
14、础 李富年 武汉科技大学N次扩展码：扩展前，一个信源符号编码成一个码字。N次扩展码，就是把N个信源符号组成的序列，变换成N个码字组成的序列N次等长扩展码次等长扩展码 否是10否否否是是否是是11100100如信源符号集 码字为2次扩展后信源符号集2次扩展码为信息论基础 李富年 武汉科技大学N N次等长扩展码次等长扩展码 进行N次扩展，共有 个信源符号， 需要 ， 平均到扩展前每一个信源符号， 这样看来并没有提高编码效率 考虑到相关性，不用对所有 个信源符号进行编码，有些信源符号不可能出现，有些出现的概率非常小。码长自然减少了NqqNqLNNloglogqLlogNq信息论基础 李富年 武汉科技
15、大学N N次等长扩展码次等长扩展码 n 对信源扩展的次数越多，利用信源的相关性就越充分，编出来的码长平均到每个信源符号上平均码长就越短，编码效率就越高 n 对信源做无限次扩展之后，能够将编码效率提高到一个极限的程度信息论基础 李富年 武汉科技大学等长编码定理等长编码定理 一个平稳离散信源的信息熵为 ，若对长为N的信源符号序列进行等长编码，N长符号对应的码长为 ,设码符号集中有r个码符号。 对于任意的 ，只要满足 当N足够大时，可以实现几乎无失真的编码。反之，则不可能实现无失真的编码( )H U0()logNlH UNrNl信息论基础 李富年 武汉科技大学等长编码定理等长编码定理 编码效率：描述
16、编码的优劣logNlRrNn 编码后信息率()HUn 每个信源符号的信息熵 ()()logNH UH UlRrNn 定义编码效率为1 n 码的冗余度(编码后的新信源的冗余度）信息论基础 李富年 武汉科技大学等长编码 例：离散无记忆信源(DMS)123456723456711111112222222uuuuuuuU1234567: 001 010 011 100 101 110111UuuuuuuuW用码元表X=0,1对U的单符号进行等长编码必须用码长为3的等长码 loglog 72.8lq 要无失真的信息传输，必须满足信息论基础 李富年 武汉科技大学3lo glo g 231NlRrNn 编码
17、后信息率63( )( )log ( )/32iiiH Up up ubit symboln 每个信源符号的信息熵 ()()63/ 3265.625%3logNH UH UlRrNn 定义编码效率为11 0.65625 34.375% n 码的冗余度(编码后的新信源的冗余度）信息论基础 李富年 武汉科技大学等长编码定理等长编码定理 等长信源编码的意义：通过不断的扩展信源进行等长编码，可以不断提高编码效率，当扩展次数N很大的时候，能够达到最大的编码效率 编码后平均每个信源符号对应的码符号序列所能携带的最大的信息量，一定要大于等于信源本身的信息量信息论基础 李富年 武汉科技大学等长编码的缺陷等长编码
18、的缺陷 会产生一定的误差：因为把一些小概率的组合去掉，没有进行编码扩展维数太大：要达到比较高的编码效率，扩展信源的维数需要很大4/14/3万41302510 例：信源的概率分布 ，要达到0.96的编码效率，错误率控制在 以内，信源需要扩展4130万次，扩展后信源符号数为 个 信息论基础 李富年 武汉科技大学变长编码变长编码- -平均码长平均码长 对于变长编码，不要求每个码字的码长都很,但却要求整个码字集合的平均码长较小121121212( )()()( )qqiqqqiiSSSSp Sp Sp SP SWWLp SWllll设信源符号的概率空间：编码后的码字平均码长 就是对个为，对应的码码字码
19、长求长为定义统计平均信息论基础 李富年 武汉科技大学变长编码变长编码- -平均码长平均码长 n 显然，要是平均码长短，除了要缩短每一个码字的码长外，还要合理的分配长短码，使概率较大的信源符号使用较短的码，概率较小的信源符号使用较长的码n 对于某一信源，若有一个唯一可译码，其平均码长小于其它任何唯一可译码的平均码长，则称此码为紧致码，或最佳码信息论基础 李富年 武汉科技大学变长信源编码定理（变长信源编码定理（香农第一定理)平稳信源信息熵为 ，对长为N的信源符号序列进行编码，编码后的平均码长为 ，码符号有r个，那么要做到无失真编码，平均码长必须满足NL( )H S()1lo gNLHSNrN()l
20、o gNLHSNr()()1lo glo gNLHSHSrNrN另一方面，一定存在唯一可译码，其平均码长满足：即：信息论基础 李富年 武汉科技大学变长编码变长编码- -变长信源编码定理变长信源编码定理 香农第一定理给出了无失真信源编码的平均码长所能达到的极限值，但是并不是所有的信源编码方法都能够达到这个极限值。为了衡量各种编码到达极限状况的程度，定义了编码效率：()lo gNHSLrN相应的码的冗余度为：1信息论基础 李富年 武汉科技大学变长编码变长编码- -变长信源编码定理变长信源编码定理【例】信源用0、1构成即时码811. 0)4143()(,4143)(21HSHSSSPS811.0)(
21、11021LSHLSS等长编码信息论基础 李富年 武汉科技大学变长编码变长编码- -变长信源编码定理变长信源编码定理对信源进行二次扩展,并变成编码111161110163101630169)(22122111SSSSSSSSpii码字22933127*2*3*316 16161616( )0.961log22LH SL信息论基础 李富年 武汉科技大学变长编码变长编码- -变长信源编码定理变长信源编码定理香农第一定理的意义：通过不断的扩展信源进行变长编码，可以不断提高编码效率，当扩展次数N很大的时候，能够达到最大的编码效率 编码后平均每个信源符号对应的码符号序列所能携带的最大的信息量，一定要大于
22、等于信源本身的信息量信息论基础 李富年 武汉科技大学经典编码方法 q霍夫曼（Huffman）编码q香农（Shannon）编码q费诺（Fano）编码 信息论基础 李富年 武汉科技大学霍夫曼（Huffman）编码 霍夫曼编码是1952年由霍夫曼提出的一种编码方法。这种编码方法的主导思想是根据源数据符号发生的概率进行编码。在源数据中出现概率越高的符号，相应的码长越短；出现概率越小的符号，其码长越长，从而达到用尽可能少的码符号表示源数据。理论表明，在数据压缩中，霍夫曼编码方法是接近压缩比上限的一种较好的编码方法。信息论基础 李富年 武汉科技大学霍夫曼（Huffman）编码 霍夫曼编码及其变种，在压缩编
23、码领域中应用的非常广泛。q数字图像 JPEGq运动图像 MPEG2、H.261、H.263 q通信编码 Modem ADSL信息论基础 李富年 武汉科技大学 (1)将n个信源U的各个符号ui按概率分布p（ui）以递减次序排列起来。 霍夫曼（Huffman）编码 编码方法 (2)将两个概率最小的信源符号合并成一个新符号，新符号的值为两个信源符号值的和，从而得到只包含n1个符号的新信源，称为U信源的缩减信源U1。信息论基础 李富年 武汉科技大学 (3)把缩减信源U1的符号仍按概率以递减次序排列，然后将其中两个概率最小的符号合并成一个符号，这样又形成了n2个符号的缩减信源U2。 霍夫曼（Huffma
24、n）编码 (4)依次继续下去，直至信源最后只剩下个符号为止。信息论基础 李富年 武汉科技大学 (5)将每次合并的两个信源符号分别用0和1码符号表示。 (6)从最后一级缩减信源开始，向前返回，就得出各信源符号所对应的码符号序列，即得各信源符号对应的码字。 霍夫曼（Huffman）编码信息论基础 李富年 武汉科技大学霍夫曼编码例霍夫曼编码例1 1编成2元霍夫曼码，求编码效率1 . 01 . 02 . 02 . 04 . 0)(54321SSSSSSPS：源符号序列中，如下图按概率插入到剩下的信并将，合并成新的信源、取出两个最小概率的2 . 0)()() (14544454SSpSpSpSSS10)
25、 1 . 0(4S) 1 . 0(5S)2 . 0( 4S2 . 02 . 02 . 04 . 03241SSSS信息论基础 李富年 武汉科技大学霍夫曼编码例霍夫曼编码例1 1：源符号序列中，如下图按概率插入到剩下的信并将，合并成新的信源、取出两个最小概率的4 . 0)()() (23323332SSpSpSpSSS10)2 .0(2S)2 .0(3S)4 .0( 3S2 .04 .04 .0413SSS信息论基础 李富年 武汉科技大学霍夫曼编码例霍夫曼编码例1 1：源符号序列中，如下图按概率插入到剩下的信并将，合并成新的信源、取出两个最小概率的6 . 0) ()() (32412241SSp
26、SpSpSSS10) 1 . 0(4S) 1 . 0(5S)2 . 0( 4S4 . 06 . 032SS01)4 . 0(1S)6 . 0( 2S信息论基础 李富年 武汉科技大学霍夫曼编码例霍夫曼编码例1 1，处理完成，如下图，合并成新的信源、取出两个最小概率的1) (41132SpSSS10)2 . 0(2S)2 . 0(3S)4 . 0( 3S10) 1 . 0(4S) 1 . 0(5S)2 . 0( 4S01)4 . 0(1S)6 . 0( 2S) 1 ( 1S01信息论基础 李富年 武汉科技大学霍夫曼编码例霍夫曼编码例1 19645. 0)(2 . 21 . 0*31 . 0*32
27、. 0*22 . 0*24 . 0*2/122. 2) 1 . 0, 1 . 0, 2 . 0, 2 . 0, 4 . 0()(LSHLbitHSH符号消息概率编码码长S10.4002S20.2102S30.2112S40.10103S50.10113信息论基础 李富年 武汉科技大学 例：离散无记忆信源: 12340.50.250.1250.125UuuuuP对应的霍夫曼编码如图所示： 霍夫曼编码霍夫曼编码- -课堂作业课堂作业信息论基础 李富年 武汉科技大学7( )(0.5,025,0,125,0,125)/471*0.52*0.253*0.1253*0.1251.754( )1.7511.
28、75*log2*logH SHbitLH SLr符号消息概率编码码长U10.501U20.25102U30.1251103U40.1251113霍夫曼编码霍夫曼编码- -课堂作业课堂作业信息论基础 李富年 武汉科技大学霍夫曼编码霍夫曼编码对于同一个信源，霍夫曼编码的方式有很多种：左分支编0、右分支编1；左分支编1、右分支编0；左右分支混编编出来的平均码长都一样信息论基础 李富年 武汉科技大学霍夫曼编码霍夫曼编码 合并后的新信源符号与其它信源符号概率相同时，合并后的符号插入到什么位置，编出来的码也是不一样的：例1中是将新信源符号插入到最前面例2将新信源符号插入到最后面信息论基础 李富年 武汉科技
29、大学霍夫曼编码例霍夫曼编码例2 2编成2元霍夫曼码，求编码效率1 . 01 . 02 . 02 . 04 . 0)(54321SSSSSSPS：源符号序列中，如下图按概率插入到剩下的信并将，合并成新的信源、取出两个最小概率的2 .0)()() (14544454SSpSpSpSSS10) 1 . 0(4S) 1 . 0(5S)2 . 0( 4S2 . 02 . 02 . 04 . 04321SSSS信息论基础 李富年 武汉科技大学霍夫曼编码例霍夫曼编码例2 2：源符号序列中，如下图按概率插入到剩下的信并将，合并成新的信源、取出两个最小概率的4 . 0) ()() (23433343SSpSpS
30、pSSS10)1 .0(4S)1 .0(5S)2 .0(3S2 .04 .04 .0231SSS01)2 .0( 4S)4 .0( 3S信息论基础 李富年 武汉科技大学霍夫曼编码例霍夫曼编码例2 2：源符号序列中，如下图按概率插入到剩下的信并将，合并成新的信源、取出两个最小概率的6 . 0)() () (32232223SSpSpSpSSS10) 1 . 0(4S) 1 . 0(5S)2 . 0(3S4 . 06 . 012SS01)2 . 0( 4S)4 . 0( 3S)2 . 0(2S01)6 . 0( 2S信息论基础 李富年 武汉科技大学霍夫曼编码例霍夫曼编码例2 2处理完成，如下图，合
31、并成新的信源，、取出两个最小概率的1) (41112SpSSS10)1.0(4S)1.0(5S)2.0(3S01)2.0( 4S)4.0( 3S)2.0(2S01)6.0( 2S)4.0(1S10信息论基础 李富年 武汉科技大学霍夫曼编码例霍夫曼编码例2 29645. 0)(2 . 21 . 0*41 . 0*42 . 0*32 . 0*24 . 0*1/122. 2) 1 . 0, 1 . 0, 2 . 0, 2 . 0, 4 . 0()(LSHLbitHSH符号消息概率编码码长S10.411S20.2012S30.20003S40.100104S50.100114信息论基础 李富年 武汉科
32、技大学霍夫曼编码霍夫曼编码两种编码方式的编码效率相等。第一种方法只有两种码长：2、3；第二种方法有4种码长14第一种方法方差比较小，更接近于等长码，更简单，更容易实现qiiiiLlSpLlE1222)(*)()(信息论基础 李富年 武汉科技大学霍夫曼编码霍夫曼编码扩展到r元霍夫曼编码，只要每次取r个最小概率的信源符号即可编成3元霍夫曼码，求编码效率1 . 01 . 02 . 02 . 04 . 0)(54321SSSSSSPS信息论基础 李富年 武汉科技大学霍夫曼编码例霍夫曼编码例3 3：源符号序列中，如下图按概率插入到剩下的信并将，合并成新的信源、取出三个最小概率的4 . 0)()()()
33、(1354333543SSpSpSpSpSSSS10) 1 . 0(4S) 1 . 0(5S)2 . 0(3S)4 . 0( 3S22 . 04 . 04 . 0213SSS信息论基础 李富年 武汉科技大学霍夫曼编码例霍夫曼编码例3 3，处理完成，合并成新的信源、取出三个最小概率的1) (211213SpSSSS10) 1 . 0(4S) 1 . 0(5S)2 . 0(3S)4 . 0( 3S2012)4 . 0(1S)2 . 0(2S信息论基础 李富年 武汉科技大学霍夫曼编码例霍夫曼编码例3 3956. 03log*4 . 1122. 23log*)(4 . 11 . 0*21 . 0*22
34、 . 0*22 . 0*14 . 0*1/122. 2) 1 . 0, 1 . 0, 2 . 0, 2 . 0, 4 . 0()(符号LSHLbitHSH消息概率编码码长S10.411S20.221S30.2002S40.1012S50.1022信息论基础 李富年 武汉科技大学霍夫曼编码解码霍夫曼编码解码 霍夫曼编码的所有码字都在码树的终端节点上，所以霍夫曼码是即时码。 因此霍夫曼码的解码可以使用即时码的解码方法。从码树的根节点开始，按码符号对应的分支逐步向下，直到找到一个终端节点。再从根节点开始对剩下的码符号序列做相同的处理，直到处理完所有的码符号。信息论基础 李富年 武汉科技大学霍夫曼编码
35、解码霍夫曼编码解码 解码10010110001101101011100054321SSSSS10)2 . 0(2S)2 . 0(3S)4 . 0( 3S10) 1 . 0(4S) 1 . 0(5S)2 . 0( 4S01)4 . 0(1S)6 . 0( 2S) 1 ( 1S01信息论基础 李富年 武汉科技大学霍夫曼编码解码霍夫曼编码解码 n 优点就是编码效率很好，是最佳编码n 缺点是容错性能非常差，只要有1位出现了错误，将可能导致后面的解码全部错误或翻译不出来0000001111112S4S3S1S5S0000000111112S4S4S1S3S原 译 码出 错 后 译 码信息论基础 李富年
36、武汉科技大学费诺编码费诺编码霍夫曼编码在构造码树的时候，是从下层节点开始，逐级向上直到根节点的；而费诺编码正好相反，是由根节点出发，直到终端节点。费诺编码的思想就是使编码后的码集尽可能的等概率分布。费诺码不是最佳编码方法，但是有时候也能编出最佳码 。信息论基础 李富年 武汉科技大学费诺编码费诺编码 将信源符号按概率大小递减排列，按照概率之和分为大致相等的r组（2组），分别编以0、1r-1（0、1），再分别对r个（2个）组做相同的处理，直到每个组只有一个信源符号为止。04. 008. 016. 018. 022. 032. 0)(654321SSSSSSSPS例：求2元费诺码及编码效率信息论基础
37、 李富年 武汉科技大学费诺编码费诺编码32. 01S01011022. 02S18. 03S16. 04S08. 05S04. 06S0101信息论基础 李富年 武汉科技大学费诺编码费诺编码979. 04 . 235. 2)(4 . 204. 0*408. 0*416. 0*318. 0*222. 0*232. 0*2/35. 2)04. 008. 016. 018. 022. 032. 0()(符号LSHLbitHSH消息概率编码码长S10.32002S20.22012S30.18102S40.161103S50.0811104S60.0411114信息论基础 李富年 武汉科技大学课堂练习课
38、堂练习离散无记忆信源 对源信源进行二维扩展后，采用费诺编码法，求编码效率；811. 0)(4341)(21XHxxXPX，信息论基础 李富年 武汉科技大学课堂练习课堂练习169163163161123212111xxxxxxxx1611169416321633010110信息论基础 李富年 武汉科技大学课堂练习课堂练习消息概率编码码长a11/161113a23/161103a33/16102a49/1601961.02)(1627169*1163*2163*3161*322LXHL信息论基础 李富年 武汉科技大学香农编码香农编码 香农编码法多余度较大，实用性不大，但在理论上的意义很大。编码方法
39、如下： 1.将信源消息出现的概率的大小依次排列qppp.212.从最初0个，1个，2个依次相加，并分别设为 ，即10P21Pp321Ppp12,.P P信息论基础 李富年 武汉科技大学香农编码香农编码2211log ()log ()1jjjmpp4.确定满足下列不等式的整数 jm3.用二进制数表示 jPjPjm5.令 的二进表示形式的小数点后面 位为 。则这个 为对应于第j个消息的码符号。 jSjS信息论基础 李富年 武汉科技大学香农编码香农编码小数：基数乘法（1）将给定的十进制纯小数乘以基数2，其积的整数部分便是等值二进制纯小数的最高位（2）将上一步中乘积的小数部分再除以基数2，所得乘积的整
40、数部分便是次高位。（3）重复步骤2，直到乘积的小数部分为0，或者达到要求的精确度为止。 各次乘积的整数部分便是二进制纯小数的各位，最后一次乘积的整数部分是最低位。信息论基础 李富年 武汉科技大学香农编码香农编码信息论基础 李富年 武汉科技大学香农编码香农编码【例】离散无记忆信源概率分布为 ： 求对应的香农编码05. 010. 015. 020. 025. 025. 0654321ssssssS信息论基础 李富年 武汉科技大学14log4log212 m321 m21m14log4log222 m322 m22m15log5log232 m3219. 33219. 23m33m香农编码香农编码2
41、4211loglog10.150.15m42.73693.7369m43m25211loglog10.100.10m53.32194.3219m54m26211loglog10.050.05m64.32195.3219m65m信息论基础 李富年 武汉科技大学香农编码香农编码信源符号S概率函数p(S)累计概率Pjmj累计概率二进制数码长码字W S10.25020.00200S20.250.2520.010201S30.20.530.10003100S40.150.730.10103101S50.10.8540.110141101S60.050.9550.111101511101信息论基础 李富年 武汉科技大学香农编码香农编码6120.25 2 0.25 2 0.2 3 0.15 3 0.10 4 0.05 5 2.7( )(0.25 0.25 0.2 0.15 0.10 0.05) 2.42( )(2.42/2.7log 2) 100% 89.6%logi iiLpnH SHH SLr 信源编码模型码的分类等长编码变长编码Huffman编码Shannon编码Fano编码香农第一定理等长编码定理