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

幻灯片1第5章无失真信源编码定理幻灯片2通信的实质是信息的传输。高效率、高质量地传送信息又是信息传输的基本问题。信源信息通过信道传送给信宿，需要解决两个问题：第一，在不失真或允许一定失真条件下，如何用尽可能少的符号来传送信源信息，以提高信息传输率。第二，在信道受干扰的情况下，如何增强信号的抗干扰能力，提高信息传输的可靠性同时又使得信息传输率最大。为了解决以上两个问题，引入了信源编码和信道编码。幻灯片3提高抗干扰能力（降低失真或错误概率）往往是增加剩余度以降低信息传输率为代价的；反之，要提高信息传输率往往通过压缩信源的剩余度来实现，常常又会使抗干扰能力减弱。上面两者是有矛盾的，然而在信息论的编码定理中，已从理论上证明，至少存在某种最佳的编码或信息处理方法，能够解决上述矛盾，做到既可靠又有效地传输信息。第5章着重讨论对离散信源进行无失真信源编码的要求、方法及理论极限，得出极为重要的极限定理——香农第一定理。幻灯片45.1编码器编码实质上是对信源的原始符号按一定的数学规则进行的一种变换。图5.1就是一个编码器，它的输入是信源符号集S={s1,s2,…,sq}。同时存在另一符号集X={x1,x2,…,xr}，一般元素xj是适合信道传输的，称为码符号（或称为码元）。编码器是将信源符号集中的符号si（或者长为N的信源符号序列ai）变换成由xj（j=1,2,…,r）组成的长度为li的一一对应序列。幻灯片5S：{s1,s2,…sq}C：{w1,w2,…wq}（wi是由li个xj（xj属于X））组成的序列，并于si一一对应X：{x1,x2,…xr}这种码符号序列Wi称为码字。长度li称为码字长度或简称码长。所有这些码字的集合C称为码。编码就是从信源符号到码符号的一种映射，若要实现无失真编码，必须这种映射是一一对应的、可逆的。幻灯片6一些码的定义二元码：若码符号集为X={0,1}，所得码字都是一些二元序列，则称为二元码。若将信源通过一个二元信道进行传输，为使信源适合信道传输，就必须把信源符号变换成0,1符号组成的码符号序列（二元序列），这种编码所得的码为二元码。二元码是数字通信和计算机系统中最常用的一种码。等长码（或称固定长度码）若一组码中所有码字的码长都相同，即li=l（i=1,2,…,q），则称为等长码。幻灯片7变长码若一组码中所有码字的码长各不相同，即任意码字由不同长度li的码符号序列组成，则称为变长码。非奇异码若一组码中所有码字都不相同，即所有信源符号映射到不同的码符号序列si≠sjwi≠wj，si,sj∈S，wi,wj∈C，则称码C为非奇异码。奇异码编码器若一组码中有相同的码字，即si≠sjwi=wj，si,sj∈S，wi,wj∈C，，则称码C为奇异码。幻灯片8同价码若码符号集：{x1x2…xr}中每个码符号xi所占的传输时间都相同，则所得的码C为同价码。一般二元码都是同价码。对同价码来说，等长码中每个码字的传输时间都相同；而变长码中每个码字的传输时间就不一定相同。电报中常用的莫尔斯码是非同价码。码的N次扩展码假定某码C，它把信源S中的符号si一一变换成码C中的码字wi，则码C的N次扩展码是所有N个码字组成的码字序列的集合。幻灯片9唯一可译码若码的任意一串有限长的码符号序列只能被惟一的译成所对应的信源符号序列，则此码称为唯一可译码，或单义可译码。若要所编的码是唯一可译码，不但要求编码时不同的信源符号变换成不同的码字，而且还必须要求任意有限长的信源序列所对应的码符号序列各不相同，即要求码的任意有限长N次扩展码都是非奇异码。因为只有任意有限长的信源序列所对应的码符号序列各不相同，才能把该码符号序列唯一地分割成一个个对应的信源符号，从而实现惟一地译码。幻灯片105.2等长码一般说来，若要实现无失真的编码，这不但要求信源符号si与码字wi是一一对应的，而且要求码符号序列的反变换也是惟一的，所编的码必须是唯一可译码。否则，所编的码不具有惟一可译码性，就会引起译码带来的错误和失真。若等长码是非奇异码，则它的任意有限长N次扩展码一定也是非奇异码。等长非奇异码一定是惟一可译码。若对信源S进行等长编码，就必须满足q≤rl，其中l是等长码的码长，r是码符号集中的码元数。幻灯片11如果对信源的N次扩展信源进行等长编码，若要求编得的等长码是惟一可译码则必须满足qN≤rl，表明只有当l长的码符号序列数(rl)大于等于N次扩展信源的符号数(qN)时，才可能存在等长非奇异码。从以上不等式可得L/N≥logq/logr，式中L/N是平均每个信源符号所需要的码符号个数。等长惟一可译码，每个信源符号至少需要用logq/logr个码符号来变换，就是每个信源符号所需最短码长为logq/logr个。幻灯片12例1英文电报有32个符号（26个英文字母加上6个符号），q=32。若r=2，N=1（对信源S逐个符号进行二元编码），由公式英文电报符号至少要用5位二元符号编码事实上，由第二章可知，考虑符号之间的依赖关系，平均每个英文电报符号所提供的信息量约等于1.4比特5比特。532logloglogrql幻灯片13续等长编码后，每个码字只载荷约1.4比特信息量，也就是编码后5个二元符号只携带约1.4比特的信息量。第三章中已知对于无噪无损二元信道，每5个二元码符号最大能载荷5比特的信息量。前述的英文电报等长编码的信息传输效率极低。幻灯片14是否可以使每个信源符号所需的码符号个数减少，也就是说是否可以提高传输效率呢？可以的通过英文电报的例子可以看出，在实际通信中每个信源符号所需的码符号个数能够减少，可以提高传输效率呢！在信息传输中，考虑信源符号出现的概率，以及信源符号之间的依赖关系，就是考虑信源的剩余度，可以使得等长编码中每个信源符号平均所需的码长减少。幻灯片15例244332211sPssPssPssPssPS141iisP143342112ssPssPssPssP0ijssP不考虑符号依赖性，q=4，进行等长二元编码，L=2幻灯片16续考虑符号之间的依赖性，此特殊信源的二次扩展信源为34344343121221212ssPssssPssssPssssPssssPsji1ijjissP4,3,2,1,jissPsPssPijiji幻灯片17续考虑到符号之间的依赖性，二次扩展信源的符号由16个缩减到4个。对此二次扩展信源进行等长编码，所需码长仍为L=2。P194页的例子可以看出，当考虑了信源符号之间的依赖关系后，有些信源符号序列不会出现，使得信源符号序列的个数减少，再进行编码时，所需的平均码长就可以缩短。幻灯片18续等长编码定理给出了信源进行等长编码所需码长的理论极限值，为了严格证明等长编码定理，需引进N长信源序列集的渐近等分隔性和ε典型序列。在信息论的定理证明中，是一种重要的数学工具。幻灯片195.4等长信源编码定理一个熵为H(S)的离散无记忆信源，若对信源长为N的符号序列进行等长编码，设码字是从r个字母的码符号集中，选取l个码元组成。对于任意ε＞0，只要满足则当N足够大时，可实现几乎无失真编码，即译码错误概率能为任意小。反之，若则不可能实现无失真编码，而当N足够大时，译码错误概率近似等于1。logrSHNLlogr2SHNL幻灯片20等长信源编码定理同样适用于平稳离散有记忆信源，只是要求有记忆信源的极限熵和极限方差存在。等长编码定理说明：只要码字传输的信息量大于信源序列携带的信息量，总可以实现几乎无失真编码。幻灯片21编码效率logrNLR'令，这是编码后平均每个信源符号能载荷的最大信息量，称R’为编码后信源的信息传输率。可见编码后信源的信息传输率大于信源的熵，才能实现几乎无失真编码。为了衡量各种实际等长编码方法的编码效果，引进称为编码效率。logrSHRSHNL'幻灯片22一般情况下，最佳等长编码的效率可接近于1。在已知信源熵的条件下，信源序列长度N是与最佳编码效率和允许错误概率有关系。若要求容许错误概率越小，编码效率越高，则信源序列长度N必须越大，然而N越大，实际应用系统的编译码器的复杂性和延时性将大大增加。在实际情况下，要实现几乎无失真的等长编码，N需要大到难以实现的程度。当N有限时，高传输效率的等长码往往要引入一定的失真和错误，它不能像变长码那样可以实现无失真编码。幻灯片235.5变长码变长码往往在N不很大时就可编出效率很高而且无失真的码。变长码也必须是惟一可译码，才能实现无失真编码。对于变长码，要满足惟一可译性，不但码本身必须是非奇异的，而且其任意有限长N次扩展码也都必须是非奇异的。唯一可译变长码的任意有限长N次扩展码都是非奇异码。幻灯片245.5.1唯一可译变长码和即时码在唯一可译变长码中，有一类码，它在译码时无需参考后续的码符号就能立即做出判断，译成对应的信源符号，则这类码称为即时码。设某码字wi=，(k=1,2…m)称码符号序列(j≤m)为码字wi的前缀（又称词头）；或称码字wi是码符号序列的延长。m21iiixxxXxkij21iiixxxj21iiixxx幻灯片25定义5.4若码C中，没有任何完整的码字是其他码字的前缀，即设wi=是码C中的任一码字，而它不是其他码字wk=(j＞m)的前缀，则此码为非延长码或前缀条件码。某码为即时码的充要条件是没有任何完整的码字是其他码字的前缀。即时码就是前缀条件码，前缀条件码（非延长码）也就是即时码。如果没有一个码字是其他码字的前缀，则在译码过程中，当收到一个完整码字的码符号序列时，就能直接把它译成对应的信源符号，无需等待下一个符号到达后才作出判断，这就是即时码。m21iiixxxjm21kkkkxxxx幻灯片26即时码（非延长码）是唯一可译码的一类子码，所以即时码一定是唯一可译码，反之唯一可译码不一定是即时码。因为有些非即时码（延长码）具有唯一可译性，但不满足前缀条件。幻灯片275.5.2即时码的树图构造法即时码的一种简单构造方法是树图法。对给定码字的全体集合C={w1,w2,…,wq}来说，可以用码树来描述它。根、节点、终端节点、中间节点、整树、非整树即时码的码树图还可以用来译码。幻灯片285.5.3克拉夫特（Kraft）不等式对于码符号集为X={x1,x2,…,xr}的任意r元即时码（非延长码），其码字为w1,w2,…,wq，所对应的码长为l1,l2,…lq，则必定满足反之，若码长满足不等式(5.48)，则一定存在具有这样码长的r元即时码。1rq1ili幻灯片29对于码符号集为X={x1,x2,…,xr}的任意r元惟一可译码，其码字为w1,w2,…wq，所对应的码长为l1,l2,…lq，则必定满足Kraft不等式反之，若码长满足不等式(5.48)，则一定存在具有这样码长的r元唯一可译码。上述定理5.5指出了唯一可译码中r、q、li之间的关系。说明如果符合这个关系式，则一定能够构成至少一种唯一可译码，否则，无法构成唯一可译码。1rq1ili幻灯片30定理5.5只给出了唯一可译变长码的存在性，说明唯一可译码一定满足不等式；反之，满足不等式的码不一定是唯一可译码，但一定存在至少一种唯一可译码。任何一个唯一可译码均可用一个即时码来代替，而不改变任一码字的长度。若存在一个码长为l1,l2,…lq，的唯一可译码，则一定存在一个具有相同码长的即时码。即时码很容易用树图法来构造。因此要构造唯一可译码，只需讨论构造即时码即可。幻灯片315.5.4唯一可译变长码的判断法根据唯一可译码的定义可知，当且仅当有限长的码符号序列能译成两种不同的码字序列，则此码一定不是唯一可译变长码。根据