数字通信原理信息论基础PPT学习教案

1、会计学1数字通信原理信息论基础数字通信原理信息论基础2010 Copyright 21、 (1) 消息是由符号、文字、数字、语音或图像组成的序列； (2) 消息是信息的，信息是消息的；消息中可能包 含信息，也可能不包含信息； (3) 收到一则消息后，所得的信息量，在数量上等于获得 消息前后“”的消除量； (4) 通信的目的在与传送信息。第1页/共102页2010 Copyright 32、 (1) 某消息的信息量获得该消息后不确定性的消除量； 不确定性可能性概率问题： (2) 不同的消息有信息量的多少的区别，因此 信息量应该是满足可加性的概率的函数。第2页/共102页2010 Copyrigh

2、t 4n 离散信源统计特性的描述方法 设离散信源包含N种可能的不同符号，相应的概率场可表述为 概率场满足条件： 11Niixp NNxpxpxpXpxxxX.:.:2121第3页/共102页2010 Copyright 5 信息量作为概率的函数，具有形式 若 与 统计独立，满足可加性要求 如定义 显然有 同时满足概率函数和可加性两个要求。 iixpfxIixjx jijijijixpfxpfxpxpfxxpfxxI iiixpxpfxI1log jijijijixpxpxpxpfxxpfxxI1log1log第4页/共102页2010 Copyright 6n 离散消息xi的信息量: 信息量的

3、单位与对数的底有关： log以2为底时，单位为：bit log以e为底时，单位为：nit log以10为底时，单位为，hart 一般在缺省时取单位为比特。 iiixPxPxPIlog1log第5页/共102页2010 Copyright 7n 输出的各符号统计独立，计算序列S“113200”的信息量 81414183:3210:XpX bitsppppppppppppSpSI83.111415. 11415. 1232201log01log21log31log11log11log0023111log1log第6页/共102页2010 Copyright 8n 定义4.2.2 离散信源 的熵 熵

4、是信源在每个符号的平均信息量。NixXi,.,2 , 1,: iNiixpxpXHlog1第7页/共102页2010 Copyright 9n ：求离散信源 的熵。 按照定义： 81414183:3210:XpX 符号比特906. 181log8141log4141log4183log83log41iiixpxpXH第8页/共102页2010 Copyright 10n ：若上述离散信源发送独立的符号序列： 201 020 130 213 001 203 210 100 321 010 023 102 002 10 312 032 100 120 210 (1)求总的信息量；(2)利用熵估计总

5、的信息量。 (1) (2) 比特55.10781log741log1341log1483log23log41iiixpnI 比特62.108096. 1713142341XHnIii第9页/共102页2010 Copyright 11 当离散信源X取等概分布时，其熵H(X)取最大值。 当信源取等概分布时，具有最大的。 ：两个信源符号的 情形。 P(x1)=p,P(x2)=1-p 当p=1/2时，H(X)=Hmax NiNNNNNNNHxpxpxpH1211log1log11,.,1,1,.,max第10页/共102页2010 Copyright 12 两随机变量 的 满足条件：NjMiyxXY

6、ji,.,2 , 1;,.,2 , 1,:NMNMMMMMNNNNyxpyxyxpyxyxpyxyxpyxyxpyxyxpyxyxpyxyxpyxyxpyxXYpXY,.,.,.,.,:221122222212221121211111111 MiNjjiyxp第11页/共102页2010 Copyright 13 定义4.2.3 两随机变量 的联合熵 如两随机变量统计独立，有NjMiyxXYji,.,2 , 1;,.,2 , 1,:符号比特 MijiNjjiyxpyxpXYH11log YHXHypypxpxpypxpypxpyxpyxpXYHjNjjMiiiMijiNjjiMijiNjji

7、loglogloglog111111第12页/共102页2010 Copyright 14 对于统计独立的两随机变量，不能从其中一个获得有关另外一个的任何信息。第13页/共102页2010 Copyright 15 定义4.2.4 两随机变量 的条件熵 一般地有 具有某种相关性的两随机变量，一个随机变量的出现总是 有助于降低另一随机变量的不确定性。 NjMiyxXYji,.,2 , 1;,.,2 , 1,: MijiNjjiyxpyxpYXH11log MiijNjjixypyxpXYH11log XHYXH第14页/共102页2010 Copyright 16 信道的输入： 信道的输出： 信

8、道模型(特性)可用其转移概率来描述p(xi/yj)xiyji=1,2,.,Mj=1,2,.,N图 4-3-1 信道模型NjMiyxXYXYpji,.,2 , 1,.,2 , 1,:,MixXi,.,2 , 1,:NjyYj,.,2 , 1,:第15页/共102页2010 Copyright 17 信道模型(特性)可用其转移概率来描述，一般地有 输出不仅与当前的输入有关，而且与之前的若干个输入值 有关，呈现某种“记忆”效应。 nkkkkjjixxxypNjMiyxXY.,.,2 , 1,.,2 , 1,:1第16页/共102页2010 Copyright 18 输出仅与当前的输入有关 或 MNM

9、MNNijxypxypxypxypxypxypxypxypxypxypXYp/././././212222111211NMNNMMjiyxpyxpyxpyxpyxpyxpyxpyxpyxpyxpYXp/././././212222111211第17页/共102页2010 Copyright 19 ：二元的离散无记忆信道 发“0”和发“1”时 能正确接收的概率为0.99， 错误的概率为0.01。 即有 转移矩阵 99. 01/10/0 pp01. 01/00/1 pp99. 001. 001. 099. 0/ijxypXYp第18页/共102页2010 Copyright 20 转移概率 是一种

10、条件概率，在通信系统中可表示 收到 后，发送端发送的是符号 的概率。 接收端收到 后，关于 的不确定性可表示为 定义4.3.1 互信息量为： ：收到 后，关于 的。 jiyxp/ixjyjyixjijiyxpyxI/1log/ jiijiyxIxIyxI/;jyix第19页/共102页2010 Copyright 21 互信息量具有 互信息量的 (1) 若 （2）若 (3) 若 (4) 若 ijjijjijiijijiijiijixyIypxypypxpyxpxpyxpyxpxpyxIxIyxI;/loglog/log/1log1log/;1/jiyxp ijixIyxI; 1/jiiyxpx

11、p ijixIyxI;0 ijixpyxp/0;jiyxI ijixpyxp/00;jiyxI第20页/共102页2010 Copyright 22 定义4.3.2 平均互信息量为： 平均互信息量具有 表明从统计上来说，两相关联的随机变量集，其中一个的出 现总是有利于提供有关另外一个的信息。 MiNjjijiyxIyxpYXI11;0;YXI第21页/共102页2010 Copyright 23 XYIYXI; YXHXHYXI/; XYHYHYXI/; XHYXH/ YHXYH/ YHXHXYH第22页/共102页2010 Copyright 24 两张密切相关图像示例 两张无关的图像示例第

12、23页/共102页2010 Copyright 25 当信源X与Y统计独立时 (1)两个符号同时出现时提供的平均信息量等于每个符号的平均信息量之和； (2)一个符号不能提供有关另一符号的任何信息。 YHXHXYH0;XYIYXI第24页/共102页2010 Copyright 26 当两个信源相关时 (1)联合熵小于两个信源的熵的和: (2)平均互信息量等于两信源熵重合的部分； (3)信源的条件熵等于其熵减去平均互信息量：YXI, XH YHXYHYXHXYH YHXHXYH YXIXHYXH;/第25页/共102页2010 Copyright 27 已知信道的转移矩阵 信源符号集： 符号传输

13、速率： 系统的为： MNMMNNijxypxypxypxypxypxypxypxypxypxyp/././././212222111211 XSR SMiNjijiijiSMiNjijijiSIRxpyxpxpyxpRxpyxpyxpRYXIR 1111/log/log;第26页/共102页2010 Copyright 28 定义4.3.3 离散信道的最大传输速率为其信道容量 信道特性(转移矩阵)确定之后，其容量由信源的统计特性决 定。 ：能使单位时间内信道可传输的平均信息量达到信 道容量的信源称之。 已知匹配信源的分布特性： ： SMixpIMixpRYXIRCii;maxmax,.,2,

14、1,.,2, 1, Nixpim,.,2 , 1, SmIMixpRIRCi,.,2, 1,max第27页/共102页2010 Copyright 29 已知信道转移概率，匹配信源统计特性的求解： (1)解方程组 求解得 (2)求最大平均互信息量： (3)求相应后验概率： (4)解方程组，确定匹配信源的分布特性 MixypxypxypjNjijNjijij,.2 , 1/log/11Mij,.2 , 1,NjmjI12logNjypIjj,.2 , 12max NjxpxypxypypimMiijMiijj,.2 , 1/11第28页/共102页2010 Copyright 30 ：已知信道转

15、移概率 (1)解方程组的参数： (2)求最大平均互信息量： (3)求相应后验概率： 2141041010000104104121/ijxypXYp2, 0, 0, 2432125log2222log2log20021NjmjI 1012,522522,101225log2425log0325log0225log21ypypypyp第29页/共102页2010 Copyright 31 ： (4)获得匹配信源统计特性： (5)信道容量为： 304,3011,3011,3044321xpxpxpxpmmmm秒比特/1320100032. 1100025logSmRIC第30页/共102页2010

16、Copyright 32 转移矩阵 各行各列均具有的信道称之。 离散无记忆对称信道满足条件： 任意的列元素和 任意的行元素和 MNMMNNijxypxypxypxypxypxypxypxypxypxyp/././././212222111211NjxypxypMiijij,.,2 , 1/log/1常数MixypxypNjijij,.,2 , 1/log/1常数第31页/共102页2010 Copyright 33 离散无记忆对称信道的条件熵满足： 与。 若输入信道的信源符号等概 则信道的输出符号也等概 ijNjijxypxypXYHlog/1jiMijiyxpyxpYXHlog/1 MiMx

17、pi,.,2 , 1,1 NjNxypMxypMxypxpyxpypMiijMiijMiijiMijij,.,2 , 1,1/1/1/1111第32页/共102页2010 Copyright 34 对于离散无记忆对称信道，若要使信息传输速率达到信道容量，要求。 SSMixpSMixpSMixpSMixpRRXHRXHRYXHXHRYXICiiii常数常数常数logMmaxmax/max;max,.,2, 1,.,2, 1,.,2, 1,.,2, 1,第33页/共102页2010 Copyright 35 若已知随机信号 幅度取值的概率密度函数： 取值在任意小区间 内的概率 连续信源转变为具有n

18、个随机变量的信源，且有 利用离散随机变量熵的定义，得 tX xp iaiaxxxXXiii,) 1(, nixpdxxpxPiaiaiiXX,.,2 , 11 11111nibaiaianiiniidxxpdxxpxpxPXX niiiiniinxpxpxPxPXH11loglog第34页/共102页2010 Copyright 36 连续信源的熵应为 可见连续信源的熵无限大。该熵称为连续信源的，无 法确切地定义。 通常上式的第一项是有限值，且其具有特定的物理意义。 dxxpxpdxxpxpxpxpxpxpxpxpxpXHXHbanbanniiinniinniiinniiinnnloglogl

19、imlogloglimloglimloglimloglimloglimlim, 0, 01, 01, 01, 01, 0, 0第35页/共102页2010 Copyright 37 连续信源的相对熵为 4.4.1 某信号的相对熵为 信号经2倍幅度放大后的相对熵为 信号的简单放大并没有增加任何新的信息，但其相对熵发生 了增大的变化，这说明相对熵已经不再具有信源平均信息量 的内涵。 dxxpxpXhbalog 121log21log111dxdxxpxpXhba 241log41log222dxdxxpxpXhba第36页/共102页2010 Copyright 38 对于连续随机变量，同样可以导

20、出其条件熵可见连续信源的条件熵取值无限大。通常上式的第一项是一 个有限取值的量。连续信源的熵和条件熵均取值无限大，说明要在一个容量有 限的通信系统中传递连续信源的全部信息是不可能的。 loglim/log/loglim/loglog/loglim/lim/00, 0110, 00, 0XXYYXXYYbabababajinimjjimndxdyyxpyxpypdxdyyxpxypyxpyxpYXHYXH第37页/共102页2010 Copyright 39 连续信源的相对条件熵 容易导出：说明和的与普通的和的 一样，仍然等于。同理可以导出： XXYYbabadxdyyxpyxpypYXh/lo

21、g/ YXhXhYXhXhYXHXHYXI/loglim/loglim/;00 XYhYhYXI/; XYhYhXhYXI;第38页/共102页2010 Copyright 40(1)峰值功率受限情况下的相对熵最大化条件 可以证明：当连续信源的概率密度函数服从均匀分布时，该连续信源有最大的相对熵。 在区间 分布连续信源 的概率密度函数为 其相对熵为 ba,X bxaabxp,1 abXhXhplogmaxAx AxAAxp,21 AXhXhp2logmax第39页/共102页2010 Copyright 41(2)均值受限情况下的相对熵最大化条件 可以证明：当连续信源的概率密度函数服从指数分布

22、时，该连续信源有最大的相对熵。 指数分布 相对熵 dxxxp 0, 00,1xxeaxpax aXhXhplogmax第40页/共102页2010 Copyright 42(2)平均功率受限情况下的相对熵最大化条件 可以证明：当连续信源的概率密度函数服从高斯分布时，该连续信源有最大的相对熵。 高斯分布 相对熵 dxxpx2 22221mxexpeXhXhp2log)()(2max第41页/共102页2010 Copyright 43 加性高斯噪声信道 信道输入： 信道输出： 加性高斯噪声： 已知通过信道后，从 可获得的关于 的平均互信息量 若已知信号 的带宽为： 则无冗余的抽样频率应为： (单

23、位时间的样点数) 单位时间内传输的信息量，即信息速率为nxynxyyx XYhYhYXhXhYXI/;xWWfS2 WXYhYhWYXhXhWYXIfYXIRSb2/2/2;第42页/共102页2010 Copyright 44 加性高斯噪声 信号与噪声间的关系可用方程组表示为 或 二维函数概率密度间的关系 WYXICxp2;maxxnxxnxnxy,xyyxnxyxx,xyxnJxnpxyp第43页/共102页2010 Copyright 45 加性高斯噪声(续) 因为 所以有11101,yyxnxyxnyyxxxyxxxyxnJ npxpxnpxyp npxpnpxpxpxnpxpxypx

24、yp/第44页/共102页2010 Copyright 46 加性高斯噪声(续) 可得 NhdnnpnpdxdnnpxnpdxdnnpxyxnJxnpdxdyxypxypXYh logloglog/log/ WNhYhWXYhYhWYXICxpxpxp2max2/max2;max第45页/共102页2010 Copyright 47加性高斯噪声(续) 因为 (1) 在均方受限的条件下，高斯分布的信源有最大的相对熵 (2) 两高斯分布的随机变量之和( )仍为高斯随机变量 (3) 信号 与噪声 统计独立 因而有nxy 2222222222121nxyynxyyeeyp 2222log212log2

25、1lognxyeedyypypYh第46页/共102页2010 Copyright 48加性高斯噪声(续) 若记 得 222222222221logloglog22log22log212log212maxnxnnxnynynyxpWWWeeWWeeWNhYhC22,nxNSSNRWNSWC1log1log22第47页/共102页2010 Copyright 49加性高斯噪声(续) (1) 信道容量C随S/N增大而增大； (2) C一定时，W与S/N之间可以彼此互换； (3) N 0, C ：无扰信道的容量为无穷大； (4) 对受高斯噪声干扰的信道，当 W ， 信道容量趋于 一确定值：SNRWN

26、SWC1log1log2202044. 1loglimNSeNSCW第48页/共102页2010 Copyright 50 ：单位时间单位频带内可达到的信息速率。NSWC1log图 441 归一化信道容量特性曲线第49页/共102页2010 Copyright 51 ：单位信息速率所需要的最小带宽。图 442 归一化信道带宽特性曲线11logNSCW第50页/共102页2010 Copyright 52图 443 关于Eb/n0的带宽特性曲线 关于Eb/N0的 Eb：比特能量； N0：噪声功率密度谱； 当 Eb/N0 1.59dB 时，无法实现无差 错的传输。120CWbCWnE第51页/共1

27、02页2010 Copyright 53 （1）去除信息中的冗余度，使传输的符号都是独立的，没有多余的成分； （2）使传输的符号所含的信息最大化。例如，通过使编码后的符号以等概分布的形式出现，使每个符号可能携带的信息量达到最大； （3）采用不等长编码，让出现概率大的符号用较短的码元序列表示，对概率小的符号用较长的码元序列； (4) 在允许一定失真的条件下，如何实现高效率的编码。第52页/共102页2010 Copyright 54 (DMS: Discrete Memoryless Source） 输出序列： 各个符号间彼此独立 其中 反之，若输出的各符号间有一定的相关性，则其为一种 有记忆的

28、信源。 有记忆的信源，经过处理后，有可能变为一种无记忆的信 源。如有记忆的信源，经过理想的、完全去除冗余度的 压缩编码后的输出。.21012nXXXXXXSXiLiSSi,.2 , 1,:第53页/共102页2010 Copyright 55 等长编码：对信源的每个符号，或每组符号，用长度相等的代码来表示。 ：由若干码元（码字元素）构成的代码单元。 采用二进制码元编码 若信源符号集有L种符号，要保证译码的惟一性，码字长度应取 表示取 X 的整数部分。2222log,loglog1,logLLNLL若为整数若不为整数 X第54页/共102页2010 Copyright 56 ：对码字承载信息能力

29、的利用程度 其中 由离散信源的最大熵定理，可知 编码效率与信源的统计特性有很大的关系，仅当信源输出 的符号等概分布时，且 为整数时，效率才能达 到100。 H SN= logH SLiii=1-p Sp S 2loglogH SLNLiii=1-p Sp S LSH2logmaxL2log第55页/共102页2010 Copyright 57 将J个信源符号进行联合编码 J 个信源符号可能排列组合个数 平均每个信源符号所需要的码元个数 若 是整数 若 不是整数 J 取值的增大有利于效率的提高。JL2222log,loglog1,logJJJLLNLL若为整数若不为整数22loglogJJNLN

30、LJJL2logL2logJLJLJNNJJ1log1log22第56页/共102页2010 Copyright 58 一般的编译码系统译码的要求 记：编码器输入的符号集： 编码输出的码元集： 扩展编码的符号长度： 编码输出的码字长度为： 则保证译码惟一性要求 平均每个信源符号所需的码元数应满足DiBBi,.2 , 1,:JNJNJDL22loglogJNLNJDLiSSi,.2 , 1,:J第57页/共102页2010 Copyright 59 若信源 可以获得较高的编码效率。 若信源则通常编码效率较低。 2logH SL 2logH SLNNp S=max 2logH SL 2logH S

31、LNN=第58页/共102页2010 Copyright 60 对于长度为 J 的DMS码组(或称为一序列): 码组中的每个符号： 由符号间的独立性，有 码组 包含的信息量为： 根据熵的含义，随着 J 的增大，有 或 SHJXIJJJXJX1JJjjP XP X 111logloglogJJJjjJJjjjjI XP XP XP XI X LiSSXij,.2 , 1,: SHJXIIJJJ第59页/共102页2010 Copyright 61 ：满足下列条件的序列 的集合称之。 其中 ，通常是一个很小的数。 ：典型序列集的补集称之。 典型序列集和非典型序列集构成了序列 所有组合构成 符号组的

32、空间。 ,:JSJI XTJXH SH SJJX0JX第60页/共102页2010 Copyright 62 ：任给 ，当 J 足够大时，有 即有： 典型序列出现的概率：若 则 即有： 典型序列趋于。 典型序列的数目：0,1JSP XTJ lim,1SJP TJ,JSXTJ 22J H SJ H SJP X 2JH SJP X 12,2J H SJ H SSTJ ,2JH SSTJ第61页/共102页2010 Copyright 63 典型序列的出现概率： 即： 典型序列集 为； 非典型序列集 为。 ,21JSJH SJSXTJP XTJ,STJ,STJ第62页/共102页2010 Copyr

33、ight 64 典型序列集在整个序列空间中所占的比例： 通常 取值很小，满足 因此 说明虽然集是一个高概率集，但在整个中可能只占很小的比例； 如果容许一定的失真，只对典型序列编码，对非典型序列不予编码传输，则可大大提高传输的效率。 loglog,222J H SJLH SSJLJTJS log0LH S,0J 第63页/共102页2010 Copyright 65 示例：已知二元信源 信源的熵为： 若取 所有的序列构成的集合为 2 . 0:, 8 . 0:2211SPSSPSS S1 1S S1 1S S1 1序列出现概率序列出现概率P(SP(Si iS Sj jS Sk k) )0.0080

34、.0080.0320.0320.0320.0320.1280.1280.1280.1280.0320.032序列集序列集S S1 1S S2 2S S2 2S S1 1S S2 2S S1 1S S1 1S S1 1S S2 2S S2 2S S1 1S S1 1S S2 2S S2 2S S2 2S S2 2S S2 2S S1 1S S2 2S S1 1S S2 20.5120.5120.1280.128序列包含信息量序列包含信息量I(SI(Si iS Sj jS Sk k) )6.9666.9664.9664.9664.9664.9662.9662.9662.9662.9664.9664

35、.9660.9660.9662.9662.966序列包含平均信息量序列包含平均信息量I(SI(Si iS Sj jS Sk k)/3)/32.3222.3221.6551.6551.6551.6550.9890.9890.9890.9891.6551.6550.3220.3220.9890.989 722. 0SH3J第64页/共102页2010 Copyright 66 示例(续)： 由： (1) 若取 平均信息量落在该范围内的序列为 如果要无失真地传输原来的全部序列，采用二进制编码的 话，需要3比特；如仅传输典型序列，只需2比特。 3 . 0 SHJSSSISHkji022. 13 . 0

36、722. 0422. 03 . 0722. 0JSSSIkji221SSS212SSS122SSS第65页/共102页2010 Copyright 67 示例(续)： (1) 若取 平均信息量落在该范围内的序列为 如仅传输典型序列，同样也只需2比特。 5 . 0222. 15 . 0722. 0222. 05 . 0722. 0JSSSIkji221SSS212SSS122SSS222SSS第66页/共102页2010 Copyright 68 假定信源输出按照 J 个符号构成的序列编码 编码输出 可能获得的编码输出的码字数为 相应的比特数为 编码速率 R 定义为： 若采用二进制编码，则有12

37、12,.,.,JJiLXXXXXS SS1212,.,.,JNiDYY YYYC CCNMDloglogMNRDJJNRJMlog第67页/共102页2010 Copyright 69 译码错误概率定义为 给定信源和编码速率R，对任意的 若存在 和编译码方法： 、 使当 时，有 则该编码速率称为可达的 反之称速率是不可达的。JJEXXPP0J0JXCNYC10JJ EP第68页/共102页2010 Copyright 70 若 ，则速率 R 是可达的； 若 ，则速率 R 是不可达的。 该定理说明，若 ，则存在编码方法，当 J 足够 大时，只需对典型序列进行编码，可使编码误差足够地小。 SHR

38、SHR SHR 第69页/共102页2010 Copyright 71 在满足一定的译码错误概率的条件下，若只对典型序列编 码，编码效率可定义为 若记：编码速率： 自信息方差： 则不能正确译码的概率 满足关系式 根据最后一个等式，可确定编码序列的长度 J 。 RSH SHR 212SHSISPiLiiI 22JII XPH SJJ第70页/共102页2010 Copyright 72 示例： (1)对二元符号进行无差错的二进制编码 此时 、 、 (2) 若要求编码效率 ， 求所需的编码序列长度 J 由 得1, 021SS1J2D1N1loglog211NRDJ 0.7220.7221H SR0

39、.9410EP 0.9H SH SRH S 0.10.1 0.7220.08020.90.9H S第71页/共102页2010 Copyright 73 示例(续)： 自信息方差： 最后得所需的符号序列长度 (该取值太大，可见等长编码不易在实际系统中应用) 22122112222loglog0.8 0.3220.7220.2 2.3220.7220.8 0.160.2 2.560.64LIiiip SI SH Sp Sp SH Sp Sp SH S252420.649.95 10100.0802IJ第72页/共102页2010 Copyright 74 ： 对出现概率大的符号或符号组用位数较少

40、的码字表示； 对出现概率小的符号或符号组用位数较大的码字表示。 ： 定理4.5.17 霍夫曼编码一种最佳的不等长编码。 ： 信源的分布(统计)特性已知。 记 信源符号集为： 编码输出符号集为： LiSPSSii,.,2 , 1,:DiZZi,.,2 , 1,:第73页/共102页2010 Copyright 75 ：(1)将L个信源符号按概率大小，以递减次序，从上到下排成一列；(2)对处于最下面的概率最小的D个信源符号，一一对应地分别赋予码字元素Z1、Z2、ZD，把这D个概率最小的信源符号相应的概率相加，所得的值用一个虚拟的符号代表，与余下的L-D个符号组成含有(L-D)+1=L-(D-1)个

41、符号的第一次缩减信源S(1)；(3)对缩减信源S(1)仍按其概率大小以递减次序从上到下排列，按照步骤(2)的方法处理，得到一个含有(L-D)+1-D+1=L-2(D-1)个符号的第二次缩减信源S(2)；(4)按照上述的方法，依次继续下去，每次缩减所减少的符号数是D-1个；只要缩减后的信源Si符号的个数大于D，缩减就继续进行；(5)当进行第k次缩减后信源S(k)符号个数刚好等于D，即有 则对最后这D个符号分别赋予码字元素Z1、Z2、ZD；DDkL1第74页/共102页2010 Copyright 76 ：(6)从最后赋予的码符号开始，沿着每一信源符号在各次缩减过程中得到的码字元素进行路线前向返回

42、，达至每一信源符号，按前后次序，把返回路途中所遇到的码元素排成序列，这个序列，就是相应信源符号对应的码字；(7)若进行k次缩减后，当进行第k次缩减后信源S(k)符号个数不等于D，即有则中止缩减，增加 个概率为0的虚假信源符号 重新编码，使在k次编码后一定有 。DDkL11DkLDm 0.00.:212121LmLixPxPxPxxxxxxxPXDDkL1第75页/共102页2010 Copyright 77 ：已知信源符号集 编码输出的码字符号集为 解：已知： 尝试 需要增加虚假符号数为 新构建的信源满足： S123456:8iiSSSSSSSP

43、S2 , 1 , 0:Z6L3D2k3213261DkL1132631DkLDmDDkL313271第76页/共102页2010 Copyright 781234561:80iiSSSSSSSSP S ：改造后的符号概率场为 编码过程如下消息符号消息符号S S1 1符号概率P(S符号概率P(Si i) )SS1 1S S6 6S S5 5S S4 4S S3 3S S2 080.160.160 00.080.080.140.140 01 12 080.160

44、.160.220.220 01 12 20.540.520.220 01 12 2码字码字C C1 1：1：1C C7 7：22：22C C6 6：21：21C C5 5：20：20C C4 4：02：02C C3 3：01：01C C2 2：00：00S S(1)(1)S S(2)(2)第77页/共102页2010 Copyright 791 0.242 0.202 0.182 0.162 0.142 0.081.76n 码字符号 信源符号 ： 平均码字长度：第78页/共102页2010 Copyright 80 ： 如果不加入虚假符号，直接进行编码，则有 平均码字长

45、度2 0.242 0.202 0.182 0.162 0.142 0.082n 码字符号 信源符号第79页/共102页2010 Copyright 81 在同样的平均码字长度的情况下，码字长度越均匀，对传输越有利。 码字长度的方差 其中 编码过程的排序过程不同影响码长的方差。2221nnLCiiiiEnP Sn1nLiiinP S第80页/共102页2010 Copyright 82 (续)信源的符号空间为 编码输出码字集 12345:0.10.1iiSSSSSSP S1 , 0:Z消息符号消息符号S S1 1符号概率P(S符号概率P(Si i) )S S5 5S S4 4S

46、 S3 3S S2 0.10 01 1码字码字C C1 1：1：1C C5 5：0011：0011C C4 4：0010：0010C C3 3：000：000C C2 2：01：00.20 01 0.40 01 0.40 01 1S S(1)(1)S S(2)(2)S S(3)(3)第81页/共102页2010 Copyright 83 平均码长： 方差：1 0.42 0.23 0.24 0.14 0.12.2An 码字符号 信源符号25212

47、2222n0.41 1.36AiiiP Sn第82页/共102页2010 Copyright 84 消息符号消息符号S S1 1符号概率P(S符号概率P(Si i) )S S5 5S S4 4S S3 3S S2 0.10 01 1码字码字C C1 1：00：00C C5 5：011：011C C4 4：010：010C C3 3：11：11C C2 2：10：100.20.20 01 0.40 01 0.40 01

48、S S(1)(1)S S(2)(2)S S(3)(3)0.40.42 0.42 0.22 0.23 0.1 3 0.12.2Bn 码字符号 信源符号252122222n0.40.16BiiiP Sn第83页/共102页2010 Copyright 85 虽然平均码长一样，但编码方法2使得输出的码长更为均匀。： 在霍夫曼编码过程中，当对缩减信源概率重新排列时，应使合并得到的局部概率和，尽量使其处于最高位置； 这样可以使得合并元素重复编码的次数减少，降低码字长度的方差，使得码字长度比较均匀。 22BA第84页/共10

49、2页2010 Copyright 86 实际系统通常需要在性能与经济性之间取得某种平衡； 通常采用以某些不可察觉或可察觉但不影响应用的信号失真代价，来换取所需的传输速率、存储空间、运算复杂度和系统实现成本的降低； 第85页/共102页2010 Copyright 87 失真是指用某种尺度衡量的实际的信源样值 与信号经过变化后对应值 之差。 ：对由符号 变为符号 引起误差造成影响的大小，人为定义一个非负函数称之： 失真函数的取值通常反映失真产生的代价。 kx kx0,iixxdkx kx第86页/共102页2010 Copyright 88 失真函数的示例： (汉明失真函数) 连续信号无失真有失

50、真dttxtxTtxtxdxxxxxxdxxxxdxxxxdTTTkkkkkkHpkkkkkkkk22221lim,01,第87页/共102页2010 Copyright 89 分析在允许一定失真的条件下，要重构一个信号，信源输出的信息率能否减少和应如何处理； 研究限定失真条件下的信源编码方法。 第88页/共102页2010 Copyright 90 已知输入信号集： 输出信号集： 对离散无记忆信道，有 ：对由输入符号 变为输出符号 引起误差造成影响的大小，可人为定义一个非负函数： MixXi,.,2 , 1,:NjyYj,.,2 , 1,:MNMMNNijxypxypxypxypxypxypxypxypxypxypXYp/././././212222111211,01,2,.,;1,2,.ijd x yiM jNjyix第89页/共102页2010 Copyright 91 与转移概率矩阵对应，可定义相应的失真度矩阵： 平均失真度定义为 111212122212,.,.,.,.,NNMMMNd x yd x yd x yd xyd xyd xyDd xyd xyd xy 1111,/MNijijijMNijijiijDd x yp x yd x yp xp yx 第90页/共102页2010 Copyrigh