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

■《数字通信原理》(第3版)（第4章）1第

4

章

信息论基础2本章的基本内容：信息的度量方法；离散信道及容量；连续信源、信道及容量；信源编码的基本方法；信道编码的基本方法；率失真理论。3n4.1

引言4消息与信息n

1948年，美国科学家香农的论文《通信的数学理论》，n

奠定了信息论的理论基础。n 消息与信息(1)消息是由符号、文字、数字、语音或图像组成的序列；nn

(2)消息是信息的载体，信息是消息的内涵；消息中可能包n

含信息，也可能不包含信息；n

(3)收到一则消息后，所得的信息量，在数量上等于获得n

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

信息的度量7信息度量的概念n(1)某消息的信息量＝获得该消息后不确定性的消除量；不确定性

可能性 概率问题：nnn(2)信息量可用概率的某种函数来度量不同的消息有信息量的多少的区别，因此nnn信息的度量方式应满足信息量的可加性信息量应该是满足可加性的概率的函数。n第4章信息论基础离散信源信息的度量离散信源的信息量离散信源统计特性的描述方法－－概率场nn

设离散信源包含N种可能的不同符号，相应的概率场可表述为nn

概率场应满足条件：nn第4章信息论基础8离散信源的信息量(续)信息量作为概率的函数，具有形式n与统计独立，满足可加性要求n

若nnn

如定义n

直观地，概率越小的事件一旦出现，提供的信息量越大。n

显然有n可同时满足是概率的函数和可加性两个要求。n第4章信息论基础9离散信源信的息量(续)n 定义离散消息xi的信息量:nn信息量的单位与对数的底有关：nlog以2为底时，单位为比特：bitnlog以e为底时，单位为奈特：nitnnnlog以10为底时，单位为哈特，hart一般在没有特别声明时均假定信息的单位为比特。n第4章信息论基础10离散信源信的息量(续)n

示例：已知某信源的概率场为nn息量输出的各符号统计独立，计算序列S：“113200”，的信nn第4章信息论基础11离散信源的平均信息量：信源的熵离散信源的熵如何描述或度量一个信源输出信息量的大小？何种类型的信源输出的信息量最大？定义4.2.2

离散信源 的熵nn

熵是信源在统计意义上输出的每个符号的平均信息量。n

熵较大的信源，输出同样个数n

的符号，所含的信息量更大。n第4章信息论基础12离散信源的熵(续)示例：求离散信源的熵。nn

按照定义：nn熵的单位：比特/符号n第4章信息论基础13离散信源的熵(续)示例（续）：若上述离散信源发送独立的符号序列：201

020

130

213

001

203

210

100

321

010023

102

002

10

312

032

100

120

210(1)求总的信息量；(2)利用熵估计总的信息量。解：(1)■■n(2)n

随着符号序列的增大，两者趋于相同。n第4章信息论基础14离散信源的最大熵定理定义4.2.3凸集对任意，有定义4.2.4

若■型凸函数(下凸函数)■型凸函数(上凸函数)n第4章信息论基础15离散信源的最大熵定理(续)若函数为若函数为型凸函数(下凸函数)，则一定存在最小值型凸函数(上凸函数)，则一定存在最大值■■型凸函数示例■n第4章信息论基础16离散信源的最大熵定理(续)若是一组概率；是一个 型凸函数，则一般地有如下的关系式■■利用上面的关系式，可以证明如下的定理定理4.2.5

熵函数 是概率的 型凸函数。(上述关系式的证明过程参见教材)物理意义：一定存在一组概率，使得熵取最大值。n第4章信息论基础17离散信源的最大熵定理(续)定理4.2.6当离散信源X取等概分布时，其熵值。取最大n

(证明过程参见教材。)n

物理意义：当信源取等概分布时，具有最大的不确定性。n示例：两个信源符号的情形。P(x1)=p,P(x2)=1-p当p=1/2时，H(X)=Hmaxnnnnn等概的二元信源，每个符号可携带1比特信息。n第4章信息论基础18离散信源的最大熵定理(续)定理4.2.6告诉我们：如果对信源的符号/码元进行某种变化，使得变换后的符号集具有等概或近似等概的特性，可使得每个符号/码元可携带最大的信息量。（不要与下面的概念混淆：对消息（语音、图像等各类信号）的处理后得到的结果，只会有可能减少该消息的信息量，而不会增加信息量。）n第4章信息论基础1n19离散信源的联合熵与条件熵两随机变量的概率场n

满足条件：n第4章信息论基础20离散信源的联合熵与条件熵(续)两随机变量的联合熵在通信系统中，常常需要同时考虑两个或两个以上随机变量。定义4.2.3两随机变量的联合熵■如两随机变量统计独立，有n第4章信息论基础21两随机变量的联合熵(续)对于统计独立的两随机变量，不能从其中一个获得有关另外一个的任何信息。两随机变量的条件熵两随机变量已知

后，

出现的概率称为条件概率，记为■同理。已知后，

条件概率为在已知某个随机变量的情况下，另一随机变量仍包含的信息量（不确定性）为

或n第4章信息论基础22离散信源的联合熵与条件熵(续)两随机变量的条件熵定义4.2.4两随机变量的条件熵■一般地有(利用稍后的平均互信息量的非负性可以证明)一般地(具有某种相关性的两随机变量)，一个随机变量的出现总是有助于降低另一随机变量的不确定性。n第4章信息论基础2324n4.3

离散信道及容量离散信源及容量信道模型■信道的输入：信道的输出：狭义信道的概念：物理传输信道，如无线信道，电缆光纤等；信道可以更一般化和广义化，如记录与重放等经历的过程。离散信道模型(特性)可用其转移概率来描述n第4章信息论基础25离散信源及容量(续)离散信道模型■离散信道模型(特性)可用其转移概率来描述，一般地有■■输出不仅与当前的输入有关，而且与之前的若干个输入值有关，呈现某种“记忆”效应。在许多情况下，信道输出主要只与当前的输入有关：这类信道称为无记忆信道。本课程主要讨论无记忆信道。离散信道模型可以看作是屏蔽了物理信道细节的统计模型。n第4章信息论基础26离散信源及容量(续)离散无记忆信道的转移矩阵 输出仅与当前的输入有关■■■：当发送xi

时，收到yj

的概率。离散无记忆信道的后验概率矩阵n第4章信息论基础n当收到yj

时，发送是xi的概率27离散无记忆信道的转移矩阵(续)示例：二元的离散无记忆信道■■发“0”和发“1”时能正确接收的概率为0.99，错误的概率为0.01。即有转移矩阵■n第4章信息论基础28离散信源及容量互信息量后验概率是一种条件概率，在通信系统中可表示收到

后，发送端发送的是符号

的概率。接收端收到

后，关于

仍存在的不确定性可表示为■显然

越大，不确定性就越小。定义4.3.1互信息量为：互信息量为收到后，关于的不确定性的消除量。n第4章信息论基础29互信息量(续)互信息量具有对称性互信息量的性质(1)若(2)若(3)若(4)若n第4章信息论基础30离散信源及容量(续)平均互信息量定义4.3.2平均互信息量为：平均互信息量具有非负性(证明参见教材)表明：从统计上来说，两相关联的随机变量集，其中一个集中符号的出现总是有利于提供有关另外一个集的信息。n第4章信息论基础31离散信源及容量(续)平均互信息量具有非负性：证明：因为对数函数是一个型凸函数，由凸函数有关特性有由此可得进而可得n第4章信息论基础32离散信源及容量(续)熵函数与平均互信息量间的关系等■n第4章信息论基础33熵函数与平均互信息量间的关系(续)n 当信源X与Y统计独立时n

(1)两个符号同时出现时提供的平均信息量等于每个符号的平均信息量之和；n

(2)一个符号不能提供有关另一符号的任何信息。n第4章信息论基础34熵函数与平均互信息量间的关系(续)n 当两个信源相关时n

(1)联合熵小于两个信源的熵的和:nn

(2)平均互信息量等于两信源熵重合的部分；n

(3)信源的条件熵等于其自身的熵减去平均互信息量：n第4章信息论基础35离散信道的容量n

已知信道的转移矩阵n 信源符号集：

； 符号传输速率：n

系统的平均信息速率为：n平均信息速率由信源统计特性和信道特性（转移概率）决定。n第4章信息论基础36离散信道的容量(续)nn 定义4.3.3离散信道的最大信息传输速率为其信道容量n(因为通常

是常数，人们在讨论问题时通常将其省略)n 匹配信源的概念n

信道容量由信道特性和信源的统计特性共同决定。

n

信道特性确定之后，其容量由信源的统计特性决定。nnnnn匹配信源：能使单位时间内信道可传输的平均信息量达到信道容量的信源称之。记匹配信源的分布特性：信道容量：n第4章信息论基础37离散信道的容量(续)匹配信源(续)已知信道转移概率，匹配信源统计特性的求解约束条件求

使得由拉格朗日求极值的原理：定义辅助方程令达到最大。可得信源分布特性应满足的条件n第4章信息论基础38离散信道的容量(续)匹配信源(续)若取得其解为：则可得最大的平均互信息量为由上述两组关系式可得整理可得n第4章信息论基础39离散信道的容量(续)匹配信源(续)记可得若已知信道转移概率可求解由此可进一步得利用概率约束条件：n第4章信息论基础40离散信道的容量(续)匹配信源(续)由此可得关于信源分布特性的方程组：求解该方程组，即可得能够达到信道容量的信源统计特性。n第4章信息论基础41离散信道的容量(续)n

由此可导出匹配信源统计特性的求解步骤：n

(1)解方程组n

求解得n

(2)求最大平均互信息量：n

(3)求相应后验概率：n

(4)解方程组，nn确定匹配信源的分布特性n第4章信息论基础42离散信道的容量(续)n

示例：求匹配信源的统计特性。已知信道转移概率n

(1)解方程组得中间结果参数：nn(2)求最大平均互信息量：n

(3)求相应后验概率：nn第4章信息论基础43n离散信道的容量(续)n

示例(续)：n

(4)获得匹配信源统计特性：n

(5)信道容量为：nn

注：若求解过程中出现n

，重新求解。n，可在方程组中令n第4章信息论基础44离散无记忆对称信道的容量(续)n 离散无记忆对称信道

(定义)：n

转移矩阵n转移矩阵各行各列均具有相同的元素集的信道称之。n

离散无记忆对称信道满足条件：n

对矩阵中任意的列元素，有n对矩阵中任意的行元素，有nn第4章信息论基础45离散无记忆对称信道的容量(续)n 离散无记忆对称信道特性：n

(1)离散无记忆对称信道的条件熵满足：n

因为：n 条件熵关。仅由信道特性决定，与信源的统计特性无n第4章信息论基础46离散无记忆对称信道的容量(续)n 离散无记忆对称信道特性：nn

(2)若输入信道的信源符号等概nnnn则信道的输出符号也等概n第4章信息论基础47离散无记忆对称信道的容量(续)n 信道容量：nn 对于离散无记忆对称信道，若要使信息传输速率达到信道容量，要求信源的符号等概分布。n

对于非等概的信源，可设法对其输出的符号进行适当的组合/变换，使得重新构建后的符号(信源)，具有近似等概的分布特性。n

(参见“信源的等长编码”一节)n第4章信息论基础4849n4.4

连续信源、信道及容量连续信源、信道及容量连续信源的相对熵离散信道可以看作一种抽象的信道，对符号进行判决后统计的的结果，实际的物理信道是一种连续的信道。若已知随机信号

幅度取值的概率密度函数：取值在任意小区间内的概率■(参见示意图)连续信源转变为具有n个随机变量的信源，且有利用离散随机变量熵的定义，得n第4章信息论基础50连续信源、信道及容量(续)连续信源的相对熵■概率密度函数的离散化示意图，输入的取值范围n第4章信息论基础51连续信源的相对熵(续)连续信源的熵应为■可见连续信源的熵无限大。该熵称为连续信源的绝对熵。连续信源的绝对熵，无法确切地定义。通常上式的第一项是有限值，且稍后可见其具有特定的物理意义。n第4章信息论基础52连续信源的相对熵(续)定义4.4.1连续信源的相对熵为示例某信号的相对熵为信号经2倍幅度放大后的相对熵为信号的简单放大并没有增加任何新的信息，但其相对熵发生了增大的变化，这说明：■相对熵已经不再具有信源平均信息量的内涵。n第4章信息论基础53连续信源的相对条件熵对于连续随机变量，同样可以导出其条件熵可见连续信源的条件熵取值无限大，同样无法确切定义。但通常上式的第一项是一个有限取值的量。连续信源的熵和条件熵均取值无限大，说明要在一个容量有限的通信系统中传递连续信源的全部信息是不可能的。n第4章信息论基础54连续信源的相对条件熵(续)定义4.4.3连续信源的相对条件熵因为：说明相对熵和相对条件熵的差值与普通的熵和条件熵的差值一样，仍然等于平均互信息量。同理可以导出：n第4章信息论基础55连续信源相对熵的最大化是信源概率密度函■定理4.4.3连续信源的相对熵函数数

的 型凸函数。相对熵作为概率密度函数的函数存在最大值。(上述结论的证明需要用到泛函的数学知识，泛函研究函数的函数问题。)n第4章信息论基础56连续信源相对熵的最大化重要结论：利用泛函分析的方法可以证明：若

和

是任意两个取值均在区间的概率密度函数。则有的连续随机变量对于某，若成立则有最大的相对熵由此可得各种不同条件下达到最大相对熵的条件。n第4章信息论基础57连续信源相对熵的最大化(续)(1)峰值功率受限情况下的相对熵最大化条件当连续信源的概率密度函数服从均匀分布时，该连续信源有最大的相对熵。在区间

均匀分布连续信源

的概率密度函数为的任意的峰值功率受限的信号，假定同样分布在区间其分布为一般地，有由此可得n第4章信息论基础58连续信源相对熵的最大化(续)(1)峰值功率受限情况下的相对熵最大化条件当连续信源的概率密度函数服从均匀分布时，该连续信源有最大的相对熵。在区间

均匀分布连续信源

的概率密度函数为其相对熵为最大相对熵峰值受限信号因为n第4章信息论基础59连续信源相对熵的最大化(续)(2)均值受限情况下的相对熵最大化条件同理可证明：当连续信源的概率密度函数服从指数分布时，该连续信源有最大的相对熵。均值受限信号对指数分布相对熵为最大相对熵n第4章信息论基础60连续信源相对熵的最大化(续)(3)平均功率受限情况下的相对熵最大化条件同样可证明：当连续信源的概率密度函数服从高斯分布时，该连续信源有最大的相对熵。平均功率受限信号对高斯分布有最大相对熵因为高斯分布的信号具有广泛的代表性，因此平均功率受限的场景在通信中作为最常用和基本的假设。n第4章信息论基础61加性高斯噪声信道的容量加性高斯噪声(干扰)信道(AWGN)（说明研究AWGN的意义）加性高斯噪声：信道输入：

信道输出：已知通过信道后，从

可获得的关于

的平均互信息量若已知信号

的带宽为

。则无失真无冗余的抽样频率应为：对任意的这类信号(单位时间的样点数)单位时间内传输的信息量，即信息速率为n第4章信息论基础62加性高斯噪声信道的容量(续)加性高斯噪声(干扰)信道(AWGN)的信道容量信号与噪声间的关系可用方程组表示为或二维函数概率密度间的关系称为雅可比行列式n第4章信息论基础63加性高斯噪声信道的容量(续)对于加性噪声与信号间的关系因为所以有即：若已知信源x的统计特性，收到y后不可确定的部分为■噪声的影响所导致。n第4章信息论基础64加性高斯噪声信道的容量(续)■因此可得n第4章信息论基础65加性高斯噪声信道的信道容量(续)因为(1)在均方受限的条件下，高斯分布的信源有最大的相对熵(2)

两高斯分布的随机变量之和(

)仍为高斯随机变量(3)

信号

与噪声

统计独立因而有n第4章信息论基础66加性高斯噪声信道容量(续)信道容量若记得香农公式(香农信道容量定理)n第4章信息论基础67加性高斯噪声信道容量(续)由香农公式(香农定理)得到的重要结论：nn (1)信道容量C随S/N增大而(关于对数)增大；n (2)C一定时，W与S/N之间可以彼此互换；n (3)N 0,C

∞：无扰信道的容量为无穷大；n (4)

对受高斯噪声干扰的信道，当

W ∞，信道容量趋于n 一个正比于信号功率、反比于噪声功率密度谱的确定值：nn第4章信息论基础68信道容量和带宽的归一化分析归一化信道容量：单位时间单位频带内可达到的信息速率。注：所谓物理不可■实现是指不可能实现无差错传输。■■n第4章信息论基础69信道容量和带宽的归一化分析(续)归一化信道带宽：单位信息速率所需要的最小带宽。n第4章信息论基础70信道容量和带宽的归一化分析(续)关于Eb/N0的归一化信道带宽Eb：比特能量；N0：噪声功率密度谱；■当Eb/N0<－1.59dB时，无法实现无差错的传输。■■■n第4章信息论基础71信道容量和带宽的归一化分析(续)■香农定理指出了给定带宽的加性高斯噪声干扰信道、已知信号平均功率和噪声平均功率的情况下可能获得的最高信息传输速率。香农定理给出的容量公式计算所得的是(两点间)信息速率的上限；香农定理并没有告诉人们如何才能实现达到信道容量的信息传输速率。n第4章信息论基础7n7273n4.5

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

最大；（3）提高编码(传输)效率。采用不等长编码，让出现概率大的符号用较短的码元序列表示，对概率小的符号用较长的码元

序列；(4)在允许一定失真的条件下，如何实现高效率的编码。n第4章信息论基础离散无记忆信源(DMS:Discrete

Memoryless

Source） 离散无记忆信源的输出序列：各个符号间彼此独立其中反之，若输出的各符号间有一定的相关性，则其为一种有记忆的信源。有记忆的信源，经过处理后，有可能变为一种无记忆或近似无记忆的的信源。如：有记忆的信源，经过理想的、完全去除冗余的压缩编码后产生的输出。n第4章信息论基础75■(信源符号集)编码输出其中■为输出的码元集。接收端的译码输出n第4章信息论基础离散无记忆信源编码与译码■在通信过程中往往需要将信源输出的符号变换成便于传输的码字若将信源输出的符号按每J

个为一组进行编码，则任意的第m个分组可以表示为76离散无记忆信源编码与译码(续)■将待编码码组简单记为编码输出码组(码字)简单记为译码后，存在虽然经过的是无扰信道，但仍存在的可能性，是因为编码后的码字，有可能不是唯一可译的。n第4章信息论基础77离散无记忆信源编码与译码(续)■定义4.5.1若对信源的每个不同的符号或不同的符号序列，编■码后产生的码字不同，则称该码为唯一可译码。J

个待编码的符号序列的不同组合个数为码字集中不同的码字个数编码输出为唯一可译码的(必要)条件对于码元取自

，码字长度为一个码字，其最大可携带的信息量(由最大熵定理)为n第4章信息论基础78离散无记忆信源编码与译码(续)定义4.5.2编码表示一个信源符号所需的平均信息量的定义为编码速率

。码字长度为常数的编码称为等长编码，反之称为不等长编码。对长度为

的信源符号序列进行编码：等长编码的编码速率不等长编码的编码速率中

为不等长编码的平均码长。n第4章信息论基础79离散无记忆信源编码与译码(续)定义4.5.3

信源的熵 与编码速率率的比值定义为编码效■要保证编码(后译码)没有信息丢失，要求n第4章信息论基础80离散无记忆信源的等长编码*等长编码：对信源的每个符号，或每组符号，用长度相等的代码来表示。单个符号独立编码

采用

进制码元编码若信源符号集有L

种符号，要保证译码的惟一性，由码字长度应取■■取整得■■编码效率：■n第4章信息论基础81离散无记忆信源的等长编码(续)扩展编码(联合编码)：将J个信源符号进行联合编码由译码唯一性要求取整得平均每个符号所需的码元数J

取值的增大有利于效率的提高。n第4章信息论基础82

离散无记忆信源的等长编码(续)信源统计特性对编码效率的影响例4.5.1采用二进制码元分别对J＝4的两信源符号序列进行编码。（假定仅考虑译码的唯一性。）信源1：因为故可取平均每个符号的码元数编码效率n第4章信息论基础83离散无记忆信源的等长编码(续)信源2：同理有取平均每个符号的码元数编码效率n第4章信息论基础84离散无记忆信源的等长编码(续)■■来自同样符号集，但不同统计特性的信源，因其熵■可能不同。编码效率■可以差异很大。n第4章信息论基础85■离散无记忆信源(DMS)的有损等长编码一种考虑信源统计特性的编码 信源符号集■■■■■得■由最大熵定理由熵的定义，可知由译码的唯一性要求可得码组长度应满足条件由其中n第4章信息论基础86离散无记忆信源(DMS)的有损等长编码一种考虑信源统计特性的编码(续)对任意统计特性的信源，要获得较高的编码效率，即在

足够小的情况下，使成立■通常J

取值要非常大，方能实现。■理论上，只有：下面考虑有损的等长编码。方可实现无损的等长编码。n第4章信息论基础87离散无记忆信源(DMS)的有损等长编码对于长度为J

的DMS码组(一组符号序列):码组中的每个符号：由符号间的独立性，有码组

包含的信息量为：根据熵的定义，随着J

的增大，有■或可以证明当J

足够大时，有n第4章信息论基础88离散无记忆信源(DMS)的有损等长编码(续)即：定义

4.5.4－典型序列集：满足下列条件的序列的集合称之。其中

。当J

足够大时，可取一个较小的正数，以保证其典型性。－非典型序列集：典型序列集的补集称之。记为典型序列集和非典型序列集构成了序列构成该符号序列的整个空间：所有组合；n第4章信息论基础89离散无记忆信源(DMS)的有损等长编码(续)定理4.5.1(信源划分定理)：任给有，当J

足够大时,即有：证明：对于消息序列其符号信息量

的方差■由概率论中的弱大数定理，任给n第4章信息论基础90离散无记忆信源(DMS)的有损等长编码(续)由此可得对于任给的，当J

足够大时，有即当J

足够大时，因而有n第4章信息论基础91离散无记忆信源(DMS)的有损等长编码(续)典型序列出现的概率：若因为由

，可得即当J

足够大时，有：即，典型序列趋于等概分布。同样可证，典型序列的数目：n第4章信息论基础92离散无记忆信源(DMS)的有损等长编码(续)典型序列的出现概率：即：典型序列集非典型序列集为高概率集；

为低概率集。n第4章信息论基础93离散无记忆信源(DMS)的有损等长编码(续)典型序列集在整个序列空间中所占的比例：在一般情况下，可选择，使满足因此说明虽然典型序列集是一个高概率集，但其数目在整个序列空间中可能只占很小的比例；■n第4章信息论基础94离散无记忆信源(DMS)的有损等长编码(续)■典型序列集的形象说明■研究典型序列集特性的意义：如果容许一定的失真，只对典型序列编码，对非典型序列不予编码传输，码字长度可大大缩短，从而有效提高传输效率。n第4章信息论基础95离散无记忆信源(DMS)的有损等长编码(续)例4.5.2：已知二元信源信源的熵为：所有的序列构成的集合为n第4章信息论基础96离散无记忆信源(DMS)的有损等长编码(续)示例(续)：(1)若取由平均信息量落在该范围内的序列(典型序列)为■其概率和■n第4章信息论基础97离散无记忆信源(DMS)的有损等长编码(续)示例(续)：(2)若取由平均信息量落在该范围内的序列(典型序列)为■所占据的比例31.25%，其概率和■n第4章信息论基础98离散无记忆信源(DMS)的有损等长编码(续)可达速率的概念译码错误概率定义为定义4.5.5可达速率给定信源和编码速率R，对任意的和编码译码方法：

、若存在使当

时，有

则该编码速率称为可达的反之称速率是不可达的。前面已经定义编码速率：n第4章信息论基础99离散无记忆信源(DMS)的有损等长编码(续)定理

4.5.2■若若，则速率R

是可达的；，则速率R

是不可达的。■该定理说明，若

，则存在编码方法，保证典型序列的译码具有唯一性。当J

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

。n第4章信息论基础101离散无记忆信源(DMS)的有损等长编码(续)示例：(1)对熵等于0.722信源的二元符号进行无差错的■二进制编码此时

、■、(2)若要求编码效率，■求所需的编码序列长度J由■■得n第4章信息论基础102离散无记忆信源(DMS)的有损等长编码(续)自信息方差：最后得所需的符号序列长度（编码输出一个码组大小）约1兆个字符组成一个码组。该取值太大，工程上难以实现。可见高效率的等长编码不易在实际系统中应用。n第4章信息论基础103不等长编码的基本概念■定义4.5.6若码中每个码字都含有一个特定的符号用于标识 一个码字的起点，则称这种码为逗点码。■例：0，01，011，0111

为逗点码。定义4.5.7

对任一码字

，称该码字的前面

位■，

，为码字

的长为

的字头或前缀。■定义4.5.8若码字集中任一码字都不是另一码字的字头，则 称这种码为异字头码，或异前缀码。■定义4.5.9对具有若符号

用个元素的信源符号集：元码编码后输出的码字长度为

，则定■义信源符号的平均码字长度为：n第4章信息论基础104异字头不等长编码异字头码的优点：异字头码译码时具有即时性，即当收到一个完整的码字后即可译码，不用担心这一码字是另一码字的字头部分。异字头码的编码树：异字头码的编码可用编码树来描述n第4章信息论基础105n第4章信息论基础异字头不等长编码(续)n（1）从根朝下，第一级有

个节点；第二级有个节点；如此类推，第r

级有个节点。n（2）从任一节点引出的分支有1，2，…，－1来标记。个，从根开始，可分别用0，n（3）不再发出分支的节点称为端节点，若用端节点表示不同的信源符号，取相应的从第一级到该节点的标号序列为码字，则必能保证码字的异字头条件。n（4）若各分支均延伸到最高级的各端点，则可构成一棵对称的树，称为满树，否则称为非满树。106n第4章信息论基础异字头不等长编码(续)异字头码的编码原则编码时应尽可能地使码字中的任一码元载荷达到其最大的信息量：

。应使每个节点发出的

种分支出现的概率尽可能相等。异字头码的编码方法将信源符号分成尽可能等概的个子集，与码树的第一级的D个节点对应；对每个子集按同样的方法又分为个二级子集，与码树的第二级D个节点相对应；以此类推，直至子集不能再分为止。107n第4章信息论基础异字头不等长编码(续)示例：对信源符号集做解：的三进制异字头不等长编码。108n第4章信息论基础不等长编码的基本定理*定理4.5.3

对具有L个符号的信源符号集：，其相应的长度为

的元异字头码存在的充要条件是如下的不等式成立

(D

为码元的个数)即：当满足条件

时，一定存在与该码字对应的编码树。定理4.5.4唯一可译码必满足(Kraft)不等式：(定理4.5.4）系：任一唯一可译码可用相应的码字长度一样的异字头码代替。即：任一唯一可译码可用相应的码字长度一样的异字头码代替，而不改变该码的任何性质。109n第4章信息论基础不等长编码的基本定理*(续)n定理4.5.5

（不等长编码定理）n（1）若

是组成码字的元素的个数，则任一唯一可译码的平均码长满足：nn（2）存在有元的可译码，其平均长度n定理4.5.5告诉我们不等长编码应该唯一可译平均码长应该满足条件110n第4章信息论基础不等长编码的基本定理*(续)多个符号的联合不等长编码记：信源符号集：待编码的符号序列(符号分组)：■特定符号序列符号序列编码后输出的码字长度编码后的平均码字长度符号序列

的熵函数则由定理4.5.5，相应地，若满足则存在使得符号序列唯一可译的编码。111n第4章信息论基础不等长编码的基本定理*(续)定义4.5.15 对

J

个信源符号进行不等长联合编码时平均一个信源符号的编码长度定义为■由前面的讨论可得■112n第4章信息论基础不等长编码的基本定理(续)离散无记忆信源的扩展信源的编码的效率以J

个离散无记忆信源符号为一组可构成一个扩展信源扩展信源的熵函数为由前面的对J

个信源符号进行不等长联合编码分析，可得可见对扩展后的离散无记忆信源的编码有利于提高编码效率。且有113n第4章信息论基础不等长编码的基本定理(续)定义4.5.11不等长码的编码速率定义为■是平均每个信源符号编码时所需的码元的个数； 是每个码元可能携带的最大信息量；编码速率的物理意义是由平均

个码元构成的码字可携带的最大信息量。定义4.5.17不等长码的编码效率定义为■编码效率表示的是每个信源符号平均信息量与编码所需的平均码字符号可携带最大信息量的比值。114n第4章信息论基础不等长编码的基本定理(续)■例4.5.7

某离散无记忆信源的消息符号和其概率场为n试分析对其采用

的码字进行单个符号编码和两个符号的联合编码时的平均码长和编码效率。解：信源的熵(1)对单个信源进行编码时，码字的码元集编码速率平均码长编码效率：115n第4章信息论基础不等长编码的基本定理(续)■例4.5.7 (2)

若对每两个信源符号进行联合编码符号序列的平均码长平均每个符号的编码长度编码速率编码效率■可见效率明显提高。且较之等长编码更容易实现。116霍夫曼(Huffman)编码霍夫曼编码是一种异字头不等长编码，其基本思想是：■■对出现概率大的符号或符号组用位数较少的码字表示；对出现概率小的符号或符号组用位数较多的码字表示。由此可提高编码效率。这一思想在不等长编码中已经用过。霍夫曼编码：提供了一种便于实现的最佳不等长编码的具体方法。■定理4.5.6

霍夫曼编码一种最佳的不等长编码。霍夫曼编码的应用条件：■信源的分布(统计)特性已知。记信源符号集为：■组成编码输出码字的码元集为：n第4章信息论基础117118霍夫曼编码(续)霍夫曼编码的步骤：■(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)})仍按其概率大小以递减次序从上到下排列，按照步骤(2)的方法处理，得到一个含有[(L-D)+1]-D+1=L-2(D-1)个符号的第二次缩减信源{S(2)}；■(4)按照上述的方法，依次继续下去，每次缩减所减少的符号数是D-1个；只要缩减后的信源Si符号的个数大于D，缩减就继续进行；n第4章信息论基础霍夫曼编码(续)霍夫曼编码的步骤：■(5)当进行第a次缩减后信源{S(a）}符号个数刚好等于D，即有■■则对最后这D个符号分别赋予码字元素C1、C2、…、CD；n(6)从最后赋予的码符号开始，沿着每一信源符号在各次缩减过程中得到的码字元素进行路线前向返回，达至每一信源符号，按前后次序，把返回路途中所遇到的码元素排成序列，这个序列，就是相应信源符号对应的码字；n第4章信息论基础119霍夫曼编码(续)霍夫曼编码的步骤：■(7)若进行a次缩减后，当进行第a次缩减后信源S(a)符号个数不等于D，即有则中止缩减，增加符号个概率为0的虚假信源重新编码，使在a次编码后一定有增加虚拟信元符号有利于提高编码效率。n第4章信息论基础120霍夫曼编码(续)示例：已知信源符号集■编码输出的码字符号集为解：已知：

尝试■需要增加虚假符号数为■新构建的信源满足：n第4章信息论基础121霍夫曼编码示例(续)：改造后的符号概率场为编码过程如下n第4章信息论基础122霍夫曼编码(续)示例(续)：平均码字长度：123n第4章信息论基础霍夫曼编码(续)■示例(续)：如果不加入虚假符号，直接进行编码，则有平均码字长度n第4章信息论基础124霍夫曼编码(续)码字长度的均匀性和方差在同样的平均码字长度的情况下，码字长度越均匀，对传输越有利。定义4.5.13码字长度的方差其中■编码的排序过程不同会极大影响码长的方差。n第4章信息论基础125霍夫曼编码(续)码字长度的均匀性和方差(续)■示例：信源的符号空间为编码输出码字集编码方式1

将局部概率和置于相同概率的最低位置n第4章信息论基础126霍夫曼编码示例：编码方式1(续)平均码长：方差：n第4章信息论基础127霍夫曼编码编码方式2将局部概率和置于相同概率的最高位置平均码长：方差：n第4章信息论基础128霍夫曼编码(续)可见■虽然平均码长一样，但编码方法2使得输出的码长更为均匀。在编码过程中，当对缩减信源概率重新排列时，应使合并得到的局部概率和，尽量使其处于较高位置；使得合并元素重复编码的次数减少，有利于降低码字长度的方差。■多个符号的霍夫曼联合编码具体操作方法与单个符号的霍夫曼编码类似，参照前面联合编码时计算概率的操作方法。n第4章信息论基础129130n4.6

信道编码的基本概念与方法信道编码的基本概念和定理编码信道的基本模型记信源符号集编码输出码字集■接收码字集信道译码输出信源符号集发送码字的先验概率■■注：在本教材中，只讨论离散无记忆信道的情形。n第8章差错控制编码131信道编码的基本概念和定理(续)记接收码字的统计特性为对于离散信道，其特性可由转移概率矩阵来表示因为有n第8章差错控制编码132信道编码的基本概念和定理(续)由先验概率率矩阵及转移概率矩阵，可导出后验概及的分布特性n第8章差错控制编码133信道编码的基本概念和定理(续)译码规则对译码性能的影响■■示例

设发送码字集接收码字集两不同的二元对称信道转移概率矩阵分别为■(1)

(2)■分析在两种信道下不同译码规则对译码性能的影响。解：若记译码的规则一般地记为n第8章差错控制编码134信道编码的基本概念和定理(续)可能的译码方法包括如下4种对于信道1：

传输正确的概率大于传输错误的概率。不同译码规则导致的出错概率依次分别为采用规则(2),出错概率最小；n第8章差错控制编码135信道编码的基本概念和定理(续)可能的译码方法包括如下4种对于信道1：对于规则（1），只要发“1”，必定出错，发“0”一定没错。因此有：对于规则（2），发“0”，收到“1”，发“1”，收到“0”时出错，因此有：其他两种情形可做类似的分析。由此可见，此时，采用规则(2),出错概率最小。n第8章差错控制编码136信道编码的基本概念和定理(续)同样的4种译码规则：对于信道2：

传输出错的概率大于传输正确的概率不同的译码规则导致的出错概率依次分别为采用规则(3),出错概率最小。■n第8章差错控制编码137信道编码的基本概念和定理(续)同样的4种译码规则：对于信道2：

，传输出错的概率大于传输正确的概率采用规则（3）时，采用与接收码元相反的状态进行译码只有在传输正确时出现译码错误：■采用规则（4）时，传输“0”时，一定出现译码错误：可见采用规则(3),出错概率最小。■n第8章差错控制编码138139信道编码的基本概念和定理(续)启示：■不同的译码规则，对误码率的影响很大；对不同的信道特性，应选择不同的译码规则。■n第8章差错控制编码信道编码的基本概念和定理(续)对于信道2：不同的译码规则导致的出错概率依次分别为采用规则(3),出错概率最小。启示：■不同的译码规则，对误码率的影响很大；对不同的信道特性，应选择不同的译码规则。■n第8章差错控制编码140信道编码的基本概念和定理(续)最大后验概率译码准则已知后验概率矩阵若译码正确译码错误误码的概率正确译码的概率n第8章差错控制编码141信道编码的基本概念和定理(续)已知后验概率矩阵，最合理的译码规则是：对每个收到的符号，取相应最可能发送的码字作为译码输出即，若规定译码规则则可使得差错概率最小最佳译码方法。具体的译码操作方法由若则取作为译码输出。n第8章差错控制编码142信道编码的基本概念和定理(续)示例：利用最大后验译码准则分析上一示例的译码问题。(1)首先确定系统的后验概率矩阵a.若转移概率矩阵为因为有可得导出后验概率矩阵n第8章差错控制编码143信道编码的基本概念和定理(续)对于前面导出的后验概率矩阵，最佳的译码规则正确译码的概率误码率n第8章差错控制编码144n第8章差错控制编码信道编码的基本概念和定理(续)b.若转移概率矩阵为同理可得■相应的后验概率矩阵■145信道编码的基本概念和定理(续)此时译码规则相应地变为正确译码的概率误码率为由本例可见：■采用后验概率译码准则，无论哪一种情形，总是可以得到最好的译码效果。n第8章差错控制编码146信道编码的基本概念和定理(续)最大似然译码准则已知概率的基本关系式对于离散无记忆信道因而在先验等概的条件下，最大后验概率译码规则可变为■即此时直接可根据转移概率矩阵进行最佳判决。注意在上例中转移概率矩阵与后验概率矩阵相同，译码结果与最大后验概率译码结果相同。n第8章差错控制编码147信道编码的基本概念和定理(续)费诺不等式■■若记

发送符号集及分布接收符号集及分布发送与接收符号集中元素相同发送符号经信道传输后出错的概率(误码率)可表示为后，关于疑义度：发送

接收到确定性称之。根据条件熵的定义，疑义度为仍然存在的平均不n第8章差错控制编码148信道编码的基本概念和定理(续)接收译码错误判决的概率■正确的判决概率与熵的定义类似，可定义：判决的不确定性■时，判决的不确定性达到最大。定理

8.4.1(费诺不等式)

与间有如下的关■系式费诺不等式表明

的大小主要由判决不确定性及判决错误导致信息的丢失的多少限定。平均每个符号判决错误导致信息的丢失小于等于

，该值为已知出现错误时，要确定正确符号所需的最大信息量。n第8章差错控制编码149信道编码的基本概念和定理(续)联合典型序列集满足下列条件的序列集分别称之分别记为的 典型序列集和联合典型序列集。和

。n第8章差错控制编码150信道编码的基本概念和定理(续)■条件下

的典型序列集定义为记为。典型序列的有关性质性质1 当

N

足够大时，有性质2 当

N

足够大时，有上述性质描述了典型序列集与熵函数及平均互信息之间的关系。(为信道编码定理的证明提供准备)n第8章差错控制编码151信道编码的基本概念和定理(续)定义8.4.3(信道)编码速率定义为:■■其中

信息位长度，

编码输出码字长度。归一化信道容量已知离散信道的容量由信息论的基本知识，有定义归一化信道容量为n第8章差错控制编码152■信道编码的基本概念和定理(续)若记发送序列为接收序列为对于离散无记忆信道：■对于N位的二元码元序列，若编码速率为■■则 可能的码字组合数合法的码字组合数合法的码字标号集■■设发送的消息编号为

；编码译码n第8章差错控制编码153信道编码的基本概念和定理(续)发送编号为

消息时出错的概率平均误码率可定义为定义8.4.4(可达编码速率)若则称

是可达的。n第8章差错控制编码154信道编码的基本概念和定理(续)定理8.4.5(信道编码定理)给定归一化信道容量■信道编码定理给出了编码速率若

，则

是可达的。可达的基本条件。中随机选择

个独立等概出现，■证明：设采用一种随机编码方法，从序列作为合法的码字，码字中每个码元有发送消息序列：接收消息序列：译码输出：若存在唯一的n第8章差错控制编码155信道编码的基本概念和定理(续)使得则取若或同时有：则认为译码错误。n

采用随机编码方法，因没有任何的倾向性，当

N

足够大时，码字中各个

元素的组合出现以大概率具有均匀性，所以译码错误的概率与发送的消息（消息的编号）无关。不妨假定发送的是编号为1

所对应的码字。定义事件n第8章差错控制编码156信道编码的基本概念和定理(续)n

则发送编号为1的码字时，译码错误的概率为n因为n由

联合典型序列的基本性质，当

N

足够大时，有n当N

足够大时，n都是可以忽略的小概率事件n因此只需考虑■时的情况。n第8章差错控制编码157为信道编码的基本概念和定理(续)当发送一个码字时，定义事件发送码字序号：接收码字

且有则有由

联合典型序列性质2，有■个，对译码输出正确的码字应与发送的合法码字一样有所有的

相加得■n第8章差错控制编码158信道编码的基本概念和定理(续)n

得到n

显然有n

综合上式及n

可得n

对于随机编码，平均错误概率就是任一特定码字的错误概率，n

因此有■n第8章差错控制编码159信道编码的基本概念和定理(续)n

将代入上式可得因此，若■则当反之，若则当■■证毕。n第8章差错控制编码160信道编码的基本概念和定理(续)定理8.4.5(信道编码定理)给定归一化信道容量■信道编码定理给出了编码速率若

，则

是可达的。可达的基本条件。在信道编码定理的证明过程中，可得当满足条件

时，信道可达性的定理包含了可通过增大码字的长度来改善信道编码误码性能的思想。但是，信道编码定理并没有告诉我们如何具体应如何编码，才能保证译码能够满足

的条件。n第8章差错控制编码161n第8章差错控制编码信道编码的基本概念和定理(续)例8.4.4设某通信系统的不加编码的错误概率为编码速率为

，分析不同编码方式的效果。(1)每两比特信息为一组进行编码可使的，相应的错误概率变为■162n第8章差错控制编码信道编码的基本概念和定理(续)例8.4.4(续)前三位中1位误码的错误可得以纠正。正确