《信息论与编码》习题集教学文稿

1、Good is good, but better carries it.精益求精，善益求善。信息论与编码习题集-第二章习题：补充题：掷色子，（1）若各面出现概率相同（2）若各面出现概率与点数成正比试求该信源的数学模型解：（1）根据，且，得，所以信源概率空间为（2）根据，且，得。2-2由符号集组成的二阶马尔可夫链，其转移概率为P(0/00)=0.8，P(0/11)=0.2，P(1/00)=0.2，P(1/11)=0.8，P(0/01)=0.5，P(0/10)=0.5，P(1/01)=0.5，P(1/10)=0.5。画出状态图，并计算各状态的稳态概率。解：由二阶马氏链的符号转移概率可得二阶马氏链的

2、状态转移概率为：P(00/00)=0.8P(10/11)=0.2P(01/00)=0.2P(11/11)=0.8P(10/01)=0.5P(00/10)=0.5P(11/01)=0.5P(01/10)=0.5二进制二阶马氏链的状态集S=00，01，10，11状态转移图各状态稳定概率计算：即得：即：P(00)=P(11)=P(01)=P(10)=2-6掷两粒骰子，当其向上的面的小圆点数之和是3时，该消息所包含的信息量是多少？当小圆点数之和是7时，该消息所包含的信息量又是多少？解：2-72-7设有一离散无记忆信源,其概率空间为该信源发出的消息符号序列为(2021201302130012032101

3、10321010021032011223210),求此消息的自信息量是多少及平均每个符号携带的信息量?解:消息序列中,“0”个数为=14,“1”个数为=13,“2”个数为=12,“3”个数为=6.消息序列总长为=+=45(个符号)消息序列的自信息量:-平均每个符号携带的信息量为:2-14在一个二进制信道中，信息源消息集X=0，1，且P(1)=P(0),信宿的消息集Y=0，1，信道传输概率P（1/0）=1/4，P（0/1）=1/8。求：（1）在接收端收到y=0后，所提供的关于传输消息x的平均条件互信息量I（X;y=0）。(2)该情况所能提供的平均互信息量I（X；Y）。解：X=0,1,Y=0,1求

4、(2)2-25某一无记忆信源的符号集为0，1，已知，。（1）求符号的平均熵。（2）由100个符号构成的序列，求某一特定序列（例如有m个0和100-m个1）的自信息量的表达式。（3）计算(2)中的序列的熵。解：（1）对离散无记忆信源符号的平均熵：比特/符号（2）长度为L=100的符号序列中某特定序列，其中“0”的个数为m，“1”的个数为100-m.该特定序列的概率为对离散无记忆信源，其符号独立出现，即则该特定序列的自信息量为：=41+1.59m(bit)(3)长度为L=100的符号序列离散无记忆信源熵：=H(XXX)=81（比特/序列）2-30有一马尔可夫信源，已知转移概率为，。试画出状态转移图

5、，并求出信源熵。解：（1）由题意知，该马尔可夫信源阶数为1，状态集S=，状态转移图为：(2)信源熵：求稳态概率计算方程：即：得：即：P(S)=0.75，P(S)=0.25求H(X/S)H(X/S)则信源熵：H=H=0.69比特/符号2-33一阶马尔可夫信源的状态图如图2-14所示，信源X符号集为0，1，2。（1）求平稳后信源的概率分布；（2）求信源熵；（3）求当p=0或p=1时信源的熵，并说明其理由。解：（1）一阶马尔可夫信源的状态空间S=X=0，1，2，由图2-14状态转移图中分析得，此马尔可夫链是时齐的，状态有限的和不可约闭集，非周期，所以具有各态历经性。平稳后状态的极限分布存在，因为是一

6、阶马尔可夫信源，状态的极限分布即平稳后信源符号的一维概率分布，即根据状态转移图，得状态一步转移矩阵：计算方程组即整理计算得：即状态极限概率P(0)=P(1)=P(2)=1/3(2)根据马尔可夫信源熵的表达式：=由=同理从而比特/符号（3）当p=0或p=1时信源的熵，这是因为p=0或p=1时信源为确定性信源，观察着对信源发出什么符号不存在任何不确定度，所以信源不提供任何的信息量。第三章3-1设二进制对称信道的概率转移距阵为2/31/31/32/3.（1）若p(x0)=3/4，p(x1)=1/4,求H(X),H(X|Y),H(Y|X)和I(X;Y)。(选做)（2）求该信道的信道容量及其达到信道容量

7、时的输入概率分布。解：（1）由题意可得x的先验概率P(x0)=3/4,p(x1)=1/4.H(x)=H(3/4,1/4)=0.82bit/符号由概率转移距阵得符号转移概率：p(y0|x0)=2/3,p(y1|x0)=1/3,p(y0|x1)=1/3,p(y1|x1)=2/3.联合概率：p(x0, y0)=p(x0)p(y0|x0)=1/2同理：p(x0, y1)=1/4，p(x1,y0)=1/12，p(x1,y1)=1/6则条件熵：=0.91bit/符号另外p(y0)=7/12p(y1)=5/12=0.9799根据得=0.7494bit/符号互信息：=0.066bit/符号(2)由概率转移距阵

8、，可知该信道为对称DMC信道故其信道容量：(m=2为接收端信宿符号集中符号数目)=0.082bit/符号当其达到信道容量时输入为等概分布p(x0)=p(x1)=1/2.3-5求下列两个信道的容量，并加以比较（1）（2）解：由于两信道均为准对称信道（行元素对应相同，但列元素不相同），可分解为其信道容量公式为则，即信道2比信道1好一些。3-10.一个平均功率受限制的连续信道，其通频带为1MHZ，信道上存在白色高斯噪声。（1）已知信道上的信道的信号与噪声的平均功率比值为10，求该信道的信道容量；（2）信道上的信道与噪声的平均功率比值降至5，要达到相同的信道容量，信道通频带应为多大？（3）若信道通频带

9、减为0.5MHZ时，要保持相同的信道容量，信道上的信号与噪声的平均功率比值应等于多大？解：(1)由题意可得:由SNR=10信道的信道容量：C=Wlog2(1+SNR)=3.46Mbit/s（2）若SNR=5,信道容量保持不变.由C=Wlog2(1+SNR)得W=C/log2(1+SNR)=1.34MHZ(3)若W减为0.5MHZ,信道容量保持不变.由C=Wlog2(1+SNR)易得1+SNR=121故SNR=120.第四章4-1设有一个二元等概信源X=0，1，通过一个二进制对称信道（BSC）。其失真函数与信道转移概率分别定义为试求失真矩阵d和平均失真。解：由失真矩阵转移概率矩阵平均失真为4-3

10、设输入符号表与输出符号表为X=Y=0，1，2，3，且输入信号的分布为，设失真矩阵为求，和，以及相应的编码器转移概率矩阵。解：对离散信源，当时为无失真编码，信源符号与码符号一一对应，即则信道转移概率矩阵为得假设时失真达到，即则此时信道转移概率矩阵为4-5具有符号集的二元信源，信源发生概率为：，。Z信道如图4-7所示，接收符号集，转移概率为：，。发出符号与接收符号的失真：，。（1）计算平均失真；（2）率失真函数R(D)的最大值是什么？当q为什么值时可达到该最大值？此时平均失真D是多大？（3）率失真函数R(D)的最小值是什么？当q为什么值时可达到该最小值？此时平均失真D是多大？（4）画出R(D)D的

11、曲线。解：概率转移矩阵为：失真矩阵为（1）（2），率失真函数取最大值时比对应最小的失真，对离散信源，最小失真为零，即，由于，所以，则（3），对应最大的失真，此时（4）R(D)D曲线：（2）（3）的传统解法：（2）解方程得则平均失真（3），令，得此时平均失真第五章信源编码5-1将下表所列的某六进制信源进行二进制编码，试问(1)这些码中哪些是唯一可译码？(2)哪些码是非延长码（即时码）？(3)对所有的唯一可译码求出其平均码长和编码效率。解：C1=000，001，010，011，100，101C2=0，01，011，0111，01111，011111C3=0，10，110，1110，11110，11

12、1110C1码组为等长码，因各码字均不相同，则必为唯一可译码。C2码组中各码字长度分别为，则根据克劳夫特不等式则存在该码长分布的唯一可译码；下一步检验该码长构成的具体码字：最短的码字“0”是其他码的前缀，尾随后缀分别为1，11，111，1111，11111，这些尾随后缀都不是码组中的单独码字；次短的码字“01”是码字011，0111，01111，011111的前缀，其尾随后缀为11，111，1111，11111不是码组中的单独码字，.依次可判断其他次短码字虽然是长码字的前缀，但尾随后缀均不是码组中的单独码字，由此可断定该码字是唯一可译码。C3码组的码长分布与C2码组相同，满足克劳夫特不等式，下

13、一步检验该码长构成的具体码字：最短的码字”0”不是其他码字的前缀，没有尾随后缀，次短码字”10”、110”“1110“、“11110”都不是其他码字的前缀，没有尾随后缀，所以必是唯一可译码。（C3码组满足克劳夫特不等式，又是非前缀码，所以是唯一可译码）C1、C2、C3是唯一可译码，在唯一可译码中，分为即时码和非即时码。即时码的判断方法有两种：根据定义：即时码又叫非前缀码或非延长码。则C1、C3是即时码根据码树：码组中的各码字都处在树的终端节点上，则为即时码。码树省略判断结果为：C1、C3的各码字均处在码树的终端节点上，是即时码根据公式根据编码效率公式得比特/符号5-10设有离散无记忆信源P(X

14、)=0.37,0.25,0.18,0.10,0.07,0.03;(1)求该信源符号熵H(X);(2)用哈夫曼编码编成二进制变长码，计算编码效率。(3)要求译码错误小于，采用定长二元码要达到(2)中的哈夫曼编码效率，问需要多少个信源符号连在一起编？解：（1）信源熵比特/符号(2)用哈夫曼编码编成二进制变长码为00，01，11，101，1000，1001平均码长码符号/信源符号编码效率(3)要求译码错误小于，采用定长二元码要达到(2)中的哈夫曼编码效率。第一步：根据第二步要求译码错误小于，令，则需要一起编的符号长度应满足5-12已知一信源包含8个消息符号，其出现的概率P(X)=0.1,0.18,0

15、.4,0.05,0.06,0.1,0.07,0.04，则求(1)该信源在每秒内发出一个符号，求该信源的熵及信息传输速率；(2)对这8个符号作哈夫曼编码，写出相应码字，并求出编码效率；(3)进行香农编码，写出相应码字，并求出编码效率；(4)进行费诺编码，写出相应码字，并求出编码效率；解：（1）信源熵比特/符号信息传输速率(2)对这8个符号作哈夫曼编码所编码为1，001，011，0000，0100，0101，00010，00011；平均码长码符号/信源符号编码效率（3）香农编码编码过程：所编码为00，011，1001，1010，1100，11011，11101，11110；平均码长码符号/信源符号

16、编码效率（4）费诺编码所编码为00，01，100，101，1100，1101，1110，1111；平均码长码符号/信源符号编码效率补充1：几种实用的无失真信源编码方法MH编码MH编码是用于黑白二值文件传真的数据压缩编码。它是一维编码方案。它将游程编码和哈夫曼编码相结合的一种标准的改进哈夫曼码。游程编码是无失真信源编码，二元序列编成多元码在二元序列中，只有“0”和“1”两个码元，我们吧连续出现的“0”叫做“0”游程，连续出现的“1”叫做“1”游程。连续出现“0”或者“1”码元的个数叫做游程长度。这样，一个二元序列可以转换成游程序列，例如：二元序列0001100111100010可以变换成3224

17、311，若规定游程必须从“0”游程开始，则上述变换是可逆的。如果连“0”或连“1”非常多，则可以达到信源压缩的目的。游程编码是无失真信源编码算术编码算术编码也是一种无失真信源编码方法。前面讨论的无失真信源编码方法，都是针对单个信源符号的编码，当信源符号之间有相关性时，这些编码方法由于没有考虑到符号之间的相关性，因此编码效率就不可能很高。解决的办法是对较长的信源序列进行编码，但会遇到与定长编码时同样的问题。而且，采用前面的序列编码需要完全知道联合概率和条件概率，这在场合下也是比较困难的。为了解决这个问题，需要跳出分组码的局限，研究非分组码。算术编码就是一种非分组编码方法。其基本思路是：从全序列出

18、发，将不同的信源序列的累计概率映射到0，1区间上，使每个序列对应区间上的一点，也就是说，把区间0，1分成许多互不重叠的小区间，不同的信源序列对应不同的小区间，可以证明，只要这些小区间互不重叠，就可以编得即时码。这种编码方法无需计算出所有信源序列的概率分布及编出码表，可以直接对输入的信源符号序列进行编码输出。LZ码LZ码是一种通用编码方法，无需知道信源的统计特性，而且编码效率很高。基本算法是：将长度不同的符号串编成一个新的短语(符号串)，形成短语词典的索引表。LZ78是一种分段编码，它的短语词典是由前面已见到的文本字段来定义的。(续上)补充2：几种常用的限失真信源编码方法：矢量量化连续信源进行编

19、码的主要方法是量化，即将连续的样值离散化成为。n是量化级数，这样就把连续值转化为n个实数中的一个，可以用0，1，2，n等n个数字来表示。由于是一个标量，因此称为标量量化。在量化的过程中，将会引入失真，量化是必须使这些失真最小。要想得到更好的性能，仅采用标量量化是不可能的。从前面的讨论我们已经知道，把多个信源符号组成一个符号序列进行联合编码可以提高编码效率。连续信源也是如此，当把多个信源符号联合起来形成多维矢量，然后进行量化，可以进一步压缩码率，这种量化方法叫做矢量量化。实验证明，即使各信源符号相互独立，矢量量化也可以压缩信息率，因此，人们对矢量量化非常感兴趣，是当前信源编码的一个热点，而且不仅

20、限于连续信源，对离散信源也可以如此。如图像编码时采用矢量量化，但由于联合概率密度不易测定，目前常用的是训练序列的方法，如图像编码时就要采用训练序列的方法，找到其码书，进行量化。还可以与神经网络方法结合，利用神经网络的自组织来得到训练集。预测编码预测就是从已收到的符号来提取关于未收到的符号的信息，从而预测其最可能的制作为预测值。并把它与实际值之差进行编码，由于这个差值一般都比较小，所以在编码时会出现很多连“0”值，再采用游程编码，就可以大大地压缩码率。由此可见，预测编码是利用信源符号之间的相关性来压缩码率的，对于独立信源，预测就没有可能。6变换编码变换是一个广泛的概念。变换编码就是经变换后的信号

21、能更有效地编码，也就是通过变换来解除或减弱信源符号间的相关性，以达到压缩码率的效果（如单频率正弦波信号，变换到频域）。一般地，对一个函数，变换式为：而反变换为：要使上式成立，要求必须是正交完备的（相当于欧氏空间的坐标投影），求的公式，实际上就是内积运算，把函数投影到上去。信源编码常用的变换有：DCT（discreteCosineTransform）变换：如JPEG、MPEG等图像压缩标准中，就是主要采用的这种变换压缩方法。K-L变换：K-L变换是均方误差准则下的最佳变换。它是一种正交变换，变幻后的随机变量之间互不相关，一般认为，K-L变换是最佳变换，其最大缺点是计算复杂，除了需要测定相关函数和

22、解积分方程外，变换时的运算也十分复杂，也没有快速算法，因此，K-L变换不是一种实用的变换编码方法，但经常用来作为标准，评估其他方法的优劣。（3）小波（WaveletTransform）变换：小波变换是当前信号处理以及多种应用科学中广泛用到的一种相当有效的数学工具。小波变换的概念首先是由法国的石油地质工程师J.Morlet于1980年提出的，1990年Mallat等人一起建立了多分辩分析的概念。与经典的Fourier分析相比较，小波的最大优势是变换本身具有时间与频率的双重局部性质，解决了Fourier分析不能处理的许多实际问题，因而小波变换被人们称之为“数学显微镜”。20世纪90年代中期以前，图

23、像压缩主要采用离散余弦变换(DCT)技术，著名的JPEG、H.263等图像压缩国际标准均采用DCT方法实现图像压缩。而DCT最大的缺陷是当压缩比较大时，会出现马赛克效应，因而影响图像压缩质量。最近几年来，由于小波变换具有DCT无可比拟的良好压缩性质，在最新推出的静态图像压缩国际标准JPEG2000中，9/7双正交小波变换已经正式取代DCT而作为新的标准变换方法。（4）分形（FractalTransform）变换：基于块的分形编码是一种利用图像的自相似性来减少图象冗余度的新型编码技术，它具有以下特点：较高的压缩比。解码图象的分辨率无关性。可按任意高于或低于原编码图象的分辨率来进行解码。当要解码成

24、较高分辨率图象时，引入的细节会与整个图象大致和谐一致，从而比象素复制或插值方法得到的图象看起来更自然。这种缩放能力也可以用作图象增强工具。解码速度快。分形压缩是一非对称过程，虽然编码很耗时，但解码速度快，因此较适用于一次编码多次解码的应用中。编码时间过长，实时性差，从而阻碍了该方法在实际中的广泛应用。还有很多其他的编码方法，这里就不再一一介绍了。补充3：香农第二定理信道编码定理1、有噪信道编码定理如一个离散无记忆信道，信道容量为C。当信息传输率RC时，只要码长足够长，总可以找到一种信道编码方法，使信道输出端的平均错误译码概率达到任意小。2、有噪信道编码逆定理如一个离散无记忆信道，信道容量为C。

25、当信息传输率RC时，则无论码长n多长，总找不到一种编码方法，使信道输出端的平均错误译码概率达到任意小。这个定理是信道编码的理论依据，可以看出：信道容量是一个明确的分界点，当取分界点以下的信息传输率时，信道输出端误码率以指数趋进于0；当取分界点以下的信息传输率时，输出端误码率以指数趋进于1；因此在任何信道中，信道容量都是可达的、最大的可靠信息传输率。这个定理是一个存在定理，它没有给出一个具体可构造的编码方法，在它的证明过程中，码书是随机的选取的，它有助于指导各种通信系统的设计，有助于评价各种系统及编码的效率。补充4：无噪信道编码定理无失真信源编码定理失真信源编码定理通常又称为无噪信道编码定理。此

26、定理可以表述为：若信道的信息传输率R不大于信道容量C，总能对信源的输出进行适当的编码，使得在无噪无损信道上能无差错地以最大传输率C传输信息；但要使信道的信息传输率R大于C而无差错地传输信息是不可能的。补充5：若有一信源每秒钟发出2.66个信源符号。将此信源的输出符号送入某一个二元信道中进行传输(假设信道是无噪无损的)，二信道每秒钟传递二个二元符号。试问此信源不通过编码能否直接与信道连接？若通过适当编码能否在信道中进行无失真传输？若能连接，使说明如何编码并说明原因。解：信源其信源熵比特/符号而其每秒钟发2.66个信源符号，所以信源输出的信息速率为送入一个二元无噪无损信道，此信道的最大信息传输率(

27、信道容量)C=1比特/符号。而信道每秒钟只传送两个二元符号，所以信道的最大信息传输速率可见，根据无噪信道编码定理（即无失真信源编码定理），因为，所以总能对信源的输出进行适当的编码，使此信源在此信道中进行无失真传输。如果对信源不进行编码，直接将信源符号s1以0符号传送，s2以1符号传送，这时因为信源输出为2.66二元信源符号/秒，大于2二元信道符号/秒，就会使信道输入端造成信源符号的堆积，信息不能按时发送出去。所以，不通过编码此信源不能直接与信道连接。若要连接，必须对信源的输出符号序列进行编码，也就是对此信源的N次扩展信源进行编码。但扩展次数N越大，编码越复杂，设备代价越大，所以尽量使扩展次数N

28、小，而又能使信源在此信道中无失真传输。先考虑N=2，并对二次扩展信源进行哈夫曼编码，得得二元符号/信源序列二元符号/信源符号二次扩展编码后，送入信道的传输速率为所以，必须考虑N=3即对三次扩展信源进行哈夫曼编码，得得二元符号/信源序列二元符号/信源符号二次扩展编码后，送入信道的传输速率为此时，就可以在此信道中进行无失真传输了。补充6：若有一信源每秒钟发出2.66个信源符号。将此信源的输出符号送入某一个二元信道中进行传输(假设信道是无噪无损的)，二信道每秒钟传递二个二元符号。(1)试问此信源能否在此信道中无失真传输。(2)若此信源失真测度定义为汉明失真，问允许信源平均失真为多大时，此信源就可以在

29、此信道中传输。解：(1)信源其信源熵比特/符号而其每秒钟发2.66个信源符号，所以信源输出的信息速率为送入一个二元无噪无损信道，此信道的最大信息传输率(信道容量)C=1比特/符号。而信道每秒钟只传送两个二元符号，所以信道的最大信息传输速率可见，根据无噪信道编码定理（即无失真信源编码定理），因为，所以不论进行任何编码此信源都不可能在此信道中实现无失真的传输，所以信源在此信道中传输会引起错误和失真。（2）若此信源失真测度定义为汉明失真，因为是二元信源，输入是等概分布，所以信源地信息率失真函数为比特/信源符号比特/秒若则此信源在此信道中传输时不会引起错误。也就是不会因为信道而增加信源新的失真。总的信源的失真是信源压缩编码所造成的允许失真D。所以有故D=0.0415允许信源平均失真为D=0.0415时，此信源就可以在此信道中传输补充7：为了传输一个由字母A，B，C，D组成的符号集，把每个字母编码成二元码脉冲序列，以“00”代表A，“01”代表B，“10”代表C，“11”代表D，每个二元码脉冲宽度为5ms，不同字母等概率出现时，计算传输的信息速率？若每个字母出现的概率分别为，试计算传输的信息速率。解：（1）不同字母等概率出现时，符号集的概率空间为：每个符号含有的平均信息量即熵为：比特/符号（字母）现在用两个二元码脉冲代表1个字母，每个二元码脉冲