《信息论基础》课件第5章 无失真信源编码.ppt

1、主要内容主要内容 信源编码的基本概念信源编码的基本概念 信源编码定理信源编码定理 信源编码方法信源编码方法 无失真信源编码的无失真信源编码的MATLABMATLAB实现实现信 源信源编码信道编码信 道信 宿信源译码信道译码通信系统模型信源编码：1.信源适合信道传输2.无失真传输3.有效传输减少信源的剩余度编码器,.,:21qsssS,.,:21raaaX信 道raaa21qwww21qqwswsws2211,.,:21qwwwW码字5.1 5.1 信源编码的基本概念信源编码的基本概念编码器 二元码二元码 码符号集为码符号集为X X 0 0，1 1，所得码字都是二元序列，所得码字都是二元序列，称

2、为二元码。称为二元码。等长码等长码 一组码中所有的码长都相同，称为等长码。一组码中所有的码长都相同，称为等长码。变长码变长码 一组码中所有的码长各不相同即任意码字由不同一组码中所有的码长各不相同即任意码字由不同长度的码符号序列组成，称为变长码。长度的码符号序列组成，称为变长码。码的分类惟一可译码：),.,2,1(),.,2,1(qisqiwiil码字与信源符号一一对应l不同的符号序列不同的码字序列例：1.1101104321ssss1s3s2s4s奇异码2.01001004321ssss非奇异码0 1 0 0 0 0 1 014321sssss0 1 0 0 0 0 1 02334ssss3.

3、111001004321ssss等长码非奇异码0 0 0 1 1 0 1 14321ssss单义可译4.10001001014321ssss非奇异码1 1 0 1 0 0 1 0 0 0单义可译1 0?2s01不即时任何一个码字是其它码字的延长或前缀5.00010010114321ssss非奇异码1 0 1 0 0 1 0 0 0 1单义可译0 12s即时任何一个码字不是其它码字的延长或前缀即 时 码 几个码类的概念几个码类的概念 非奇异码（奇异码、单义码）非奇异码（奇异码、单义码）唯一可译码唯一可译码 即时码（前缀码、非延长码、异前置码）即时码（前缀码、非延长码、异前置码）最佳码（紧致码）最

4、佳码（紧致码）Kraft定理定理 唯一可译码存在定理唯一可译码存在定理唯一可译变长码与即时码几个码类的概念l唯一可译码唯一可译码 编码单义、译码单义编码单义、译码单义 对任何一个有限长度的信源字母序列，如果编对任何一个有限长度的信源字母序列，如果编码得到的码字母序列不与其他任何信源字母序码得到的码字母序列不与其他任何信源字母序列所对应的码字母序列相同。列所对应的码字母序列相同。所有的码非奇异码唯一可译码即时码即时码的树图构造法从根开始，画出r条分支，任选一个分支作为w1；在另一个分支上再分出r条分支，任选一个分支作为W2；继续进行，直至结束；从根到各端点，所经过的状态即为码字。例如：A:0,1

5、,r=2,W:w1,w2,w3,w4 w4 w3 w2 w1 0 0 0 1 1 1 根 w4 w3 w2 w1 1 1 1 0 0 0 根 Kraft定理l引出l码树lKraft定理描述Kraft定理引出 Kraft定理 定理定理 设原始信源符号集为X:x1,x2,xr的任意即时码，码字集合为W:W1,W2,Wq，其码长分别为l1,l2,ln；则满足 ；反之，若码长满足以上不等式，则一定存在具有这样码长的即时码。11qilir物理意义：给定信源个数q q和码字数r r，只要允许码字长度可以足够长，就总可以满足KraftKraft不等式，从而得到即时码.例：三阶节点的二元整树 N=3,r=2,

6、N阶共有 个节点，即 8个树枝 若li 1，则 4个节点不能伸展；若li 2，则 2个节点不能伸展。NrN232132232iNlriNlr证明:必要性证明 若设码树共有N阶，则总码枝数为 个。若某个长度为li的码枝被选用，即为码字，则自该支第li节点以后所有码枝不能再选用，即有 码枝不能再选用。由于li中i是任意的（i=1,2,q），所以全树中不能再选用的总码枝数应为：，显然其值一定要小于全树总码枝数 ，即有NrqilNir1111qilNqilNiirrrNriNlr 惟一可译码定理惟一可译码定理 定理定理 对于码符号为X:x1,x2,xr的任意惟一可译码，码字集合为W:W1,W2,Wq，

7、其码长分别为l1,l2,ln；则满足Kraft不等 式，；反之，若码长满足以上 不等式，则一定存在具有这样码长的惟一可译码。11qilir 结论：惟一可译码一定满足不等式；反之，满足不等式的码不一定是惟一可译码，但一定存在至少一种可译码。定理 若存在一个码长为li（i=1,2,q）的惟一可译码，则一定存在具有相同的码长的即时码。l 惟一可译变长码的判断法惟一可译变长码的判断法 将码C中所有可能的尾随后缀组成一个集合F，当且仅当集合F中没有包含任一码字，则可判断此码C为惟一可译变长码。1、Kraft不等式 惟一可译码存在的必要条件l1=1，l2=2，l3=l4=3的二元码如：C1=1,01,00

8、1,000 C2=0,10,110,111l1=1，l2=l3=l4=2的二元码 必存在惟一可译码 4174ilir/必不存在惟一可译码C3=0,00,000,000 非惟一可译411ilir符号码1码2码3码4等长码变长码u100001u201101101u3100000001u31101110001惟一可译码非惟一可译码非惟一可译码惟一可译码121nili4521nili4521nili1161521nili 2、根据定义判断等长码若为非奇异码，则为唯一可译码；变长码码本身及任意次扩展码均非奇异。树图法（即时码必为惟一可译码）尾随后缀法（尾随后缀集合F中不含任一码字）01011001001

9、0111010011001110101111例2.C1=0,10,1100,1110,1011,1101F:11,00,10,01,0,11,1,100,110,011,101100eg:1011001110.例3.C2=1,10,100,10001101000000 F=0,00C3=1,01,001,0001 F=考察离散、随机序列信源的统计特性 渐进等分割性（AEP）AEP描述：描述：渐进等分割定理：渐进等分割定理：（熵定理，遍历性定理）设 是离散无记忆信源输出的一个特定序列，则任给 和 ，总可以找到一个整数 ，使当 时，有：Nssss.21000N0NN 1|)(|)(logSHPNs

10、P渐进等分割性（AEP）5.2 信源编码定理NGNG1)(NNGpLim)(),(221MqPPHPPPHlM/1PPM10)(NNGpLim0)(NGPNGNGNG信源序列集合NSNGNGNG集合 和 中的序列分别称为 典型序列和 非典型序列l可以证明：对于任意小的正数 ，当L足够大时，表示 中所有 典型序列的集合 表示 集合中序列的个数l还可以证明：对于任意小的正数 ，当L足够大时，表示序列 出现的概率由切比雪夫不等式可得：表示S中每个符号携带的信息量的方差 00)()(2|2)1(SHNNSHNG|NGNS0NiG)()(2)(2SHNiSHNP)(iPiNNGP21)(2NGNGNGN

11、G1)(NGp)(2SNH 1、基本问题、基本问题 等长码特点：C2=000,001,100,101,111，l2=3 code/sigill 要求：(1)iis 问题：l？例1 123451 2 1 4 1 8 1 16 1 16iSsssssP(s)/C1=00,01,10,11,10，l1=2 code/sig(2)高效信源编码定理等长码基本问题 可能的码字数消息数 对基本信源编码：对N长源编码：1,qiSssW 112,(,)NlNiiiqSxx 消息数码字数：rl121(),iiiilijrWx xxxxx r lq (llogrq)（对例1，q=5,要求：2l5，即l 3）r lq

12、N(l/Nlogrq)例：英文电报有32个符号，即q=32，若r2，N=1(即对信源S的逐个符号进行二元编码），得 log32=5 即每个英文电报符号至少要用5位二元符号编码。rqlloglog则，q=53=125种128=27 l=7 code/3_sigs平均码长：l/N=7/3=2.33 code/sig l2 例1（续）S的三次扩展：等长码码长要求 l/N logrq（保证唯一可译码，无失真）logrq为下限 扩展信源编码的平均码长0，只要满足：(L/N)log rH(S)+则当N足够大时，可实现几乎无失真编码，即译码错误概率能为任意小。反之，当 (L/N)log rH(S)2时，则不

13、可能实现无失真编码，而当N足够大时，译码错误概率近似等于1。解释：等长编码定理给出了信源进行等长编码所需码长的理论极限值。532loglogqLBit/符号 bitH4.1考察：字母个数为q，字母出现非等概，且字母之间相关长度为L的英文信源，其可能的字母序列总数为 ；但其中大部分字母序列是无意义的字母组合，而且随着L的增加，这种无意义序列的总数越来越大。方法：进行联合编码，即对字母序列编码，且只对哪些有意义的字母序列编码，即需编码的字母序列的总数 N H(S)左边表示左边表示长为长为L的码符号序列能载荷的最大信的码符号序列能载荷的最大信息量息量，右边表示，右边表示长为长为N的信源序列平均携带的

14、信的信源序列平均携带的信息量息量。即只要码字传输的信息量大于信源序列携。即只要码字传输的信息量大于信源序列携带的信息量，总可以实现几乎无失真编码。带的信息量，总可以实现几乎无失真编码。编码效率编码效率 因为 (L/N)log rH(S)+令 R=(L/N)log r 表示编码后平均每个信源符号能载荷的最大信息量，称表示编码后平均每个信源符号能载荷的最大信息量，称为为编码信息率编码信息率。为了衡量编码的效果，引进为了衡量编码的效果，引进 称为编码效率。称为编码效率。rNlSHRSHlog)()(41()log1.75(/iiiH Sppbit 信源符号）()90%()H SH S0.68750.

15、68750.90.90.19442262252 0.68751.819 10(0.1944)10PNLP2422()1log()0.6875iiippH S123411112488ssssSp 可见,需要182万个信源符号联合编码，才能达到上述要求，这显然是不现实的。一般来说：当一般来说：当N有限时，高传输效率的等长码有限时，高传输效率的等长码往往要引入一定的失真和错误，它不能象变长编往往要引入一定的失真和错误，它不能象变长编码那样可以实现真正的无失真编码。码那样可以实现真正的无失真编码。当 10-5（即PE10-5）解：H(S)=0.811 bit/sig 例DMS 进行等长编码 12()3

16、414iSssP s/220 4715iiiD I(s)E I(s)E I(s).则有：=0.5 得N71687 =0.8 得N1146990 =0.9 得N5806641 =0.96 得N41291672 适用于DMS及平稳有记忆信源 平均码长下限：基本方法：N长源、变长编码 N 则则 对等长编码,若要实现几乎无失真编码,则信源长度必满足:rSHlog)(rNLSHRSHlog)()(,其中epSHN2222)1()(2122)()(1)log(SHspspNiii3 变长信源编码定理码率与有效编码qqqqLwspsLwspsLwsps)()()(22221111平均码长：码符/信符qiii

17、LspL1)(一般离散无记忆信源输出的各消息（符号）的概率是不相等的。对出现频率大的信源符号采用较短的码字；而对出现概率小的信源符号采用较长的码字。从整个信源来看，编成的信源码字的平均码长最短，也实现了与信源统计特性相匹配。平均码长是每个信源符号平均需用的码元数。它和编码后的压缩效果密切相关。平均码长大，则压缩效果差，系统有效性差。因此，我们一般选用平均码长最短的编码。编码后每个码元携带的信息量就是.,/,)(信息传输效率越高越大越短 RLcodebitLSHR qiiispspSH1)(log)()(bit/信符bit/信符码符/信符=bit/码符码率iiLsp)(iiLsp)(LSHR)(

18、L有效性qiiiLspL1)(L 若传输一个码符号平均需要t秒钟，则编码后信道每秒钟传输的信息量为：=bit/秒LtSHRt)(因此，越短，越大，信息传输效率就越高。LtR 定理定理 若一个离散无记忆信源S的熵为H(S)，并有r个码元的码符号X:x1,x2,xr，则总可以找到一种无失真的编码方法，构成惟一可译码，使其平均码长满足：对于常用的二元编码来说：H(S)LH(S),就存在惟一可译变长编码；若 H(S)，就存在唯一可译变长编码；若R 0(i=1,2,n),定义信源符号的定义信源符号的为为 P1=0;P2=p1;P3=p1+p2;11riirpP累积概率r=1,2,npr=Pr+1-Pr)

19、1,0rPP1p1P2P3P41p2p30 当A=0,1二元信源时，P1=P(0)=0;P2=P(1)=p0P(0)P(1)01p0p1二元序列的累积概率引例 设有二元序列S=011，求S的累积概率P(S)=p(000)+p(001)+p(010)若S后面接0P(S0)=p(0000)+p(0001)+p(0010)+p(0011)+p(0100)+p(0101)=p(000)+p(001)+p(010)=P(S)若S后面接1P(S1)=p(0000)+p(0001)+p(0010)+p(0011)+p(0100)+p(0101)+p(0110)=P(S)+p(0110)=P(S)+p(S)p

20、0二元序列的累积概率S0=0110S1=01117)(1logSpL设二元无记忆信源S=0,1,p(0)=1/4,p(1)=3/4。S=11111100，对其做算术编码。P(S)=p(00000000)+p(00000001)+p(00000010)+p(11111011)=1-p(11111111)-p(11111110)-p(11111101)-p(11111100)=1-p(111111)=1-(3/4)6=0.110100100111从而得C=0.1101010，S的码字为1101010解：p(S)=p2(0)p6(1)=(1/4)2(3/4)6例 题1101001%7.928/7811.02300011320023000113200,aaaaaaaaaaaaaaaaaaaaaa2300011320023000113200,aaaaaaaaaaaaaaaaaaaaaa00000 00110 00011 00001 10000 00100 011101 2 3 4 5 6 75.5 无失真信源编码的MATLAB实现2 实验内容 等长编码等长编码 霍夫曼编码霍夫曼编码 香农香农-费诺编码费诺编码1 相关原理 无失真信源等长、变长编码定理无失真信源等长、变长编码定理