信息论基础.doc

信息论基础第一讲 信息的基本概念与预备知识一、信息的基本概念1、信息论是通信的数学理论，是运用数理统计的方法研究信息的传输、存储与处理的科学。2、物质、能量、信息是构成客观世界的三大要素，信息存在于任何事物中，有物质的地方就有信息。3、信息具有的性质（1）无形不具实体性；（2）共享交流者不会失去原有信息，还可获得新的信息，可无限传播，也可限制传播，如设密码、安全措施 ；（3）信息是一种资源永远在产生、更新、演变，取之不尽用之不竭；（4）可度量信息的数量和质量可度量。3、概率信息（香农信息或狭义信息）美国数学家香农（C.E.Shannan）提出，信息源具有随机性不定度，为了消除一定的不定度必须获得与此不定度相等的信息量。（1）甲袋有100个球，50个红，50个人白，取出一个为红；（2）乙袋有100个球，25个红，25个白，25个蓝，25个黑，取出一个为红；概率大，不确定性小，信息量小，。4、消息构成消息的条件：能被通信双方理解，可在通信中进行传递和交换。消息具有不同的形式，如语言、文字、符号、数据、图片等。消息是信息的载荷者，同一消息可以含不同的信息量，同一信息可以用不同形式的消息来载荷。5、信号信号是消息的表现形式，消息是信号的具体内容。信号是消息的载体。6、信息的传输系统信源编码信道译码器信宿二、预备知识1、全概公式2、贝叶斯公式3、条件概率4、乘法公式4、不等式三、自信息的度量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张牌，所给出的点数都不相同能得到多少信息量？解：(1) 52张牌共有52！种排列方式，假设每种排列方式出现是等概率的则所给出的信息量是：(2) 52张牌共有4种花色、13种点数，抽取13张点数不同的牌的概率如下：补充1设离散无记忆信源，其发出的信息为202120130213001203210110321010021032011223210，求(1) 此消息的自信息量是多少？(2) 此消息中平均每符号携带的信息量是多少？解：(1) 此消息总共有14个0、13个1、12个2、6个3，因此此消息发出的概率是：此消息的信息量是：(2) 此消息中平均每符号携带的信息量是：2、联合自信息 3、条件自信息给定后还存在的不确定性。例2 见教材p9习题2.4居住某地区的女孩子有25%是大学生，在女大学生中有75%是身高160厘米以上的，而女孩子中身高160厘米以上的占总数的一半。假如我们得知“身高160厘米以上的某女孩是大学生”的消息，问获得多少信息量？解：设随机变量X代表女孩子学历Xx1（是大学生） x2（不是大学生）P(X) 0.250.75设随机变量Y代表女孩子身高Yy1（身高160cm） y2（身高 log6不满足信源熵的极值性。解：不满足极值性的原因是。（2）同时掷出两个正常的骰子，也就是各面呈现的概率都为1/6，求：(1) “3和5同时出现”这事件的自信息；(2) “两个1同时出现”这事件的自信息；(3) 两个点数的各种组合（无序）对的熵；(4) 两个点数之和（即2, 3, , 12构成的子集）的熵；(5) 两个点数中至少有一个是1的自信息量。解：(1)(2)(3)两个点数的排列如下：111213141516212223242526313233343536414243444546515253545556616263646566共有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（增加条件可以减少不确定性）第三讲 平均互信息一、复习1、 2、3、4、二、平均条件互信息 1、定义2.4.1由提供的关于集的平均条件互信息量为 。2、定理：（可直接用不等式）3、定义：平均互信息4、平均互信息的性质P345、连续随机变量的互信息6、连续随机变量的平均互信息7、性质P388、 连续随机变量的熵 三、举例1、对某城市进行交通忙闲的调查，并把天气分成晴雨两种状态，气温分成冷暖两个状态，调查结果得联合出现的相对频度如下：若把这些频度看作概率测度，求：(1) 忙闲的无条件熵；(2) 天气状态和气温状态已知时忙闲的条件熵；(3) 从天气状态和气温状态获得的关于忙闲的信息。解：(1)根据忙闲的频率，得到忙闲的概率分布如下： (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)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） 四、证明 ：第四讲 第三章 离散信源一、离散无记忆信源1、定义1 （基本离散信源） 设信源 输出符号 这些符号彼此互不相关，则称为离散无记忆信源。2、定义2 自信息 3、定义3 信源熵4、举例p49二、离散无记忆信源的扩展信源1、二进制信源的扩展（1）基本信源 (2)二次扩展 ,，（3）三次扩展 ,，2、离散无记忆信源的N次扩展信源3、定理 4、举例（1）p53（2）每帧电视图像可以认为是由3105个像素组成的，所有像素均是独立变化，且每像素又取128个不同的亮度电平，并设亮度电平是等概出现，问每帧图像含有多少信息量？若有一个广播员，在约10000个汉字中选出1000个汉字来口述此电视图像，试问广播员描述此图像所广播的信息量是多少（假设汉字字汇是等概率分布，并彼此无依赖）？若要恰当的描述此图像，广播员在口述中至少需要多少汉字？解：1) 128个不同的亮度电平等概出现2) 10000个汉字等概率分布3) 广播员描述此图像至少需要多少汉字三、离散平稳信源1、定义（P55） 概率与时间起点无关。一维平稳信源：二维平稳信源：2、平稳信源的熵P553、极限熵（1）记 由P26有证明：类似地（2）定义（平均符号熵）(3)极限熵注：(4)定理：对任意离散平稳信源，若，则证明：由平稳性所以由 ：可得而 又所以（5）举例设有一个信源，它产生0，1序列的信息。它在任意时间而且不论以前发生过什么符号，均按P(0) = 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、如果你在不知道今天是星期几的情况下问你的朋友“明天是星期几”？则答案中含有的信息量为（ ）；如果你在知道今天是星期四的情况下提出同样的问题，则答案中含有的信息量为（ ）。2、有一非均匀的骰子，其任一面出现的概率与该面上的点数成正比，则信息熵为（ ）。3、一信源有6种输出状态，概率分别为， ，设信源先后发出的符号相互独立，试求：（1） ；（2）消息ABABBA 所含的信息量 和FDDFDF所含的信息量；（3） 。4、已知二维随机变量X、Y的概率分布为 ， ，求：（1） ；（2） 。5、证明：第五讲 马尔可夫信源一、有限状态马尔可夫链1、定义1（马尔可夫链）设为一随机序列，时间参数集，其状态空间,若对所有，有=则称为马尔可夫链。注：时间离散、状态离散，未来只与现在有关，而与过去无关。2、状态转移概率记当时，称为一步转移概率， 记为当时，称为步转移概率，记为3、状态转移图与状态转移矩阵例1已知状态空间，其中,条件概率（1）画状态转移图；（2）写出状态转移矩阵。解：（1）略；（2） 例2已知状态空间，其中,条件概率（1）画状态转移图；（2）写出状态转移矩阵；（3）写出符号序列01001110001对应的状态序列。解：（1）略；（2） （3）4、定义2（时齐马氏链）马氏链中，即状态转移概率与无关，则称这类马氏链为时齐马氏链。注：对时齐马氏链有切普曼柯尔莫哥洛夫方程若初始状态分布为 ，则例：假设人的健康状况分为健康和疾病两种状态，今年健康、明年保持健康的概率为0.8,今年患病、明年转为健康的概率为0.7，研究若干年后处于两种状态的概率。记第年，表示健康，表示疾病，表示第年处于状态的概率 。5、定义3（遍历性）若时齐马氏链对一切存在不依赖于的极限 ，且 ，则称其具有遍历性，称为平稳分布，其中为初始分布。注：若存在正整数，使所有元素均大于0，则该马氏链是遍历的。6、设稳态分布为，则有例 设有一马氏链，状态转移矩阵 （1）是否具有遍历性？（2）求稳态分布。二、马尔可夫信源设信源的状态空间 ，信源输出符号集 当信源发出一个符号后，所处状态将发生变化。1、（一阶马尔可夫信源）若信源输出的符号序列为 和状态序列 满足下列条件，则称此信源为一阶马尔可夫信源，（1）某一时刻信源符号的输出只与当时的信源状态有关，与之前的状态无关；（2）信源状态只由当前输出符号和前一时刻信源状态唯一确定。状态之间的一步转移概率为 。2、遍历的阶马尔可夫信源的信息熵3、举例（1）设有一个二进制二阶马尔可夫信源，信源符号集为，条件概率为 求信息熵 。解：状态转移矩阵为 符号转移矩阵 .（2）一个马尔可夫过程的基本符号为0，1，2，这三个符号等概率出现，并且具有相同的转移概率，（1）画出一阶马尔可夫过程的状态图，并求稳定状态下的一阶马尔可夫信源熵和信源剩余度；（2）求稳定状态下的二阶马尔可夫信源熵和信源剩余度。解：（1）（2）设类似有（3）p54（配套习题集）设马尔可夫信源的状态集合,符号集，如图所示，求：（1）状态极限概率（稳态分布）和符号极限概率；（2）各状态下输出符号的条件熵；(3) 极限熵。解：（1）状态转移矩阵 状态极限概率（稳态分布） 符号转移矩阵 符号极限概率（2）(3) （三、信源的相关性和剩余度对离散平稳信源相关性：剩余度（冗余度）：熵的相对率：信源输出符号间的依赖关系越大、相关长度越长，则信源的实际熵小，剩余度大。四、小结1、稳态分布 2、遍历的阶马尔可夫信源的信息熵3、剩余度 作业：3.11 , 3.12 ,3.13 ,3.15补充例题1、 一阶马尔可夫信源的状态图如下图所示。信源X的符号集为0, 1, 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)表示的物理含义是：无记忆信源的不确定度大与有记忆信源的不确定度，有记忆信源的结构化信息较多，能够进行较大程度的压缩。测验3一、填空1、离散无记忆信源X的N次扩展信源的熵（ ）。2、信源输出长为N的符号序列，则平均符号熵（ ）。3、信源输出长为N的符号序列，则极限熵（ ）。4、m阶遍历的马尔可夫信源的极限熵（ ）。5、信源的剩余度R=（ ）。二、计算一阶马尔可夫信源的信源符号集为，状态转移矩阵 ， （1）画状态转移图，求平稳后的信源概率分布；（2）求信源熵 ；（3）求信源剩余度。、第六讲 CH4 离散信道及其容量信道是信息传播的通道，它将输入事件x变换成输出事件y，由于干扰的存在，一个输入事件总是以一定的概率变换成各种可能的输出事件。一、信道类型1、按输入和输出空间离散或连续分类离散信道（数字信道，输入与输出空间均离散）、连续信道（模拟信道）、半连续信道2、按输入和输出时间离散或连续分类时间离散的连续信道、波形信道3、按输入和输出端的个数分类两端信道（两用户信道）、多端信道（多用户信道、网络信道，如多元接入信道和多元输出信道）4、按信道统计特性分类恒参信道（信道统计特性不随时间变化）、随参信道5、按信道的记忆特性分类无记忆信道、有记忆信道6、特殊信道无损信道（1对多）、确定信道（多对1）、无噪信道（无扰信道，既是无损又是确定，1对1）、无用信道二、离散无记忆信道设离散信道的输入空间：输入序列：输出空间：输出序列:传递概率： 1、定义（离散无记忆信道DMC）在任何时刻信道的输出只与此时的信道输入有关，与以前的输入无关，即则称之为离散无记忆信道。当时（即不随时间变化），称之为平稳信道或恒参信道。2、单符号离散信道输入：输出：传递概率：信道矩阵：3、几个概率先验概率：联合概率：前向概率（信道传递概率）：后向概率（后验概率）：输出符号概率：矩阵表示 ，4、举例（P79）（1）二元对称信道（BSC）（2）二元删除信道（3）二元对称消失信道5、信道疑义度（损失熵）含义：由于信道干扰，输出端收到Y后对输入X尚存在的平均不确定性。例P81 二元删除信道,输入分布信道矩阵 求：解：可由输出分布三、平均互信息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)一、离散无记忆扩展信道1、设信道输入随机变量取值于符号集，信道输出随机变量取值于取值于符号集，信道矩阵为 ，其中 。2、N次扩展输入随机向量 , 其可能取值有个，输出随机向量,其可能取值有个，信道无记忆时，例1 二元无记忆对称信道的扩展信道输入符号集，输出符号集 ，信道矩阵 二次扩展：， ，二次扩展的信道矩阵为 （见p92）3、定理1 对一般无记忆信道，输入随机向量，输出随机向量，当信源无记忆时，等号成立 。其中注：信道无记忆时 信源无记忆时，信道无记忆且信源无记忆时， ，见p94 证明：（1） 当信道无记忆时，当信源也无记忆时，等号成立 。4、定理2 对一般无记忆信源，输入随机向量，输出随机向量， ， 当信道无记忆时，等号成立 。证明：（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）等号成立的充要条件是： 。证明：（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次无记忆扩展信道，当信源无记忆时，（4） X,Y, Z构成一个马尔可夫链，则有： （1） 等号成立的条件是：（2） 等号成立的条件是： 四、信道容量信道容量是信道传输信息量的最大能力的度量。1、定义1 信道容量 2、信息传输率就是平均互信息，即3、信息传输速率是单位时间平均传输的信息量，4、单位时间平均传输的最大信息量五、特殊信道的信道容量1、无损信道等概输入2、确定信道等概输出3、无噪信道（无损确定信道）六、对称信道的信道容量1、离散无记忆信道中，每行都是其他行元素的不同排列，则称此信道为输入对称信道。如 2、离散无记忆信道中，每列都是其他列元素的不同排列，则称此信道为输出对称信道。如 3、准对称信道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.2若一个离散对称信道具有r个输入符号，s个输出符号，则当输入为等概分布时，达到信道容量C，且 。5、引理：对于对称信道，只有当信道输入分布为等概分布时，输出分布才能为等概分布。一般离散信道的容量一、信道容量定义为在信道固定的条件下，寻找使平均互信息达到极大值的输入概率分布。而是输入分布的上凸函数，即是r个变量的多元函数，且有 ，故可用拉格朗日乘子法求条件极值。1、令 解方程组 2、定理4.5.3 对一般离散信道，当且仅当存在常数C使输入分布满足：（1） (对一切)(2) (对一切)时，达到极大，此时常数C即为所求的信道容量。其中为平均条件互信息。（见P33）（3）准对称离散无记忆信道，输入分布等概时，信道容量 .或输入等概时或输入等概时例（1）解一：（2）解二：同上（3）解三：=同上3、离散无记忆N次扩展信道4、独立并联信道（略）5、信源和信道的匹配信道容量是一定的，只有当输入分布满足一定条件时，才能达到信道容量，一般情况下，信息传输率并未达到最大，当信息传输率达到信道容量时，称此信源与信道达到匹配，否则认为信道有剩余，信道剩余度=,相对剩余度=二、举例P1221、（19题）设电阻值为X，电阻功率为Y， ，通过测量电阻值可以得到关于瓦数的平均信息量即平均互信息，或2、（21题）每组4个等概发出，概率为，每个含信息量，1秒=1000ms , 其中含信息量，平均信息传输速率 bit/秒 。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为码字的集合，称为码长。信源符号与码字是一一对应。要实现无失真信源编码，信源符号与码字必须是一一对应、可逆的。2、例1 二元信道的信源编码，信源 码符号集 码 定长码、非奇异码（长度相同、码字都不同）码 变长码、非奇异码码变长码、奇异码码 变长码、奇异码3、N次扩展码信源码二、分组码1、定义：将信源符号集中的每个符号映射成一个固定的码字，这样的码称为分组码。2、分组码性质（1）、奇异性分组码非奇异是正确译码的必要条件。非奇异码当码字排在一起时可能出现奇异性。P129（2）、唯一可译性定义：信源符号映射为一个固定的码字，则信源N次扩展符号映射为N次扩展码的分组码称为原分组码的N次扩展。定义：一个分组码若对于任意有限的整数N，其N次扩展码均为非奇异的，则称之为唯一可译码。（3）定义：无须考虑后续的码符号即可从码符号序列中译出码字，这样的唯一可译码称为即时码。即时码（瞬时码、逗点码、非延长码）：接受到一个完整码字后立即可以译码。P129（4）定义：设为一个码字，称前j个元素为码字的前缀。命题：一个唯一可译码称为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。证明见P130（5）r进制树图 树码树根：树图最顶部的节点，树枝：节点引出的线段，节点：树枝的尽头。n级节点有个，即可有个码字。整树，非整树 r=2 的树图见P130三、定长码1、若信源有q个符号，码符号集有r个码元，码长，则存在唯一可译码需 。若对N次扩展信源进行定长编码，唯一可译需 。N=1时，当r=2（二元码），N=1，如：英文电报32个符号，采用二元符号编定长码，至少 要用5位二元符号进行编码才可能得到唯一可译码。 第九讲 无失真信源编码（续）复习1、 信源符号集 码符号集 码符号（码元）代码组 C为码字的集合，称为码长。2、N次扩展码信源符号及2次扩展信源符号码字及2次扩展码字3、几个概念（1）定义：一个分组码若对于任意有限的整数N，其N次扩展码均为非奇异的，则称之为唯一可译码。（2）定义：无须考虑后续的码符号即可从码符号序列中译出码字，这样的唯一可译码称为即时码。注：即时码必为唯一可译码，反之不一定。（3）定义：设为一个码字，称前j个元素为码字的前缀。（4）命题：一个唯一可译码称为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。4、定长码若信源有q个符号，码符号集有r个码元，码长，则存在唯一可译码需 。若对N次扩展信源进行定长编码，唯一可译需 。新授内容1、定理：离散无记忆信源 ，信源熵为H(S)，N次扩展信源现用码符号集 对N次扩展信源进行长度为的定长编码，对，只要 ，则当N足够大时，必可使译码差错小于；若 ，则当N足够大时，译码错误概率趋于1 。证明：信源符号的自信息信源熵 信源符号自信息的方差 N次扩展信源符号的自信息N次扩展信源熵扩展信源符号自信息的方差 由车贝晓夫不等式，对任意表明，N充分大时，事件几乎不可能发生，故可将N次扩展信源分为两部分：由 只对经常出现的信源序列进行编码，将不经常出现的信源序列抛弃，故所需码字总数减少。设集合中含个，最小概率为，最大概率为，则由总码字 ,只要 即 ， 。将不经常出现的信源序列抛弃，不对编