第4章_离散信源编码理论

1、第1页2022-6-54.1 信源编码的基本概念信源编码的基本概念4.3 信源无失真编码信源无失真编码4.4 信息率失真函数及性质信息率失真函数及性质4.5 信息率失真函数与信道容量信息率失真函数与信道容量4.7 香农第三定理香农第三定理第2页2022-6-54.1 信源编码的基本概念信源编码的基本概念4.1信源编码的基本概念1.为什么要进行信源编码为什么要进行信源编码 信源的两个重要问题信源的两个重要问题q 信源输出的信息量计算问题；信源输出的信息量计算问题；q 如何更有效地表示信源输出的问题。如何更有效地表示信源输出的问题。q 信源编码就是为了提高通信效率，对信源所发送的消息进行变信源编码

2、就是为了提高通信效率，对信源所发送的消息进行变换的方法之一。换的方法之一。 为什么要进行信源编码为什么要进行信源编码q 人们都希望无失真传送，首先要对信源无差错编码；人们都希望无失真传送，首先要对信源无差错编码；q 数字技术应用越来越多，模拟信源通过数字化变成数字信号传数字技术应用越来越多，模拟信源通过数字化变成数字信号传送。送。第3页2022-6-54.1信源编码的基本概念2. 信源编码的概念信源编码的概念 信源编码定义：信源编码定义：指定能够满足信道特性（适合于信道传指定能够满足信道特性（适合于信道传输）的符号序列输）的符号序列码序列码序列，来代表信源输出的消息。，来代表信源输出的消息。

3、编码器：完成编码功能的器件。编码器：完成编码功能的器件。 离散信源输出的码序列离散信源输出的码序列q 离散信源输出的消息是由一个个离散符号组成的随机序列离散信源输出的消息是由一个个离散符号组成的随机序列q 信源编码就是把信源输出的随机符号序列变成码序列信源编码就是把信源输出的随机符号序列变成码序列 nilLlx,x,xxXXXXXX2121)( mjkKky,y,yyYYYYYY2121)( 第4页2022-6-54.1信源编码的基本概念2. 信源编码的概念信源编码的概念研究信源编码时，将信道编码和译码看成是信道的一部分，而突研究信源编码时，将信道编码和译码看成是信道的一部分，而突出信源编码；

4、出信源编码；研究信道编码时，将信源编码和译码看成是信源和信宿的一部分，研究信道编码时，将信源编码和译码看成是信源和信宿的一部分，而突出信道编码。而突出信道编码。第5页2022-6-54.1信源编码的基本概念2. 信源编码的概念信源编码的概念讨论无失真信源编码先不考虑抗干扰问题，它的数学模讨论无失真信源编码先不考虑抗干扰问题，它的数学模型比较简单，如下图。型比较简单，如下图。信源符号：信源符号：编码器的输入是信源符号编码器的输入是信源符号 X=x1,x2,xi,xn。信源符号序列：信源符号序列：码符号码符号/码元：码元：元素元素 yj 是适合信道传输的符号，是适合信道传输的符号，Y=y1,y2,

5、yj,ym 称为码符号称为码符号/码元。码元。XxxxxlLiiiii ),(21x x第6页2022-6-54.1信源编码的基本概念码字（码符号序列）：码字（码符号序列）：码长（码字长度）码长（码字长度）： ki 称为码字长度或简称码长。称为码字长度或简称码长。编码：编码：从信源符号到码符号的一种映射。若要实现无失真编从信源符号到码符号的一种映射。若要实现无失真编码，这种映射必须是一一对应的，可逆的。码，这种映射必须是一一对应的，可逆的。Yyyyylikiiiii ),(21y y2. 信源编码的概念信源编码的概念编码器功能：编码器功能：将信源符号集当中的符号将信源符号集当中的符号 xi（或

6、者长为（或者长为 L 的信的信源符号序列）变换成由源符号序列）变换成由 yj(j=1,2, ,m) 组成的长度为组成的长度为ki 的序列。的序列。Yyyyynixlikiiiiii),(), 2 , 1(21y）（）（iiiiiiiiiiiklYyLlXxyyyxxxllikL, 2 , 1, 2 , 1),(),(2121 y yx x第7页2022-6-54.1信源编码的基本概念二元码：二元码：码符号集为码符号集为 X=0,1，所得码字都是一些二元序列。，所得码字都是一些二元序列。定长码（等长码）：定长码（等长码）：一组码中所有码字的码长都相同，即：一组码中所有码字的码长都相同，即： ki

7、=K(i=1,2,n)。变长码：变长码：一组码字中所有码字的码长各不相同，即任意码字由不一组码字中所有码字的码长各不相同，即任意码字由不同长度的码符号序列组成。同长度的码符号序列组成。非奇异码：非奇异码：一组码字中所有码字都不相同，即所有信源符号影射一组码字中所有码字都不相同，即所有信源符号影射到不同的码符号序列。到不同的码符号序列。奇异码：奇异码：一组码中有相同的码字。一组码中有相同的码字。惟一可译码：惟一可译码：码的任意一串有限长的码符号序列只能被惟一地译码的任意一串有限长的码符号序列只能被惟一地译成所对应的信源符号。成所对应的信源符号。即时码：即时码：不需要考虑后续的码符号，可以根据当前

8、的码符号序列不需要考虑后续的码符号，可以根据当前的码符号序列正确译出相应的码字。正确译出相应的码字。 第8页2022-6-54.1信源编码的基本概念码树图码树图 m 元（元（m 进制）码树图进制）码树图树根：树根：最顶部画一个起始点。最顶部画一个起始点。树枝：树枝：从根部引出从根部引出 m 条线段，每条线段都称为树枝。条线段，每条线段都称为树枝。一级节点：一级节点：自根部起自根部起,通过一条树枝到达的节点。一级节点最多有通过一条树枝到达的节点。一级节点最多有 m 个个.n 级节点：级节点：通过通过 n 条树枝达到的节点。最多有条树枝达到的节点。最多有 mn。终节点终节点/终端节点：终端节点：下

9、面不再有树枝的节点。下面不再有树枝的节点。中间节点：中间节点：除了树根和终节点以外的节点。除了树根和终节点以外的节点。联枝：联枝：串联的树枝。串联的树枝。满树：满树：在码树图中，当每一个码字的串联枝数都相同时，就是定长在码树图中，当每一个码字的串联枝数都相同时，就是定长码。此时的码树称为满树。码。此时的码树称为满树。第9页2022-6-54.1信源编码的基本概念例例：码码 1：显然不是惟一可译码。显然不是惟一可译码。x2 和和 x4 对应于同一码字对应于同一码字“11”，码，码 1 是一个奇异码。是一个奇异码。码码 2：是非奇异码，不是惟一可译码。当收到一串码符号是非奇异码，不是惟一可译码。当

10、收到一串码符号“01000”时，可将它译成时，可将它译成“x4 x3 x1”，也可译为，也可译为“x4x1x3”， “x1x2x3”或或“x1x2x1x1”等，这种码从单个码字来看虽然不是奇异的，但从有限等，这种码从单个码字来看虽然不是奇异的，但从有限长的码序列来看，它仍然是一个奇异码。长的码序列来看，它仍然是一个奇异码。码码 3：虽然是惟一可译码，但它要等到下一个虽然是惟一可译码，但它要等到下一个“1”收到后才能确定收到后才能确定码字的结束，译码有延时。码字的结束，译码有延时。码码 4：既是惟一可译码，又没有译码延时。码字中的符号既是惟一可译码，又没有译码延时。码字中的符号“1”起了起了逗点

11、的作用，故称为逗点码。逗点的作用，故称为逗点码。即时码即时码/前缀条件码前缀条件码/异前置码异前置码/异字头码异字头码/逗点码逗点码/非延长码非延长码：如果一：如果一个码的任何一个码字都不是其它码字的前缀。个码的任何一个码字都不是其它码字的前缀。第10页2022-6-53. 克拉夫特不等式克拉夫特不等式 克拉夫特不等式：克拉夫特不等式：m 元长度为元长度为 ki，i=1,2,n 的即时码存在的充要的即时码存在的充要条件是条件是证明：证明： 必要条件：必要条件：q 设即时码第设即时码第 i 个码字的长度为个码字的长度为 ki，i=1,2,n，q 造一个码树图，在第造一个码树图，在第 ki 级总共

12、有级总共有 个节点。第个节点。第 i 个码字占据个码字占据了第了第 ki 级的级的 ，根据即时码的定义，其后的树枝不能再用。，根据即时码的定义，其后的树枝不能再用。q 对于对于 N 级满树，其后不能用的枝数为级满树，其后不能用的枝数为 ，那么总共不用的，那么总共不用的枝数为枝数为 。q N 级满树第级满树第 N 级上的总枝数已知为级上的总枝数已知为 mN，所以必有，所以必有 两边除以两边除以 mN，就得：，就得： 。11 nikimikm1ikm4.1信源编码的基本概念ikNm nikNim1NnikNmmi 111 nikim第11页2022-6-53. 克拉夫特不等式克拉夫特不等式 克拉夫

13、特不等式：克拉夫特不等式：m 元长度为元长度为 ki，i=1,2,n 的即时码存在的充要条件的即时码存在的充要条件是是证明：证明： 充分条件：充分条件：q 如果式如果式 成立，则成立，则 必成立，总可以把必成立，总可以把 第第 N 级上的树枝分成级上的树枝分成 n 组；组；q 各组中从第各组中从第 N 级开始删除级开始删除 (i=1,2,n)个枝；个枝；q 相对于相对于 N 级满树，等于删除了所有可能的级满树，等于删除了所有可能的 ki 级节点的级节点的q 在该组中以第在该组中以第 ki 级节点作为终节点，就构造好了第级节点作为终节点，就构造好了第 i 个码字。个码字。q 对所有码字如法炮制，

14、则总共删除了所有对所有码字如法炮制，则总共删除了所有 mN 个节点中的个节点中的 。q 由于由于 ，于是构造了一个即时码。，于是构造了一个即时码。11 nikimikNm iikkmm 1NnikNmmi 111 nikim4.1信源编码的基本概念 nikim111 nikim第12页2022-6-54.3 信源无失真编码信源无失真编码 码字与信息率的关系码字与信息率的关系q 有时消息太多，不可能或者没必要给每个消息分配一有时消息太多，不可能或者没必要给每个消息分配一个码字；个码字；q 给多少消息分配码字可以做到几乎无失真译码？给多少消息分配码字可以做到几乎无失真译码？q 传送码字需要一定的信

15、息率，码字越多，所需的信息传送码字需要一定的信息率，码字越多，所需的信息率越大。编多少码字的问题可以转化为对信息率大小的问率越大。编多少码字的问题可以转化为对信息率大小的问题；题；q 信息率越小越好，最小能小到多少才能做到无失真译信息率越小越好，最小能小到多少才能做到无失真译码呢？码呢？ 这些问题就是信源编码定理要研究的问题。这些问题就是信源编码定理要研究的问题。第13页2022-6-54.3 信源无失真编码信源无失真编码 信源编码有定长和变长两种方法。信源编码有定长和变长两种方法。定长编码：定长编码：码字长度码字长度 K 是固定的，相应的编码定理称为定长信源是固定的，相应的编码定理称为定长信

16、源编码定理，是寻求最小编码定理，是寻求最小 K 值的编码方法。值的编码方法。变长编码：变长编码：K 是变值，相应的编码定理称为变长编码定理。这里是变值，相应的编码定理称为变长编码定理。这里的的 K 值最小意味着数学期望最小。值最小意味着数学期望最小。 无失真信源编码就是要求信源符号与码字之间形成一一映射无失真信源编码就是要求信源符号与码字之间形成一一映射的关系，并且要求编码输出的码字序列对应的反变换是惟一的，的关系，并且要求编码输出的码字序列对应的反变换是惟一的，即是惟一可译码的，否则会造成译码错误或者失真。即是惟一可译码的，否则会造成译码错误或者失真。 第14页2022-6-51. 定长编码

17、定理定长编码定理(1) 定长编码定理定长编码定理定长编码定理：定长编码定理：一个熵为一个熵为 H(X) 的离散无记忆信源的离散无记忆信源 X1X2XlXL，若，若对信源长为对信源长为 L 的符号序列进行定长编码，设码字是从的符号序列进行定长编码，设码字是从 m 个字母的码符个字母的码符号集中，选取号集中，选取 K 个码元组成个码元组成Y1Y2YkYK。对于任意。对于任意0，0 ，只要，只要满足满足 当当 L 足够大时，必可使译码差错小于足够大时，必可使译码差错小于，即译码错误概率能为任意，即译码错误概率能为任意小；反之，若：小；反之，若： 则不可能实现无失真编码，而当则不可能实现无失真编码，而

18、当 L 足够大时，译码错误概率近似等于足够大时，译码错误概率近似等于1。 )(log2XHmLK 2)(log2 XHmLK4.3信源无失真编码第15页2022-6-5(1) 定长编码定理定长编码定理 4.3信源无失真编码 )(log2XHmLK定理中的公式改写成：定理中的公式改写成：Klog2mLH(X) Klog2m：表示长为：表示长为 K 的码符号序列能载荷的最大信息量的码符号序列能载荷的最大信息量LH(X) ：代表长为：代表长为 L 的信源序列平均携带的信息量的信源序列平均携带的信息量 平均符号熵。平均符号熵。：mLK2log定长编码定理说明：只要码字传输的信息量大于信源携带的信息定长

19、编码定理说明：只要码字传输的信息量大于信源携带的信息量，总可实现几乎无失真编码。量，总可实现几乎无失真编码。 译译码码差差错错率率：编编码码效效率率： )()(XHXH)(1XH 第16页2022-6-5(1) 定长编码定理定长编码定理 信源熵信源熵 H(X) 就是一个界限（临界值）。当编码器输出的信息率超就是一个界限（临界值）。当编码器输出的信息率超过这个临界值时，就能无失真译码，否则就不行。过这个临界值时，就能无失真译码，否则就不行。 信源编码定理从理论上说明了编码效率接近于信源编码定理从理论上说明了编码效率接近于 1，即：，即： 的理想编码器的存在性，代价是在实际编码时取无限长的信源符号

20、的理想编码器的存在性，代价是在实际编码时取无限长的信源符号 (L) 进行统一编码。进行统一编码。说明：说明：定长编码定理是在平稳无记忆离散信源的条件下论证的，定长编码定理是在平稳无记忆离散信源的条件下论证的，但它同样适用于平稳有记忆信源，只是要求有记忆信源的但它同样适用于平稳有记忆信源，只是要求有记忆信源的极限熵极限熵和和极限方差极限方差存在即可。对于平稳有记忆信源，定理中的熵应改为存在即可。对于平稳有记忆信源，定理中的熵应改为极限熵。极限熵。1log)(2mLKXH4.3信源无失真编码第17页2022-6-5 定长编码定理的意义定长编码定理的意义 (1) 对于给定的离散无记忆信源对于给定的离

21、散无记忆信源X和码元数和码元数m，如果对，如果对X的的N次扩次扩展信源进行无失真等长编码，那么当码长展信源进行无失真等长编码，那么当码长K满足条件满足条件 时，一定存在一种编码方案，能够实现无失真编码；反之，不可能时，一定存在一种编码方案，能够实现无失真编码；反之，不可能进行无失真编码。进行无失真编码。 4.3信源无失真编码2log()KmH XL (2) 对于给定的信源离散无记忆对于给定的信源离散无记忆X，信源的熵，信源的熵H(X)是一定的，当码是一定的，当码符号数量符号数量m选定时，可以增加信源序列的长度选定时，可以增加信源序列的长度L，使得无失真编码产，使得无失真编码产生的每个符号平均长

22、度尽可能小，但是无论怎样增加序列长生的每个符号平均长度尽可能小，但是无论怎样增加序列长度度L，信源每个符号的平均码长不可能小于，信源每个符号的平均码长不可能小于 ，即码长的极限，即码长的极限为为 。 KKL2()logH Xm2()logH Xm第18页2022-6-5定长编码定理的意义定长编码定理的意义4.3信源无失真编码(3) 当序列长度当序列长度L一定，译码错误概率一定，译码错误概率PE为为2E22 ( )()( , )iD I aXPLLL其中，其中，DI(ai)为自信息量方差，定义为为自信息量方差，定义为221 ( )( )log( )()riiiiD I ap ap aHX 当信源

23、给定时，自信息方差是一定的，序列长度当信源给定时，自信息方差是一定的，序列长度L越大，越大，错误概率越小，要实现无失真编码，序列长度就应当足够长，错误概率越小，要实现无失真编码，序列长度就应当足够长，使使PE能够满足一定要求。能够满足一定要求。 第19页2022-6-5(2) 举举 例例例例4.1：设单符号信源模型为：设单符号信源模型为：其信息熵为：其信息熵为：H(X)=2.55（比特符号）（比特符号） 若编码效率为若编码效率为 = 90%，取，取L=1，则则取：取： =0.28，若译码差错率为若译码差错率为 =106,在差错率和效率要求都不苛刻的情况下，就必须有在差错率和效率要求都不苛刻的情

24、况下，就必须有1600多万个信多万个信源符号一起编码，技术实现非常困难。源符号一起编码，技术实现非常困难。 04. 005. 006. 007. 010. 010. 018. 04 . 0)(87654321xxxxxxxxxpX90. 0)()( XHXH722106875. 1)( xL4.3信源无失真编码1. 定长编码定理定长编码定理82221()( )(log)()7.8246.5021.322iiiiXD I xppH X2.5590%2.83bit/sK 2.832=7.11第20页2022-6-5(2) 举举 例例例例：离散无记忆信源：离散无记忆信源：其信息熵为：其信息熵为：自信

25、息的方差为：自信息的方差为：12,31( ),44xxXp x（比比特特信信源源符符号号）811. 034log434log41)(22 XH 4715. 0)811. 0(41log4143log43)()(log)()(2222212222 niiiiXHxpxpxID 4.3信源无失真编码若对信源若对信源X采取等长二元编码时，要求采取等长二元编码时，要求=0.96，=105信源序列长度需长达信源序列长度需长达4130万以上，才能实现给定的要求，这在实际万以上，才能实现给定的要求，这在实际中很难实现。中很难实现。一般来说，当一般来说，当 L 有限时，高传输效率的等长码往往要引入一定的失有限

26、时，高传输效率的等长码往往要引入一定的失真和错误，它不能像变长码那样可以实现无失真编码。真和错误，它不能像变长码那样可以实现无失真编码。752222221013. 410)04. 0()96. 0()811. 0(4715. 0)1 ()()( XHxL第21页2022-6-5 编码信息率：编码信息率：设离散无记忆信源设离散无记忆信源X的熵为的熵为H(X)，对，对X扩展信源的符扩展信源的符号序列号序列XL进行等长无失真编码，码长为进行等长无失真编码，码长为K，编码信息率为，编码信息率为 如果编码信息率如果编码信息率R小于信源熵小于信源熵H(X)，存在一种编码器能够实现无，存在一种编码器能够实现

27、无失真编码；反之，如果编码信息率大于信源熵失真编码；反之，如果编码信息率大于信源熵H(X)，则不能实现无，则不能实现无失真编码。失真编码。 编码效率编码效率： 4.3信源无失真编码1. 定长编码定理定长编码定理2logKRmL2()()logH XH XKRmL第22页2022-6-5(1) 基本概念基本概念变长编码（不等长编码）：变长编码（不等长编码）：不等长编码允许把等长的消息变不等长编码允许把等长的消息变换成不等长的码序列。通常把经常出现的消息编成短码，不换成不等长的码序列。通常把经常出现的消息编成短码，不常出现的消息编成长码。这样可使平均码长最短，从而提高常出现的消息编成长码。这样可使

28、平均码长最短，从而提高通信效率，代价是增加了编译码设备的复杂度。通信效率，代价是增加了编译码设备的复杂度。 例如：在不等长码字组成的序列中要正确识别每个长度不同例如：在不等长码字组成的序列中要正确识别每个长度不同的码字的起点就比等长码复杂得多。的码字的起点就比等长码复杂得多。译码延时译码同步：译码延时译码同步：接收到一个不等长码序列后，有时不接收到一个不等长码序列后，有时不能马上断定码字是否真正结束，因而不能立即译出该码，要能马上断定码字是否真正结束，因而不能立即译出该码，要等到后面的符号收到后才能正确译出。等到后面的符号收到后才能正确译出。2. 变长编码定理变长编码定理4.3信源无失真编码第

29、23页2022-6-5(2) 变长编码定理变长编码定理（香农第一定理）（香农第一定理）平均码长：平均码长：变长编码定理：变长编码定理：若一离散无记忆信源的平均符号熵为若一离散无记忆信源的平均符号熵为 H(X)，对信，对信源符号进行源符号进行 m 元变长编码，一定存在一种无失真编码方法，其码元变长编码，一定存在一种无失真编码方法，其码字平均长度字平均长度 满足下列不等式：满足下列不等式：化莫化莫 其平均信息率满足不等式其平均信息率满足不等式 H(X) + RH(X)，式中，式中为任意正数。为任意正数。mXHKmXH22log)(log)(1 niiikxpK1)(4.3信源无失真编码K对信源进行

30、变长编码一般所要求的信源符号长度对信源进行变长编码一般所要求的信源符号长度 L 比定长编码小比定长编码小的多。的多。：，得到编码效率的下界，得到编码效率的下界由：由： )()(XHRXHLmXHXHRXH2log)()()( 第24页2022-6-5(2) 变长编码定理变长编码定理（香农第一定理）（香农第一定理）信道的信道的信息传输率信息传输率为（从信道的角度看）：为（从信道的角度看）：编码效率编码效率定义为：定义为：二元无损无噪信道中二元无损无噪信道中 m=2，所以，所以 Hm(X X)=H(X X) 码码符符号号比比特特信信源源符符号号码码符符号号信信源源符符号号比比特特/)(/)(KHK

31、HRX XX X KmHKHm2log)()(X XX X ：平平均均码码长长KRKH )(X X 4.3信源无失真编码第25页2022-6-5(2) 变长编码定理变长编码定理 举举 例例 例例：设单符号信源模型为：设单符号信源模型为：其信息熵为：其信息熵为：H(X)=2.55（比特（比特/符号）符号）这里这里 m=2，log2m=1要求要求90%，则：，则： 04. 005. 006. 007. 010. 010. 018. 04 . 0)(87654321xxxxxxxxXPX140 28.L 4.3信源无失真编码与定长编码相比，对同一信源，要求编码效率都达到与定长编码相比，对同一信源，要

32、求编码效率都达到 90% 时，变时，变长编码只需长编码只需 L=4 进行编码，而等长码则要求进行编码，而等长码则要求 L 大于大于 1.6875107。用变长编码时用变长编码时, L 不需要很大就可以达到相当高的编码效率而且可不需要很大就可以达到相当高的编码效率而且可实现无失真编码。实现无失真编码。2 550 912 55.L 第26页2022-6-5(2) 变长编码定理变长编码定理举举 例例 例例：离散无记忆信源：离散无记忆信源：其信息熵为：其信息熵为：用二元码符号用二元码符号(0,1)来构造一个即时码：来构造一个即时码：x10，x21这时平均码长：这时平均码长：编码效率为：编码效率为：信道

33、信息传输率为：信道信息传输率为：R=0.811 比特比特/二元码符号二元码符号12,31( ),44xxXp x信源符号）信源符号）（比特（比特 /811. 034log434log41)(22 XH信信源源符符号号）（二二元元码码符符号号/1 K811. 0)( KXH 4.3信源无失真编码为了提高传输效率，对无记忆信源为了提高传输效率，对无记忆信源 X 的二次扩展信源的二次扩展信源 X2 进行编码，进行编码，下面给出扩展信源下面给出扩展信源 X2 及其某一个即时码：及其某一个即时码：第27页2022-6-5信信源源符符号号）（二二元元码码符符号号/322722 KK二二个个信信源源符符号号

34、）（二二元元码码符符号号 /162731613163216311692 K 这个码的平均长度为：这个码的平均长度为： 信源符号信源符号X中每一单个符号的平均码长为：中每一单个符号的平均码长为：4.3信源无失真编码其编码效率为：其编码效率为：信息传输速率为：信息传输速率为：编码复杂了一些，但信息传输率有了提高。编码复杂了一些，但信息传输率有了提高。对信源对信源X的三次和四次扩展信源进行编码，编码效率为：的三次和四次扩展信源进行编码，编码效率为：信息传输率为：信息传输率为：二二元元码码符符号号）（比比特特/96102.R 9610278110322. 二二元元码码符符号号）（比比特特二二元元码码符

35、符号号）（比比特特/9910/985043.R.R 9910985043. 12,31( ),44xxXp x第28页2022-6-5(2) 变长编码定理变长编码定理 与定长码比较：对于同一信源，要求编码效率都达到与定长码比较：对于同一信源，要求编码效率都达到96%时，时，变长码只需对二次扩展信源（变长码只需对二次扩展信源（N=2）进行编码，而等长码则要求）进行编码，而等长码则要求L4.13107。 结论结论q 用变长码编码时，用变长码编码时，L L不需要很大就可以达到相当高的编码效率，不需要很大就可以达到相当高的编码效率，而且可以实现无失真编码。而且可以实现无失真编码。q 随着扩展信源次数的

36、增加，编码的效率越来越接近于随着扩展信源次数的增加，编码的效率越来越接近于1 1比特比特/ /二元码符号，达到信源与信道匹配，使信道得到充分利用。二元码符号，达到信源与信道匹配，使信道得到充分利用。4.3信源无失真编码第29页2022-6-5信道编码定理：信道编码定理：无论何种信道，只要信息率无论何种信道，只要信息率 R 小于信道容量小于信道容量 C，总能找到一种编码，使在信道上能以任意小的错误概率，总能找到一种编码，使在信道上能以任意小的错误概率和任意接近于和任意接近于 C 的传输率来传送信息。反之，若的传输率来传送信息。反之，若 R C，则，则传输总要失真。传输总要失真。 完全无失真传送不

37、可实现完全无失真传送不可实现q 实际的信源常常是连续的，信息率无限大，要无失真实际的信源常常是连续的，信息率无限大，要无失真传送要求信息率传送要求信息率 R 为无穷大；为无穷大；q 实际信道带宽是有限的，所以信道容量受限制。要想实际信道带宽是有限的，所以信道容量受限制。要想无失真传输，所需的信息率大大超过信道容量无失真传输，所需的信息率大大超过信道容量 RC。基本概念基本概念第30页2022-6-5技术发展的需要技术发展的需要q 随着科技的发展，数字系统应用得越来越广泛，需要传送、存储随着科技的发展，数字系统应用得越来越广泛，需要传送、存储和处理大量的数据。为了提高传输和处理效率，需要对数据压

38、缩，和处理大量的数据。为了提高传输和处理效率，需要对数据压缩，这样会带来一定的信息损失。这样会带来一定的信息损失。q 信息时代，信息爆信息时代，信息爆炸，炸，要求解决对海量数据有效的压缩，减少数要求解决对海量数据有效的压缩，减少数据的存储容量据的存储容量(如各种数据库、电子出版物、多媒体娱乐如各种数据库、电子出版物、多媒体娱乐)、传输时、传输时间间(如数据通信和遥测如数据通信和遥测)、或占有带宽、或占有带宽(如多媒体通信、数字音频广播、如多媒体通信、数字音频广播、高清晰度电视高清晰度电视)，想方设法压缩给定消息，想方设法压缩给定消息 集合占用的空间域、时间集合占用的空间域、时间域和频率域资源域

39、和频率域资源.q 如海洋地球物理勘探遥测数据，用如海洋地球物理勘探遥测数据，用 60 路传感器，每路信号路传感器，每路信号 1kHz，16 位位 A/D 量化，每航测量化，每航测 1km 就需记录就需记录 1 盘盘 0.5 英寸的磁带，一条测英寸的磁带，一条测量船每年就可勘测量船每年就可勘测 15000km。基本概念基本概念4.4信息率失真函数及性质第31页2022-6-5实际生活中的需要实际生活中的需要q 实际生活中，人们一般并不要求获得完全无失真的消息，通常只实际生活中，人们一般并不要求获得完全无失真的消息，通常只要求近似地再现原始消息，即允许一定的失真存在。要求近似地再现原始消息，即允许

40、一定的失真存在。q 打电话：打电话：即使语音信号有一些失真，接电话的人也能听懂。人耳接即使语音信号有一些失真，接电话的人也能听懂。人耳接收信号的带宽和分辨率是有限的。收信号的带宽和分辨率是有限的。q 放电影：放电影：理论上需要无穷多幅静态画面，由于人眼的理论上需要无穷多幅静态画面，由于人眼的“视觉暂留视觉暂留性性”，实际上只要每秒放映，实际上只要每秒放映 24 幅静态画面。幅静态画面。q 有些失真没有必要完全消除。有些失真没有必要完全消除。q 既然允许一定的失真存在，对信息率的要求便可降低。既然允许一定的失真存在，对信息率的要求便可降低。基本概念基本概念4.4信息率失真函数及性质第32页202

41、2-6-5信息率失真理论研究的内容信息率失真理论研究的内容: 信息率信息率与与允许失真允许失真之间的关系之间的关系。 信息率失真函数信息率失真函数q 香农定义了信息率失真函数香农定义了信息率失真函数 R(D)。q “保真度准则下的信源编码定理保真度准则下的信源编码定理”指出：在允许一定指出：在允许一定失真度失真度 D 的情况下，信源输出的信息率可压缩到的情况下，信源输出的信息率可压缩到 R(D)。q 信息率失真理论是量化（模数转换）、数模转换、频信息率失真理论是量化（模数转换）、数模转换、频带压缩和数据压缩的理论基础。带压缩和数据压缩的理论基础。基本概念基本概念4.4信息率失真函数及性质第33

42、页2022-6-5信息率失真函数极小值问题信息率失真函数极小值问题q I(X;Y) 是是 P(X) 和和 P(X/Y) 的二元函数；的二元函数；q 在讨论信道容量时：在讨论信道容量时：规定了规定了P(X/Y) ， I(X;Y) 变成了变成了P(X) 的函数。的函数。在离散情况下，因为在离散情况下，因为 I(X;Y) 对对 p(xi) 是上凸函数，所以变更是上凸函数，所以变更 p(xi) 所求所求极值一定是极值一定是 I(X;Y)的极大值；在连续情况下，变更信源的极大值；在连续情况下，变更信源 P(X) 求出的求出的也是极大值，但求极值时还要一些其它的限制条件。也是极大值，但求极值时还要一些其它

43、的限制条件。q 在讨论信息率时：在讨论信息率时：规定规定 p(xi)，变更，变更 p(yj /xi) 来求平均互信息的极值，来求平均互信息的极值，称为信道容量对偶问题。由于称为信道容量对偶问题。由于I(X;Y) 是是 p(yj /xi) 的下凸函数，所求的的下凸函数，所求的极值一定是极小值。但若极值一定是极小值。但若 X 和和 Y 相互统计独立（相互统计独立（p(yj /xi)= p(yj )），这），这个极小值就是个极小值就是 0，因为，因为 I(X;Y) 是非负的，是非负的，0 必为极小值，这样求极小必为极小值，这样求极小值就没意义了。值就没意义了。q 引入一个失真函数，计算在失真度一定的

44、情况下信息率的极小值就引入一个失真函数，计算在失真度一定的情况下信息率的极小值就变的有意义了。变的有意义了。4.4信息率失真函数及性质第34页2022-6-5(1) 信息率与失真的关系信息率与失真的关系信道中固有的噪声和不可避免的干扰，使信源的消息通信道中固有的噪声和不可避免的干扰，使信源的消息通过信道传输后造成误差和失真。过信道传输后造成误差和失真。误差或失真越大，接收者收到消息后对信源存在的不确误差或失真越大，接收者收到消息后对信源存在的不确定性就越大，获得的信息量就越小，信道传输消息的信定性就越大，获得的信息量就越小，信道传输消息的信息率也越小。息率也越小。4.4.1 失真测度失真测度4

45、.4信息率失真函数及性质第35页2022-6-5(2) 失真度失真度 失真度失真度q 设离散无记忆信源为：设离散无记忆信源为：q 信源符号通过信道传送到接收端信源符号通过信道传送到接收端Y：q 信道的传递概率矩阵：信道的传递概率矩阵：q 对每一对对每一对 (xi,yj)，指定一个非负函数，指定一个非负函数 d(xi,yj)0 i=1,2,n j=1,2,m 称称 d(xi,yj) 为单个符号的失真度（失真函数）。表示信为单个符号的失真度（失真函数）。表示信源发出一个符号源发出一个符号 xi，在接收端再现，在接收端再现 yj 所引起的误差或失真。所引起的误差或失真。1212,()(),(),()

46、mjmYyyyp yp yp yp y )(,),(),(,)(2121nnixpxpxpxxxxpX 112111222212(/)(/)(/)(/)(/)(/)(/)(/)(/)(/)mmnnmnp yxp yxp yxp yxp yxp yxp YXp yxp yxp yx 4.4.1 失真测度失真测度4.4信息率失真函数及性质第36页2022-6-5(2) 失真度失真度 失真矩阵失真矩阵q 失真度还可表示成矩阵的形式失真度还可表示成矩阵的形式q 称称 D 为失真矩阵。它是为失真矩阵。它是 nm 阶矩阵。阶矩阵。 连续信源和连续信道的失真函数连续信源和连续信道的失真函数 在连续信源和连续

47、信道情况下，失真度定义为：在连续信源和连续信道情况下，失真度定义为：d(x,y)0。 ),(),(),(),(),(),(),(),(),(212221212111mnnnmmyxdyxdyxdyxdyxdyxdyxdyxdyxdD D4.4信息率失真函数及性质第37页2022-6-5(3) 常用的失真函数常用的失真函数 第一种：第一种：q 当当 i=j 时，时，X 与与 Y 的取值一样，用的取值一样，用 Y 来代表来代表 X 就没有误差，所以就没有误差，所以定义失真度为定义失真度为 0；q 当当 ij 时，用时，用 Y 代表代表 X 就有误差。就有误差。q 这种定义认为对所有不同的这种定义认

48、为对所有不同的 i 和和 j 引起的误差都一样，所以定义引起的误差都一样，所以定义失失真度常数真度常数 a。q 特点：特点：对角线上的元素均为对角线上的元素均为 0，对角线以外的其它元素都为常数，对角线以外的其它元素都为常数 a。q 汉明失真函数汉明失真函数： a=1 。 0000000),(aaaaaaaaaaaajiaajiyxdjiD D4.4.1 失真测度失真测度4.4信息率失真函数及性质第38页2022-6-5(3) 常用的失真函数常用的失真函数 第二种（平方误差失真函数）：第二种（平方误差失真函数）：d(xi,yj)=(yjxi)2q 失真矩阵：平方误差失真矩阵。失真矩阵：平方误差

49、失真矩阵。q 若信源符号代表输出信号的幅度值，则较大的幅度失真比较小的幅若信源符号代表输出信号的幅度值，则较大的幅度失真比较小的幅度失真引起的错误更为严重度失真引起的错误更为严重, 严重程度用平方表示严重程度用平方表示。 第三种（绝对失真函数）：第三种（绝对失真函数）： d(xi,yj)=|yjxi|4.4信息率失真函数及性质q 失真矩阵：绝对误差失真矩阵失真矩阵：绝对误差失真矩阵。 失真函数是根据人们的实际需要和失真引起的损失、风险、主观感觉失真函数是根据人们的实际需要和失真引起的损失、风险、主观感觉上的差别大小等因素人为规定的。上的差别大小等因素人为规定的。21112212000mmnny

50、xyxyxyxDyxyx第39页2022-6-5(4) 平均失真度平均失真度 平均失真度平均失真度q d(xi,yj) 只能表示两个特定的具体符号只能表示两个特定的具体符号 xi 和和 yj 之间的失真。之间的失真。q 平均失真度：平均失真度：失真度的数学期望，即：失真度的数学期望，即： nimjjiijiyxdxypxpD11),()/()( 由由数数学学期期望望的的定定义义：中中的的统统计计平平均均值值：的的联联合合概概率率空空间间和和在在),()(),(jijiyxdEDXYPYXyxd 4.4.1 失真测度失真测度4.4信息率失真函数及性质第40页2022-6-5(4) 平均失真度平均

51、失真度平均失真度的意义平均失真度的意义q 是在平均意义上，从总体上对整个系统失真情况的描述。它是是在平均意义上，从总体上对整个系统失真情况的描述。它是信源统计特性信源统计特性 p(xi) 、信道统计特性、信道统计特性 p(yj/xi ) 和失真度和失真度 d(xi,yj) 的函数的函数 。q 当当 p(xi)，p(yj/xi ) 和和 d(xi,yj) 给定后，平均失真度就不是一个随机变给定后，平均失真度就不是一个随机变量了，而是一个确定的量。量了，而是一个确定的量。q 如果信源和失真度一定，如果信源和失真度一定， 就只是信道统计特性的函数。信道传就只是信道统计特性的函数。信道传递概率不同，平

52、均失真度随之改变。递概率不同，平均失真度随之改变。DD 保真度准则保真度准则q 人们所允许的失真指的都是平均意义上的失真。人们所允许的失真指的都是平均意义上的失真。q 保真度准则：保真度准则：规定平均失真度规定平均失真度 不能超过某一限定的值不能超过某一限定的值 D，即即 ，则，则 D 就是允许失真的上界。该式称为保真度准则。就是允许失真的上界。该式称为保真度准则。DDD 4.4信息率失真函数及性质 nimjjiijiyxdxypxpD11),()/()(第41页2022-6-5(5) N 次扩展信道的平均失真度次扩展信道的平均失真度 N 次扩展次扩展q 单符号离散无记忆信源单符号离散无记忆信

53、源 X x1,x2,xn 的的 N 次扩展信源次扩展信源 XN =X1X2XN ，在信道中的传递作用相当于单符号离散无记忆信道的，在信道中的传递作用相当于单符号离散无记忆信道的 N 次扩展信道，输出也是一个随机变量序列次扩展信道，输出也是一个随机变量序列 YN =Y1Y2YN 。q 此时输入共有此时输入共有 nN 个不同的符号：个不同的符号：q 信道的输出共有信道的输出共有 mN 个不同的符号：个不同的符号： NNniiiiiiininiiixxxxxxxxxNN, 2 , 1, 2 , 1,)(21212121 a a4.4.1 失真测度失真测度 NNmjjjjjjjmjmjjjyyyyyy

54、yyyNN, 2 , 1, 2 , 1,)(21212121 b b4.4信息率失真函数及性质第42页2022-6-5(5) N 次扩展信道的平均失真度次扩展信道的平均失真度 N 次扩展次扩展q 定义离散无记忆信道定义离散无记忆信道 X P(Y/X) Y 的的 N 次扩展信道的输入序列次扩展信道的输入序列 X和输出序列和输出序列 Y 之间的失真函数：之间的失真函数：q 定义的说明：定义的说明：离散无记忆信道的离散无记忆信道的 N 次扩展信道输入输出之间的失次扩展信道输入输出之间的失真，等于输入序列真，等于输入序列 X 中中 N 个信源符号个信源符号 xi1,xi2,xiN 各自通过信道各自通过

55、信道 X P(Y/X) Y ，分别输出对应的，分别输出对应的 N 个信宿符号个信宿符号 yj1,yj2,yjN 后所引起的后所引起的 N 个单符号失真个单符号失真 d(xik ,yjk)(k=1,2, ,N) 之和。之和。q N 次离散无记忆扩展信源和信道的平均失真度为次离散无记忆扩展信源和信道的平均失真度为 ，则：，则：121211221NNNNkkijiiijjjNijijijijkd xyd x xxy yyd xyd xyd xyd xy(,)(,)(,)(,)(,)(,) 11()( ) (/) ( ,)NNnmijiijijD Np x p yx d x y)(ND4.4信息率失真

56、函数及性质第43页2022-6-512111NNnmNNkijiijijkD Np x p yx d x yDDDD( )( ) (/) ( ,) (5) N 次扩展信道的平均失真度次扩展信道的平均失真度 “N 次扩展次扩展”与与“单符号单符号”平均失真度的关系平均失真度的关系q 由扩展信源和扩展信道的无记忆性有：由扩展信源和扩展信道的无记忆性有：q （k=1,2, ,N）是同一信源）是同一信源 X 在在 N 个不同时刻通过同一信道个不同时刻通过同一信道 X P(Y/X) Y 所造成的平均失真度，因此都等于单符号信源所造成的平均失真度，因此都等于单符号信源 X 通过信道通过信道 X P(Y/X

57、) Y 所造成的平均失真度，即：所造成的平均失真度，即：q 结论说明：结论说明：离散无记忆离散无记忆 N 次扩展信源通过离散无记忆次扩展信源通过离散无记忆 N 次扩展信次扩展信道的平均失真度是单符号信源通过单符号信道的平均失真度的道的平均失真度是单符号信源通过单符号信道的平均失真度的 N 倍。倍。q N 次扩展的保真度准则：次扩展的保真度准则：离散无记忆离散无记忆 N 次扩展信源通过离散无记次扩展信源通过离散无记忆忆 N 次扩展信道的保真度准则为：次扩展信道的保真度准则为：11( )() (/)(/)1,2,1,2,kkkNNNNiijijikkp xp xp yxp yxinjm，11( )

58、 (/) ( ,)nmkijiijijDDp x p yx d x y kD:( )D NND 因此()D NND4.4信息率失真函数及性质第44页2022-6-5(1) 试验信道试验信道 单符号信源和单符号信道的试验信道单符号信源和单符号信道的试验信道q 当固定信源（当固定信源（ P(X)已知），单个符号失真度也给定时，选择信道已知），单个符号失真度也给定时，选择信道使使 。凡满足要求的信道称为。凡满足要求的信道称为 D 失真许可的试验信道失真许可的试验信道，简称，简称试试验信道验信道。q 所有试验信道构成的集合用所有试验信道构成的集合用 PD 来表示，即：来表示，即： mjniDDxypP

59、ijD, 2 , 1, 2 , 1: )/( DD 4.4.2 信息率失真函数的定义信息率失真函数的定义 N 次扩展的试验信道次扩展的试验信道： 对于离散无记忆信源的对于离散无记忆信源的 N 次扩展信源和离散无记忆信道的次扩展信源和离散无记忆信道的 N 次次扩展信道，其试验信道集合扩展信道，其试验信道集合 PD(N) 为：为：()(/):();1,2,1,2,NND NjiPp yxD NND injm4.4信息率失真函数及性质第45页2022-6-5(2) 信息率失真函数信息率失真函数 单符号信源和单符号信道的信息率失真函数单符号信源和单符号信道的信息率失真函数q 信息率失真函数（率失真函数

60、）信息率失真函数（率失真函数） R(D) ：在信源和失真度给定以：在信源和失真度给定以后，后，PD 是满足保真度准则是满足保真度准则 的试验信道集合，平均互信息的试验信道集合，平均互信息 I(X;Y) 是信道传递概率是信道传递概率 p(yj /xi) 的下凸函数，所以在的下凸函数，所以在 PD 中一定可以中一定可以找到某个试验信道，使找到某个试验信道，使 I(X;Y) 达到最小，即：达到最小，即：q 在信源给定以后，总希望在允许一定失真的情况下，传送信源所在信源给定以后，总希望在允许一定失真的情况下，传送信源所必须的信息率越小越好。从接收端来看，就是在满足保真度准则必须的信息率越小越好。从接收