三章信源编码一离散信源无失真编码复习课程.ppt

第三章信源编码（一）离散信源无失真编码3.1信源及其分类信源及其分类离散无记忆源离散无记忆源的等长编码离散无记忆源的等长编码离散无记忆源的等长编码离散无记忆源的等长编码离散无记忆源的等长编码DMS的等长编码弱、强e典型序列集例3.2.2信源划分定理信源划分定理信源划分定理信源划分定理编码速率和等长编码定理DMS的等长编码DMS的等长编码DMS的等长编码DMS的等长编码DMS的等长编码DMS的等长编码DMS的等长编码DMS的等长编码DMS的等长编码DMS的等长编码DMS的等长编码DMS的等长编码DMS的等长编码DMS的等长编码3.3DMS的不等长编码DMS的不等长编码平均码长不等长编码面临问题几个定义例子例观察表3.3.1。
码A不是唯一可译的。码B不是唯一可译的。
码C是唯一可译的，识别码字的方法为：见“0”或“111”就是一个码字的结束。实际上，码C是异字头码。
码D是唯一可译的，识别码字的方法为：见“0”就是一个码字的开始。实际上，码D是逗点码，其中“0”是逗号。
码C不是逗点码。码D不是异字头码。
码C的平均码长比码D的平均码长小：
码C的平均码长为1×0.5+2×0.25+3×0.125+3×0.125=1.75；
码D的平均码长为1×0.5+2×0.25+3×0.125+4×0.125=1.875。异字头码的第一种构造方法：Shannon-Fano编码法（D元编码，字母表为{0,1,…,D-1}）Shannon－Fano编码 异字头码可以通过树图构成异字头码存在的充分必要条件唯一可译码不等长编码定理不等长编码定理不等长编码定理不等长编码定理不等长编码定理不等长编码定理关于不等长编码的几个概念3.4最佳不等长编码两个定理二元Huffman编码Huffman编码Huffman编码多元Huffman编码LZ编码Eg：对下面信息序列进行LZ编码10101101001001110101000011001110101100011011

分段phrases：1,0,10,11,01,00,100,111,010,1000,011,001,110,101,10001,1011序号游程编码算术编码算术编码算术编码A：通过计算来编码，
F(s)=p(00000000)+p(00000001)+…+p(11111011)
=1-p(11111111)-p(11111110)-p(11111101)
-p(11111100)=1-p(1111111)-p(1111110)
=1-p(111111)
=1-
=0.110100100111
所以C(s)=0.1101010B：用递推公式编码C：用〔0,1）区间表示第三章结束