g第4-5章：连续信号与连续信道容量

1、第四章 连续信源和连续信道容量n连续信源连续信源n连续信道容量连续信道容量4.1 连续信源n连续信源的统计特性连续信源的统计特性n连续信源的熵连续信源的熵n几种特殊连续信源的熵几种特殊连续信源的熵TTP已优化方便打印1、连续信源的统计特性、连续信源的统计特性n连续信源，指输出消息在时间和取值上都连续的信源；连续信源，指输出消息在时间和取值上都连续的信源；n连续信源输出的消息是随机的，与随机过程相对应；连续信源输出的消息是随机的，与随机过程相对应；n连续信源的统计特性连续信源的统计特性-概率密度函数；概率密度函数；n单变量连续信源的输出是取值连续的随机变量。可用变量单变量连续信源的输出是取值连续

2、的随机变量。可用变量的的概率密度概率密度、变量间的、变量间的条件概率密度条件概率密度和和联合概率密度联合概率密度描述。描述。 一维概率密度函数一维概率密度函数 随机变量随机变量 X 的的一维概率密度函数一维概率密度函数（边缘概率密度函数）为：（边缘概率密度函数）为： yYxXYXYXdyypyYPyFdxxpxXPxFYXyFxFYXypxpdyydFypdxxdFxp)()()()()()()()()()()()()()(的的一一维维概概率率分分布布函函数数、分分别别为为变变量量、的的一一维维概概率率密密度度函函数数、分分别别为为变变量量、 条件概率密度和联合概率密度函数条件概率密度和联合概

3、率密度函数n条件概率密度函数：条件概率密度函数：n联合概率密度函数：联合概率密度函数：n它们之间的关系为：它们之间的关系为：n边缘概率密度函数满足：边缘概率密度函数满足： RXYYRXYXdxxypypdyxypxp)()()()()/()()/()()()()()/(),/(/yxpypxypxpxypyxxyFxypyxpxypYXYXYXXYXYYXXY 2、 连续信源的熵连续信源的熵n单变量连续信源数学模型：单变量连续信源数学模型：nR 是连续变量是连续变量 X 的取值范围。的取值范围。n先将连续信源在先将连续信源在时间上离散化时间上离散化，再对连续变量进行，再对连续变量进行量化量化分

4、层分层，并用离散变量来逼近连续变量。量化间隔越小，并用离散变量来逼近连续变量。量化间隔越小，离散变量与连续变量越接近，离散变量与连续变量越接近，当量化间隔趋近于零时，当量化间隔趋近于零时，离散变量就等于连续变量。离散变量就等于连续变量。 RdxxpxpRX1)()(:并并满满足足：n设设 p(x) 如图所示。把连续随机变量如图所示。把连续随机变量 X 的取值分割成的取值分割成 n 个小个小区间，各小区间等宽，即：区间，各小区间等宽，即：=(ba)/n。则变量落在第。则变量落在第 i 个个小区间的概率为：小区间的概率为：n其中其中 xi 是是 a+(i1) 到到 a+i 之间的某一值。当之间的某

5、一值。当 p(x) 是是 X 的连续函数时，由中值定理可知，必存在一个的连续函数时，由中值定理可知，必存在一个 xi 值使上式成值使上式成立。立。 iaiaixpdxxpiaXiaP) 1()()() 1(n这样连续变量这样连续变量 x 就可用取值为就可用取值为 xi(i=1,2,n) 的离散的离散变量近似。连续信源被量化成离散信源。变量近似。连续信源被量化成离散信源。)(loglim)(log)()()(loglim)(log)()()(loglim)(log)(lim)(lim2022021201200 nbabanbaniinniiinndxxpxpdxxpdxxpxpxpxpxpXH连

6、连续续信信源源的的熵熵为为：时时，若若极极限限存存在在，即即得得当当0,log)()(log)()(log)()(121212 nxpxpxpxpxpXHniiniiiniiin上式右端的第一项一般是定值，而第二项在上式右端的第一项一般是定值，而第二项在 0 时是时是一无限大量。丢掉后一项，定义连续信源的熵为：一无限大量。丢掉后一项，定义连续信源的熵为：n上式定义的熵在形式上和离散信源相似，也满足离散熵上式定义的熵在形式上和离散信源相似，也满足离散熵的主要特性，如可加性，但在概念上与离散熵有差异因的主要特性，如可加性，但在概念上与离散熵有差异因为它失去了离散熵的部分含义和性质。为它失去了离散熵

7、的部分含义和性质。RcdxxpxpXH)(log)()(2)(loglim)(log)()(lim2020 nbandxxpxpXH连续信源的联合熵和条件熵连续信源的联合熵和条件熵n两个连续变量的联合熵：两个连续变量的联合熵：n两个连续变量的条件熵：两个连续变量的条件熵：dxdyxypxypXYHRc)(log)()(22dxdyyxpxypYXHdxdyxypxypXYHRcRc)/(log)()/()/(log)()/(22223、 几种特殊连续信源的熵(1) 均匀分布的连续信源的熵均匀分布的连续信源的熵n一维连续随机变量一维连续随机变量 X 在在 a,b 区间内均匀分布时的熵为区间内均匀

8、分布时的熵为: Hc(X)=log2(ba)n若若 N 维矢量维矢量 X X=(X1X2XN) 中各分量彼此统计独立，中各分量彼此统计独立，且分别在且分别在 a1,b1a2,b2 aN,bN 的区域内均匀分布，的区域内均匀分布，即：即：axbxbxaabxp,01)()()()()(log)(log)(1log)(1)(log)()()(211212112112211111NccciiNiNiiibabaNNiiiNiiibabaNNccXHXHXHababdxdxababdxdxxpxpXXXHXHNNNN NiiiNiiiNiiiabxabxabxp111)(0)()(1)(2) 高斯分布

9、的连续信源的熵高斯分布的连续信源的熵n一维随机变量一维随机变量 X 的取值范围是整个实数轴的取值范围是整个实数轴 R，概率密概率密度函数呈正态分布，即：度函数呈正态分布，即：分分布布的的连连续续信信源源。所所代代表表的的信信源源称称为为高高斯斯由由这这样样随随机机变变量量 X dxxxpXEmXm)(的的均均值值：是是 dxxpmxmXEX)()()(2222 的的方方差差：是是 dxxpxPm)(022率率：就就是是随随机机变变量量的的平平均均功功时时，当当 222)(221)(mxexp-4-3-2-10123400.51-4-3-2-10123400.51-4-3-2-10123400.

10、51nx=-4:0.3:4;nm1=1;n1=0.5;nm2=2;n2=0.5;nm3=1;n3=0.3;nz1=(1/sqrt(2*pi*n1)*exp(-1/2)*(x-m1).2/n12);nz2=(1/sqrt(2*pi*n2)*exp(-1/2)*(x-m2).2/n22);nz3=(1/sqrt(2*pi*n3)*exp(-1/2)*(x-m3).2/n32);nsubplot(3,1,1);n plot(x,z1)n subplot(3,1,2);n plot(x,z2)n subplot(3,1,3);n plot(x,z3)22222222log21log212log)()(

11、)(, 1)( eeXHdxxpmxdxxpc 所所以以：因因为为： dxexpdxxpdxexpdxxpxpXHmxcmx22222)(22)(2222122)(log()2log)(log)()(log)()( 说明说明n 高斯连续信源的熵与数学期望高斯连续信源的熵与数学期望 m 无关，只与方差无关，只与方差2 有有关；关；n 熵描述的是信源的整体特性，由图熵描述的是信源的整体特性，由图2.3.2看出，当均值看出，当均值 m 变化时，只是变化时，只是 p(x) 的对称中心在横轴上发生平移，曲的对称中心在横轴上发生平移，曲线的形状没有任何变化，即数学期望线的形状没有任何变化，即数学期望 m

12、对高斯信源的总对高斯信源的总体特性没有任何影响；体特性没有任何影响；n 若方差若方差2 不同，曲线的形状随之改变，不同，曲线的形状随之改变，所以高斯连续信所以高斯连续信源的熵与方差有关而与数学期望无关源的熵与方差有关而与数学期望无关。这是信源熵的总体。这是信源熵的总体特性的再度体现。特性的再度体现。222log21)( eXHc n连续信道的数学模型连续信道的数学模型n连续信道容量连续信道容量-香农公式香农公式n举例举例4.2 连续信道容量连续信道：输入输出随机变量都取值于连续集合的信道连续信道：输入输出随机变量都取值于连续集合的信道一、单维连续通信系统数学模型：一、单维连续通信系统数学模型：

13、XYp(Y/X)1)(badxxpYxypX)/(数学描述：两类情况两类情况 高斯加性信道高斯加性信道非高斯加性信道非高斯加性信道加性信道的重要性质：加性信道的重要性质： 信道的传递概率密度函数就等于噪声的概率密度函数信道的传递概率密度函数就等于噪声的概率密度函数)()/(npxyp加加性信道性信道条件熵是由噪声引起的，所以称为噪声熵条件熵是由噪声引起的，所以称为噪声熵 NHXYH)/( NHYHXYHYHYXICxpxpxpmax/max;max由于加性噪声由于加性噪声N和信源和信源X相互统计独立，相互统计独立，X的概率密度函数的概率密度函数p(x)的变动不会引起噪声熵的变动不会引起噪声熵H

14、(N)的改变，因此加性信道的容的改变，因此加性信道的容量量C就是选择就是选择p(x)，使输出熵，使输出熵H(Y)达到最大。达到最大。n 连续信道容量连续信道容量可以证明可以证明式中式中 S 信号平均功率信号平均功率 （W）；）； N 噪声功率（噪声功率（W）；）； B 带宽（带宽（Hz）。）。 设噪声单边功率谱密度为设噪声单边功率谱密度为n0，则，则N = n0B；故上式可以改写成：故上式可以改写成：由上式可见，由上式可见，连续信道的容量连续信道的容量Ct和信道带宽和信道带宽B、信号功、信号功率率S及噪声功率谱密度及噪声功率谱密度n0三个因素有关三个因素有关。 )/(1log2sbNSBCt)

15、/(1log02sbBnSBCt当当S ，或，或n0 0时，时，Ct 。但是，当但是，当B 时，时，Ct将趋向何值？将趋向何值？令：令：x = S / n0B，上式可以改写为：，上式可以改写为：利用关系式利用关系式上式变为上式变为)/(1log02sbBnSBCtxtxnSBnSSBnnSC/12002001log1log1)1ln(lim/10 xxxaealnloglog22020/120044. 1log)1 (loglimlimnSenSxnSCxxtB 上式表明，当给定上式表明，当给定S / n0时，若带宽时，若带宽B趋于无穷大，趋于无穷大，信道容量不会趋于无限大，而只是信道容量不会

16、趋于无限大，而只是S / n0的的1.44倍倍。这。这是因为当带宽是因为当带宽B增大时，噪声功率也随之增大。增大时，噪声功率也随之增大。 Ct和带宽和带宽B的关系曲线：的关系曲线：020/120044. 1log)1 (loglimlimnSenSxnSCxxtB图图4-24 信道容量和带宽关系信道容量和带宽关系S/n0S/n0BCt1.44(S/n0)上式还可以改写成如下形式：上式还可以改写成如下形式：式中式中Eb 每比特能量；每比特能量；Tb = 1/B 每比特持续时间。每比特持续时间。 上式表明，为了得到给定的信道容量上式表明，为了得到给定的信道容量Ct，可以，可以增大增大带宽带宽B以换

17、取以换取Eb的减小的减小；另一方面，在接收功率受限的；另一方面，在接收功率受限的情况下，由于情况下，由于Eb = STb，可以，可以增大增大Tb以减小以减小S来保持来保持Eb和和Ct不变不变。 0202021log/1log1lognEBBnTEBBnSBCbbbt)/(1log02sbBnSBCt香农公式的主要结论：香农公式的主要结论： （1 1）信道容量）信道容量C C随随S/NS/N增大而增大；增大而增大； （2 2）N N0, C0, C，无扰信道的容量为无穷大；无扰信道的容量为无穷大； （3 3） ，n n0 0为噪声功率谱密度；为噪声功率谱密度；02044. 1loglimnSen

18、SCW【例例】已知黑白电视图像信号每帧有已知黑白电视图像信号每帧有30万个像素；每个像素有万个像素；每个像素有8个亮个亮度电平；各电平独立地以等概率出现；图像每秒发送度电平；各电平独立地以等概率出现；图像每秒发送25帧。若要求帧。若要求接收图像信噪比达到接收图像信噪比达到30dB，试求所需传输带宽。，试求所需传输带宽。【解解】因为每个像素独立地以等概率取因为每个像素独立地以等概率取8个亮度电平，故每个像素的个亮度电平，故每个像素的信息量为信息量为Ip = -log2(1/ 8) = 3 (b/pix)并且每帧图像的信息量为并且每帧图像的信息量为IF = 300,000 3 = 900,000

19、(b/F)因为每秒传输因为每秒传输25帧图像，所以要求传输速率为帧图像，所以要求传输速率为Rb = 900,000 25 = 22,500,000 = 22.5 106 (b/s) 信道的容量信道的容量Ct必须不小于此必须不小于此Rb值。将上述数值代入式：值。将上述数值代入式：得到得到22.5 106 = B log2 (1 + 1000) 9.97 B最后得出所需带宽最后得出所需带宽B = (22.5 106) / 9.97 2.26 (MHz)NSBCt/1log2n信道的信息传输率信道的信息传输率R与信源分布密切相关；与信源分布密切相关；n当信息传输率当信息传输率R=信道容量信道容量C时

20、时-信道与信源匹配信道与信源匹配n当信息传输率当信息传输率R信道容量信道容量C时时-信道与信源不匹配，信道信道与信源不匹配，信道有冗余有冗余YXIC;信道剩余度CYXICYXIC;-1;信道相对剩余度通信系统的优化模型第五章 信源编码n信源信源编码加密信道编码信源译码信道译码信道解密信宿密 钥 源噪声密 钥 源ULVLULSmCmXnYnCmSmVLK1K2本章内容n离散信源编码离散信源编码n连续信源编码连续信源编码n编码的基本概念编码的基本概念n码的分类码的分类n香农编码香农编码n费诺编码费诺编码n赫夫曼编码赫夫曼编码n无失真信源编码定理无失真信源编码定理-香农第一定理香农第一定理5.1 离

21、散信源编码 a1, a2, , aK 为信源符号集，序列中每一个符号为信源符号集，序列中每一个符号uml都取自信源符都取自信源符号集。号集。 b1 ，b2 ，bD 是适合信道传输的是适合信道传输的D个符号，用作信源编码器的个符号，用作信源编码器的编码符号。编码输出码字编码符号。编码输出码字cm = cm1 cm2 cmn， c mk b1 ，b2 ，bD k = 1, 2 , , n ，n表示码字长度，简称表示码字长度，简称码长码长 信源符号信源符号 a1,a2, , aK 信道符号（码符号）信道符号（码符号） b1, b2, , bD 信源编码器信源编码器 ui = ui1 ui2 uiL

22、码字码字ci = ci1 ci2 cin 1、编码的基本概念信源符号集信源符号集=我我, 是是, 一名一名，学生，老师，编码，理论，学生，老师，编码，理论, 信道符号集信道符号集=I=I ，am，is, are, a, student, coding, theory, apple, 如果某次该编码器的输入是如果某次该编码器的输入是“我是一名学生我是一名学生”，即输入序列，即输入序列ui = (ui1=“我我”，ui2=“是是” ，ui3=“一名一名” ，ui4=“学生学生”)，编码器，编码器的输出的输出“I am a student”，即输出序列，即输出序列ci = (ci1=“I”, ci2

23、 =“am”, ci3 =“a”, ci4 =“student”) 信源编码可看成是从信源符号集到码符号集的一种映射信源编码可看成是从信源符号集到码符号集的一种映射，即将，即将信源符号集中的每个元素（可以是单符号，也可以是符号序列）映信源符号集中的每个元素（可以是单符号，也可以是符号序列）映射成一个长度为射成一个长度为n的码字。对于同一个信源，编码方法是多种的。的码字。对于同一个信源，编码方法是多种的。【例【例5.1】 用用 u1 ，u2 ，u3，u4， 表示信源的四个消息，码符号集为表示信源的四个消息，码符号集为0,1，表，表1列出了该信源的几种不同编码。列出了该信源的几种不同编码。表1 同

24、一信源的几种不同编码2、编码的分类信源信源消息消息各消息各消息概率概率码码1 1码码2 2码码3 3码码4 4u1q( (u1) )000001u2q( (u2) )1101110u3q( (u3) )101000100u4q( (u4) )1111111000码码5 51010010001 3.变长码变长码若码字集合若码字集合C中的所有码字中的所有码字cm (m = 1,2, ,M)，其码长不都相同，称其码长不都相同，称码码C为变长码，表为变长码，表1中列出的码中列出的码3、码、码4 和码和码5就是变长码。就是变长码。 2.等长码等长码在一组码字集合在一组码字集合C中的所有码字中的所有码字c

25、m (m = 1,2, ,M)，其码长都相同，其码长都相同，则称这组码则称这组码C为等长码，表为等长码，表1中列出的码中列出的码1、码、码2 就码长就码长n = 2等长码等长码一般，可以将码简单的分成如下几类：一般，可以将码简单的分成如下几类： 1.二元码二元码若码符号集为若码符号集为0，1，则码字就是二元序列，称为二元码，则码字就是二元序列，称为二元码, ,二元码二元码通过二进制信道传输，这是数字通信和计算机通信中最常见的一种通过二进制信道传输，这是数字通信和计算机通信中最常见的一种码，表码，表1列出的列出的5种码都是二元码。种码都是二元码。 5.非奇异码非奇异码从信源消息到码字的影射是一一

26、对应的，每一个不同的信源消从信源消息到码字的影射是一一对应的，每一个不同的信源消息都用不同的码字对其编码，例表息都用不同的码字对其编码，例表1 1中的码中的码2、码、码3、码、码4和码和码5都都是非奇异码。是非奇异码。 4.奇异码奇异码对奇异码来说，从信源消息到码对奇异码来说，从信源消息到码字的影射不是一一对应的。例表字的影射不是一一对应的。例表1中中的码的码1 1，信源消息，信源消息u2和和u4都用码字都用码字11对其编码，因此这种码就是奇异码对其编码，因此这种码就是奇异码，奇异码不具备惟一可译性。，奇异码不具备惟一可译性。6 6）唯一可译码：）唯一可译码：若码的任意一串有限长的码符号序列只

27、能唯一地被译成所对应若码的任意一串有限长的码符号序列只能唯一地被译成所对应的信源符号序列，则此码称为唯一可译码，否则就称为非唯一的信源符号序列，则此码称为唯一可译码，否则就称为非唯一可译码。可译码。111001004321ssss等长码等长码非奇异码非奇异码0 0 0 1 1 0 1 14321ssss唯一可译唯一可译 如果接收端收到一个完整的码字后，不能立即译码，还要如果接收端收到一个完整的码字后，不能立即译码，还要等下一个码字开始接收后才能判断是否可以译码，这样的码叫等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码。做非即时码。7 7 非即时码：非即时码：100010010

28、14321ssss非奇异码非奇异码1 1 0 1 0 0 1 0 0 01 0?2s01不即时不即时任何一个码字是其它码字的延长或前缀任何一个码字是其它码字的延长或前缀如果收到一个完整的码字以后，就可以立即译码，则叫做即时码。如果收到一个完整的码字以后，就可以立即译码，则叫做即时码。即时码要求任何一个码字都不是其他码字的前缀部分，也叫做即时码要求任何一个码字都不是其他码字的前缀部分，也叫做异异前缀码。前缀码。8 8、即时码、即时码00010010114321ssss非奇异码非奇异码1 0 1 0 0 1 0 0 0 1任何一个码字不是其它码字的延长或前缀任何一个码字不是其它码字的延长或前缀即

29、时 码0 12s即时n即时码的判决准则即时码的判决准则n克拉夫特不等式：克拉夫特不等式：设信源为设信源为 ，对其进行，对其进行r元信源编码，相应码字长度为元信源编码，相应码字长度为 ，则即时码存在，则即时码存在的充要条件是：的充要条件是：nuuuU,21nlll,2111nilirn唯一可译码的判决准则唯一可译码的判决准则n麦克米伦不等式：麦克米伦不等式：设信源为设信源为 ，对其进行，对其进行r元信源编码，相应码字长度为元信源编码，相应码字长度为 ，则唯一可译码，则唯一可译码存在的充要条件是：存在的充要条件是：nuuuU,21nlll,2111nilirn不同编码方式的衡量标准不同编码方式的衡

30、量标准n平均码长：平均码长：对离散无记忆信源进行信源编码，设编码后各个对离散无记忆信源进行信源编码，设编码后各个码字的码长分别为码字的码长分别为 ，则定义该码的平均码长为，则定义该码的平均码长为：n如果某种编码方式的平均码长小于所有其他编码方式，则该如果某种编码方式的平均码长小于所有其他编码方式，则该码称为紧致码或最佳码。码称为紧致码或最佳码。 niiilupL1nlll,21n编码信息率编码信息率(编码速率编码速率)：n码长码长 表示长为表示长为N的信源序列用多少个的信源序列用多少个r进制码符号表示，因进制码符号表示，因此此 表示平均一个信源符号用多少个表示平均一个信源符号用多少个r进制符号

31、表示，再进制符号表示，再乘以乘以 表示将表示将r进制转换成二进制进制转换成二进制signbitrNlR/logNl /rlogln编码效率：编码效率：n含义：理论上平均每个信源符号用多少个二进制符号的个数含义：理论上平均每个信源符号用多少个二进制符号的个数除以实际上用的二进制码符号的个数，即表示一种编码的效除以实际上用的二进制码符号的个数，即表示一种编码的效率。率。 RuHn 有时消息太多，不可能或者没必要给每个消息都分配有时消息太多，不可能或者没必要给每个消息都分配一个码字；一个码字；n 给多少消息分配码字可以做到几乎无失真译码？给多少消息分配码字可以做到几乎无失真译码？n 传送码字需要一定

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

33、最小最小 K 值值的编码方法。的编码方法。n变长编码：变长编码：K 是变值，相应的编码定理称为变是变值，相应的编码定理称为变长编码定理。这里的长编码定理。这里的 K 值最小意味着值最小意味着数学期望数学期望最小最小。信源编码的方法n定长编码定理定长编码定理：一个熵为一个熵为 H(X) 的的离散无记忆信源离散无记忆信源 X1X2XlXN，若对信源长为，若对信源长为 N 的符号序列进行定长编的符号序列进行定长编码，设码字是从码，设码字是从 m 个字母的码符号集中，选取个字母的码符号集中，选取 K 个码元个码元组成组成Y1Y2YkYK。对于任意。对于任意0，0 ，只要满足，只要满足 则当则当 N 足

34、够大时，必可使译码差错小于足够大时，必可使译码差错小于，即译码错误概，即译码错误概率能为任意小率能为任意小.反之，若：反之，若： 则不可能实现无失真编码，而当则不可能实现无失真编码，而当 N 足够大时，译码错误足够大时，译码错误概率近似等于概率近似等于1.)(log2XHmNK2)(log2XHmNK3、定长编码定理n定理中的公式改写成：定理中的公式改写成：Klog2mNH(X) Klog2m：表示长为：表示长为 K 的码符号序列能载荷的最大信息量的码符号序列能载荷的最大信息量NH(X) ：代表长为：代表长为N 的信源序列平均携带的信息量的信源序列平均携带的信息量 平均符号熵。平均符号熵。 定

35、长编码定理告诉我们：定长编码定理告诉我们：只要码字传输的信息量大于信源携只要码字传输的信息量大于信源携带的信息量，总可实现几乎无失真编码。带的信息量，总可实现几乎无失真编码。 译译码码差差错错率率：编编码码效效率率： )()(XHXH：mNK2log)(1XH )(log2XHmNKn可以证明： 。整整数数译译码码差差错错率率小小于于任任意意正正 niiiiiiiiXHxpxpXHxIEXHXHxIxIEXHxIExID1222222222)()(log)()()()()()(2)()()()(22)(xN 只要2222)1 ()()(XHxNn信源编码定理从理论上说明了编码效率接近于信源编码

36、定理从理论上说明了编码效率接近于 1，即：，即： 的理想编码器的存在性，代价是在实际编码时的理想编码器的存在性，代价是在实际编码时 取无限长的信源符号取无限长的信源符号 (N) 进行统一编码。进行统一编码。说明：说明：定长编码定理是在平稳无记忆离散信源的条定长编码定理是在平稳无记忆离散信源的条件下论证的，但它同样适用于平稳有记忆信源，只件下论证的，但它同样适用于平稳有记忆信源，只是要求有记忆信源的是要求有记忆信源的极限熵极限熵和和极限方差极限方差存在即可。存在即可。对于平稳有记忆信源，定理中的熵应改为极限熵。对于平稳有记忆信源，定理中的熵应改为极限熵。1log)(2mNKXH例例：设单符号信源

37、模型为：设单符号信源模型为：n其信息熵为：其信息熵为：H(X)=2.55（比特符号）（比特符号） 2(x)=1.323n若要求编码效率为若要求编码效率为 = 90%，即：即：n译码差错率为译码差错率为=106，则，则=0.28，n在差错率和效率要求都不苛刻的情况下，就必须有在差错率和效率要求都不苛刻的情况下，就必须有1600多万个多万个信源符号一起编码，技术实现非常困难。信源符号一起编码，技术实现非常困难。 04. 005. 006. 007. 010. 010. 018. 04 . 0)(87654321xxxxxxxxxpX90. 0)()( XHXH722106875. 1)(xN例：离

38、散无记忆信源：n其信息熵为：n自信息的方差为： 41,43,)(21xxxpX（比特信源符号）（比特信源符号）811. 034log434log41)(22 XH 4715. 0)811. 0(41log4143log43)()(log)()(2222212222 niiiiXHxpxpxID n若对信源若对信源X采取等长二元编码时，要求采取等长二元编码时，要求=0.96，=105n信源序列长度需长达信源序列长度需长达4130万万以上，才能实现给定的要以上，才能实现给定的要求，这在实际中很难实现。求，这在实际中很难实现。n一般来说，当一般来说，当 N 有限时，高传输效率的等长码往往要引有限时，

39、高传输效率的等长码往往要引入一定的失真和错误，它不能像变长码那样可以实现无入一定的失真和错误，它不能像变长码那样可以实现无失真编码。失真编码。7522222221013.410)04.0()96.0()811.0(4715.0)1()()(XHxN(1) 基本概念基本概念n变长编码（不等长编码）：变长编码（不等长编码）：不等长编码允许把等长的消不等长编码允许把等长的消息变换成不等长的码序列。通常把经常出现的消息编成息变换成不等长的码序列。通常把经常出现的消息编成短码短码，不常出现的消息编成，不常出现的消息编成长码长码。这样可使。这样可使平均码长平均码长最最短，从而提高通信效率，代价是增加了编译

40、码设备的复短，从而提高通信效率，代价是增加了编译码设备的复杂度。杂度。 例如：在不等长码字组成的序列中要正确识别每个长例如：在不等长码字组成的序列中要正确识别每个长度不同的码字的起点就比等长码复杂得多。度不同的码字的起点就比等长码复杂得多。n译码延时译码同步：译码延时译码同步：接收到一个不等长码序列后，有接收到一个不等长码序列后，有时不能马上断定码字是否真正结束，因而不能立即译出时不能马上断定码字是否真正结束，因而不能立即译出该码，要等到后面的符号收到后才能正确译出。该码，要等到后面的符号收到后才能正确译出。(1) 基本概念基本概念(2) 码树图码树图 (3) 变长编码定理变长编码定理 4、变

41、长编码定理例例：码码 1：显然不是惟一可译码。显然不是惟一可译码。x2 和和 x4 对应于同一码字对应于同一码字“11”，码码 1 是一个奇异码。是一个奇异码。码码 2：是非奇异码，不是惟一可译码。当收到一串码符是非奇异码，不是惟一可译码。当收到一串码符号号“01000”时，可将它译成时，可将它译成“x4 x3 x1”，也可译为，也可译为“x4x1x3”， “x1x2x3”或或“x1x2x1x1”等，这种码从单等，这种码从单个码字来看虽然不是奇异的，但从有限长的码序列来看，个码字来看虽然不是奇异的，但从有限长的码序列来看，它仍然是一个奇异码。它仍然是一个奇异码。例例：码码 3：虽然是惟一可译码

42、，但它要等到下一个虽然是惟一可译码，但它要等到下一个“1”收到收到后才能确定码字的结束，译码有延时。后才能确定码字的结束，译码有延时。码码 4：既是惟一可译码，又没有译码延时。码字中的符既是惟一可译码，又没有译码延时。码字中的符号号“1”起了逗点的作用，故称为起了逗点的作用，故称为逗点码逗点码。即时码即时码/前缀条件码前缀条件码/异前置码异前置码/异字头码异字头码/逗点码逗点码/非延非延长码长码：如果一个码的任何一个码字都不是其它码字的前：如果一个码的任何一个码字都不是其它码字的前缀。缀。码 4 是即时码 (2) 码树图码树图 m 元（元（m 进制）码树图进制）码树图n树根：树根：最顶部画一个

43、起始点。最顶部画一个起始点。n树枝：树枝：从根部引出从根部引出 m 条线段，每条线段都称为树枝。条线段，每条线段都称为树枝。n一级节点：一级节点：自根部起自根部起,通过一条树枝到达的节点。一级通过一条树枝到达的节点。一级节点最多有节点最多有 m 个个.nn 级节点：级节点：通过通过 n 条树枝达到的节点。最多有条树枝达到的节点。最多有 mn。n终节点终节点/终端节点：终端节点：下面不再有树枝的节点。下面不再有树枝的节点。n中间节点：中间节点：除了树根和终节点以外的节点。除了树根和终节点以外的节点。n联枝：联枝：串联的树枝。串联的树枝。n满树：满树：在码树图中，在码树图中，当每一个码字的串联枝数

44、都相同时，当每一个码字的串联枝数都相同时，就是定长码。此时的码树称为满树。就是定长码。此时的码树称为满树。 例如：码长为例如：码长为 N 的满树的终节点个数为的满树的终节点个数为 mN，即可表示，即可表示 mN 个码字。个码字。n非满树：非满树：有些树枝未用时的码树。有些树枝未用时的码树。 非满树构造的就是变长码非满树构造的就是变长码。 如果每一个码字都被安排在终节点上如果每一个码字都被安排在终节点上,这种码就是即时码。这种码就是即时码。(3) 变长编码定理变长编码定理 变长编码定理（香农第一定理）变长编码定理（香农第一定理）n平均码长：平均码长：n变长编码定理：变长编码定理：若一若一离散无记

45、忆信源离散无记忆信源的平均符号熵为的平均符号熵为 H(X)，对信源符号进行，对信源符号进行 m 元变长编码，一定存在一种元变长编码，一定存在一种无失真编码方法，其码字平均长度无失真编码方法，其码字平均长度 满足下列不等满足下列不等式：式： 其平均信息率满足不等式其平均信息率满足不等式 H(X) + RH(X)，式，式中中为任意正数。为任意正数。mXHKmXH22log)(log)(1 niiikxpK1)(n多符号情况多符号情况n 对于平稳无记忆信源来说，当信源输出的是长度为对于平稳无记忆信源来说，当信源输出的是长度为 N 的消息序列时，容易证明定理中式子可改进为：的消息序列时，容易证明定理中

46、式子可改进为：n 这时的这时的 代表代表平均码序列长度。平均码序列长度。mXNHKmXNH22log)(log)(1K 证明：证明： 多符号情况多符号情况n 已知编码后已知编码后平均每个信源符号能载荷的最大信息量平均每个信源符号能载荷的最大信息量为（不等长信源编码信源平均输出为（不等长信源编码信源平均输出信息率信息率）：）：，mNKR2logNmN2log足够大时，可使当)(log)(2XHRNmXH故有：n对信源进行变长编码一般所要求的信源符号长度对信源进行变长编码一般所要求的信源符号长度N 比定比定长编码小的多。长编码小的多。：，得到编码效率的下界，得到编码效率的下界由：由： )()(XH

47、RXHNmXHXHRXH2log)()()( 变长编码定理（香农第一定理）n信道的信息传输率为（从信道的角度看）：n编码效率定义为：n二元无损无噪信道中 m=2，所以 Hm(X)=H(X) 码码符符号号比比特特信信源源符符号号码码符符号号信信源源符符号号比比特特/)(/)(KHKHRX XX X KmHKHm2log)()(X XX X ：平平均均码码长长KRKH )(X X 例例：设单符号信源模型为：设单符号信源模型为：其信息熵为：其信息熵为：H(X)=2.55（比特（比特/符号）符号）这里这里 m=2，log2m=1要求要求90%，则：，则： 04. 005. 006. 007. 010.

48、 010. 018. 04 . 0)(87654321xxxxxxxxXPX428. 019 . 0155. 255. 2NN例例：与定长编码相比，对同一信源，要求编码效率都达到与定长编码相比，对同一信源，要求编码效率都达到 90% 时，变长编码只需时，变长编码只需 N=4 进行编码，而等长码则进行编码，而等长码则要求要求 N 大于大于 1.6875107。用变长编码时。用变长编码时, N 不需要不需要很大就可以达到相当高的编码效率而且可实现无失真编很大就可以达到相当高的编码效率而且可实现无失真编码。码。例例：离散无记忆信源：离散无记忆信源：n其信息熵为：其信息熵为：n用二元码符号用二元码符号

49、(0,1)来构造一个即时码：来构造一个即时码：x10，x21n这时平均码长：这时平均码长：n编码效率为：编码效率为：n信道信息传输率为：信道信息传输率为：R=0.811 比特比特/二元码符号二元码符号 41,43,)(21xxxpX信信源源符符号号）（比比特特/811. 034log434log41)(22 XH信信源源符符号号）（二二元元码码符符号号/1 K811. 0)( KXH 例例：n为了提高传输效率，对无记忆信源为了提高传输效率，对无记忆信源 X 的二次扩展信源的二次扩展信源 X2 进行编码，下面给出扩展信源进行编码，下面给出扩展信源 X2 及其某一个即时码：及其某一个即时码：信信源

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

51、610278110322. 二二元元码码符符号号）（比比特特二二元元码码符符号号）（比比特特/9910/985043.R.R 9910985043. 例例：n 与定长码比较：对于同一信源，要求编码效率都达到与定长码比较：对于同一信源，要求编码效率都达到96%时，变长码只需对二次扩展信源（时，变长码只需对二次扩展信源（N=2）进行编码，）进行编码，而等长码则要求而等长码则要求N4.13107。n 结论结论n 用变长码编码时，用变长码编码时，L不需要很大就可以达到相当高的不需要很大就可以达到相当高的编码效率，而且可以实现无失真编码。编码效率，而且可以实现无失真编码。n 随着扩展信源次数的增加，编码

52、的效率越来越接近于随着扩展信源次数的增加，编码的效率越来越接近于1比特比特/二元码符号，达到信源与信道匹配，使信道得二元码符号，达到信源与信道匹配，使信道得到充分利用。到充分利用。n 二进制香农码的编码步骤如下：二进制香农码的编码步骤如下：n将信源符号按概率从大到小的顺序排列，为方便起见，令：将信源符号按概率从大到小的顺序排列，为方便起见，令： p(x1) p(x2) p(xn)n 令令 p(x0)=0，用，用 pa(xj)，j=i+1 表示第表示第 i 个码字的个码字的累加概累加概率率，则：，则：n确定满足下列不等式的整数确定满足下列不等式的整数 ki ，并令，并令 ki 为第为第 i 个码

53、字的长个码字的长度度log2 p(xi) ki 1 log2 p(xi)n 将将 pa(xj) 用二进制表示，并取小数点后用二进制表示，并取小数点后 ki 位作为符号位作为符号 xi 的的编码。编码。njxpxpjiija, 2 , 1, )()(10 niininixpxpxpxpxpxxxxXPX121211)(,)(,),(,),(),(,)(设离散无记忆信源：设离散无记忆信源：5、香农编码例例6.1.1 ：有一单符号离散无记忆信源：有一单符号离散无记忆信源：n对该信源编二进制香农码。对该信源编二进制香农码。 05. 010. 015. 020. 025. 025. 0,)(654321

54、xxxxxxXPXn计算出给定信源香农码的平均码长：计算出给定信源香农码的平均码长：n若对上述信源采用等长编码，要做到无失真译码，每个符若对上述信源采用等长编码，要做到无失真译码，每个符号至少要用号至少要用 3 个比特表示。相比较，香农编码对信源进个比特表示。相比较，香农编码对信源进行了压缩。行了压缩。)/(7 .2505.0410.03)15.02 .0(2225.0符符号号比比特特 Kn由离散无记忆信源熵定义，可计算出信源上熵为：由离散无记忆信源熵定义，可计算出信源上熵为：n对上述信源采用香农编码的信息率为：对上述信源采用香农编码的信息率为：n编码效率为信源熵和信息率之比。则：编码效率为信

55、源熵和信息率之比。则：可以看出，编码效率并不是很高。可以看出，编码效率并不是很高。)/(42. 2)(log)()(612符符号号比比特特 iiixpxpXH2, 17 . 22log17 . 2log22 mLmLKR这这里里%63.897 . 242. 2)( RXH n将概率按从大到小的顺序排列，令：将概率按从大到小的顺序排列，令：p(x1) p(x2) p(xn)n按编码进制数将概率分组，使每组概率尽可能接近或相按编码进制数将概率分组，使每组概率尽可能接近或相等。如等。如编二进制码就分成两组，编二进制码就分成两组，编编 m 进制码就分成进制码就分成 m 组。组。n给每一组分配一位码元。

56、给每一组分配一位码元。n将每一分组再按同样原则划分，重复步骤将每一分组再按同样原则划分，重复步骤 2 和和 3，直，直至概率不再可分为止。至概率不再可分为止。6、费诺编码例例6.3.1：设有一单符号离散信源：设有一单符号离散信源n对该信源编二进制费诺码。对该信源编二进制费诺码。05. 010. 015. 020. 025. 025. 0,)(654321xxxxxxXPX表表二进制费诺编码二进制费诺编码 信源符号信源符号 概率概率 编码编码 码字码字 码长码长 x1 0.25 0 00 2 x2 0.25 0 1 01 2 x3 0.20 0 10 2 x4 0.15 0 110 3 x5 0

57、.10 0 1110 4 x6 0.05 1 1 1 1 1111 4 n该信源的熵为：该信源的熵为：n平均码长为：平均码长为：n对上述信源采用费诺编码的信息率为：对上述信源采用费诺编码的信息率为：n编码效率为：编码效率为：n本例中费诺编码有较高的编码效率。费诺码比较适合于本例中费诺编码有较高的编码效率。费诺码比较适合于每次分组概率都很接近每次分组概率都很接近的信源。特别是对每次的信源。特别是对每次分组概率分组概率都相等都相等的信源进行编码时，可达到理想的编码效率。的信源进行编码时，可达到理想的编码效率。)/(42325. 2)(log)()(612符号比特iiixpxpXH)/( 54 .

58、2)(61符号比特iiikxpK2, 145. 22log145. 2log22mLmLKR这里%91.9845. 242325. 2)(RXH例例6.3.2：有一单符号离散无记忆信源：有一单符号离散无记忆信源n对该信源编二进制费诺码，编码过程如下表。对该信源编二进制费诺码，编码过程如下表。 16/116/116/116/18/18/14/14/1,)(87654321xxxxxxxxXPXn信源熵为：信源熵为：H(X)=2.75(比特比特/符号符号)n平均码长为：平均码长为：n编码效率为编码效率为=1。之所以如此，因为每次所分两组的。之所以如此，因为每次所分两组的概率恰好相等。概率恰好相等。

59、（比比特特符符号号）75. 2440625. 03212. 02)25. 025. 0( K 哈夫曼哈夫曼( (HuffmanHuffman) ) 编码是一种效率比较高的变长无失编码是一种效率比较高的变长无失真信源编码方法。真信源编码方法。7、哈弗曼编码编码步骤(1) 将信源符号按概率从大到小的顺序排列，令：将信源符号按概率从大到小的顺序排列，令：p(x1) p(x2) p(xn)(2) 信源的第一次缩减信源：信源的第一次缩减信源：给两个概率最小的信源符号给两个概率最小的信源符号 p(xn1) 和和 p(xn) 各分配一个码位各分配一个码位“0”和和“1”，将这，将这两个信源符号合并成一个新符

60、号，并用这两个最小的概两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含率之和作为新符号的概率，结果得到一个只包含 (n1) 个信源符号的新信源，用个信源符号的新信源，用 S1 表示。表示。(3) 将缩减信源将缩减信源 S1 的符号仍按概率从大到小顺序排列，的符号仍按概率从大到小顺序排列，重复步骤重复步骤 (2)，得到只含，得到只含 (n2) 个符号的缩减信源个符号的缩减信源 S2。(4) 重复上述步骤，直至缩减信源只剩两个符号为止，此重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为时所剩两个符号的概率之和必为 1。然后从最后一