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

1、数字通信原理(4)冯穗力等编著电子工业出版社2012年8月1第 4 章 信息论基础本章的基本内容：信息的度量方法；离散信道及容量；连续信源、信道及容量；信源编码的基本方法；率失真理论。24.1 引言3 消息与信息 1948年，美国科学家香农的论文通信的数学理论， 奠定了信息论的理论基础。 消息与信息 (1)消息是由符号、文字、数字、语音或图像组成的序列； (2)消息是信息的载体，信息是消息的内涵；消息中可能包 含信息，也可能不包含信息； (3)收到一则消息后，所得的信息量，在数量上等于获得 消息前后“不确定性”的消除量； (4)通信的目的在与传送信息。第4章 信息论基础4 消息与信息(续)通信

2、系统传递信息的机制和本质 形式化：通信的基本任务是在接收端把发送端发出的消息从形式上恢复出来，而对消息内容的理解和判断，不是通信的任务。非决定论：通信过程传递的消息中所包含的内容，对接收者来说事先是无法预料的。不确定性：是指收到该消息之前，对其中的内容出现与否，具有不确定的因素；不确定的因素可以通过通信来加以消除或部分消除。 第4章 信息论基础54.2 信息的度量6 信息度量的概念 (1) 某消息的信息量获得该消息后不确定性的消除量； 不确定性可能性概率问题： 信息量可用概率的某种函数来度量 (2) 不同的消息有信息量的多少的区别，因此 信息的度量方式应满足信息量的可加性 信息量应该是满足可加

3、性的概率的函数。第4章 信息论基础7 离散信源信息的度量 离散信源的信息量 离散信源统计特性的描述方法概率场 设离散信源包含N种可能的不同符号，相应的概率场可表述为 概率场应满足条件： 第4章 信息论基础8 离散信源的信息量(续) 信息量作为概率的函数，具有形式 若 与 统计独立，满足可加性要求 如定义 显然有 可同时满足是概率的函数和可加性两个要求。 第4章 信息论基础9 离散信源信的息量(续) 定义 离散消息xi的信息量: 信息量的单位与对数的底有关： log以2为底时，单位为比特：bit log以e为底时，单位为奈特：nit log以10为底时，单位为哈特，hart 一般在没有特别声明时

4、均假定信息的单位为比特。 第4章 信息论基础10 离散信源信的息量(续) 示例：已知某信源的概率场为 输出的各符号统计独立，计算序列S“113200”的信息量 第4章 信息论基础11 离散信源的平均信息量：信源的熵 离散信源的熵 定义4.2.2 离散信源 的熵 熵是信源在统计意义上每个符号的平均信息量。第4章 信息论基础12 离散信源的熵(续) 示例：求离散信源 的熵。 按照定义： 熵的单位：比特/符号 第4章 信息论基础13 离散信源的熵(续) 示例（续）：若上述离散信源发送独立的符号序列： 201 020 130 213 001 203 210 100 321 010 023 102 00

5、2 10 312 032 100 120 210 (1)求总的信息量；(2)利用熵估计总的信息量。解：(1) (2) 第4章 信息论基础14 离散信源的最大熵定理 定义4.2.3 凸集 对任意 ，有 定义4.2.4 若 型凸函数(下凸函数) 型凸函数(上凸函数) 第4章 信息论基础15 离散信源的最大熵定理(续) 若函数为型凸函数(下凸函数)，则一定存在最小值 若函数为型凸函数(上凸函数)，则一定存在最大值 型凸函数示例 第4章 信息论基础16 离散信源的最大熵定理(续) 若 是一组概率； 是一个型凸函数，则一般地有如下的关系式 利用上面的关系式，可以证明如下的定理 定理4.2.5 熵函数 是

6、概率 的型凸函数。 第4章 信息论基础17 离散信源的最大熵定理(续) 定理4.2.6 当离散信源X取等概分布时，其熵 取最大值。 即：当信源取等概分布时，具有最大的不确定性。示例：两个信源符号的情形。 P(x1)=p,P(x2)=1-p 当p=1/2时，H(X)= Hmax第4章 信息论基础18 离散信源的联合熵与条件熵 两随机变量 的概率场 满足条件：第4章 信息论基础19 离散信源的联合熵与条件熵(续) 两随机变量的联合熵 定义4.2.3 两随机变量 的联合熵 如两随机变量统计独立，有第4章 信息论基础20 两随机变量的联合熵(续) 对于统计独立的两随机变量，不能从其中一个获得有关另外一

7、个的任何信息。第4章 信息论基础21 离散信源的联合熵与条件熵(续) 两随机变量的条件熵 定义4.2.4 两随机变量 的条件熵 一般地有(利用稍后的平均互信息量的非负性) 具有某种相关性的两随机变量，一个随机变量的出现总是 有助于降低另一随机变量的不确定性。 第4章 信息论基础224.3 离散信道及容量23 离散信源及容量 信道模型 信道的输入： 信道的输出： 信道模型(特性)可用其转移概率来描述第4章 信息论基础24 离散信源及容量(续) 信道模型 信道模型(特性)可用其转移概率来描述，一般地有 输出不仅与当前的输入有关，而且与之前的若干个输入值 有关，呈现某种“记忆”效应。第4章 信息论基

8、础25 离散信源及容量(续) 离散无记忆信道的转移矩阵 输出仅与当前的输入有关 离散无记忆信道的后验概率矩阵 第4章 信息论基础26 离散无记忆信道的转移矩阵(续) 示例：二元的离散无记忆信道 发“0”和发“1”时 能正确接收的概率为0.99， 错误的概率为0.01。 即有 转移矩阵 第4章 信息论基础27 离散信源及容量 互信息量 后验概率 是一种条件概率，在通信系统中可表示 收到 后，发送端发送的是符号 的概率。 接收端收到 后，关于 的不确定性可表示为 定义4.3.1 互信息量为： 互信息量为收到 后，关于 的不确定性的消除量。 第4章 信息论基础28 互信息量(续) 互信息量具有对称性

9、 互信息量的性质 (1) 若 (2) 若 (3) 若 (4) 若 第4章 信息论基础29 离散信源及容量(续) 平均互信息量 定义4.3.2 平均互信息量为： 平均互信息量具有非负性 表明从统计上来说，两相关联的随机变量集，其中一个集中符号的出现总是有利于提供有关另外一个集的信息。第4章 信息论基础30 离散信源及容量(续) 熵函数与平均互信息量间的关系 第4章 信息论基础31 熵函数与平均互信息量间的关系(续) 当信源X与Y统计独立时 (1)两个符号同时出现时提供的平均信息量等于每个符号的平均信息量之和； (2)一个符号不能提供有关另一符号的任何信息。第4章 信息论基础32 熵函数与平均互信

10、息量间的关系(续) 当两个信源相关时 (1)联合熵小于两个信源的熵的和: (2)平均互信息量等于两信源熵重合的部分； (3)信源的条件熵等于其自身的熵减去平均互信息量：第4章 信息论基础33 离散信道的容量 已知信道的转移矩阵 信源符号集： ； 符号传输速率： 系统的平均信息速率为： 第4章 信息论基础34 离散信道的容量(续) 定义4.3.3 离散信道的最大传输速率为其信道容量 匹配信源的概念 信道容量由信道特性和信源的统计特性决定。 信道特性确定之后，其容量由信源的统计特性决定。 匹配信源：能使单位时间内信道可传输的平均信息量达到信 道容量的信源称之。 记匹配信源的分布特性： 信道容量：

11、第4章 信息论基础35 离散信道的容量(续) 匹配信源(续) 已知信道转移概率，匹配信源统计特性的求解 约束条件 求 使得 达到最大。 由拉格朗日求极值的原理： 定义辅助方程 令 可得信源分布特性应满足的条件第4章 信息论基础36 离散信道的容量(续) 由此可导出匹配信源统计特性的求解步骤： (1)解方程组 求解得 (2)求最大平均互信息量： (3)求相应后验概率： (4)解方程组，确定匹配信源的分布特性 第4章 信息论基础37 离散信道的容量(续) 示例：求匹配信源的统计特性。已知信道转移概率 (1)解方程组得中间结果参数： (2)求最大平均互信息量： (3)求相应后验概率： 第4章 信息论

12、基础38离散信道的容量(续) 示例(续)： (4)获得匹配信源统计特性： (5)信道容量为： 注：若求解过程中出现 ，可在方程组中令 ，重新求解。 第4章 信息论基础39 离散无记忆对称信道的容量(续) 离散无记忆对称信道(定义)： 转移矩阵 转移矩阵各行各列均具有相同的元素集的信道称之。 离散无记忆对称信道满足条件： 对矩阵中任意的列元素，有 对矩阵中任意的行元素，有 第4章 信息论基础40 离散无记忆对称信道的容量(续) 离散无记忆对称信道特性： (1)离散无记忆对称信道的条件熵满足： 条件熵取值仅由信道特性决定，与信源的统计特性无关。 (2)若输入信道的信源符号等概 则信道的输出符号也等

13、概 第4章 信息论基础41 离散无记忆对称信道的容量(续) 信道容量： 对于离散无记忆对称信道，若要使信息传输速率达到信道容量，要求信源的符号等概分布。 对于非等概的信源，可设法对其输出的符号进行适当的组合，使得重新构建后的符号(信源)，具有近似等概的分布特性。 (参见“信源的等长编码”一节)第4章 信息论基础424.4 连续信源、信道及容量43 连续信源、信道及容量 连续信源的相对熵 若已知随机信号 幅度取值的概率密度函数： 取值在任意小区间 内的概率 (参见示意图) 连续信源转变为具有n个随机变量的信源，且有 利用离散随机变量熵的定义，得 第4章 信息论基础44 连续信源、信道及容量(续)

14、 连续信源的相对熵 概率密度函数的离散化示意图，输入的取值范围 第4章 信息论基础45 连续信源的相对熵(续) 连续信源的熵应为 可见连续信源的熵无限大。该熵称为连续信源的绝对熵，无 法确切地定义。 通常上式的第一项是有限值，且其具有特定的物理意义。第4章 信息论基础46 连续信源的相对熵(续) 定义4.4.1 连续信源的相对熵为 示例 某信号的相对熵为 信号经2倍幅度放大后的相对熵为 信号的简单放大并没有增加任何新的信息，但其相对熵发生 了增大的变化，这说明相对熵已经不再具有信源平均信息量 的内涵。第4章 信息论基础47 连续信源的相对条件熵 对于连续随机变量，同样可以导出其条件熵 可见连续

15、信源的条件熵取值无限大，同样无法确切定义。但通常上式的第一项是一个有限取值的量。 连续信源的熵和条件熵均取值无限大，说明要在一个容量有 限的通信系统中传递连续信源的全部信息是不可能的。第4章 信息论基础48 连续信源的相对条件熵(续) 定义4.4.3 连续信源的相对条件熵 因为： 说明相对熵和相对条件熵的差值与普通的熵和条件熵的差值 一样，仍然等于平均互信息量。 同理可以导出：第4章 信息论基础49 连续信源相对熵的最大化 定理4.4.3 连续信源的相对熵函数 是信源概率密度函 数 的型凸函数。 相对熵 作为概率密度函数 的函数存在最大值。 第4章 信息论基础50 连续信源相对熵的最大化(续)

16、(1)峰值功率受限情况下的相对熵最大化条件 可以证明：当连续信源的概率密度函数服从均匀分布时，该连续信源有最大的相对熵。 在区间 均匀分布连续信源 的概率密度函数为 其相对熵为 峰值受限信号 若 第4章 信息论基础51 连续信源相对熵的最大化(续)(2)均值受限情况下的相对熵最大化条件 可以证明：当连续信源的概率密度函数服从指数分布时，该连续信源有最大的相对熵。 均值受限信号 指数分布 相对熵第4章 信息论基础52 连续信源相对熵的最大化(续)(3)平均功率受限情况下的相对熵最大化条件 可以证明：当连续信源的概率密度函数服从高斯分布时，该连续信源有最大的相对熵。 平均功率受限信号 高斯分布 相

17、对熵第4章 信息论基础53 加性高斯噪声信道的容量 加性高斯噪声(干扰)信道(AWGN) 信道输入： 信道输出： 加性高斯噪声： 已知通过信道后，从 可获得的关于 的平均互信息量 若已知信号 的带宽为 。 对任意的这类信号 则无失真无冗余的抽样频率应为： (单位时间的样点数) 单位时间内传输的信息量，即信息速率为第4章 信息论基础54 加性高斯噪声信道的容量(续) 加性高斯噪声(干扰)信道(AWGN)的信道容量 信号与噪声间的关系可用方程组表示为 或 二维函数概率密度间的关系 为雅可比行列式第4章 信息论基础55 加性高斯噪声信道的容量(续) 因为 所以有 若已知信源x的统计特性，收到y后不可

18、确定的部分为 噪声的影响所导致。第4章 信息论基础56 加性高斯噪声信道的容量(续) 因此可得第4章 信息论基础57加性高斯噪声信道的信道容量(续) 因为 (1) 在均方受限的条件下，高斯分布的信源有最大的相对熵 (2) 两高斯分布的随机变量之和( )仍为高斯随机变量 (3) 信号 与噪声 统计独立 因而有第4章 信息论基础58 加性高斯噪声信道容量(续) 信道容量 若记 得香农公式第4章 信息论基础59加性高斯噪声信道容量(续)由香农公式(香农定理) 得到的重要结论： (1) 信道容量C随S/N增大而增大； (2) C一定时，W与S/N之间可以彼此互换； (3) N 0, C ：无扰信道的容

19、量为无穷大； (4) 对受高斯噪声干扰的信道，当 W ， 信道容量趋于 一有限的确定值： (S与N0固定时)第4章 信息论基础60 信道容量和带宽的归一化分析 归一化信道容量：单位时间单位频带内可达到的信息速率。 注：所谓物理不可 实现是指不可 能实现无差错 传输。第4章 信息论基础61 信道容量和带宽的归一化分析(续) 归一化信道带宽：单位信息速率所需要的最小带宽。第4章 信息论基础62 信道容量和带宽的归一化分析(续) 关于Eb/N0的归一化信道带宽 Eb：比特能量； N0：噪声功率密度谱； 当 Eb/N0 1.59dB 时，无法实现无差 错的传输。第4章 信息论基础634.5 信源编码的

20、基本方法64 信源编码的基本方法 信源编码的目的：提高传输效率 （1）去除消息中的冗余度，使传输的符号尽可能都是独立的，没有多余的成分(如语音、图像信号压缩)； （2）使传输的符号所含的信息最大化。例如，通过编码使符号以等概分布的形式出现，使每个符号可能携带的信息量达到最大； （3）采用不等长编码，让出现概率大的符号用较短的码元序列表示，对概率小的符号用较长的码元序列； (4) 在允许一定失真的条件下，如何实现高效率的编码。第4章 信息论基础65 离散无记忆信源 (DMS: Discrete Memoryless Source） 离散无记忆信源的输出序列： 各个符号间彼此独立 其中 反之，若输

21、出的各符号间有一定的相关性，则其为一种 有记忆的信源。 有记忆的信源，经过处理后，有可能变为一种无记忆的信 源。如有记忆的信源，经过理想的、完全去除冗余的 压缩编码后产生的输出。第4章 信息论基础66 离散无记忆信源编码与译码 若将信源输出的符号按每J个为一组进行编码，则任意的第m个分组可以表示为 (信源符号集) 编码输出 其中 为输出的码元集。 接收端的译码输出第4章 信息论基础67 离散无记忆信源编码与译码(续) 待编码码组简单记为 编码输出码组(码字)第4章 信息论基础68 离散无记忆信源编码与译码(续)定义4.5.1 若对信源的每个不同的符号或不同的符号序列，编 码后产生的码字不同，则

22、称该码为唯一可译码。 若待编码的符号序列的不同组合个数为 码字集中不同的码字个数 编码输出为唯一可译码的(必要)条件 对于码元取自 ，码字长度为 一个码字，其最大可携带的信息量为第4章 信息论基础69 离散无记忆信源编码与译码(续)定义4.5.2 编码表示一个信源符号所需的平均信息量的定义为 编码速率 。 码字长度为常数的编码称为等长编码，反之称为不等长编码。 对长度为 的信源符号序列进行编码： 等长编码的编码速率 不等长编码的编码速率 其中 为不等长编码的平均码长。第4章 信息论基础70 离散无记忆信源编码与译码(续) 定义4.5.3 信源的熵 与编码速率 的比值定义为编码效率 要保证编码没

23、有信息丢失，要求第4章 信息论基础71 离散无记忆信源的等长编码* 等长编码：对信源的每个符号，或每组符号，用长度相等的代码来表示。 单个符号独立编码 采用 进制码元编码 若信源符号集有 L 种符号，要保证译码的惟一性，由 码字长度应取 取整得 编码效率： 第4章 信息论基础72 离散无记忆信源的等长编码(续) 扩展编码(联合编码)：将 J 个信源符号进行联合编码 由译码唯一性要求 取整得 平均每个符号所需的码元数 J 取值的增大有利于效率的提高。第4章 信息论基础73 离散无记忆信源的等长编码(续) 信源统计特性对编码效率的影响例4.5.1 采用二进制码元分别对J4的两信源符号序列进行编码。

24、 信源1： 因为 故可取 平均每个符号的码元数 编码效率第4章 信息论基础74 离散无记忆信源的等长编码(续) 信源2： 同理有 平均每个符号的码元数 编码效率第4章 信息论基础75 离散无记忆信源的等长编码(续) 来自同样符号集，但不同统计特性的信源，因其熵 不同。编码效率 可能差异很大。第4章 信息论基础76 离散无记忆信源(DMS)的有损等长编码 一种考虑信源统计特性的编码 信源符号集 由最大熵定理 由熵的定义，可知 由译码的唯一性要求 可得 码组长度应满足条件 由 得第4章 信息论基础77 离散无记忆信源(DMS)的有损等长编码 一种考虑信源统计特性的编码(续) 对任意统计特性的信源，

25、要使下式成立，即获得较高的编码效率，通常 J 取值要非常大，方能使 无损的等长编码，往往会因为 J 的取值过大，难以实际应用。 下面考虑有损的等长编码。第4章 信息论基础78 离散无记忆信源(DMS)的有损等长编码 对于长度为 J 的DMS码组(或称为一序列): 码组中的每个符号： 由符号间的独立性，有 码组 包含的信息量为： 根据熵的定义，随着 J 的增大，有 或 可以证明当 J 足够大时，有第4章 信息论基础79 离散无记忆信源(DMS)的有损等长编码(续) 即： 定义 4.5.4 典型序列集：满足下列条件的序列 的集合称之。 其中 。 通常取 为一个较小的正数。 非典型序列集：典型序列集

26、的补集称之。记为 典型序列集和非典型序列集构成了序列 所有组合； 构成该符号序列的整个空间：第4章 信息论基础80 离散无记忆信源(DMS)的有损等长编码(续) 定理4.5.5 (信源划分定理)：任给 ，当 J 足够大时,有 即有： 典型序列出现的概率：若 则 即有： 典型序列趋于等概分布。 典型序列的数目：第4章 信息论基础81 离散无记忆信源(DMS)的有损等长编码(续) 典型序列的出现概率： 即： 典型序列集 为高概率集； 非典型序列集 为低概率集。 第4章 信息论基础82 离散无记忆信源(DMS)的有损等长编码(续) 典型序列集在整个序列空间中所占的比例： 可选择 ，使满足 因此 说明

27、虽然典型序列集是一个高概率集，但其数目在整个序列空间中可能只占很小的比例； 第4章 信息论基础83 离散无记忆信源(DMS)的有损等长编码(续) 典型序列集的形象说明 如果容许一定的失真，只对典型序列编码，对非典型序列不 予编码传输，码字长度可大大缩短，从而有效提高传输效率。第4章 信息论基础84 离散无记忆信源(DMS)的有损等长编码(续) 例4.5.2：已知二元信源 信源的熵为： 所有的序列 构成的集合 为第4章 信息论基础85 离散无记忆信源(DMS)的有损等长编码(续) 示例(续)： (1) 若取 由 平均信息量落在该范围内的序列(典型序列)为 其概率和 第4章 信息论基础86 离散无

28、记忆信源(DMS)的有损等长编码(续) 示例(续)： (2) 若取 由 平均信息量落在该范围内的序列(典型序列)为 其概率和 第4章 信息论基础87 离散无记忆信源(DMS)的有损等长编码(续) 可达速率的概念 译码错误概率定义为 定义4.5.6 可达速率 给定信源和编码速率R，对任意的 若存在 和编译码方法： 、 使当 时，有 则该编码速率称为可达的 反之称速率是不可达的。 前面已经定义编码速率：第4章 信息论基础88 离散无记忆信源(DMS)的有损等长编码(续) 定理 4.5.7 若 ，则速率 R 是可达的； 若 ，则速率 R 是不可达的。 该定理说明，若 ，则存在编码方法，当 J 足够

29、大时，只需对典型序列进行编码，可使编码误差足够地小。 定理的物理意义是：只有用于承载每个符号信息的平均比特数大于等于信源的熵，才能使译码的误差任意地小。 第4章 信息论基础89 离散无记忆信源(DMS)的有损等长编码(续) 分析在满足一定的译码错误概率的条件下，若只对典型序列编码，如何确定编码长度： 若记：编码速率： 自信息方差： 则不能正确译码的概率 满足关系式(参见信源划分定理证明) 根据上式，可确定编码序列的长度 J 。第4章 信息论基础90 离散无记忆信源(DMS)的有损等长编码(续) 示例： (1)对二元符号进行无差错的二进制编码 此时 、 、 (2) 若要求编码效率 ， 求所需的编

30、码序列长度 J 由 得第4章 信息论基础91 离散无记忆信源(DMS)的有损等长编码(续) 自信息方差： 最后得所需的符号序列长度 (该取值太大，可见等长编码不易在实际系统中应用)第4章 信息论基础92 不等长编码的基本概念 定义4.5.8 若码中每个码字都含有一个特定的符号用于标识 一个码字的起点，则称这种码为逗点码。 例：0，01，011，0111 为逗点码。 定义4.5.9 对任一码字 ，称该码字的前面 位 ， ，为码字 的长为 的字头或前缀。 定义4.5.10 若码字集中任一码字都不是另一码字的字头，则 称这种码为异字头码，或异前缀码。 定义4.5.11 对具有 个元素的信源符号集：

31、若符号 用 元码编码后输出的码字长度为 ，则定 义信源符号的平均码字长度为：第4章 信息论基础93 异字头不等长编码 异字头码的优点：异字头码译码时具有即时性，即当收到一个完整的码字后即可译码，不用担心这一码字是另一码字的字头部分。 异字头码的编码树：异字头码的编码可用编码树来描述第4章 信息论基础94第4章 信息论基础 异字头不等长编码(续)（1）从根朝下，第一级有 个节点；第二级有 个节点；如此类推，第r 级有 个节点。（2）从任一节点引出的分支有 个，从根开始，可分别用0，1，2， 1来标记。（3）不再发出分支的节点称为端节点，若用端节点表示不同的信源符号，取相应的从根到该节点的标号序列

32、为码字，则必能保证码字的异字头条件。（4）若各分支均延伸到最高级的各端点，则可构成一棵对称的树，称为满树，否则称为非满树。95第4章 信息论基础 异字头不等长编码(续) 异字头码的编码原则 编码时应尽可能地使码字中的任一码元载荷达到其最大的信息量： 。 应使每个节点发出的种 分支出现的概率尽可能相等。 异字头码的编码方法 将信源符号分成尽可能等概的个子集，与码树的第一级的个节点对应； 对每个子集按同样的方法又分为个二级子集，与码树的第二级节点相对应； 以此类推，直至子集不能再分为止。 96第4章 信息论基础 异字头不等长编码(续) 示例： 对信源符号集 做 的三进制异字头不等长编码。 解：97

33、第4章 信息论基础 不等长编码的基本定理* 定理4.5.12 对具有个符号的信源符号集： ，其相应的长度为 的元异字头码存在的充要条件是如下的不等式成立即：当满足条件 时，一定存在与该码字对应的编码树。 定理4.5.13 唯一可译码必满足(Kraft)不等式： (定理4.5.13）系：任一唯一可译码可用相应的码字长度一样的异字头码代替。 即：任一唯一可译码可用相应的码字长度一样的异字头码代替，而不改变该码的任何性质。 98第4章 信息论基础 不等长编码的基本定理*(续)定理4.5.14 （不等长编码定理）（1）若 是组成码字的元素的个数，则任一唯一可译码的平均码长满足： （2）存在有 元的可译

34、码，其平均长度99第4章 信息论基础 不等长编码的基本定理*(续) 多个符号的联合不等长编码 记： 信源符号集： 待编码的符号序列(符号分组)： 特定符号序列 编码后输出的码字长度 符号序列 编码后的平均码字长度 符号序列 的熵函数 则由定理4.5.14，可得 100第4章 信息论基础 不等长编码的基本定理*(续) 定义4.5.15 对 J 个信源符号进行不等长联合编码时平均一个信源符号的编码长度定义为 由前面的讨论可得 可见：多个符号的不等长联合编码有同样利于提高编码效率。 101第4章 信息论基础 不等长编码的基本定理(续) 离散无记忆信源的扩展信源的编码 以 J 个离散无记忆信源符号为一

35、组可构成一个扩展信源 扩展信源的熵函数为 由前面的分析可得 可见对扩展后的离散无记忆信源的编码有利于提高编码效率。 且有102第4章 信息论基础 不等长编码的基本定理(续) 定义4.5.16 不等长码的编码速率定义为 是平均每个信源符号编码时所需的码元的个数； 是每个码元可能携带的最大信息量； 编码速率的物理意义是由平均 个码元构成的码字可携带的最大信息量。 定义4.5.17 不等长码的编码效率定义为编码效率表示的是每个信源符号平均信息量与编码所需的平均码字符号可携带最大信息量的比值。 103第4章 信息论基础 不等长编码的基本定理(续)例4.5.7 某离散无记忆信源的消息符号和其概率场为 试

36、分析对其采用 的码字进行单个符号编码和两个符号的联合编码时的平均码长和编码效率。解：信源的熵(1) 对单个信源进行编码时，码字的码元集 平均码长 编码速率 编码效率：104第4章 信息论基础 不等长编码的基本定理(续)例4.5.7 (2) 若对每两个信源符号进行联合编码 符号序列的平均码长 平均每个符号的编码长度 编码速率 编码效率 可见效率明显提高。105 霍夫曼(Huffman)编码 霍夫曼编码是一种异字头不等长编码，其基本思想是： 对出现概率大的符号或符号组用位数较少的码字表示； 对出现概率小的符号或符号组用位数较多的码字表示。 由此可提高编码效率。 霍夫曼编码： 定理4.5.17 霍夫

37、曼编码一种最佳的不等长编码。 霍夫曼编码的应用条件： 信源的分布(统计)特性已知。 记 信源符号集为： 组成编码输出码字的码元集为：第4章 信息论基础106 霍夫曼编码(续) 霍夫曼编码的步骤：(1)将L个信源符号:S1、S2、SL 按概率P(Si)大小，以递减次序，从上到下排成一列；(2)对处于最下面的概率最小的D个信源符号，一一对应地分别赋予码字元素C1、C2、CD，把这D个概率最小的信源符号相应的概率相加，所得的值用一个虚拟的符号代表，与余下的L-D个符号组成含有(L-D)+1=L-(D-1)个符号的第一次缩减信源S(1)；(3)对缩减信源S(1)仍按其概率大小以递减次序从上到下排列，按

38、照步骤(2)的方法处理，得到一个含有(L-D)+1-D+1=L-2(D-1)个符号的第二次缩减信源S(2)；(4)按照上述的方法，依次继续下去，每次缩减所减少的符号数是D-1个；只要缩减后的信源Si符号的个数大于D，缩减就继续进行；第4章 信息论基础107 霍夫曼编码(续) 霍夫曼编码的步骤：(5)当进行第a次缩减后信源S(a）符号个数刚好等于D，即有 则对最后这D个符号分别赋予码字元素C1、C2、CD；(6)从最后赋予的码符号开始，沿着每一信源符号在各次缩减过程中得到的码字元素进行路线前向返回，达至每一信源符号，按前后次序，把返回路途中所遇到的码元素排成序列，这个序列，就是相应信源符号对应的

39、码字；第4章 信息论基础108 霍夫曼编码(续) 霍夫曼编码的步骤：(7)若进行a次缩减后，当进行第k次缩减后信源S(a)符号个数不等于D，即有则中止缩减，增加 个概率为0的虚假信源符号 重新编码，使在k次编码后一定有 。第4章 信息论基础109 霍夫曼编码(续) 示例：已知信源符号集 编码输出的码字符号集为 解：已知： 尝试 需要增加虚假符号数为 新构建的信源满足：第4章 信息论基础110 霍夫曼编码示例(续)：改造后的符号概率场为 编码过程如下第4章 信息论基础111 霍夫曼编码(续) 示例(续)： 平均码字长度：第4章 信息论基础112 霍夫曼编码(续) 示例(续)： 如果不加入虚假符号

40、，直接进行编码，则有 平均码字长度第4章 信息论基础113 霍夫曼编码(续) 码字长度的均匀性和方差 在同样的平均码字长度的情况下，码字长度越均匀，对传输越有利。 定义4.5.16 码字长度的方差 其中 编码过程的排序过程不同会影响码长的方差。第4章 信息论基础114 霍夫曼编码(续) 码字长度的均匀性和方差(续) 示例：信源的符号空间为 编码输出码字集 编码方式1 将局部概率和置于相同概率的最低位置第4章 信息论基础115 霍夫曼编码示例：编码方式1(续) 平均码长： 方差：第4章 信息论基础116 霍夫曼编码 编码方式2 将局部概率和置于相同概率的最高位置 平均码长： 方差：第4章 信息论

41、基础117 霍夫曼编码(续) 可见 虽然平均码长一样，但编码方法2使得输出的码长更为均匀。 在编码过程中，当对缩减信源概率重新排列时，应使合并得到的局部概率和，尽量使其处于最高位置；使得合并元素重复编码的次数减少，有利于降低码字长度的方差。 第4章 信息论基础1184.6 率失真理论119 实际系统中的权衡问题 实际系统中通常需要考虑性能与经济性之间的权衡问题； 可采用以某些不可察觉或可察觉但不影响应用的信号失真代价，来换取所需的传输速率、存储空间、运算复杂度和系统实现成本的降低； 电话系统采样8kHz采样，8比特量化； 数字音响系统采样44kHz采样，16或24比特量化； 第4章 信息论基础120 失真的概念 失真是指用某种尺度衡量的理想信源样值 与“变换”后的样值 间的差异。 这里所谓的“变换”，可以是某种有损的编码，或者是经传输后受到劣化的信号。 失真函数：对由符号 变为符号 产生失真造成的影响，可根据不同的情况定义一个非负函数 来描述，该函数就称为失真函数。 失真函数的取值通常反映失真产生的代价。 第4章 信息论基础121 失真的概念(续) 失真函数的示例： 第4章 信息论基础122 率失真理论研究的问题 率失真理论研究的是限定失真条件下信源的编