信息论基础复习题目

设离散无记忆信源

其发生的消息为：（23211223210）求（1）此消息的自信息量。（2）在此消息中平均每个符号携带的信息量。例2-2第一页第二页，共125页。解：（1）消息的自信息量就是等于消息中各个符号的自信息量之和。根据题意可得：

此消息中共有14个“0”符号，13个“1”符号，12个“2”符号，6个“3”符号，则得到的自信息量是：第二页第三页，共125页。（2）此消息中平均每个符号携带的信息量为：原因：(2)问的值是该特定消息中平均每个符号携带的信息量，而信息熵是离散无记忆信源平均每个符号携带的信息量，是统计平均值。信源的信息熵:结论:

(2)问的值与信源的信息熵不完全相等第三页第四页，共125页。

设在一正方形棋盘上共有64个方格，如果甲将一粒棋子随意放在棋盘中的某方格且让乙猜测棋子所在的位置所携带的信息量：（1）将方格按顺序编号，令乙猜测棋子所在方格的顺序号；（2）将方格分别按行和列编号，甲将棋子所在方格的行或列编号告诉乙之后，再令乙猜测棋子所在列或行的位置。

例2-3：第四页第五页，共125页。解：（1）令把棋子任意放在棋盘的某一格为事件xi，则该事件发生的概率为：则该事件携带的信息量为：

（2）设行为随机变量X，列为随机变量Y，则在事件yj发生后事件xi发生的概率为：则该事件携带的信息量为：由结果可知:

事件yj的出现降低了事件xi发生所携带的信息量原因:

事件yj的出现带来了事件xi的部分的信息，导致对事件xi的不确定性减小第五页第六页，共125页。设一系统的输入符号集X=(x1,x2,x3,x4,x5)，输出符号集Y=(y1,y2,y3,y4)

输入符号与输出符号间的联合分布为试求:

H(XY)、H(X)、H(Y)、H(Y|X)和H(X|Y)例2-4第六页第七页，共125页。解：由全概率公式可知：则从已知可求：第七页第八页，共125页。H(Y|X)=H(XY)-H(X)=2.665-2.066=0.599bit/symbolH(X|Y)=H(XY)-H(Y)=2.665-1.856=0.809bit/symbol第八页第九页，共125页。定义：联合集ＸＹＺ中，在给定zk的条件下，xi与yj之间的互信息量定义为条件互信息量，即表明：在随机变量Z出现符号zk的前提条件下，随机变量Y出现符号yj前、后，对信源发送符号xi的条件不确定性的减少2.2.2条件互信息第九页第十页，共125页。上式表明：在随机变量Z出现符号zk的前提条件下，信道1通信前、后，输入与输出端同时出现yj和xi的条件不确定性的减少。

利用互信息和条件互信息可解决符号序列的信息测量问题第十页第十一页，共125页。发送的信息:H(X)损失的信息:H(X|Y)通过信道传递到接收端的关于X的信息:I(X;Y)

信源X有扰信道信宿Y例2-6问:通信中发送的信息是多少?

信道中损失的信息是多少?X通过信道传递了多少信息给信宿？如果X=Y，说明信道无干扰,则I(X;Y)=H(X)如果X与Y相互独立，说明干扰很大,I(X;Y)=0第十一页第十二页，共125页。例2-7：把已知信源信道上，求在该信道上传输的平均互信息量I(X;Y)、疑义度H(X/Y)、噪声熵H(Y/X)和联合熵H(XY).接到下图所示的0.980.80.020.2第十二页第十三页，共125页。解：由题意可知第十三页第十四页，共125页。第十四页第十五页，共125页。第十五页第十六页，共125页。平均互信息：噪声熵：疑义度：第十六页第十七页，共125页。例2-10：设有一批电阻，按阻值分70%是2千欧姆，30%是5千欧姆；按功耗分64%是1/8W，其余是1/4W。现已知2千欧姆阻值的电阻中80%是1/8W。问通过测量阻值可以平均得到的关于瓦数的信息量是多少？解：根据题意，设电阻的阻值为事件X，电阻的功率为事件Y。它们的概率空间分别为：并且已知：第十七页第十八页，共125页。首先计算根据全概率公式可得：

通过测量电阻阻值可以得到关于瓦数的平均信息量就是平均互信息I（X；Y）则通过测量阻值可以平均得到的关于瓦数的信息量是0.816比特第十八页第十九页，共125页。0110011/21/201201101001012例2-11：有一离散无记忆信源，其输出为相应的概率为设计两个独立试验去观察它，其结果分别为已知条件概率为第十九页第二十页，共125页。XY1011/4001/41/41/40121/21/2P(Y1)XY2011/401/4001/20121/21/2P(Y2)解：（1）因为所以必须求出则有：由此可知第二个试验好。第二十页第二十一页，共125页。（2）：因为所以必须求出又由于试验Y1，Y2是相互独立的试验，所以则有：XY1Y2000110111000001001/201/2012XY1Y2000110111/4000001/4001/401/40121/41/41/41/4P(Y1Y2)则有：第二十一页第二十二页，共125页。由此可知：做两个试验比做可多得关于X的信息为中的一个试验各（3）表示做完实验Y2后，从实验Y1可获得关于X的信息量为0.5bit/signal。表示做完实验Y1后，从实验Y2可获得关于X的信息量为1bit/signal。第二十二页第二十三页，共125页。例3-1第二十三页第二十四页，共125页。例3-2：

（1）为了使电视图像获得良好的清晰度和规定的适当的对比度，需要用

个像素和10个不同亮度的电平，设每秒要传递30帧图像，所有象素是独立变化的，且所有亮度电平等概率出现.求传递此图像所需的信息率（比特/秒）.

（2）设某彩电系统，除了满足对黑白电视系统的上述要求外，还须有30个不同的色彩度，试证明传输这彩色系统的信息率约是黑白系统信息率的2.5倍。第二十四页第二十五页，共125页。解：（1）每个象素亮度信源的概率空间为：

每个象素亮度含有的信息量为：

H(X)=log10=1哈特来/象素=3.32比特/象素每帧图像含有的信息量为：

设每秒传送30帧图像，则传递此图像所需的信息率为：

第二十五页第二十六页，共125页。（2）证明：

色彩度信源的概率空间为:

每个象素色彩度含有的信息量为：

H(Y)=log30=4.91比特/象素亮度和色彩度同时出现，每个象素含有的信息量为：

H(XY)=H(X)+H(Y)=log10+log30=8.23比特/象素

传输这彩色系统的信息率与传输黑白系统的信息率之比就等于彩色系统每象素含有的信息量与黑白系统每象素含有信息量之比，即：H(XY)/H(X)=2.5

则证明传输这彩色系统的信息率是传输黑白系统的信息率的2.5倍。第二十六页第二十七页，共125页。例3-3：

每帧电视图像可以认为是由

个象素组成的，所以象素都是独立变化的。且每一个象素又取128个不同的亮度电平，并设亮度电平等概率出现。若现有一个广播员在约10000个汉字的字集中选1000个字来口述此电视图像（设每个字是等概率分布的，并且彼此独立的）。试问广播员描述此图像所广播的信息量是多少？若要恰当描述此图像，广播员在口述中至少需用多少汉字？第二十七页第二十八页，共125页。解：（1）分析可知汉字字集是等概率分布的，则汉字字集信源为得该汉字字集中每个汉字含有的信息量为：

H(Y)=log10000=13.29比特/字广播员描述此帧图像所广播的信息量为：（2）分析可知每个象素的亮度信源为每个象素亮度含有的信息量为：

H(X)=log128=7比特/象素每帧图像含有的信息量为：广播员口述此图像至少需用的汉字数为：第二十八页第二十九页，共125页。例3-4：

对一最高频率分量为4kHz的模拟信号以奈奎斯特采样定理采样，已知抽样结果是一个独立的平稳随机序列。现将每个抽样值量化为5个离散电平之一，已知这5个电平构成的符号集{X}的概率特性为

求这个离散信源每秒传送的平均信息量。解：由题意可知采样率为8kHz，则符号速率是8000个符号/s。每个符号的平均信息量为则这个离散信源每秒传送的平均信息量为

第二十九页第三十页，共125页。例3-5：设某二阶离散平稳信源X=X1X2的原始信源的信源模型为：

X=X1X2中前后两个符号的条件概率为：

比较原始信源与二阶信源的熵。第三十页第三十一页，共125页。信源X提供的熵

平均每个符号携带的信息量：

结论：极限熵、条件熵都小于原始信源的熵原因：符号之间存在相关性

解：原始信源的熵：

条件概率确定的条件熵：

第三十一页第三十二页，共125页。二.马尔可夫信源的状态转移图

例3-6： 设有一个二进制一阶马尔可夫信源，其信源符号集为A={0,1},条件概率为

求状态转移矩阵。第三十二页第三十三页，共125页。解：信源符号个数q=2，k=1,故状态数则令状态S1=0,状态S2=1状态图：

S1=0S2=10.750.500.250.50根据状态图求状态转移概率：

p(S1|S1)=0.25p(S2|S1)=0.75p(S1|S2)=0.50p(S2|S2)=0.50则状态转移矩阵为：

第三十三页第三十四页，共125页。有一个二进制二阶马尔可夫信源，其信源符号集为A={0,1},条件概率为：求状态转移矩阵。例3-7：第三十四页第三十五页，共125页。由状态图可知转移矩阵：则令：状态S1=00,状态S2=01，状态S3=10，状态S4=11则状态图：

0.5S201S310S100S4110.80.80.50.50.50.20.2解：信源符号个数q=2，k=2,故状态数第三十五页第三十六页，共125页。定理：马尔可夫信源具有稳态分布的充要条件是存在一个正整数N，使马尔可夫信源的状态转移矩阵中的所有元素均大于零。例3-8

有一个马尔可夫链，其状态转移矩阵为：问：是否存在稳态分布，如果存在求此稳态分布。

第三十六页第三十七页，共125页。解：

由此判断：稳态分布存在由WP=W以及各状态概率之和为1得：和第三十七页第三十八页，共125页。3.举例说明马尔可夫信源熵的计算方法

例3-9:有一个二进制二阶马尔可夫信源，其信源符号集为A={0,1},条件概率为：求状态转移矩阵。第三十八页第三十九页，共125页。解:由例7可知状态转移矩阵为：可知：此信源是遍历性的马尔可夫信源，稳态分布存在设稳态分布为：

则利用WP=W和可知：对于遍历性马尔可夫信源有第三十九页第四十页，共125页。由

则有：

第四十页第四十一页，共125页。3.5

信源的相关性和剩余度一.信源的相关性

信源输出符号之间的依赖关系

对于离散平稳信源有

当信源输出符号之间的相关程度越长，实际熵越小

二.信源冗余度γ

第四十一页第四十二页，共125页。例3-10:

英文26个字母加空格共27个符号，根据统计出现的概率如表所示，则英文字母携带的最大信息量是多少？冗余度为多少？

序号字母出现概率序号字母出现概率1空格0.181715M0.021052E0.107316U0.020103T0.085617G0.016334A0.066818Y0.016235O0.065419P0.016236N0.058120W0.012607R0.055921B0.011798I0.051022V0.007529S0.049923K0.0034410H0.0430524X0.0013611D0.0310025J0.0010812L0.0277526Q0.0009913F0.0239527Z0.0006314C0.02260第四十二页第四十三页，共125页。解：英文字母携带的最大信息量即为等概时携带的信息量：英文字母携带的实际熵英文字母的冗余度第四十三页第四十四页，共125页。例3-11：中文冗余度的统计比英文要复杂得多，难得多，假如以《辞海》（上海，1989）收集的大约15000汉字为信源消息符号，则中文的最大信息熵为目前还没有找到给出中文实际熵好的统计方法的文献，但根据目前广泛使用的文本压缩软件的压缩率来看，中文实际熵应该不会大于5比特/汉字，估计中文的冗余度大约在80%左右。

第四十四页第四十五页，共125页。

讨论γ

：

从提高抗干扰能力角度出发:希望减少或去掉剩余度希望增加或保留信源的剩余度因为:剩余度大的消息具有很强的抗干扰能力。当干扰使消息在传输过程中出现错误时，能从它的上下关联中纠正错误。从提高信息传输的有效性观点出发:原因是什么?第四十五页第四十六页，共125页。例3-12：黑白气象传真图的消息只有黑白两种颜色，即信源X={黑，白}，且p(黑)=0.3，p(白)=0.7。（1）假设图上黑白消息出现前后没有关系，求熵H(X)。（2）假设消息前后由关系，其依赖关系为

p(白|白)=0.9，p(黑|白)=0.1，p(白|黑)=0.2，

p(黑|黑)=0.8，求此一阶马尔可夫信源的熵H2。（3）分别求上述两种信源得剩余度，并比较H(X)和H2的大小，并说明其物理意义。第四十六页第四十七页，共125页。信源的信息熵

（2）分析得此信源为一阶马尔可夫信源，它的的状态集为：A={S1=黑，S2=白}。则状态转移图：S1

S20.20.10.80.9解：（1）假设黑白气象传真图上黑白消息出现的前后没有关系，则等效于一个离散无记忆信源。信源概率空间为：

第四十七页第四十八页，共125页。则其状态转移矩阵为：由此可见：此马尔可夫信源是遍历的，稳态分布存在，则设W=(p(S1)p(S2)),根据WP=W可得：可以求出:

第四十八页第四十九页，共125页。则此信源的熵为：

（3）黑白消息信源的剩余度

即第四十九页第五十页，共125页。例4-1：其中：p表示传输中发生错误的概率二元对称信道(BSC)(二进制对称信道)第五十页第五十一页，共125页。

其中：p、q表示正确传输的概率

二元删除信道(二进制删除信道)第五十一页第五十二页，共125页。例4-2：考虑二元对称信道，其信源概率空间为

信道XY（0，1）（0，1）求其平均互信息第五十二页第五十三页，共125页。解:应用全概率公式则有：第五十三页第五十四页，共125页。则平均互信息：当信道固定，即p为一个固定常数时，可得到I(X;Y)是信源输出分布ω的上凸函数。

当信源固定，即ω是一个常数时,可得到I(X;Y)是信道传递概率p的下凸函数。当p=0.5时，I(X;Y)=0，在接收端未获得信息量。

当ω=1/2

时，即取极大值.第五十四页第五十五页，共125页。例4-3：掷色子，如果结果是1，2，3，4，则抛一次硬币；如果结果是5、6，则抛两次硬币。试计算从抛硬币的结果可以得到多少掷色子的信息量。解：设掷色子结果是1，2，3，4为事件X=0，结果是5、6为事件X=1；Y=0表示抛硬币出现0次正面,Y=1表示抛硬币出现1次正面,Y=2表示抛硬币出现2次正面。信源概率空间为信道矩阵为输出符号的概率空间为则有：第五十五页第五十六页，共125页。例4-4：求二元无记忆对称信道的二次扩展信道。解：输入扩展为：00，01，10，11输出扩展为：00，01，10，11传递矩阵扩展为：请问：与I（X；Y）之间的关系？第五十六页第五十七页，共125页。

定理1:若信道的输入、输出分别为N长序列X和Y，且信道是无记忆的，即：用两个定理回答这个问题定理2：若信道的输入、输出分别为N长序列X和Y，且信源是无记忆的，即：第五十七页第五十八页，共125页。由定理1和定理2当信源和信道都是无记忆时有：

当每个序列中的分量Xi取值于同一信源符号集，且具有同一种概率分布，则输出Y的分量Yi也取值同一符号集，则各I（Xi；Yi）是相等的。即：对于N次扩展，则有第五十八页第五十九页，共125页。例4-5：下图中的X、Y、Z满足马氏链，求该串联信道的总信道矩阵。b1a1a2c1b2c2b3c3XYZ1/31/31/31/21/21/31/32/32/31解：由图可知第五十九页第六十页，共125页。例4-6：考虑二元对称信道，其信源概率空间为求该信道的信道容量。解：信道的平均互信息

当ω=1-ω=1/2

时，I(X;Y)取极大值，即接收到的信息量最大，则信道容量为：C=maxI(X;Y)=1-H(p)由此可知：信道容量只是传递概率的函数第六十页第六十一页，共125页。例4-7：求具有以下信道矩阵的信道的信道容量解：分析可知这是一个对称信道，则信道容量为

结论：在该对称信道中，只有当信道输入符号等概分布时，每个符号平均能传送的信息为0.126bit，一般情况下每个符号平均传输的信息都是小于0.126bit

。第六十一页第六十二页，共125页。例4-8：求均匀信道的信道容量。为正确传递概率为错误传递概率对于二元对称信道：r=2，则信道容量C：解：均匀信道是对称信道的一种特例，则其信道容量用对称信道的信道容量的求解公式，则

第六十二页第六十三页，共125页。例4-9：求二元对称删除信道的信道容量。解：分析可知该信道分成对称的2个子信道则该信道是一个准对称信道

其信道容量为

其中输入符号个数n=2，则有：第六十三页第六十四页，共125页。例4-10：设有扰离散信道的传输情况如图所示，求C以及达到C时的输入概率分布.利用对称信道的信道容量公式求得：第六十四页第六十五页，共125页。解：I(X;Y)=H(Y)-H(Y|X)则有：达到C时的输入分布：第六十五页第六十六页，共125页。六.N次扩展离散无记忆信道的信道容量

表示某时刻通过离散无记忆信道传输的最大信息量。则：

对于离散无记忆信道有：对于N次扩展信道，任何时刻是相同的。第六十六页第六十七页，共125页。

例4-12:

已知信道的带宽B为3kHz,信号在信道传输中受到单边功率谱密度为的加性白高斯噪声的干扰,信号的平均功率S为9W.

(1)求信道的容量;(2)若信道带宽增加到原来的10倍,并保持信道容量不变,那么信号平均功率要改变多少dB?解:

(1)信道容量为(2)带宽变为10B,而C保持不变,假设此时对应的信号功率为则第六十七页第六十八页，共125页。无损信道的剩余度第五节信源与信道匹配一.信道剩余度=C-I(X;Y)=C-R二.相对剩余度=1-R/C对于无损信道C=logr无损信道的相对剩余度信源的剩余度

对于无损信道，可通过信源编码，减小信源的剩余度，提高信道的信息传输率使之达到C。第六十八页第六十九页，共125页。例4-13：有一个二元对称信道，其信道矩阵如图所示。设该信道以1500个二元符号/秒的速度传输输入符号。现有一消息序列共有14000个二元符号，并设在这消息中p(1)=p(0)=1/2。问从信息传输的角度来考虑，10秒内能否将这消息序列无失真传送完。1000.980.020.980.021解： 分析得消息信源的熵为H（X）=1比特则这个消息序列含有信息量

14000*1=14000比特。第六十九页第七十页，共125页。由图可知，信道矩阵为：由信道矩阵可知，此信道为二元对称信道，所以其信道容量（最大信息传输率）为：信道的最大信息传输速率：信道在10秒钟内能无失真传输的最大信息量=12879比特

14000>12879则从信息传输的角度考虑，不可能在10秒内将这消息无失真传输完。第七十页第七十一页，共125页。例4-14：设某一信号的信息输出率为5.6kbps，噪声功率谱为传输。试求无差错传输需要的最小输入功率P是多少？

在带宽B=4kHz的高斯信道中解：由香农公式可知，该信道的信道容量为要想使信息输出率为5.6kbps的信号无差错的传输，则必须有得

第七十一页第七十二页，共125页。2.二元码：3.定长码：8.非同价码：信道的基本符号集中码元个数为2√

每个码元所占的传输时间不完全相同7.同价码：每个码元所占的传输时间相同√6.奇异码：码中码字至少有两个相同5.非奇异码：码中所有的码字都不相同√4.变长码：码中的码字长短不一码中所有码字的长度都相同二.码的类型1.分组码：将信源符号集中的每个信源组符号映射成一个固定的码字

第七十二页第七十三页，共125页。例5-1：设有二元信道的信源编码器，其概率空间编码后的结果：信源符号Si码1码2码3码4S100000S201011110S3100010000S4111111110定长码非奇异码非奇异码变长码变长码奇异码第七十三页第七十四页，共125页。9.N次扩展码（类似N次扩展信源）举例：10.唯一可译码：

一个分组码若对任意有限的整数N,其N次扩展码均为非奇异码，则称为唯一可译码。或每个信源符号序列映射成一个固定的码字，并且代码组中每个码字只能唯一地被译成所对应的信源符号序列。11.即时码：

无需考虑后续的码符号即可从码符号序列中译出码字，这样的唯一可译码称为即时码，又称非延时码。*唯一可译码要成为即时码的条件：其中任一码字都不是其他码字的前缀第七十四页第七十五页，共125页。即时码可用树图构造：树根一阶节点二阶节点

三阶节点(终端节点)A00011010111001000111110101100011010001(1)树图的最顶部的节点称为树根，树枝的尽头称为节点(2)每个节点的分支数等于码元数，且各分支分别对应一个固定的码元，各分支伸出方向所对应的码元是统一的，如图向左伸出为0，向右伸出为1。

(3)各码字分布在码树的终端节点(即不再分支的节点)。

(4)节点一旦被分配码字，后边的枝便要去掉，否则成为非即时码。第七十五页第七十六页，共125页。例5-2：

英文电报有32个符号(26个字母加上6个字符),请问对信源符号进行二进制编码，要想有唯一可译码，码长至少为多少？解：r=2,q=32,N=1，要想有唯一可译码，则第七十六页第七十七页，共125页。二、定长编码定理进行长度为的定长编码，对用码元集设离散无记忆信源的熵为H(S)，其N次扩展对于只要满足(正定理)则当N足够大时，几乎可实现无失真信源编码，此时译码差错小于δ。反之，若则当N足够大时，译码错误概率趋于1(编码误差任意大)（逆定理）信源为第七十七页第七十八页，共125页。例5-3：仍以英文电报为例，当认为各符号是等概分布时的熵为，但是考虑相关性后英文信源的极限熵为

那么对它们进行码长为l的定长编码时，各自需要的码长是多少？解：等概时所需的码长是5，而考虑相关性时需要的码长是2。第七十八页第七十九页，共125页。三.编码效率η当允许错误概率小于δ时，信源符号序列的长度N：为自信息的方差如果为最佳编码，则第七十九页第八十页，共125页。例5-4：设离散无记忆信源求信源序列的长度。对S采取等长二元编码，要求编码效率允许错误概率第八十页第八十一页，共125页。二.克拉夫特(Kraft)不等式和麦克米伦(McMillan)不等式

设信源符号集为其分别对应码长为l1,l2,…lq，则即时码存在的充要条件是：对信源进行编码，相应的码字集为码符号集为1.Kraft不等式：2.McMillan不等式

在满足kraft不等式的条件下，唯一可译码存在的充要条件是：第八十一页第八十二页，共125页。

设S0为原始码字的集合。再构造一系列集合S1,S2,…Sn。构造S1,S2,…Sn的方法：

1、首先考察S0中所有的码字。若码字Wj是码字Wi的前缀，即Wi=WjA，则将后缀A列为S1中的元素，S1就是由所有具有这种性质的A构成的集合。

2、当n>1，则将S0于Sn-1比较，看是否S0中的码字是Sn-1的前缀，如果是，则取后缀为Sn中元素，且看Sn-1中码字是否为S0中码字的前缀，如果是，则取后缀为Sn中元素，如此构成集合Sn。三.唯一可译码判断准则准则：一种码为唯一可译码的充要条件是S1,S2,…中没有一个含有S0中的码字。第八十二页第八十三页，共125页。S0S1S2S3S4S5S6S7S8adebdebaddeb0cbbcdebcdeadabbbaddebbbcde结论：当N>7时，Sn为空集，而在S5中包含S0中的码字，故而S0不是唯一可译码。例5-5：设消息集合中共有7个消息，分别为被编码成对应的码字，判断是否是唯一可译码。第八十三页第八十四页，共125页。例5-6:有一离散无记忆信源

,求对原始信源和二次扩展信源用{0，1}码元集进行编码后的信息传输率以及编码效率.解:(1)用{0，1}对之进行编码，有(2)二次扩展信源为：第八十四页第八十五页，共125页。②用0，1码符号分别代表概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个，从而得到只包含q-1个符号的新信源S1,称为缩减信号源。三.二元Huffman编码1.编码步骤①将信源发出的q个信源按其概率依次从大到小排列③把缩减信源S1的符号按概率从大到小排列，再将其最后两个概率最小的符号合并成一个符号，并分别用0和1码元表示，这样形成q-2个符号的新信源S2。④依此类推，直至信源只剩两个符号为止，并分别用“0”和“1”表示。⑤从最后一级缩减信源开始，向前返回，得出各信源符号所对应的码符号序列，即相应码字。第八十五页第八十六页，共125页。例5-8信源符号Si

概率p(Si)

编码过程码字Wi

码长liS1S2S3S10.4S20.2S30.2S40.1S50.10.40.20.40.60.210101001编码过程：101200030010400114第八十六页第八十七页，共125页。用树图检验是否为即时码0A01001110100000100011第八十七页第八十八页，共125页。(1)每次对信号缩减时，赋予最后两个概率最小的符号用“0”和“1”是可任意的。(2)对信源进行缩减时两个概率最小的符号合并后的概率与其他符号概率相同时，可任意排序。经哈夫曼编码方法得到的码并非是唯一的,造成非唯一的原因：

码字Wi

码长l

i

S10.40.40.40.6002

S20.20.20.40.4102

S30.20.20.2112

S40.10.20103

S50.1011301010101例题5-8：第八十八页第八十九页，共125页。A00111000101101010011即时码由此可见：结论：当进行哈夫曼编码时，为了得到质量好的码，应使合并的信源符号位于缩减信源序列尽可能高的位置，这样可充分利用短码。第八十九页第九十页，共125页。r元哈夫曼码可由二元哈夫曼码的编码方法推广得到。只是编码过程中构成缩减信源时，每次将r个概率最小的符号合并，并分别用0，1，…，r-1码元表示。为了充分利用短码，使哈夫曼码的平均码长最短，必须是最后一个缩减信源有r个信源符号。因此，对于r元哈夫曼码，信源S的符号个数q必须满足

如果信源S的符号个数q不满足上式，则增补一些概率为0的信源符号。四.r元哈夫曼码第九十页第九十一页，共125页。例5-9：有一离散无记忆信源码元集X=(0,1,2)，对S进行3元哈夫曼编码。解：第九十一页第九十二页，共125页。信源符号概率编码过程码字Wi

码长li

Sip(Si)S1S2

Wi

li

S10.40.40.401

S20.30.30.321

S30.20.20.3102

S40.050.05122S50.0250.051103S60.0251113S701123210210210第九十二页第九十三页，共125页。霍夫曼编码的特点：

1）由于霍夫曼编码总是以最小概率相加的方法来缩减参与皮埃对的概率个数，因此概率越小，对缩减的贡献越大，其对应消息的码字也越长。2）最小概率相加的方法使得编码不具有唯一性，尤其是碰到存在几个消息符号有着相同概率的情况，将会有多种路径选择，即既具有多种可能的代码组集合。3）尽管对同一信源存在着多种结果的霍夫曼编码，但它们的平均码长几乎都是相等的，因为每一种路径选择都是使用最小概率相加的方法，其实质都是遵循最佳编码的原则，因此霍夫曼编码是最佳编码。

霍夫曼编码存在的问题：

1）霍夫曼编码要求信源消息概率已知或可估计。由于初始信源不可能总是统计好了概率，为此编码之前必须先估算信源的统计特性。在信源具有记忆性能并用霍夫曼编码来表示信源的扩展输出时，概率的估计很耗费时间。2）霍夫曼编码是建立在编码器和译码器都知道码树结构的基础上的，如果信源消息数目变大，则树型结构的大小和算法的复杂性会呈指数规律增加。第九十三页第九十四页，共125页。例6-1：

参见下图，假设P(a1)=0.4,分别求出4种译码规则所对应的平均差错率。0.80.20.10.9a1a2b1b2第九十四页第九十五页，共125页。解：信道输入概率矩阵和转移矩阵分别为：

转移矩阵各行元素乘以对应的输入概率，得联合概率矩阵

译码规则F1对应的平均差错率为

其它译码规则对应的平均差错率分别为Pe(F2)=0.4 Pe(F3)=0.14 Pe(F4)=0.86四种规则相比，F3最好，F4最差第九十五页第九十六页，共125页。例6-2

参见下图，假设P(a1)=0.4，求最佳译码规则。

0.80.20.10.9a1a2b1b2解：例6-1已经求出联合概率矩阵，重写为则最大联合概率译码规则为：对应的平均差错概率：

第九十六页第九十七页，共125页。——按最大转移概率条件确定的译码规则例6-3：已知信道转移矩阵，试确定译码规则。解：按转移概率最大原则确定极大似然译码规则如下：

二、极大似然译码规则第九十七页第九十八页，共125页。提问：传输系统的Pe要求控制在10-6以下，而利用译码规则的Pe太高，如何降低平均差错率呢？－－－信道编码一.简单重复编码

对信源符号进行“重复2次”编码:信道编码f信道译码F第九十八页第九十九页，共125页。“重复2次”编码规则为

第九十九页第一百页，共125页。求出3次扩展信道的转移矩阵按极大似然译码规则得译码函数

即：

译码差错率为：结论：信道编码降低平均错误率第一百页第一百零一页，共125页。提问：信道编码对信息传输速率有什么影响呢？

信道编码，或称为纠错编码，就是靠增加“冗余”码元来克服或减轻噪声影响的。结论：信道编码降低了信道的信息传输率信道编码之后的信息率或信道待传的信息率为无信道编码的信息率或信道待传的信息率为

第一百零一页第一百零二页，共125页。二.对符号串编码(矢量编码）例6-4：二元信源U，若取二元符号串“00，01，10，11”作为消息，则消息个数增加为M=4。提问：此时平均差错率又发生怎样的变化呢？结论：增加信源消息个数，可提高信道的信息传输率取码长N=3，则编码后的信息率为

R=(log4)/3=2/3比特/码元第一百零二页第一百零三页，共125页。码长N=3，可供选择的码字为选择以下编码函数：

根据信道转移矩阵确定极大似然译码规则为

则平均差错率为：

结论：增加消息个数M与重复编码相比，在提高信息率的同时会使平均差错率增大。第一百零三页第一百零四页，共125页。第四节汉明距离

两个等长符号序列x和y之间的汉明距离，记为D(x,y)，是x与y之间对应位置上不同符号的个数。解：求汉明距离：

D(x,z)=2;D(y,z)=3因此，z与x的相似程度高于与y的相似程度一.定义例6-5：

x=100111,y=111000,z=111111,比较z与x和y的相似程度。第一百零四页第一百零五页，共125页。X和Y是二元序列，记为

是等长码，则C中任意两个不同码字之间的汉明距离或码间距离为码C的最小码间距离定义为第一百零五页第一百零六页，共125页。二元对称信道，可以根据汉明距离来决定译码规则

假如有一个信源有M个消息二元对称信道的输入符号集和输出符号集分别为A={0，1}和B={0，1}。其N次扩展信道的输入符号集和输出符号集分别为：第一百零六页第一百零七页，共125页。经N次扩展信道传送之后，按极大似然译码规则进行译码记N长二元符号串为

由信道无记忆可知转移概率为码元错误概率为p，正确概率为

则有：极大似然译码规则等价为最小汉明距离译码规则第一百零七页第一百零八页，共125页。

最小距离译码规则可在一般信道中采用，但不一定与极大似然译码规则等价，只有对于二元对称信道，它才与极大似然译码规则等价，并且当输入等概时是最佳的。

对于二元对称信道，若输入等概，无论用什么规则确定译码函数，与之对应的平均差错率都可用汉明距离表示：

结论：第一百零八页第一百零九页，共125页。第五节有噪信道编码定理一.正定理（香农第二定理）若信道是离散、无记忆、平稳的，且信道容量为C，只要待传送的信息率R<C，就一定能找到一种信道编码方法，使得码长足够大时，平均差错率任意接近于零。二.逆定理若信道是离散、无记忆、平稳的，且信道容量为C，只要待传送的信息率R>C，就一定找不到一种信道编码方法，使得码长足够大时，平均差错率任意接近于零。

信道编码定理告诉我们：R<=C时，通过编码可使平均差错率逼近零；逆定理则说明：R>C时，无论如何编码，都不可能使平均差错绿逼近零。因此，信道容量C是确保可靠性传输的信息传输率的上限。第一百零九页第一百一十页，共125页。例7-1假定离散矢量信源N=3，输出矢量序列为X=X1X2X3，其中Xi,i=1,2,3的取值为{0,1}，经信道传输后的输出为Y=Y1Y2Y3

，其中Yj,j=1,2,3的取值为{0,1}.定义失真函数为

d(0,0)=d(1,1)=0,d(0,1)=d(1,0)=1,求矢量失真矩阵[dN]。解：由矢量失真函数的定义得：第一百一