数字通信原理第4章信息论基础

1、数字通信原理数字通信原理(4)冯穗力等编著冯穗力等编著电子工业出版社电子工业出版社20122012年年8 8月月1 1第第 4 章章 信息论基础信息论基础本章的基本内容：本章的基本内容：信息的度量方法；信息的度量方法；离散信道及容量；离散信道及容量；连续信源、信道及容量；连续信源、信道及容量；信源编码的基本方法；信源编码的基本方法；率失真理论。率失真理论。2 24.1 4.1 引言引言3 3n 消息与信息n 1948年，美国科学家香农的论文通信的数学理论，n 奠定了信息论的理论基础。 n 消息与信息n (1)消息是由符号、文字、数字、语音或图像组成的序列；n n (2)消息是信息的载体，信息是

2、消息的内涵；消息中可能包n 含信息，也可能不包含信息；n (3)收到一则消息后，所得的信息量，在数量上等于获得n 消息前后“不确定性”的消除量；n n (4)通信的目的在与传送信息。第4章 信息论基础4 4n 消息与信息(续)n通信系统传递信息的机制和本质 n形式化：通信的基本任务是在接收端把发送端发出的消息从形式上恢复出来，而对消息内容的理解和判断，不是通信的任务。n非决定论：通信过程传递的消息中所包含的内容，对接收者来说事先是无法预料的。n不确定性：是指收到该消息之前，对其中的内容出现与否，具有不确定的因素；不确定的因素可以通过通信来加以消除或部分消除。 第4章 信息论基础5 54.2 4

3、.2 信息的度量信息的度量6 6n 信息度量的概念n (1) 某消息的信息量获得该消息后不确定性的消除量；n 不确定性可能性概率问题：n 信息量可用概率的某种函数来度量n n (2) 不同的消息有信息量的多少的区别，因此n 信息的度量方式应满足信息量的可加性n n 信息量应该是满足可加性的概率的函数。第4章 信息论基础7 7n 离散信源信息的度量离散信源信息的度量n 离散信源的信息量离散信源的信息量n 离散信源统计特性的描述方法概率场离散信源统计特性的描述方法概率场n n 设离散信源包含设离散信源包含N N种可能的不同符号，相应的概率场可表述种可能的不同符号，相应的概率场可表述为为nn 概率场

4、应满足条件：概率场应满足条件： n 11Niixp NNxpxpxpXpxxxX.:.:2121第4章 信息论基础8 8 离散信源的信息量(续) 信息量作为概率的函数，具有形式 若 与 统计独立，满足可加性要求 如定义 显然有 可同时满足是概率的函数和可加性两个要求。 iixpfxIixjx jijijijixpfxpfxpxpfxxpfxxI iiixpxpfxI1log jijijijixpxpxpxpfxxpfxxI1log1log第4章 信息论基础9 9n 离散信源信的息量(续)n 定义 离散消息xi的信息量:nn 信息量的单位与对数的底有关：n log以2为底时，单位为比特：bitn

5、 log以e为底时，单位为奈特：nitn log以10为底时，单位为哈特，hartn n 一般在没有特别声明时均假定信息的单位为比特。 iiixPxPxPIlog1log第4章 信息论基础1010n 离散信源信的息量(续)n 示例：已知某信源的概率场为nn 输出的各符号统计独立，计算序列S“113200”的信息量n 81414183:3210:XpX bitsppppppppppppSpSI83.111415. 11415. 1232201log01log21log31log11log11log0023111log1log第4章 信息论基础11 11n 离散信源的平均信息量：信源的熵离散信源的

6、平均信息量：信源的熵n 离散信源的熵离散信源的熵n 定义定义4.2.2 4.2.2 离散信源离散信源 的熵的熵n n 熵是信源在统计意义上每个符号的平均信息量。熵是信源在统计意义上每个符号的平均信息量。NixXi,.,2 , 1,: iNiixpxpXHlog1第4章 信息论基础1212n 离散信源的熵(续)n 示例：求离散信源 n 的熵。n n 按照定义： n n 熵的单位：比特/符号 81414183:3210:XpX 符号比特906. 181log8141log4141log4183log83log41iiixpxpXH第4章 信息论基础1313n 离散信源的熵(续)n 示例（续）：若上

7、述离散信源发送独立的符号序列：n 201 020 130 213 001 203 210 100 321 010 n 023 102 002 10 312 032 100 120 210 n (1)求总的信息量；(2)利用熵估计总的信息量。n解：(1)n n n (2) 比特55.10781log741log1341log1483log23log41iiixpnI 比特62.108096. 1713142341XHnIii第4章 信息论基础1414n 离散信源的最大熵定理n 定义4.2.3 凸集 n 对任意 ，有n 定义4.2.4 若 n 型凸函数(下凸函数)n 型凸函数(上凸函数) 1,2,

8、.,iiin ixxxx1,2,.,jjjn jxxxx nxR01 1ijxxx 11ijijfxxfxfx 11ijijfxxfxfx ,ijx xx nxR01第4章 信息论基础1515n 离散信源的最大熵定理(续)n 若函数为型凸函数(下凸函数)，则一定存在最小值n 若函数为型凸函数(上凸函数)，则一定存在最大值n n 型凸函数示例n 第4章 信息论基础1616n 离散信源的最大熵定理(续)n 若 是一组概率； 是一个型凸函数，则一般地有如下的关系式n 利用上面的关系式，可以证明如下的定理n 定理4.2.5 熵函数 是概率 n 的型凸函数。 H X 12,.,Np xp xp x12,

9、.,Npp pp f x 11NNiiiiiifp xp f x第4章 信息论基础1717n 离散信源的最大熵定理(续)n 定理4.2.6 当离散信源X取等概分布时，其熵 取最大值。n 即：当信源取等概分布时，具有最大的不确定性。n示例：两个信源符号的情形。n P(x1)=p,P(x2)=1-pn n 当p=1/2时，H(X)= Hmax NiNNNNNNNHxpxpxpH1211log1log11,.,1,1,.,maxH X第4章 信息论基础1818n 离散信源的联合熵与条件熵n 两随机变量n 的概率场n 满足条件：NjMiyxXYji,.,2 , 1;,.,2 , 1,:11111212

10、1122212222221122,.,:,., :.,.,NNNNMMMMMNMNx y p x yx yp x yx yp x yXYx yp x yx yp x yx yp x yp XYx y p x yx yp x yx yp x y111 MiNjjiyxp第4章 信息论基础1919n 离散信源的联合熵与条件熵(续)n 两随机变量的联合熵n 定义4.2.3 两随机变量 n 的联合熵n n 如两随机变量统计独立，有NjMiyxXYji,.,2 , 1;,.,2 , 1,:符号比特 MijiNjjiyxpyxpXYH11log YHXHypypxpxpypxpypxpyxpyxpXYHj

11、NjjMiiiMijiNjjiMijiNjji loglogloglog111111第4章 信息论基础2020n 两随机变量的联合熵(续)n 对于统计独立的两随机变量，不能从其中一个获得有关另外一个的任何信息。第4章 信息论基础2121n 离散信源的联合熵与条件熵(续)n 两随机变量的条件熵n 定义4.2.4 两随机变量 n 的条件熵n n 一般地有(利用稍后的平均互信息量的非负性)n 具有某种相关性的两随机变量，一个随机变量的出现总是n 有助于降低另一随机变量的不确定性。 NjMiyxXYji,.,2 , 1;,.,2 , 1,: MijiNjjiyxpyxpYXH11log MiijNjj

12、ixypyxpXYH11log XHYXH第4章 信息论基础22224.3 4.3 离散信道及容量离散信道及容量2323n 离散信源及容量n 信道模型n 信道的输入：n 信道的输出：n 信道模型(特性)可用其转移概率来描述NjMiyxXYXYpji,.,2 , 1,.,2 , 1,:,MixXi,.,2 , 1,:NjyYj,.,2 , 1,:第4章 信息论基础2424n 离散信源及容量(续)n 信道模型n n 信道模型(特性)可用其转移概率来描述，一般地有n 输出不仅与当前的输入有关，而且与之前的若干个输入值n 有关，呈现某种“记忆”效应。:,1,2,.,1,2,.,ijXY x y iM

13、jN 1.kkkk njp yxxx第4章 信息论基础2525n 离散信源及容量(续)n 离散无记忆信道的转移矩阵 输出仅与当前的输入有关n n 离散无记忆信道的后验概率矩阵 112111222212/././././NNMMNMp yxp yxp yxp yxp yxp yxp YXp yxp yxp yx112111222212/././././MMNNMNp xyp xyp xyp xyp xyp xyp X Yp xyp xyp xy第4章 信息论基础2626 离散无记忆信道的转移矩阵(续) 示例：二元的离散无记忆信道 发“0”和发“1”时 能正确接收的概率为0.99， 错误的概率为0

14、.01。 即有 转移矩阵 /0/01/10.99iip yxpp/1/00/10.01 jip yxppij99. 001. 001. 099. 0/ijxypXYp第4章 信息论基础2727n 离散信源及容量n 互信息量n 后验概率 是一种条件概率，在通信系统中可表示n 收到 后，发送端发送的是符号 的概率。 n 接收端收到 后，关于 的不确定性可表示为n 定义4.3.1 互信息量为：n 互信息量为收到 后，关于 的不确定性的消除量。 jiyxp/ixjyjyixjijiyxpyxI/1log/ jiijiyxIxIyxI/;jyix第4章 信息论基础2828 互信息量互信息量( (续续)

15、) 互信息量具有对称性互信息量具有对称性 互信息量的性质互信息量的性质 (1) (1) 若若 (2) (2) 若若 (3) (3) 若若 (4) (4) 若若 ijjijjijiijijiijiijixyIypxypypxpyxpxpyxpyxpxpyxIxIyxI;/loglog/log/1log1log/;1/jiyxp ijixIyxI; 1/jiiyxpxp ijixIyxI;0 ijixpyxp/0;jiyxI ijixpyxp/00;jiyxI第4章 信息论基础2929 MiNjjijiyxIyxpYXI11;0;YXI第4章 信息论基础3030n 离散信源及容量(续)n 熵函数与

16、平均互信息量间的关系n XYIYXI; YXHXHYXI/; XYHYHYXI/; XHYXH/ YHXYH/ YHXHXYH第4章 信息论基础3131 熵函数与平均互信息量间的关系(续) 当信源X与Y统计独立时 (1)两个符号同时出现时提供的平均信息量等于每个符号的平均信息量之和； (2)一个符号不能提供有关另一符号的任何信息。 YHXHXYH0;XYIYXI第4章 信息论基础3232n 熵函数与平均互信息量间的关系(续) n 当两个信源相关时n (1)联合熵小于两个信源的熵的和:n n (2)平均互信息量等于两信源熵重合的部分；n (3)信源的条件熵等于其自身的熵减去平均互信息量：YXI,

17、 XH YHXYHYXHXYH YHXHXYH YXIXHYXH;/第4章 信息论基础3333n 离散信道的容量 n 已知信道的转移矩阵n 信源符号集： ； 符号传输速率： n 系统的平均信息速率为： MNMMNNijxypxypxypxypxypxypxypxypxypxyp/././././212222111211 XSR SMiNjijiijiSMiNjijijiSIRxpyxpxpyxpRxpyxpyxpRYXIR 1111/log/log;第4章 信息论基础3434 离散信道的容量(续) 定义4.3.3 离散信道的最大传输速率为其信道容量 匹配信源的概念 信道容量由信道特性和信源的统

18、计特性决定。 信道特性确定之后，其容量由信源的统计特性决定。 匹配信源：能使单位时间内信道可传输的平均信息量达到信 道容量的信源称之。 记匹配信源的分布特性： 信道容量： SMixpIMixpRYXIRCii;maxmax,.,2, 1,.,2, 1, ,1,2,.,ip xiNSmIMixpRIRCi,.,2, 1,max第4章 信息论基础3535 离散信道的容量(续) 匹配信源(续) 已知信道转移概率，匹配信源统计特性的求解 约束条件 求 使得 达到最大。 由拉格朗日求极值的原理： 定义辅助方程 令 可得信源分布特性应满足的条件 ,1,2,.,ip xiN 11Miixp;I X Y 1;

19、,.,121MiiMxpYXIxpxpxpF MixpYXIxpxpxpxpFiiM,.2 , 10;,.,21 1,.2 , 1/log/11MiijijNjijxpMiypxypxyp第4章 信息论基础3636 离散信道的容量(续) 由此可导出匹配信源统计特性的求解步骤： (1)解方程组 求解得 (2)求最大平均互信息量： (3)求相应后验概率： (4)解方程组，确定匹配信源的分布特性 MixypxypxypjNjijNjijij,.2 , 1/log/11Mij,.2 , 1,NjmjI12log NjypIjj,.2 , 12max NjxpxypxypypimMiijMiijj,.2

20、 , 1/11第4章 信息论基础3737 离散信道的容量(续) 示例：求匹配信源的统计特性。已知信道转移概率 (1)解方程组得中间结果参数： (2)求最大平均互信息量： (3)求相应后验概率： 1 21 401 40100/00101 401 41 2p YX2, 0, 0, 2432125log2222log2log20021NjmjI 1012,522522,101225log2425log0325log0225log21ypypypyp第4章 信息论基础3838离散信道的容量(续) 示例(续)： (4)获得匹配信源统计特性： (5)信道容量为： 注：若求解过程中出现 ，可在方程组中令 ，

21、重新求解。 304,3011,3011,3044321xpxpxpxpmmmm秒比特/1320100032. 1100025logSmRIC 0imxp0mipx第4章 信息论基础3939 离散无记忆对称信道的容量(续) 离散无记忆对称信道(定义)： 转移矩阵 转移矩阵各行各列均具有相同的元素集的信道称之。 离散无记忆对称信道满足条件： 对矩阵中任意的列元素，有 对矩阵中任意的行元素，有 112111222212/././././NNMMNMp yxp yxp yxp yxp yxp yxp YXp yxp yxp yxNjxypxypMiijij,.,2 , 1/log/1常数Mixypxy

22、pNjijij,.,2 , 1/log/1常数第4章 信息论基础4040 离散无记忆对称信道的容量(续) 离散无记忆对称信道特性： (1)离散无记忆对称信道的条件熵满足： 条件熵取值仅由信道特性决定，与信源的统计特性无关。 (2)若输入信道的信源符号等概 则信道的输出符号也等概 ijNjijxypxypXYHlog/1jiMijiyxpyxpYXHlog/1 MiMxpi,.,2 , 1,1 NjNxypMxypMxypxpyxpypMiijMiijMiijiMijij,.,2 , 1,1/1/1/1111第4章 信息论基础4141 离散无记忆对称信道的容量(续) 信道容量： 对于离散无记忆对

23、称信道，若要使信息传输速率达到信道容量，要求信源的符号等概分布。 对于非等概的信源，可设法对其输出的符号进行适当的组合，使得重新构建后的符号(信源)，具有近似等概的分布特性。 (参见“信源的等长编码”一节),1,2,.,1,2,.,1,2,.,1,2,.,max;max/maxmaxlogMiiiiSSp xiMp xiMSSp xiMp xiMSCI X YRH XH X YRH XRH XRR常数常数常数第4章 信息论基础42424.4 4.4 连续信源、信道及容量连续信源、信道及容量4343n 连续信源、信道及容量n 连续信源的相对熵n 若已知随机信号 幅度取值的概率密度函数：n 取值在

24、任意小区间 内的概率n (参见示意图)n 连续信源转变为具有n个随机变量的信源，且有 n 利用离散随机变量熵的定义，得 tX xp iaiaxxxXXiii,) 1(, nixpdxxpxPiaiaiiXX,.,2 , 11 11111nibaiaianiiniidxxpdxxpxpxPXX niiiiniinxpxpxPxPXH11loglog第4章 信息论基础4444n 连续信源、信道及容量(续) n 连续信源的相对熵n 概率密度函数的离散化示意图，输入的取值范围 XXba ,ninabxXXi,.,2 , 1 nidxxpiaXiaPxxXxPxPiaiaXXiiiiXX,.,2 , 1

25、11第4章 信息论基础4545 连续信源的相对熵(续) 连续信源的熵应为 可见连续信源的熵无限大。该熵称为连续信源的绝对熵，无 法确切地定义。 通常上式的第一项是有限值，且其具有特定的物理意义。 dxxpxpdxxpxpxpxpxpxpxpxpxpXHXHbanbanniiinniinniiinniiinnnlogloglimlogloglimloglimloglimloglimloglimlim, 0, 01, 01, 01, 01, 0, 0第4章 信息论基础4646 连续信源的相对熵(续) 定义4.4.1 连续信源的相对熵为 示例 某信号的相对熵为 信号经2倍幅度放大后的相对熵为 信号的

26、简单放大并没有增加任何新的信息，但其相对熵发生 了增大的变化，这说明相对熵已经不再具有信源平均信息量 的内涵。 dxxpxpXhbalog 121log21log111dxdxxpxpXhba 241log41log222dxdxxpxpXhba第4章 信息论基础4747n 连续信源的相对条件熵连续信源的相对条件熵n 对于连续随机变量，同样可以导出其条件熵对于连续随机变量，同样可以导出其条件熵n 可见连续信源的条件熵取值无限大，同样无法确切定义。可见连续信源的条件熵取值无限大，同样无法确切定义。但通常上式的第一项是一个有限取值的量。但通常上式的第一项是一个有限取值的量。n 连续信源的熵和条件熵

27、均取值无限大，说明要在一个容量连续信源的熵和条件熵均取值无限大，说明要在一个容量有有n 限的通信系统中传递连续信源的全部信息是不可能的。限的通信系统中传递连续信源的全部信息是不可能的。 loglim/log/loglim/loglog/loglim/lim/00, 0110, 00, 0XXYYXXYYbabababajinimjjimndxdyyxpyxpypdxdyyxpxypyxpyxpYXHYXH第4章 信息论基础4848n 连续信源的相对条件熵连续信源的相对条件熵( (续续) )n 定义定义4.4.3 4.4.3 连续信源的相对条件熵连续信源的相对条件熵n 因为：因为：n 说明相对熵

28、和相对条件熵的差值与普通的熵和条件熵的差值说明相对熵和相对条件熵的差值与普通的熵和条件熵的差值n 一样，仍然等于平均互信息量。一样，仍然等于平均互信息量。 n 同理可以导出：同理可以导出： XXYYbabadxdyyxpyxpypYXh/log/ YXhXhYXhXhYXHXHYXI/loglim/loglim/;00 XYhYhYXI/; XYhYhXhYXI;第4章 信息论基础4949n 连续信源相对熵的最大化连续信源相对熵的最大化n 定理定理4.4.3 4.4.3 连续信源的相对熵函数连续信源的相对熵函数 是信源概率密度函是信源概率密度函n 数数 的的型凸函数。型凸函数。 n 相对熵相对

29、熵 作为概率密度函数作为概率密度函数 的函数存在最大值。的函数存在最大值。 h X p x p xh X第4章 信息论基础5050ba,X bxaabxp,1 abXhXhplogmaxAx AxAAxp,21 AXhXhp2logmax第4章 信息论基础5151 dxxxp 0, 00,1xxeaxpax aXhXhplogmax第4章 信息论基础5252 dxxpx2 22221mxexpeXhXhp2log)()(2max第4章 信息论基础5353n 加性高斯噪声信道的容量加性高斯噪声信道的容量n 加性高斯噪声加性高斯噪声( (干扰干扰) )信道信道(AWGN)(AWGN)n 信道输入：

30、信道输入： 信道输出：信道输出： 加性高斯噪声：加性高斯噪声：n 已知通过信道后，从已知通过信道后，从 可获得的关于可获得的关于 的平均互信息量的平均互信息量n 若已知信号若已知信号 的带宽为的带宽为 。 对任意的这类信号对任意的这类信号n 则无失真无冗余的抽样频率应为：则无失真无冗余的抽样频率应为： ( (单位时间的样点数单位时间的样点数) )n 单位时间内传输的信息量，即信息速率为单位时间内传输的信息量，即信息速率为nxynxyyx XYhYhYXhXhYXI/;xWWfS2 WXYhYhWYXhXhWYXIfYXIRSb2/2/2;第4章 信息论基础5454 WYXICxp2;maxxn

31、xxnxnxy,xyyxnxyxx,xyxnJxnpxyp J 第4章 信息论基础5555n 加性高斯噪声信道的容量(续)n n 因为n 所以有n 若已知信源x的统计特性，收到y后不可确定的部分为n 噪声的影响所导致。11101,yyxnxyxnyyxxxyxxxyxnJ npxpxnpxyp npxpnpxpxpxnpxpxypxyp/第4章 信息论基础5656n 加性高斯噪声信道的容量(续)n n 因此可得 /log/logloglogh YXp xyp y x dxdyxnp xn Jp n dxdnp xnp n dxdnxyp np n dnh N WNhYhWXYhYhWYXICx

32、pxpxp2max2/max2;max第4章 信息论基础5757加性高斯噪声信道的信道容量(续) 因为 (1) 在均方受限的条件下，高斯分布的信源有最大的相对熵 (2) 两高斯分布的随机变量之和( )仍为高斯随机变量 (3) 信号 与噪声 统计独立 因而有nxy 2222222222121nxyynxyyeeyp 2222log212log21lognxyeedyypypYh第4章 信息论基础5858n 加性高斯噪声信道容量(续)n 信道容量n 若记n 得香农公式 222222222221logloglog22log22log212log212maxnxnnxnynynyxpWWWeeWWee

33、WNhYhC22,nxNSSNRWNSWC1log1log22第4章 信息论基础5959加性高斯噪声信道容量(续)由香农公式(香农定理) 得到的重要结论： (1) 信道容量C随S/N增大而增大； (2) C一定时，W与S/N之间可以彼此互换； (3) N 0, C ：无扰信道的容量为无穷大； (4) 对受高斯噪声干扰的信道，当 W ， 信道容量趋于 一有限的确定值： (S与N0固定时)SNRWNSWC1log1log2202044. 1loglimNSeNSCW第4章 信息论基础6060n 信道容量和带宽的归一化分析n 归一化信道容量：单位时间单位频带内可达到的信息速率。n 注：所谓物理不可n

34、 实现是指不可n 能实现无差错n 传输。2log1CSWN图 441 归一化信道容量特性曲线第4章 信息论基础6161n 信道容量和带宽的归一化分析信道容量和带宽的归一化分析( (续续) )n 归一化信道带宽：单位信息速率所需要的最小带宽。归一化信道带宽：单位信息速率所需要的最小带宽。图 442 归一化信道带宽特性曲线12log1WSCN第4章 信息论基础6262n 信道容量和带宽的归一化分析(续)n 关于Eb/N0的归一化信道带宽n Eb：比特能量；n N0：噪声功率密度谱；n 当n Eb/N0 1.59dBn 时，无法实现无差n 错的传输。021WbCEWNC第4章 信息论基础63634.

35、5 4.5 信源编码的基本方法信源编码的基本方法6464n 信源编码的基本方法信源编码的基本方法n 信源编码的目的：提高传输效率信源编码的目的：提高传输效率n （1 1）去除消息中的冗余度，使传输的符号尽可能都是独立）去除消息中的冗余度，使传输的符号尽可能都是独立的，没有多余的成分的，没有多余的成分( (如语音、图像信号压缩如语音、图像信号压缩) )；n （2 2）使传输的符号所含的信息最大化。例如，通过编码使）使传输的符号所含的信息最大化。例如，通过编码使符号以等概分布的形式出现，使每个符号可能携带的信息量达符号以等概分布的形式出现，使每个符号可能携带的信息量达到最大；到最大；n （3 3）

36、采用不等长编码，让出现概率大的符号用较短的码元）采用不等长编码，让出现概率大的符号用较短的码元序列表示，对概率小的符号用较长的码元序列；序列表示，对概率小的符号用较长的码元序列；n (4) (4) 在允许一定失真的条件下，如何实现高效率的编码。在允许一定失真的条件下，如何实现高效率的编码。第4章 信息论基础6565n 离散无记忆信源离散无记忆信源 (DMS: Discrete Memoryless Source (DMS: Discrete Memoryless Source）n 离散无记忆信源的输出序列：离散无记忆信源的输出序列：n 各个符号间彼此独立各个符号间彼此独立n 其中其中n 反之，

37、若输出的各符号间有一定的相关性，则其为一种反之，若输出的各符号间有一定的相关性，则其为一种n 有记忆的信源。有记忆的信源。n 有记忆的信源，经过处理后，有可能变为一种无记忆的有记忆的信源，经过处理后，有可能变为一种无记忆的信信n 源。如有记忆的信源，经过理想的、完全去除冗余的源。如有记忆的信源，经过理想的、完全去除冗余的 n 压缩编码后产生的输出。压缩编码后产生的输出。.21012nXXXXXXSXiLiSSi,.2 , 1,:第4章 信息论基础6666n 离散无记忆信源编码与译码离散无记忆信源编码与译码n 若将信源输出的符号按每若将信源输出的符号按每J J个为一组进行编码，则任意的个为一组进

38、行编码，则任意的第第m m个分组可以表示为个分组可以表示为 n ( (信源符号信源符号集集) )n 编码输出编码输出n 其中其中n 为输出的码元集。为输出的码元集。n 接收端的译码输出接收端的译码输出 LiSSXXXXXimkmJmmmJ,.2 , 1,:,.,21 JmmnJYC X 12.:,1,2,.,JJmmmmmnnkiYYYYYC C iDDiCCi,.2 , 1,: 1JmmJnXCY第4章 信息论基础6767n 离散无记忆信源编码与译码(续)n n 待编码码组简单记为 n 编码输出码组(码字)LiSSXXXXXikJJ,.2 , 1,:,.,2112.:,1,2,.,JJnnk

39、iYY YYYC C iD第4章 信息论基础6868n 离散无记忆信源编码与译码(续)n定义4.5.1 若对信源的每个不同的符号或不同的符号序列，编n 码后产生的码字不同，则称该码为唯一可译码。n 若待编码的符号序列的不同组合个数为n 码字集中不同的码字个数n 编码输出为唯一可译码的(必要)条件n 对于码元取自 ，码字长度为 一个码字，其最大可携带的信息量为JJLXJJnnYDJnJDL第4章 信息论基础6969DiCCi,.2 , 1,:Jn2logJnDn 离散无记忆信源编码与译码(续)n定义4.5.2 编码表示一个信源符号所需的平均信息量的定义为n 编码速率 。n 码字长度为常数的编码称

40、为等长编码，反之称为不等长编码。n 对长度为 的信源符号序列进行编码：n 等长编码的编码速率n 不等长编码的编码速率n 其中 为不等长编码的平均码长。RJn2logJnRDJ2logJnRDJ第4章 信息论基础7070Jn 离散无记忆信源编码与译码(续)n 定义4.5.3 信源的熵 与编码速率 的比值定义为编码效率n n 要保证编码没有信息丢失，要求 SHR RSHC 1CRH S第4章 信息论基础7171n 离散无记忆信源的等长编码离散无记忆信源的等长编码* *n 等长编码：对信源的每个符号，或每组符号，用长度相等的等长编码：对信源的每个符号，或每组符号，用长度相等的代码来表示。代码来表示。

41、n 单个符号独立编码单个符号独立编码 采用采用 进制码元编码进制码元编码n 若信源符号集有若信源符号集有 L L 种符号，要保证译码的惟一性，由种符号，要保证译码的惟一性，由n 码字长度应取码字长度应取n n 取整得取整得n n 编码效率：编码效率：n JnJDL1J212loglogJLnnD222212222loglogloglogloglog1loglogLDLDnLDLD若为整数若不为整数 12logCH SH SRnD第4章 信息论基础D7272n 离散无记忆信源的等长编码离散无记忆信源的等长编码( (续续) )n 扩展编码扩展编码( (联合编码联合编码) )：将：将 J J 个信源

42、符号进行联合编码个信源符号进行联合编码n 由译码唯一性要求由译码唯一性要求n n 取整得取整得n 平均每个符号所需的码元数平均每个符号所需的码元数n J J 取值的增大有利于效率的提高。取值的增大有利于效率的提高。JnJDL22loglogJLnJD22222222loglogloglogloglog1loglogJJLDJLDnJLDJLD若为整数若不为整数222212222loglogloglogloglog1loglogJJLDJLDNnJLDJLDJJJ若为整数不为整数第4章 信息论基础737310JJ n 离散无记忆信源的等长编码离散无记忆信源的等长编码( (续续) )n 信源统计特

43、性对编码效率的影响信源统计特性对编码效率的影响n例例4.5.1 4.5.1 采用二进制码元分别对采用二进制码元分别对J J4 4的两信源符号序列进行编的两信源符号序列进行编码。码。n 信源信源1 1：n 因为因为 故可取故可取n 平均每个符号的码元数平均每个符号的码元数n 编码效率编码效率 12345678: 1 81 81 81 81 81 81 81 8SSSSSSSSSp S 822111log8log388iiiH SP SP S 2222loglog 8412loglog 2LJD12Jn 1412 43Jnn 1231log3 1CH SnD第4章 信息论基础7474n 离散无记忆

44、信源的等长编码(续)n n 信源2：n 同理有 n 平均每个符号的码元数n 编码效率12345678: : 1 161 161 161 161 81 81 41 4SSSSSSSSSP S821222 log111111114log2log2log161688444iiiH SP SP S 2222loglog 8412loglog 2LJD12Jn 1412 43Jnn1211 411log3 112CH SnD第4章 信息论基础7575n 离散无记忆信源的等长编码(续)n n 来自同样符号集，但不同统计特性的信源，因其熵n 不同。编码效率n 可能差异很大。 12logCH SnD1logC

45、H SnD 第4章 信息论基础7676 , H SH Sn 离散无记忆信源(DMS)的有损等长编码n 一种考虑信源统计特性的编码n 信源符号集n 由最大熵定理n 由熵的定义，可知n 由译码的唯一性要求n 可得n 码组长度应满足条件n 由 得JnJDL 1212:.:.LLSSSSp Sp Sp Sp S 2logH SL JJJIXJH S 22loglog( )JnDJLJH S2log( )JJnDJ H S2( )logJJJ H SnD第4章 信息论基础7777n 离散无记忆信源(DMS)的有损等长编码n 一种考虑信源统计特性的编码(续)n 对任意统计特性的信源，要使下式成立，即获得较

46、高的编码效率，通常 J 取值要非常大，方能使n n 无损的等长编码，往往会因为 J 的取值过大，难以实际应用。n 下面考虑有损的等长编码。2( )1logJJJJ H SnD 第4章 信息论基础7878n 离散无记忆信源(DMS)的有损等长编码n 对于长度为 J 的DMS码组(或称为一序列):n 码组中的每个符号：n 由符号间的独立性，有n 码组 包含的信息量为：n 根据熵的定义，随着 J 的增大，有n 或n 可以证明当 J 足够大时，有 SHJXIJJJXJX1JJjjP XP X 111logloglogJJJjjJJjjjjI XP XP XP XI X LiSSXij,.2 , 1,:

47、 SHJXIIJJJ 1SHIPJ0第4章 信息论基础7979n 离散无记忆信源(DMS)的有损等长编码(续)n 即：n 定义 4.5.4n 典型序列集：满足下列条件的序列 的集合称之。n 其中 。 通常取 为一个较小的正数。n 非典型序列集：典型序列集的补集称之。记为n 典型序列集和非典型序列集构成了序列 所有组合；n 构成该符号序列的整个空间： ,:JSJI XTJXH SH SJJX0JX JJIH S依概率1第4章 信息论基础8080,STJ,SSJTJTJXn 离散无记忆信源(DMS)的有损等长编码(续)n 定理4.5.5 (信源划分定理)：任给 ，当 J 足够大时,有n 即有：n

48、典型序列出现的概率：若n 则n 即有：n 典型序列趋于等概分布。n 典型序列的数目：0,1JSP XTJ lim,1SJP TJ,JSXTJ 22J H SJ H SJP X 2JH SJP X 12,2J H SJ H SSTJ ,2JH SSTJ第4章 信息论基础8181n 离散无记忆信源离散无记忆信源(DMS)(DMS)的有损等长编码的有损等长编码( (续续) )n 典型序列的出现概率：典型序列的出现概率：n 即：即：n 典型序列集典型序列集 为高概率集；为高概率集；n 非典型序列集非典型序列集 为低概率集。为低概率集。n ,21JSJH SJSXTJP XTJ,STJ,STJ第4章 信

49、息论基础8282n 离散无记忆信源(DMS)的有损等长编码(续)n 典型序列集在整个序列空间中所占的比例：n 可选择 ，使满足n 因此n 说明虽然典型序列集是一个高概率集，但其数目在整个序列空间中可能只占很小的比例；n loglog,222J H SJLH SSSJJLJTJTJLX log0LH S0,0J 第4章 信息论基础8383n 离散无记忆信源(DMS)的有损等长编码(续)n n 典型序列集的形象说明n n 如果容许一定的失真，只对典型序列编码，对非典型序列不n 予编码传输，码字长度可大大缩短，从而有效提高传输效率。第4章 信息论基础8484n 离散无记忆信源(DMS)的有损等长编码

50、(续)n 例4.5.2：已知二元信源n 信源的熵为：n 所有的序列n 构成的集合n 为 2 . 0:, 8 . 0:2211SPSSPS 722. 0SH第4章 信息论基础8585n 离散无记忆信源(DMS)的有损等长编码(续) n示例(续)：n (1) 若取n 由n 平均信息量落在该范围内的序列(典型序列)为n n 其概率和n 3 . 04J ijklI S S S SH SH SJ0.72190.30000.42190.72190.30001.02194ijklI S S S S0001S S S S0010S S S S0100S S S S1000S S S S,00010010010

51、010000.10240.10240.10240.10240.4096JJXTS JP XP S S S SP S S S SP S S S SP S S S S第4章 信息论基础8686n 离散无记忆信源(DMS)的有损等长编码(续) n示例(续)：n (2) 若取n 由n 平均信息量落在该范围内的序列(典型序列)为n n 其概率和n 0.54J ijklI S S S SH SH SJ0001S S S S0010S S S S0100S S S S1000S S S S0.72190.50000.22190.72190.50001.22194ijklI S S S S0000S S S

52、S,000000010010010010000.40960.10240.10240.10240.10240.8192JJXTS JP XP S S S SP S S S SP S S S SP S S S SP S S S S第4章 信息论基础8787n 离散无记忆信源(DMS)的有损等长编码(续)n 可达速率的概念n 译码错误概率定义为n 定义4.5.6 可达速率 n 给定信源和编码速率R，对任意的 若存在n 和编译码方法： 、 n 使当 时，有 则该编码速率称为可达的n 反之称速率是不可达的。n 前面已经定义编码速率：JJEXXPP0J0JXCNYC10JJ EP2logJnRDJ第4章

53、信息论基础8888n 离散无记忆信源(DMS)的有损等长编码(续) n 定理 4.5.7n 若 ，则速率 R 是可达的；n 若 ，则速率 R 是不可达的。n 该定理说明，若 ，则存在编码方法，当 J 足够n 大时，只需对典型序列进行编码，可使编码误差足够地小。n 定理的物理意义是：只有用于承载每个符号信息的平均比特数大于等于信源的熵，才能使译码的误差任意地小。 RH S SHR SHR 第4章 信息论基础8989n 离散无记忆信源(DMS)的有损等长编码(续) n 分析在满足一定的译码错误概率的条件下，若只对典型序列编码，如何确定编码长度： n 若记：编码速率： n 自信息方差：n 则不能正确

54、译码的概率 满足关系式(参见信源划分定理证明)n n 根据上式，可确定编码序列的长度 J 。 SHR 212SHSISPiLiiI 22JII XPH SJJ第4章 信息论基础9090n 离散无记忆信源(DMS)的有损等长编码(续) n 示例：n (1)对二元符号进行无差错的二进制编码n 此时 、 、n (2) 若要求编码效率 ，n 求所需的编码序列长度 Jn 由 n 得1, 021SS1J2D1N1loglog211NRDJ 0.7220.7221H SR0.9410EP 0.9H SH SRH S 0.10.1 0.7220.08020.90.9H S第4章 信息论基础9191n 离散无记

55、忆信源离散无记忆信源(DMS)(DMS)的有损等长编码的有损等长编码( (续续) ) n 自信息方差：自信息方差：n 最后得所需的符号序列长度最后得所需的符号序列长度n ( (该取值太大，可见等长编码不易在实际系统中应用该取值太大，可见等长编码不易在实际系统中应用) ) 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第4章 信息论基础9292n 不等长编码的基本概念n 定义4.5.8 若码中每个码

56、字都含有一个特定的符号用于标识n 一个码字的起点，则称这种码为逗点码。 n 例：0，01，011，0111 为逗点码。n 定义4.5.9 对任一码字 ，称该码字的前面 位 n ， ，为码字 的长为 的字头或前缀。n 定义4.5.10 若码字集中任一码字都不是另一码字的字头，则n 称这种码为异字头码，或异前缀码。n 定义4.5.11 对具有 个元素的信源符号集：n 若符号 用 元码编码后输出的码字长度为 ，则定n 义信源符号的平均码字长度为：1 2.nnYYYYi1 2.iYYYinnYiLLiSSi,.,2 , 1,:iSDin1Liiinn p S第4章 信息论基础9393n 异字头不等长编

57、码n 异字头码的优点：异字头码译码时具有即时性，即当收到一个完整的码字后即可译码，不用担心这一码字是另一码字的字头部分。 n 异字头码的编码树：异字头码的编码可用编码树来描述第4章 信息论基础9494第4章 信息论基础n 异字头不等长编码(续)n（1）从根朝下，第一级有 个节点；第二级有 个节点；如此类推，第r 级有 个节点。n（2）从任一节点引出的分支有 个，从根开始，可分别用0，1，2， 1来标记。n（3）不再发出分支的节点称为端节点，若用端节点表示不同的信源符号，取相应的从根到该节点的标号序列为码字，则必能保证码字的异字头条件。n（4）若各分支均延伸到最高级的各端点，则可构成一棵对称的树

58、，称为满树，否则称为非满树。9595D2DrDDD第4章 信息论基础n 异字头不等长编码(续)n 异字头码的编码原则 n 编码时应尽可能地使码字中的任一码元载荷达到其最大的信息量： 。n 应使每个节点发出的种 分支出现的概率尽可能相等。n 异字头码的编码方法 n 将信源符号分成尽可能等概的个子集，与码树的第一级的个节点对应；n 对每个子集按同样的方法又分为个二级子集，与码树的第二级节点相对应；n 以此类推，直至子集不能再分为止。 D2logD9696第4章 信息论基础n 异字头不等长编码(续)n 示例： 对信源符号集n 做 的三进制异字头不等长编码。 n 解： 2712712719191919

59、19131:987654321SPSSSSSSSSSS3D消息符号消息符号S S1 1符号概率p(S符号概率p(Si i) )第一次划分第一次划分（编码）（编码）第二次划分第二次划分（编码）（编码）第三次划分第三次划分（编码）（编码）码字码字S S9 9S S8 8S S7 7S S6 6S S5 5S S4 4S S3 3S S2 21/31/31/91/91/91/91/91/91/271/271/91/91/91/91/271/271/271/271/31/31/31/31/31/3（0）（0）（1）（1）（2）（2） 1/271/271/91/91/91/91/271/271/271/

60、271/9（0）1/9（0）1/9（1）1/9（1）1/9（2）1/9（2）1/91/91/91/91/91/91/9（0）1/9（0）1/9（1）1/9（1）1/9（2）1/9（2）1/27（0）1/27（0）1/27（1）1/27（1）1/27（2）1/27（2）0 0101011111212202021212202202212212222229797第4章 信息论基础n 不等长编码的基本定理*n 定理4.5.12 对具有个符号的信源符号集： ，其相应的长度为 的元异字头码存在的充要条件是如下的不等式成立n即：当满足条件 时，一定存在与该码字对应的编码树。n 定理4.5.13 唯一可译码必