信息论基础 (1)

1、信息论基础第一讲 信息的基本概念与预备知识一、信息的基本概念1、信息论是通信的数学理论，是运用数理统计的方法研究信息的传输、存储与处理的科学。2、物质、能量、信息是构成客观世界的三大要素，信息存在于任何事物中，有物质的地方就有信息。3、信息具有的性质（1）无形不具实体性；（2）共享交流者不会失去原有信息，还可获得新的信息，可无限传播，也可限制传播，如设密码、安全措施 ；（3）信息是一种资源永远在产生、更新、演变，取之不尽用之不竭；（4）可度量信息的数量和质量可度量。3、概率信息（香农信息或狭义信息）美国数学家香农（C.E.Shannan）提出，信息源具有随机性不定度，为了消除一定的不定度必须获

2、得与此不定度相等的信息量。（1）甲袋有100个球，50个红，50个人白，取出一个为红；（2）乙袋有100个球，25个红，25个白，25个蓝，25个黑，取出一个为红；概率大，不确定性小，信息量小，。4、消息构成消息的条件：能被通信双方理解，可在通信中进行传递和交换。消息具有不同的形式，如语言、文字、符号、数据、图片等。消息是信息的载荷者，同一消息可以含不同的信息量，同一信息可以用不同形式的消息来载荷。5、信号信号是消息的表现形式，消息是信号的具体内容。信号是消息的载体。6、信息的传输系统信源编码信道译码器信宿二、预备知识1、全概公式2、贝叶斯公式3、条件概率4、乘法公式4、不等式三、自信息的度量

3、1、自信息随机事件发生概率为，则随机事件的自信息量为 。（1）非负性（2）随机性 是随机变量（3）单调性 概率大 则 自信息量小（4）随机事件的不确定性在数量上等于它的自信息量。（5）单位以2为底，记作lb，单位比特（bit）；以e为底，记作ln，单位奈特（nat）；以10为底，记作lg，单位哈脱来（hat）。常用数值:lb3=1.585 , lbe =1.443 , lb10=3.322 , lb5= 2.322 ， lb7= 2.806 ，例1 见教材p9习题2.5一副充分洗乱了的牌（含52张牌），试问(1) 任一特定排列所给出的信息量是多少？(2) 若从中抽取13张牌，所给出的点数都不相

4、同能得到多少信息量？解：(1) 52张牌共有52！种排列方式，假设每种排列方式出现是等概率的则所给出的信息量是：(2) 52张牌共有4种花色、13种点数，抽取13张点数不同的牌的概率如下：补充1设离散无记忆信源，其发出的信息为202120130213001203210110321010021032011223210，求(1) 此消息的自信息量是多少？(2) 此消息中平均每符号携带的信息量是多少？解：(1) 此消息总共有14个0、13个1、12个2、6个3，因此此消息发出的概率是：此消息的信息量是：(2) 此消息中平均每符号携带的信息量是：2、联合自信息 3、条件自信息给定后还存在的不确定性。例

5、2 见教材p9习题2.4居住某地区的女孩子有25%是大学生，在女大学生中有75%是身高160厘米以上的，而女孩子中身高160厘米以上的占总数的一半。假如我们得知“身高160厘米以上的某女孩是大学生”的消息，问获得多少信息量？解：设随机变量X代表女孩子学历Xx1（是大学生） x2（不是大学生）P(X) 0.250.75设随机变量Y代表女孩子身高Yy1（身高>160cm） y2（身高<160cm）P(Y)0.50.5已知：在女大学生中有75%是身高160厘米以上的即：求：身高160厘米以上的某女孩是大学生的信息量即：四、互信息的度量1、先验的不确定性减去尚存在的不确定性，即消除的不确定

6、性的度量；或的出现后所提供的有关的信息量。2、性质（1）互易性 （2）独立时互信息为零（3）可正可负为正，事件的出现有助于肯定事件的出现；为负，则不利，存在信道干扰。（4） ，例3见教材p12补充2有两个二元随机变量X和Y，它们的联合概率为Y Xx1=0x2=1y1=01/83/8y2=13/81/8试求：（1）， ；（2）；（3），；（4），其中解：（1）（2）， ，（3）（4）3、条件互信息4、五、小结六、作业习题p41 2.1 ，2.2 ，2.5 ，2.8思考题：2.3 ，2.7，第二讲 平均自信息信息熵一、复习二、信息熵1、的数学期望定义为平均自信息，又称为信息熵，简称熵，表示事件出现

7、的平均不确定性，在观测之前，确定出现一个事件平均所需的信息量；或在观测之后，每出现一个事件平均给出的信息量。规定：特别地，等概时，2、举例（1）p15（2）试问四进制、八进制脉冲所含信息量是二进制脉冲的多少倍？解：四进制脉冲可以表示4个不同的消息，例如：0, 1, 2, 3八进制脉冲可以表示8个不同的消息，例如：0, 1, 2, 3, 4, 5, 6, 7二进制脉冲可以表示2个不同的消息，例如：0, 1假设每个消息的发出都是等概率的，则：四进制脉冲的平均信息量八进制脉冲的平均信息量二进制脉冲的平均信息量所以：四进制、八进制脉冲所含信息量分别是二进制脉冲信息量的2倍和3倍。（3）、从大量统计资料

8、知道，男性中红绿色盲的发病率为7%，女性发病率为0.5%，如果你问一位男士：“你是否是色盲？”他的回答可能是“是”，可能是“否”，问这两个回答中各含多少信息量，平均每个回答中含有多少信息量？如果问一位女士，则答案中含有的平均自信息量是多少？解：男士：女士：3、熵的数学特性记上凸函数：（严格上凸函数，下凸函数，严格下凸函数）（1）引理2.3.1 Jenson 不等式 p17（2）熵的数学特性性质1 对称性性质2 非负性 （离散成立，连续不一定成立）性质3 扩展性性质4 可加性性质5 极值性性质6 确定性性质7 上凸性4、条件熵定义2.3.3 称为噪声熵，是由于信道中噪声引起的。称为信道疑义度，表

9、示得到输出的条件下，输入中剩余的不确定性，即信道损失。5、联合熵 共熵例p286、各种熵的关系(1) 独立时，推广：独立时，(2) 7、例题（1）设信源，求这个信源的熵，并解释为什么H(X) > log6不满足信源熵的极值性。解：不满足极值性的原因是。（2）同时掷出两个正常的骰子，也就是各面呈现的概率都为1/6，求：(1) “3和5同时出现”这事件的自信息；(2) “两个1同时出现”这事件的自信息；(3) 两个点数的各种组合（无序）对的熵；(4) 两个点数之和（即2, 3, , 12构成的子集）的熵；(5) 两个点数中至少有一个是1的自信息量。解：(1)(2)(3)两个点数的排列如下：1

10、11213141516212223242526313233343536414243444546515253545556616263646566共有21种组合：其中11，22，33，44，55，66的概率是其他15个组合的概率是(4)参考上面的两个点数的排列，可以得出两个点数求和的概率分布如下：(5)8、加权熵P32三、小结1、2、3、4、独立时，5、四、作业 P42 2.9. 2.10 ，2.11，2.15判断题1、2、若X与Y独立，则3、若，则4、5、若X与Y独立，则6、解：1、F（X含一个可能的结果时）2、T （，按公式可算得）3、F4、T5、F6、T（增加条件可以减少不确定性）第三讲 平

11、均互信息一、复习1、 2、3、4、二、平均条件互信息 1、定义2.4.1由提供的关于集的平均条件互信息量为 。2、定理：（可直接用不等式）3、定义：平均互信息4、平均互信息的性质P345、连续随机变量的互信息6、连续随机变量的平均互信息7、性质P388、 连续随机变量的熵 三、举例1、对某城市进行交通忙闲的调查，并把天气分成晴雨两种状态，气温分成冷暖两个状态，调查结果得联合出现的相对频度如下：若把这些频度看作概率测度，求：(1) 忙闲的无条件熵；(2) 天气状态和气温状态已知时忙闲的条件熵；(3) 从天气状态和气温状态获得的关于忙闲的信息。解：(1)根据忙闲的频率，得到忙闲的概率分布如下： (

12、2) 设忙闲为随机变量X，天气状态为随机变量Y，气温状态为随机变量Z 求：(3) 2、有两个二元随机变量X和Y，它们的联合概率为Y Xx1=0x2=1y1=01/83/8y2=13/81/8并定义另一随机变量Z = XY（一般乘积），试计算：(1) H(X), H(Y), H(Z), H(XZ), H(YZ)和H(XYZ)；(2) H(X/Y), H(Y/X), H(X/Z), H(Z/X), H(Y/Z), H(Z/Y), H(X/YZ), H(Y/XZ)和H(Z/XY)；(3) I(X;Y), I(X;Z), I(Y;Z), I(X;Y/Z), I(Y;Z/X)和I(X;Z/Y)。解：(1

13、)Z = XY的概率分布如下：(2)(3)四、小结1、2、3、4、5、五、作业: 复习第二章 小测验1一、填空1、（ ）， （ ）， （ ） 2、（ ）， （ ），（ ） 3、( ) , （ ），（ ） 4、( ) = ( ) 5、（ ），（ ）= （ ）= （ ）=（ ）二、判断题1、 （ ）2、 （ ） 3、 （ ） 4、 （ ） 三、计算题1、同时掷出两个骰子，求：(1) “3和5同时出现”这事件的自信息；（2）两个点数中至少有一个是1的自信息量 (3) 两个点数之和的熵；2、给定X、Y的联合概率分布， XY0 1 0 1 0求：（1） ， , ； （2） ， ；（3） 四、证明 ：第四

14、讲 第三章 离散信源一、离散无记忆信源1、定义1 （基本离散信源） 设信源 输出符号 这些符号彼此互不相关，则称为离散无记忆信源。2、定义2 自信息 3、定义3 信源熵4、举例p49二、离散无记忆信源的扩展信源1、二进制信源的扩展（1）基本信源 (2)二次扩展 ,，（3）三次扩展 ,，2、离散无记忆信源的N次扩展信源3、定理 4、举例（1）p53（2）每帧电视图像可以认为是由3X105个像素组成的，所有像素均是独立变化，且每像素又取128个不同的亮度电平，并设亮度电平是等概出现，问每帧图像含有多少信息量？若有一个广播员，在约10000个汉字中选出1000个汉字来口述此电视图像，试问广播员描述此

15、图像所广播的信息量是多少（假设汉字字汇是等概率分布，并彼此无依赖）？若要恰当的描述此图像，广播员在口述中至少需要多少汉字？解：1) 128个不同的亮度电平等概出现2) 10000个汉字等概率分布3) 广播员描述此图像至少需要多少汉字三、离散平稳信源1、定义（P55） 概率与时间起点无关。一维平稳信源：二维平稳信源：2、平稳信源的熵P553、极限熵（1）记 由P26有证明：类似地（2）定义（平均符号熵）(3)极限熵注：(4)定理：对任意离散平稳信源，若，则证明：由平稳性所以由 ：可得而 又所以（5）举例设有一个信源，它产生0，1序列的信息。它在任意时间而且不论以前发生过什么符号，均按P(0) =

16、 0.4，P(1) = 0.6的概率发出符号。(1) 试问这个信源是否是平稳的？(2) 试计算, H(X3/X1X2)及H；(3) 试计算并写出信源中可能有的所有符号。解：(1) 试问这个信源是否是平稳的？这个信源是平稳无记忆信源。因为有这些词语：“它在任意时间而且不论以前发生过什么符号”(2) 试计算, H(X3/X1X2)及H；(3) 试计算并写出信源中可能有的所有符号。四、小结1、离散无记忆信源：信源 输出符号 这些符号彼此互不相关。2、自信息 信源熵3、离散平稳信源概率与时间起点无关。4、平均符号熵5、极限熵五、作业3.1 3.2 3.3 3.4 小测验21、如果你在不知道今天是星期几

17、的情况下问你的朋友“明天是星期几”？则答案中含有的信息量为（ ）；如果你在知道今天是星期四的情况下提出同样的问题，则答案中含有的信息量为（ ）。2、有一非均匀的骰子，其任一面出现的概率与该面上的点数成正比，则信息熵为（ ）。3、一信源有6种输出状态，概率分别为， ，设信源先后发出的符号相互独立，试求：（1） ；（2）消息ABABBA 所含的信息量 和FDDFDF所含的信息量；（3） 。4、已知二维随机变量X、Y的概率分布为 ， ，求：（1） ；（2） 。5、证明：第五讲 马尔可夫信源一、有限状态马尔可夫链1、定义1（马尔可夫链）设为一随机序列，时间参数集，其状态空间,若对所有，有=则称为马尔可

18、夫链。注：时间离散、状态离散，未来只与现在有关，而与过去无关。2、状态转移概率记当时，称为一步转移概率， 记为当时，称为步转移概率，记为3、状态转移图与状态转移矩阵例1已知状态空间，其中,条件概率（1）画状态转移图；（2）写出状态转移矩阵。解：（1）略；（2） 例2已知状态空间，其中,条件概率（1）画状态转移图；（2）写出状态转移矩阵；（3）写出符号序列01001110001对应的状态序列。解：（1）略；（2） （3）4、定义2（时齐马氏链）马氏链中，即状态转移概率与无关，则称这类马氏链为时齐马氏链。注：对时齐马氏链有切普曼柯尔莫哥洛夫方程若初始状态分布为 ，则例：假设人的健康状况分为健康和疾

19、病两种状态，今年健康、明年保持健康的概率为0.8,今年患病、明年转为健康的概率为0.7，研究若干年后处于两种状态的概率。记第年，表示健康，表示疾病，表示第年处于状态的概率 。5、定义3（遍历性）若时齐马氏链对一切存在不依赖于的极限 ，且 ，则称其具有遍历性，称为平稳分布，其中为初始分布。注：若存在正整数，使所有元素均大于0，则该马氏链是遍历的。6、设稳态分布为，则有例 设有一马氏链，状态转移矩阵 （1）是否具有遍历性？（2）求稳态分布。二、马尔可夫信源设信源的状态空间 ，信源输出符号集 当信源发出一个符号后，所处状态将发生变化。1、（一阶马尔可夫信源）若信源输出的符号序列为 和状态序列 满足下

20、列条件，则称此信源为一阶马尔可夫信源，（1）某一时刻信源符号的输出只与当时的信源状态有关，与之前的状态无关；（2）信源状态只由当前输出符号和前一时刻信源状态唯一确定。状态之间的一步转移概率为 。2、遍历的阶马尔可夫信源的信息熵3、举例（1）设有一个二进制二阶马尔可夫信源，信源符号集为，条件概率为 求信息熵 。解：状态转移矩阵为 符号转移矩阵 .（2）一个马尔可夫过程的基本符号为0，1，2，这三个符号等概率出现，并且具有相同的转移概率，（1）画出一阶马尔可夫过程的状态图，并求稳定状态下的一阶马尔可夫信源熵和信源剩余度；（2）求稳定状态下的二阶马尔可夫信源熵和信源剩余度。解：（1）（2）设类似有（

21、3）p54（配套习题集）设马尔可夫信源的状态集合,符号集，如图所示，求：（1）状态极限概率（稳态分布）和符号极限概率；（2）各状态下输出符号的条件熵；(3) 极限熵。解：（1）状态转移矩阵 状态极限概率（稳态分布） 符号转移矩阵 符号极限概率（2）(3) （三、信源的相关性和剩余度对离散平稳信源相关性：剩余度（冗余度）：熵的相对率：信源输出符号间的依赖关系越大、相关长度越长，则信源的实际熵小，剩余度大。四、小结1、稳态分布 2、遍历的阶马尔可夫信源的信息熵3、剩余度 作业：3.11 , 3.12 ,3.13 ,3.15补充例题1、 一阶马尔可夫信源的状态图如下图所示。信源X的符号集为0, 1,

22、 2。(1) 求平稳后信源的概率分布；(2) 求信源的熵H 。解：(1) (2)2、黑白气象传真图的消息只有黑色和白色两种，即信源X=黑，白。设黑色出现的概率为P(黑) = 0.3，白色出现的概率为P(白) = 0.7。(1) 假设图上黑白消息出现前后没有关联，求熵H(X)；(2) 假设消息前后有关联，其依赖关系为P(白/白) = 0.9，P(黑/白) = 0.1，P(白/黑) = 0.2，P(黑/黑) = 0.8，求此一阶马尔可夫信源的熵H2(X);(3) 分别求上述两种信源的剩余度，比较H(X)和H2(X)的大小，并说明其物理含义。解：(1)(2) (3)H(X) > H2(X)表示

23、的物理含义是：无记忆信源的不确定度大与有记忆信源的不确定度，有记忆信源的结构化信息较多，能够进行较大程度的压缩。测验3一、填空1、离散无记忆信源X的N次扩展信源的熵（ ）。2、信源输出长为N的符号序列，则平均符号熵（ ）。3、信源输出长为N的符号序列，则极限熵（ ）。4、m阶遍历的马尔可夫信源的极限熵（ ）。5、信源的剩余度R=（ ）。二、计算一阶马尔可夫信源的信源符号集为，状态转移矩阵 ， （1）画状态转移图，求平稳后的信源概率分布；（2）求信源熵 ；（3）求信源剩余度。第六讲 CH4 离散信道及其容量信道是信息传播的通道，它将输入事件x变换成输出事件y，由于干扰的存在，一个输入事件总是以一

24、定的概率变换成各种可能的输出事件。一、信道类型1、按输入和输出空间离散或连续分类离散信道（数字信道，输入与输出空间均离散）、连续信道（模拟信道）、半连续信道2、按输入和输出时间离散或连续分类时间离散的连续信道、波形信道3、按输入和输出端的个数分类两端信道（两用户信道）、多端信道（多用户信道、网络信道，如多元接入信道和多元输出信道）4、按信道统计特性分类恒参信道（信道统计特性不随时间变化）、随参信道5、按信道的记忆特性分类无记忆信道、有记忆信道6、特殊信道无损信道（1对多）、确定信道（多对1）、无噪信道（无扰信道，既是无损又是确定，1对1）、无用信道二、离散无记忆信道设离散信道的输入空间：输入序

25、列：输出空间：输出序列:传递概率： 1、定义（离散无记忆信道DMC）在任何时刻信道的输出只与此时的信道输入有关，与以前的输入无关，即则称之为离散无记忆信道。当时（即不随时间变化），称之为平稳信道或恒参信道。2、单符号离散信道输入：输出：传递概率：信道矩阵：3、几个概率先验概率：联合概率：前向概率（信道传递概率）：后向概率（后验概率）：输出符号概率：矩阵表示 ，4、举例（P79）（1）二元对称信道（BSC）（2）二元删除信道（3）二元对称消失信道5、信道疑义度（损失熵）含义：由于信道干扰，输出端收到Y后对输入X尚存在的平均不确定性。例P81 二元删除信道,输入分布信道矩阵 求：解：可由输出分布三

26、、平均互信息1、定义：含义：接受到Y后，平均每个符号获得的关于输入X的信息量。互易性、非负性例：已知信源X分布 ，信宿收到的消息集Y包含，信道矩阵求 .提示：2、定理1对于固定的信道，是信源分布的上凸函数。3、定理2对于固定的信源分布，是信道传递概率的下凸函数。（证明略）4、例P85，P875、相互关系P88作业P121 4.1 ,4.5 ,4.19第七讲 离散无记忆扩展信道复习1：例：已知信源X分布 ，信宿收到的消息集Y包含，信道矩阵求 .解：X,Y联合分布提示：2、p70 3.12解：（1）初始分布状态转移矩阵的分布的联合分布或的联合分布由马氏链平均符号熵(2)极限平均符号熵(3)一、离散

27、无记忆扩展信道1、设信道输入随机变量取值于符号集，信道输出随机变量取值于取值于符号集，信道矩阵为 ，其中 。2、N次扩展输入随机向量 , 其可能取值有个，输出随机向量,其可能取值有个，信道无记忆时，例1 二元无记忆对称信道的扩展信道输入符号集，输出符号集 ，信道矩阵 二次扩展：， ，二次扩展的信道矩阵为 （见p92）3、定理1 对一般无记忆信道，输入随机向量，输出随机向量，当信源无记忆时，等号成立 。其中注：信道无记忆时 信源无记忆时，信道无记忆且信源无记忆时， ，见p94 证明：（1） 当信道无记忆时，当信源也无记忆时，等号成立 。4、定理2 对一般无记忆信源，输入随机向量，输出随机向量，

28、， 当信道无记忆时，等号成立 。证明：（1）当信源无记忆时，类似有（2）当信道也无记忆时，等号成立 。5、对N次无记忆扩展信道，当信源无记忆时，二、信道的组合1、级联信道（串联信道）信道I的输入为随机变量X，取值符号集，输出随机变量Y，取值符号集，信道I传递概率，信道矩阵；信道II的输入为随机变量Y，输出随机变量Z，取值符号集，信道II传递概率为 ，信道矩阵 ，若X，Y，Z构成马氏链，则总的信道矩阵 .注：信道II传递概率一般与前面的符号x和y均有关。例1 信道I和信道II图P103 ，等效信道p103例2 p1012、定理4.4.1 串联信道中，（1） ,等号成立的充要条件是： ； （2）等

29、号成立的充要条件是： 。证明：（1） 等号成立的充要条件是： 。注：此时意味着X,Y, Z构成一个一阶马尔可夫链。(2) 等号成立的充要条件是： 。3、定理4.4.2随机变量X,Y, Z构成一个马尔可夫链，则有： （1） （2） 证明：（1）由定理4.4.1 当时，而所以 。等号成立的条件是：，此时有 ；（2）Z , Y , X 也构成马尔可夫链，即有，将定理4.4.1中X与Z互换，类似可证。表明，任何信息传输系统中，最后获得的信息至多是信源所提供的信息，称之为信息不增性原理。三、小结（1）无记忆信道，当信源也无记忆时，等号成立 。（2） 无记忆信源，当信道也无记忆时，等号成立 。（3）对N次

30、无记忆扩展信道，当信源无记忆时，（4） X,Y, Z构成一个马尔可夫链，则有： （1） 等号成立的条件是：（2） 等号成立的条件是： 四、信道容量信道容量是信道传输信息量的最大能力的度量。1、定义1 信道容量 2、信息传输率就是平均互信息，即3、信息传输速率是单位时间平均传输的信息量，4、单位时间平均传输的最大信息量五、特殊信道的信道容量1、无损信道等概输入2、确定信道等概输出3、无噪信道（无损确定信道）六、对称信道的信道容量1、离散无记忆信道中，每行都是其他行元素的不同排列，则称此信道为输入对称信道。如 2、离散无记忆信道中，每列都是其他列元素的不同排列，则称此信道为输出对称信道。如 3、准

31、对称信道4、对称信道 , 5、定理4.5.1 实现离散准对称无记忆信道信道容量的输入分布为等概分布。6、定理4.5.2若一个离散对称信道具有r个输入符号，s个输出符号，则当输入为等概分布时，达到信道容量C，且 。引理：对于对称信道，只有当信道输入分布为等概分布时，输出分布才能为等概分布。例 7、定义（强对称信道，均匀信道）主对角线上是正确传输概率，错误传输概率相等，输入、输出符号数相等，列和也为1 。作业 P4.31,4.36第八讲 一般离散信道复习：1、定义1 信道容量 2、信息传输率就是平均互信息，即3、定理4.5.1 实现离散准对称无记忆信道信道容量的输入分布为等概分布。4、定理4.5.

32、2若一个离散对称信道具有r个输入符号，s个输出符号，则当输入为等概分布时，达到信道容量C，且 。5、引理：对于对称信道，只有当信道输入分布为等概分布时，输出分布才能为等概分布。一般离散信道的容量一、信道容量定义为在信道固定的条件下，寻找使平均互信息达到极大值的输入概率分布。而是输入分布的上凸函数，即是r个变量的多元函数，且有 ，故可用拉格朗日乘子法求条件极值。1、令 解方程组 2、定理4.5.3 对一般离散信道，当且仅当存在常数C使输入分布满足：（1） (对一切)(2) (对一切)时，达到极大，此时常数C即为所求的信道容量。其中为平均条件互信息。（见P33）（3）准对称离散无记忆信道，输入分布

33、等概时，信道容量 .或输入等概时或输入等概时例（1）解一：（2）解二：同上（3）解三：=同上3、离散无记忆N次扩展信道4、独立并联信道（略）5、信源和信道的匹配信道容量是一定的，只有当输入分布满足一定条件时，才能达到信道容量，一般情况下，信息传输率并未达到最大，当信息传输率达到信道容量时，称此信源与信道达到匹配，否则认为信道有剩余，信道剩余度=,相对剩余度=二、举例P1221、（19题）设电阻值为X，电阻功率为Y， ，通过测量电阻值可以得到关于瓦数的平均信息量即平均互信息，或2、（21题）每组4个等概发出，概率为，每个含信息量，1秒=1000ms , 其中含信息量，平均信息传输速率 bit/秒

34、 。3、（23题）4个字母等概出现，每个字母占，每秒发出个字母，（1）平均信息传输速率 bit/秒 ;（2） bit/秒 。4、（24题），每个字母占，每秒发出个字母，（1）平均信息传输速率 bit/秒 ;（2） bit/秒 。5、（25题） ,对称信道，6、（27题） 一般信道信道容量的计算 ，设 其中 练习 已知信道矩阵 求 ：信道容量C 及达到信道容量信源的最佳分布; 作业P123 20 , 26 ，28、 第五章 无失真信源编码一、基本概念1、使信源产生的全部信息无损地传送给信宿，这时的信源编码称为无失真信源编码。（1）信源符号集 码符号集 码符号（码元）代码组 C为码字的集合，称为码

35、长。信源符号与码字是一一对应。要实现无失真信源编码，信源符号与码字必须是一一对应、可逆的。2、例1 二元信道的信源编码，信源 码符号集 码 定长码、非奇异码（长度相同、码字都不同）码 变长码、非奇异码码变长码、奇异码码 变长码、奇异码3、N次扩展码信源码二、分组码1、定义：将信源符号集中的每个符号映射成一个固定的码字，这样的码称为分组码。2、分组码性质（1）、奇异性分组码非奇异是正确译码的必要条件。非奇异码当码字排在一起时可能出现奇异性。P129（2）、唯一可译性定义：信源符号映射为一个固定的码字，则信源N次扩展符号映射为N次扩展码的分组码称为原分组码的N次扩展。定义：一个分组码若对于任意有限

36、的整数N，其N次扩展码均为非奇异的，则称之为唯一可译码。（3）定义：无须考虑后续的码符号即可从码符号序列中译出码字，这样的唯一可译码称为即时码。即时码（瞬时码、逗点码、非延长码）：接受到一个完整码字后立即可以译码。P129（4）定义：设为一个码字，称前j个元素为码字的前缀。命题：一个唯一可译码称为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。证明见P130（5）r进制树图 树码树根：树图最顶部的节点，树枝：节点引出的线段，节点：树枝的尽头。n级节点有个，即可有个码字。整树，非整树 r=2 的树图见P130三、定长码1、若信源有q个符号，码符号集有r个码元，码长，则存在唯一可译码需 。

37、若对N次扩展信源进行定长编码，唯一可译需 。N=1时，当r=2（二元码），N=1，如：英文电报32个符号，采用二元符号编定长码，至少 要用5位二元符号进行编码才可能得到唯一可译码。 第九讲 无失真信源编码（续）复习1、 信源符号集 码符号集 码符号（码元）代码组 C为码字的集合，称为码长。2、N次扩展码信源符号及2次扩展信源符号码字及2次扩展码字3、几个概念（1）定义：一个分组码若对于任意有限的整数N，其N次扩展码均为非奇异的，则称之为唯一可译码。（2）定义：无须考虑后续的码符号即可从码符号序列中译出码字，这样的唯一可译码称为即时码。注：即时码必为唯一可译码，反之不一定。（3）定义：设为一个码

38、字，称前j个元素为码字的前缀。（4）命题：一个唯一可译码称为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。4、定长码若信源有q个符号，码符号集有r个码元，码长，则存在唯一可译码需 。若对N次扩展信源进行定长编码，唯一可译需 。新授内容1、定理：离散无记忆信源 ，信源熵为H(S)，N次扩展信源现用码符号集 对N次扩展信源进行长度为的定长编码，对，只要 ，则当N足够大时，必可使译码差错小于；若 ，则当N足够大时，译码错误概率趋于1 。证明：信源符号的自信息信源熵 信源符号自信息的方差 N次扩展信源符号的自信息N次扩展信源熵扩展信源符号自信息的方差 由车贝晓夫不等式，对任意表明，N充分大时

39、，事件几乎不可能发生，故可将N次扩展信源分为两部分：由 只对经常出现的信源序列进行编码，将不经常出现的信源序列抛弃，故所需码字总数减少。设集合中含个，最小概率为，最大概率为，则由总码字 ,只要 即 ， 。将不经常出现的信源序列抛弃，不对编码，当这样的信源序列出现时，可能会造成译码错误，错误概率 若要求译码错误小于则当 时，有 N充分大时， 若码长满足 即总码字 即中将有些信源序列不能用不同的的码字来对应，此时，正确译码的概率错误译码的概率此时中将有些信源序列未编码，译码时肯定会出错。结论：总码字 或 ，则当N足够大时，必可使译码差错小于；总码字 或 ，则当N足够大时，译码错误概率趋于1 。定理

40、证毕。2、设有离散无记忆信源，熵H(S)，若对信源的长为N的符号序列进行定长编码，码字是从r个码符号集中选取 个码元构成，对任意，只要，即 ，则当N足够大时，译码错误概率可任意小，即几乎可以实现无失真编码。若满足 ，则不可能实现无失真编码，当N足够大时，译码错误概率近似为1 。注：定理结论也适合平稳有记忆信源，此时H(S)用极限熵 代替。3、定义（编码速率） 设熵为H(S)的离散无记忆信源，若对信源的长为N的符号序列进行定长编码，码字是从r个码符号集中选取 个码元构成，则 称为编码速率。由定理：才可能实现无失真传输，即编码速率才可能实现无失真传输。4、定义（编码效率）称为编码效率。一般地， 对

41、定长码，最佳编码效率为 又译码错误概率 要 只要 已知 例 1 P139 例2 P139二、变长码1、奇异码与非奇异码-码字有无相同唯一可译码与非唯一可译码-N次扩展是否非奇异即时码与非即时码-收到一个完整码字能否译码见表5.7 P140 2、信源编码的三种主要方法匹配编码 -对信源符号编码，概率大码短变换编码-对变化后的信源符号编码识别编码-对文字、数据等编码三、两个不等式1、定理（克拉夫特不等式）设信源符号集 码符号集 码字集 其对应的码长分别为 ，则即时码存在的充要条件是 。2、定理（麦克米伦不等式）设信源符号集 码符号集 码字集 其对应的码长分别为 ，则唯一可译码存在的充要条件是 。注

42、：满足不等式必可构造出即时码（唯一可译码），不满足则不能构造出。但满足不等式的码的不一定是即时码（唯一可译码），即上述定理不能作为判别即时码（唯一可译码）的依据。（证明略）3、唯一可译码判别准则（1）构造后缀集合设 为原始码字的集合，若码字是码字的前缀，即，则将后缀A列为后缀集合的元素。中元素是：的码字是中码字前缀、的码字是中码字前缀的所有后缀的集合，中元素是：的码字是中码字前缀、的码字是中码字前缀的后缀的集合，等等。（2）命题 一种码是唯一可译码的充要条件是后缀集合中没有一个含有中的码字。（3）例题P146四、变长码编码定理1、变长码的平均长度定义：设有信源 ，码符号集 编码后的码字分别为

43、其对应的码长分别为 ，则码的平均长度为 。注：平均长度 表示每个信源符号编码平均需要用的码符号个数。2、变长码的信息传输率 平均每个码元载荷的信息量就是编码后信道的信息传输率，即 （bit/码符号） .3、定义（最佳码）对给定的信源和码符号集，若有一种唯一可译码，其平均长度小于所有其他的唯一可译码，则称这种码为紧致码或最佳码。4、定理 对于熵为H(S)的离散无记忆信源若用具有r个符号的码符号集进行编码，则一定存在一种编码方式构成唯一可译码，其平均码长满足 。注：（1）平均码长小于下界唯一可译码不存在；（2）平均码长大于上界不是最佳码；（3）平均码长达到下界时成为最佳码，此时 ，。证明：证明下界

44、：由麦克米伦不等式：唯一可译码存在的充要条件是 。若存在唯一可译码。（其中用到詹森不等式）等号成立的充要条件是，即，此时 。证明上界：令 若是整数，取若不是整数，取满足 ，故只要取 由两边求和：由麦克米伦不等式知，这样构造的变长码是唯一可译码。由 两边取数学期望得故有 所以如此选择的码小于上界且是唯一可译的。5、变长无失真信源编码定理（香农第一定理）对于熵为H(S)离散无记忆信源它的N次扩展信源为现用码符号集 对N次扩展信源进行编码，总可以构成唯一可译码，使信源S中的每个符号所需的码字平均长度满足 ，且 。其中 是N次扩展信源中每个符号所对应的平均码长， ，是所对应的码字长度。表示原始信源S中

45、每个信源符号所对应的平均码长。证明见P1506、变长码的编码速率 。表示编码后平均每个符号能载荷的最大信息量。（P138 定长码编码速率 ）7、变长码的编码效率其中 （P138 定长码编码效率 ）8、举例例1（P152）第十讲 变长码的编码方法一、香农编码方法1、按发出符号的概率大小递减排列；2、计算自信息，确定码长；3、累加概率并化为二进制数；4、根据码长确定编码。P154例二、霍夫曼码1、按发出符号的概率大小递减排列；2、概率最小的两个标注0和1，并将两概率相加；3、对缩减信源按概率大小递减排列，概率最小的两个标注0和1，并将两概率相加；4、直至两个符号标注0和1，向前返回可得编码。注：两

46、概率相加在缩减信源中尽量向前排，这样方差小，码的质量高。P154三、费诺码1、按发出符号的概率大小递减排列；2、分两组，使两组概率近于相同，各组标0和1；3、各组再分两组，方法同上，直至最后，两小组各只剩一个符号。P160四、举例P162（第2题）（1）等概时，自信息为2，故码长为2，按霍夫曼码可编为晴00，云01，雨10，雾11，=2；（2）不等概时，自信息：晴2，云3，雨3，雾1，所需码长晴2，云3，雨3，雾1，按霍夫曼码可编为晴01，云000，雨001，雾1；=1.75 .作业P162 3 , 4 , 9 , 10CH6 有噪信道编码一、信道编码与译码规则1、有噪信道编码就是按一定的规则

47、给信源编的码字（信息序列）增加一些多余的码元，使之变为具有某种规律的码序列，这些多余的码元与原信息序列的码元是相关的，在接受端可根据这种相关性来检测和纠正传输过程中产生的差错。2、译码规则除噪声干扰产生错误外，译码规则不同也是产生错误的原因。例P167（1）定义设信道输入符号集为，输出符号集为，若对每一个输出符号都有一个确定的函数，使对应于唯一的一个输入符号，则称这样的函数为译码规则，记为。注：译码规则共有种。如：有一信道，信道矩阵为设计译码规则A为，也可设计译码规则B为，共可设计27种译码规则。3、错误概率在确定译码规则为后，收到就译成 ，如果发出的就是，就是正确译码；若发出的不是，那么就是错误译码。条件正确概率为 条件错误概率为经过译码后的平均错误概率4、译码规则总的原则是平均错误概率最小，与译码规则无关，故要 最小，即最大。定义：选择译码函数，使之满足，则称为最大后验概率准则（理想观测者准则、最小错误概率准则）。含义：对于每一个输出符号 ，都译成具有最大后验概率的那个输入符号，这样译码错误概率会最小。当输入符号为等概分布时，