信息论与编码-第7讲-信源及其信息量6-无失真信源编码定理

第1页2024/4/14第二章信源及其信息量本章重点：信源的统计特性和数学模型、各类信源的信息测度—熵及其性质。2.1单符号离散信源2.2多符号离散平稳信源2.3连续信源2.4离散无失真信源编码定理2.5小结ElectronicsEngineeringDepartment,XXXXXxxXxxx第2页2024/4/142.4离散无失真信源编码定理2.4.1问题的提出2.4.2等长／定长编码定理2.4.3不等长编码定理2.4离散无失真信源编码定理第3页2024/4/142.4.1问题的提出(1)为什么要进行信源编码(2)信源编码的概念(3)一些码的定义(4)信源编码的方法2.4离散无失真信源编码定理第4页2024/4/142.4.1问题的提出(1)为什么要进行信源编码信源的两个重要问题信源输出的信息量计算问题；如何更有效地表示信源输出的问题。信源编码就是为了提高通信效率，对信源所发送的消息进行变换的方法之一。为什么要进行信源编码人们都希望无失真传送，首先要对信源无差错编码；数字技术应用越来越多，模拟信源通过数字化变成数字信号传送。2.4离散无失真信源编码定理第5页2024/4/142.4.1问题的提出(2)信源编码的概念信源编码定义：指定能够满足信道特性（适合于信道传输）的符号序列—码序列，来代表信源输出的消息。

编码器：完成编码功能的器件。离散信源输出的码序列离散信源输出的消息是由一个个离散符号组成的随机序列信源编码就是把信源输出的随机符号序列变成码序列2.4离散无失真信源编码定理第6页2024/4/142.4.1问题的提出(2)信源编码的概念研究信源编码时，将信道编码和译码看成是信道的一部分，而突出信源编码；研究信道编码时，将信源编码和译码看成是信源和信宿的一部分，而突出信道编码。2.4离散无失真信源编码定理第7页2024/4/142.4.1问题的提出(2)信源编码的概念讨论无失真信源编码可以先不考虑抗干扰问题，所以它的数学模型比较简单，如图2.4.0。2.4离散无失真信源编码定理第8页2024/4/142.4.1问题的提出(2)信源编码的概念信源符号：编码器的输入是信源符号X={x1,x2,…,xi,…,xn}信源符号序列：码符号/码元：元素

cj是适合信道传输的符号，

C={c1,c2,…,cj,…,cr}称为码符号/码元。码字（码符号序列）：码长（码字长度）：

li称为码字Wi

的码长。编码：从信源符号到码符号的一种映射。若要实现无失真编码，这种映射必须是一一对应的，可逆的。2.4离散无失真信源编码定理第9页2024/4/142.4.1问题的提出(2)信源编码的概念编码器功能：将信源符号集中的符号xi（或者长为N

的信源符号序列）变换成由cj(j=1,2,

…,r)

组成的长度为li的序列。2.4离散无失真信源编码定理第10页2024/4/142.4.1问题的提出(3)一些码的定义二元码：码符号集为X={0,1}，所得码字都是一些二元序列。等长码（定长码）：一组码中所有码字的码长都相同，即：li=L(i=1,2,…,n)。不等长码（变长码）：一组码字中所有码字的码长各不相同，即任意码字由不同长度的码符号序列组成。2.4离散无失真信源编码定理第11页2024/4/142.4.1问题的提出(3)一些码的定义非奇异码：一组码字中所有码字都不相同，即所有信源符号影射到不同的码符号序列。奇异码：一组码中有相同的码字。唯一可译码：码的任意一串有限长的码符号序列只能被唯一地译成所对应的信源符号。2.4离散无失真信源编码定理第12页2024/4/142.4.1问题的提出(3)一些码的定义举例：设信源X

的概率空间为：把它通过一个二元信道传输；为使信源适合信道传输，必须把信源符号变换成0、1符号组成的码符号序列（二元序列）；可采用不同的二元序列使其与信源符号一一对应，得到不同的二元码。2.4离散无失真信源编码定理第13页2024/4/142.4.1问题的提出(3)一些码的定义举例：码1是等长非奇异码，码2是不等长非奇异码。2.4离散无失真信源编码定理第14页2024/4/142.4.1问题的提出(3)一些码的定义码的N

次扩展：以码2的二次扩展为例X2=[α1=x1x1,α2=x1x2,α3=x1x3,…,α16=x4x4]

所以码的二次扩展为：2.4离散无失真信源编码定理第15页2024/4/142.4.1问题的提出(3)一些码的定义码字与信息率的关系有时消息太多，不可能或者没必要给每个消息都分配一个码字；给多少消息分配码字可以做到几乎无失真译码？传送码字需要一定的信息率，码字越多，所需的信息率越大。编多少码字的问题可以转化为对信息率大小的问题；信息率越小越好，最小能小到多少才能做到无失真译码呢？这些问题就是信源编码定理要研究的问题。2.4离散无失真信源编码定理第16页2024/4/142.4.1问题的提出(4)信源编码的方法信源编码有等长和不等长两种方法。等长编码：码字长度L

是固定的，相应的编码定理称为等长信源编码定理，是寻求最小L值的编码方法。不等长编码：L是变值，相应的编码定理称为不等长编码定理。这里的L值最小意味着数学期望最小。2.4离散无失真信源编码定理第17页2024/4/142.4.2等长编码定理(1)等长编码定理等长编码定理：一个熵为H(X)的离散无记忆信源X1X2…Xl…XN，若对信源长为N的符号序列进行等长编码，设码字是从r个字母的码符号集中，选取L个码元组成c1c2…cl…cL。对于任意ε>0，δ>0，只要满足：则当N足够大时，必可使译码差错小于δ，即译码错误概率能为任意小。反之，若：

则不可能实现无失真编码，而当N足够大时，译码错误概率近似等于1。2.4离散无失真信源编码定理第18页2024/4/142.4.2等长编码定理(1)等长编码定理定理中的公式改写成：Llog2r>NH(X)

Llog2r：表示长为L的码符号序列能载荷的最大信息量

NH(X)

：代表长为

N的信源序列平均携带的信息量平均符号熵。

等长编码定理告诉我们：只要码字传输的信息量大于信源携带的信息量，总可实现几乎无失真编码。2.4离散无失真信源编码定理编码效率译码差错率δ第19页2024/4/142.4.2等长编码定理(1)等长编码定理可以证明：信息熵H(X)就是一个界限（临界值）。当编码器输出的信息率超过这个临界值时，就能无失真译码，否则就不行。2.4离散无失真信源编码定理译码差错率小于任意正整数δ。第20页2024/4/142.4.2等长编码定理(1)等长编码定理

信源编码定理从理论上说明了编码效率接近于1，即：的理想编码器的存在性，代价是在实际编码时取无限长的信源符号(N→∞)进行统一编码。说明：等长编码定理是在平稳无记忆离散信源的条件下论证的，但它同样适用于平稳有记忆信源，只是要求有记忆信源的极限熵和极限方差存在即可。对于平稳有记忆信源，定理中的熵应改为极限熵。2.4离散无失真信源编码定理第21页2024/4/142.4.2等长编码定理(2)举例[例2.4.1]：设单符号信源模型为：其信息熵为：H(X)=2.55（比特／符号）

σ2(x)=1.323若要求编码效率为η=

90%，即：译码差错率为δ=10－6，则ε=0.28，在差错率和效率要求都不苛刻的情况下，就必须有1600多万个信源符号一起编码，技术实现非常困难。2.4离散无失真信源编码定理第22页2024/4/142.4.2等长编码定理(2)举例[例]：离散无记忆信源：其信息熵为：自信息的方差为：2.4离散无失真信源编码定理第23页2024/4/142.4.2等长编码定理(2)举例[例]：若对信源X采取等长二元编码时，要求η=0.96，δ=10－5信源序列长度需长达4130万以上，才能实现给定的要求，这在实际中很难实现。一般来说，当N

有限时，高传输效率的等长码往往要引入一定的失真和错误，它不能像变长码那样可以实现无失真编码。2.4离散无失真信源编码定理第24页2024/4/14DepartmentofElectronicsandInformation,NCUTSongPeng2.4.3不等长编码定理(1)基本概念(2)码树图(3)克拉夫特不等式(4)变长编码定理2.4离散无失真信源编码定理第25页2024/4/142.4.3不等长编码定理(1)基本概念不等长编码（变长编码）：不等长编码允许把等长的消息变换成不等长的码序列。通常把经常出现的消息编成短码，不常出现的消息编成长码。这样可使平均码长最短，从而提高通信效率，代价是增加了编译码设备的复杂度。例如：在不等长码字组成的序列中要正确识别每个长度不同的码字的起点就比等长码复杂得多。译码延时／译码同步：接收到一个不等长码序列后，有时不能马上断定码字是否真正结束，因而不能立即译出该码，要等到后面的符号收到后才能正确译出。2.4离散无失真信源编码定理第26页2024/4/142.4.3不等长编码定理(1)基本概念[例2.4.2]：码1：显然不是唯一可译码。x2

和x4

对应于同一码字“11”，码1

是一个奇异码。码2：是非奇异码，不是唯一可译码。当收到一串码符号“01000”时，可将它译成“x4x3x1”，也可译为“x4x1x3”，“x1x2x3”或“x1x2x1x1”等，这种码从单个码字来看虽然不是奇异的，但从有限长的码序列来看，它仍然是一个奇异码。2.4离散无失真信源编码定理第27页2024/4/142.4.3不等长编码定理(1)基本概念[例2.4.2]：码3：虽然是唯一可译码，但它要等到下一个“1”收到后才能确定码字的结束，译码有延时。码4：既是唯一可译码，又没有译码延时。码字中的符号“1”起了逗点的作用，故称为逗点码。即时码/前缀条件码/异前置码/异字头码/逗点码/非延长码：如果一个码的任何一个码字都不是其它码字的前缀。码4是即时码2.4离散无失真信源编码定理

(2)码树图

r

元（r

进制）码树图树根：最顶部画一个起始点。树枝：从根部引出

r

条线段，每条线段都称为树枝。一级节点：自根部起，通过一条树枝到达的节点。一级节点最多有r

个。n级节点：通过

n

条树枝达到的节点。最多有rn。第28页2024/4/142.4.3不等长编码定理2.4离散无失真信源编码定理第29页2024/4/14

(2)码树图终节点/终端节点：下面不再有树枝的节点。中间节点：除了树根和终节点以外的节点。联枝：串联的树枝。满树：在码树图中，当每一个码字的串联枝数都相同时，就是等长码。此时的码树称为满树。2.4.3不等长编码定理2.4离散无失真信源编码定理第30页2024/4/14

(2)码树图例如：码长为N的满树的终节点个数为rN，即可表示rN个码字。非满树：有些树枝未用时的码树。

非满树构造的就是变长码。

如果每一个码字都被安排在终节点上，这种码就是即时码。2.4.3不等长编码定理2.4离散无失真信源编码定理第31页2024/4/14(3)克拉夫特不等式克拉夫特不等式：r

元长度为li，i=1,2,…,n的即时码存在的充要条件是：证明：必要条件：设即时码第

i个码字的长度为li，i=1,2,…,n造一个码树图，在第

li级总共有个节点。第

i个码字占据了第

li级的，根据即时码的定义，其后的树枝不能再用。2.4.3不等长编码定理2.4离散无失真信源编码定理第32页2024/4/14(3)克拉夫特不等式

克拉夫特不等式：r

元长度为li，i=1,2,…,n的即时码存在的充要条件是：证明：必要条件：对于

N级满树，其后不能用的枝数为，那么总共不用的枝数为。

N

级满树第

N级上的总枝数已知为rN，所以必有两边除以rN，就得：。2.4.3不等长编码定理2.4离散无失真信源编码定理第33页2024/4/14(3)克拉夫特不等式

克拉夫特不等式：r

元长度为li，i=1,2,…,n的即时码存在的充要条件是：证明：充分条件：如果式

成立，则必成立，总可以把第N

级上的树枝分成n

组；各组中从第N

级开始删除

(i=1,2,…,n)个枝；相对于N

级满树，等于删除了所有可能的

li级节点的2.4.3不等长编码定理2.4离散无失真信源编码定理第34页2024/4/14(3)克拉夫特不等式

克拉夫特不等式：r

元长度为li，i=1,2,…,n的即时码存在的充要条件是：证明：充分条件：在该组中以第li

级节点作为终节点，就构造好了第

i

个码字。对所有码字如法炮制，则总共删除了所有

rN个节点中的。由，构造了一个即时码。2.4.3不等长编码定理2.4离散无失真信源编码定理第35页2024/4/14(4)不等长编码定理①不等长编码定理（香农第一定理）平均码长：不等长编码定理：若一离散无记忆信源的平均符号熵为H(X)，对信源符号进行

r元变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式：其平均信息率满足不等式

H(X)+ε>R≥H(X)，式中ε为任意正数。2.4.3不等长编码定理2.4离散无失真信源编码定理第36页2024/4/14(4)不等长编码定理①不等长编码定理（香农第一定理）证明：设信源符号X∈{x1,x2,…,xi,…,xn}，概率p(xi)(i=1,2,…,n)

对

xi用一个长度为

li的码字，使：规定为正整数时，上式取等号，非整数时，li

取比它大一些的最接近的整数，则满足上式的整数必存在。将上式分别乘以p(xi)

再对

i求和，得：2.4.3不等长编码定理2.4离散无失真信源编码定理第37页2024/4/14(4)不等长编码定理①不等长编码定理（香农第一定理）证明：对

li取数学期望就是平均值，故：由上面式子可得

lilog2r≥－log2p(xi)，或，对两边求和得：码字长度满足克拉夫特不等式，因而是即时码。2.4.3不等长编码定理2.4离散无失真信源编码定理第38页2024/4/14(4)不等长编码定理①不等长编码定理（香农第一定理）证明：多符号情况对于平稳无记忆信源来说，当信源输出的是长度为N的消息序列时，容易证明定理中式子可改进为：这时的代表平均码序列长度。2.4.3不等长编码定理2.4离散无失真信源编码定理第39页2024/4/14(4)不等长编码定理①不等长编码定理（香农第一定理）证明：多符号情况已知编码后平均每个信源符号能载荷的最大信息量为（不等长信源编码信源平均输出信息率）：2.4.3不等长编码定理2.4离散无失真信源编码定理第40页2024/4/14(4)不等长编码定理①不等长编码定理（香农第一定理）对信源进行不等长编码一般所要求的信源符号长度N

比定长编码小的多。2.4.3不等长编码定理2.4离散无失真信源编码定理第41页2024/4/14(4)不等长编码定理①不等长编码定理（香农第一定理）信道的信息传输率为（从信道的角度看）：编码效率定义为：二元无损无噪信道中r=2，所以Hr(X)=H(X)2.4.3不等长编码定理2.4离散无失真信源编码定理第42页2024/4/14(4)不等长编码定理②举例[例2.4.1]：设单符号信源模型为：其信息熵为：H(X)=2.55（比特/符号）这里r=2，log2r=1要求η>90%，则：2.4.3不等长编码定理2.4离散无失真信源编码定理第43页2024/4/14(4)不等长编码定理②举例[例2.4.1]：与等长编码相比，对同一信源，要求编码效率都达到90%

时，变长编码只需N=4

进行编码，而等长码则要求N

大于1.6875×107。用变长编码时,N不需要很大就可以达到相当高的编码效率而且可实现无失真编码。2.4.3不等长编码定理2.4离散无失真信源编码定理第44页2024/4/142.4.3不等长编码定理(4)不等长编码定理②举例[例]：离散无记忆信源：其信息熵为：用二元码符号(0,1)来构造一个即时码：x1→0，x2→1这时平均码长：编码效率为：信道信息传输率为：R=0.811比特/二元码符号2.4离散无失真信源编码定理第45页2024/4/142.4.3不等长编码定理(4)不等长编码定理②举例[例]：为了提高传输效率，对无记忆信源X

的二次扩展信源X2进行编码，下面给出扩展信源X2

及其某一个即时码：

这个码的平均长度为：

信源符号X中每一单个符号的平均码长为：2.4离散无失真信源编码定理第46页2024/4/142.4.3不等长编码定理(4)不等长编码定理②举例[例]：其编码效率为：编码复杂了一些，但信息传输率有了提高。对信源X的三次和四次扩展信源进行编码，编码效率为：2.4离散无失真信源编码定理第47页2024/4/142.4.3不等长编码定理(4)不等长编码定理②举例[例]：与等长码比较：对于同一信源，要求编码效率都达到96%时，变长码只需对二次扩展信源（N=2）进行编码，而等长码则要求N>4.13×107。结论用变长码编码时，N不需要很大就可以达到相当高的编码效率，而且可以实现无失真编码。随着扩展信源次数的增加，编码的效率越来越接近于1比特/二元码符号，达到信源与信道匹配，使信道得到充分利用。2.4离散无失真信源编码定理第48页2024/4/14(1)单符号离散信源①信息量自信息、条件自信息概念、性质、计算2.5小结第49页2024/4/14(1)单符号离散信源②信息熵信息熵的概念、性质、计算无条件熵、条件熵（信道疑义度、噪声熵）2.5小结第50页2024/4/14(1)单符号离散信源②信息熵信息熵的性质：若离散随机变量X的概率分布为，则H(P)具有以下性质：2.5小结第51页2024/4/14(1)单符号离散信源②信息熵信息熵的性质：若离散随机变量X的概率分布为，则H(P)具有以下性质：2.5小结第52页2024/4/14(1)单符号离散信源②信息熵信息熵的性质：若离散随机变量X的概率分布为，则H(P)具有以下性质：2.5小结第53页2024/4/14(1)单符号离散信源②信息熵互信息概念、性质、计算平均互信息概念、性质、计算2.5小结第54页2024/4/14(1)单符号离散信源②信息熵平均条件互信息：三个离散随机变量X，Y和Z之间的平均条件互信息平均互信息：三个离散随机变量X，Y和Z之间的平均互信息2.5小结第55页2024/4/14(1)单符号离散信源②信息熵平均互信息的性质2.5小结第56页2024/4/14(2)多符号离散信源①离散平稳无记忆信源概念、计算离散无记忆信源的N次扩展信源的熵：H(X)=H(XN)=NH(X)2.5小结第57页2024/4/14(2)多符号离散信源②离散平稳有记忆信源概念、简单计算条件熵、极限熵概念、简单计算离散平稳信源的平均符号熵：离散平稳信源的条件熵：H(XN/X1X2…XN－1)离散平稳信源的极限熵：2.5