第5章无失真信源编码定理课件

1第5章无失真信源编码5.1编码器5.2等长码5.3渐进等分割性和e典型序列*5.4等长信源编码定理5.5变长码5.6变长信源编码定理1第5章无失真信源编码5.1编码器25.1编码器对整个通信系统来说，要解决两个问题：信源编码和信道编码。

对信源来说有两个重要问题：一个是信源输出信息量的定量度量问题。这在前面信源及其信息熵章中已讨论。本章将要讨论第二个问题：如何有效地表示信源输出问题。即将重点讨论对信源进行无失真信源编码的要求、方法及理论极限，从而得出香农第一定理。

25.1编码器对整个通信系统来说，要解决两个问题：信源编码3编码器的描述码元码字码码长l码符号集3编码器的描述码元码字码码长l码符号集4信源编码器的主要任务：完成输入消息集合与输出代码集合之间的映射。若要实现无失真编码，则这种映射必须是一一对应的、可逆的。4信源编码器的主要任务：完成输入消息集合与输出代码集合之间的5常用码型1、二元码：若信道码符号集A={0，1}，编码输出的码字都是二元码，称为二元码。2、等长码：若一组码中所有码字的码长都相同，称为等长码。3、变长码：若一组码中所有码字的码长Ki各不相同，即任意码字由不同长度的码符号序列组成，则称为变长码。5常用码型1、二元码：若信道码符号集A={0，1}，编码输6常用码型4、非奇异码和奇异码：若一组分组码中的所有码字都不相同，即所有信源符号映射到不同的码字。称此分组码为非奇异码。否则为奇异码5、同价码和非同价码：若每个码符号的传输时间都相同则称为同价码。否则为非同价码6常用码型4、非奇异码和奇异码：若一组分组码中的所有码字都不7常用码型6、码的N次扩展码：假使某分组码W，把信源X中的符号xi一一变换成码W中的码字Wi字，则码W的N次扩展码是N个码字组成的码字序列的集合。

7常用码型6、码的N次扩展码：假使某分组码W，把信源X中的符8例：设信源X的概率空间为若把该信源通过一个二元信道进行传输，为适合信道传输，就必须把信源符号xi变换成0、1符号组成的码序列（二元序列）。可采用不同的二元序列使其与信源符号si一一对应，所以可有多种方法得到二元码。如表4.1所示8例：设信源X的概率空间为若把该信源通过一个二元信道进行传输9表5.1信源X的两种不同编码码字

现求码S2的二次扩展码。

9表5.1信源X的两种不同编码码字现求码S2的二次扩展10常用码型7、唯一可译码：若码的任意一串有限长的码符号序列只能被唯一地译成所对应的信源符号序列，则此码为唯一可译码。否则，称为非唯一可译码。唯一可译码的物理含义：不仅要求不同的码字表示不同的信源符号，而且还进一步要求对由信源符号构成的信息序列进行编码时，在接收端仍能正确译码，而不发生混淆。本章主要研究的是同价唯一可译码。10常用码型7、唯一可译码：若码的任意一串有限长的码符号序列115.2定长码

一般来说，若要实现无失真的编码，所编的码必须是唯一可译码，否则，就会因译码带来的错误与失真。非奇异定长码的N次扩展码一定也是非奇异定长码。非奇异定长码一定是唯一可译码。

115.2定长码一般来说，若要实现无失真的编码，所编的码12信源存在唯一可译定长码的条件：对信源X进行等长编码，必须满足其中l

是等长码的码长,有例：英文电报有32个符号，即n=32。若对它进行二元编码，则r=2，可得l=5。也就是说，每个英文电报符号至少要用5位二元符号编码才行。12信源存在唯一可译定长码的条件：13实际英文电报符号信源，在考虑了符号出现的概率以及符号之间的依赖性后，其信息熵约为1.4比特/符号，即平均每个英文符号所提供的信息量为1.4比特。因此等长编码后5个二元符号只携带约1.4比特信息量。对于无噪无损二元信道，每5个二元符号最大能载荷5比特的信息量。因此，如此等长编码的信息传输效率极低。13实际英文电报符号信源，在考虑了符号出现的概率以及符号之间145.4等长信源编码定理定理4.3一个熵为H(X)的离散无记忆信源，若对信源长为N的符号序列进行等长编码，设码字是从r个字母的码符号集中选取l个码元组成。对于任意

>0，只要满足则当N足够大时，可实现几乎无失真编码，即译码错误概率能为任意小。145.4等长信源编码定理定理4.3一个熵为H(X)的离散15编码信息率编码效率举例：书145页例4.115编码信息率编码效率举例：书145页例4.1165.5变长码变长码也必须是唯一可译码，才能实现无失真编码。定义：在唯一可译变长码中，有一类码，它在译码时，无须参考后续的码符号就能立即作出判断，译成对应的信源符号，则这类码称为即时码165.5变长码变长码也必须是唯一可译码，才能实现无失真编17一个唯一可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。故即时码一定是唯一可译码，反之，唯一可译码不一定是即时码。即时码可用树图法来进行编码和译码。17即时码可用树图法来进行编码和译码。18树码：通过树图法构成的码叫树码对r进制树图，有树根、树枝和节点。树图最顶部的节点称为树根。树枝的尽头称为节点，每个节点生出的树枝树目等于码符号树r。即时码的构造

18树码：通过树图法构成的码叫树码即时码的构造191920即时码可用树图法来进行编码和译码。构造步骤：1、最上端为树根，从根出发向下伸出树枝，树枝总数等于m（码符号数），树枝的尽头为节点。2、从每个节点再伸出m枝树枝，当某节点被安排为码字后，就不再伸枝，这节点为终端节点。能再伸枝的节点称为中间节点。一直继续进行，直到都不能伸枝为止。3、每个节点所伸出的树枝标上码符号，从根出发到终端节点所走路径对应的码符号序列则为终端节点的码字。20即时码可用树图法来进行编码和译码。21树码一定是即时码，任一即时码都可用上述树图法来表示。即时码一定是唯一可译码。唯一可译码，不一定是即时码。21树码一定是即时码，任一即时码都可用上述树图法来表示。即时22例：一信源X(x1,x2,x3,x4)经编码后得码字集合S

(1,01,001,0001)且一一对应。现接收码元序列为101110001001101011，试写出译码结果。

解：该编码规则为：x1→1,x2→01,x3→001,x4→001，每一码字均以1结尾，见1即可译码。对所接收序列的译码结果为

x1,x2,x1,x1,x4,x3,…这种编码，译码时不需要考察后续码元，故又称之为即时码。22例：一信源X(x1,x2,x3,x4)经编码后得23编码的树图表示

即时码一定是单义可译码。23编码的树图表示即时码一定是单义可译码。24单义可译定理（即时码存在的充要条件）对含有n个信源符号的信源用含r个符号的码符号集进行编码，各码字的码长为的唯一可译码存在的充要条件是，满足Kraft不等式含义：24单义可译定理（即时码存在的充要条件）对含有n个信源符号的25例：信源空间为

X：

x1,x2,x3,x4

P(X)：

1/2，

1/4，

1/8，

1/8对其进行信源编码，信道基本符号集合为：{m=0,1}；若编码后对应的码长分别为k1=1,k2=2,k3=3,k4=3，问能否构造出一种即时码？解：将m=2,n=4和ki的4个值带入Kraft不等式得满足Kraft不等式，所以一定能构成至少一种即时码

25例：信源空间为X：x1,x2,262627唯一可译码的判断法应该注意的是克拉夫特（Kraft）不等式只是给出来即时码或唯一可译码存在的充分必要条件，但该定理并不能作为判别一种码是否为即时码或唯一可译码的依据。即唯一可译码（或即时码）一定满足不等式，反之，满足不等式的码不一定是唯一可译码。例：码字（0，10，010，111），满足克拉夫特不等式，但它不是唯一可译码。

27唯一可译码的判断法应该注意的是克拉夫特（Kraft）不等28唯一可译码的判断步骤：

1、观察是否是非奇异码。若是奇异码则一定不是唯一可译码。2、计算是否满足Kraft不等式，若不满足一定不是唯一可译码。3、将码画成一棵树图，观察是否满足即时码的树图构造，若满足则是唯一可译码。4、直接用判别测试算法：28唯一可译码的判断步骤：1、观察是否是非奇异码。若是奇异295.6变长信源编码定理设信源有n个离散符号，编码后的码字为其码长分别为对于唯一可译码来说，信源符号与码字一一对应，所以有则这个码的平均长度为295.6变长信源编码定理设信源30码的平均长度是每个信源符号平均需用的码元数。平均每个码元携带的信息量即编码后信道的信息传输率为若要信息传输效率高，需寻求使平均码长最短的码，即紧致码，或称最佳码。30码的平均长度是每个信源符号平均需用的码元数。平均每个码元31平均码长可能达到的理论极限定理：若一离散无记忆信源X具的熵为H(X)，并有r个码元的码符号，则总可以找到一种无失真编码方法，构成唯一可译码，使其平均码长满足无失真变长信源编码定理香农第一定理31平均码长可能达到的理论极限定理：若一离散无记忆信源X32编码效率：码的剩余度：二元无噪无损信道中信息传输率32编码效率：33例：有一离散无记忆信源其熵为H(X)=0.811比特/信源符号。用二元码构造一个非续长码：x10，x21这时平均码长，编码效率