信息论与编码答案.doc 35页

'《信息论与编码》-曹雪虹-课后习题答案第二章2.1一个马尔可夫信源有3个符号，转移概率为：，，，，，，，，，画出状态图并求出各符号稳态概率。解：状态图如下状态转移矩阵为：设状态u1，u2，u3稳定后的概率分别为W1，W2、W3由得计算可得2.2由符号集{0，1}组成的二阶马尔可夫链，其转移概率为：=0.8，=0.2，=0.2，=0.8，=0.5，=0.5，=0.5，=0.5。画出状态图，并计算各状态的稳态概率。解： 于是可以列出转移概率矩阵：状态图为：设各状态00，01，10，11的稳态分布概率为W1,W2,W3,W4有得计算得到2.3同时掷出两个正常的骰子，也就是各面呈现的概率都为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)2-4 2.5居住某地区的女孩子有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厘米以上的某女孩是大学生的信息量即：2.6掷两颗骰子，当其向上的面的小圆点之和是3时，该消息包含的信息量是多少？当小圆点之和是7时，该消息所包含的信息量又是多少？解：1）因圆点之和为3的概率该消息自信息量2）因圆点之和为7的概率该消息自信息量 2.7设有一离散无记忆信源，其概率空间为（1）求每个符号的自信息量（2）信源发出一消息符号序列为{202120130213001203210110321010021032011223210}，求该序列的自信息量和平均每个符号携带的信息量解：同理可以求得因为信源无记忆，所以此消息序列的信息量就等于该序列中各个符号的信息量之和就有：平均每个符号携带的信息量为bit/符号2.8试问四进制、八进制脉冲所含信息量是二进制脉冲的多少倍？解：四进制脉冲可以表示4个不同的消息，例如：{0,1,2,3}八进制脉冲可以表示8个不同的消息，例如：{0,1,2,3,4,5,6,7}二进制脉冲可以表示2个不同的消息，例如：{0,1}假设每个消息的发出都是等概率的，则：四进制脉冲的平均信息量八进制脉冲的平均信息量二进制脉冲的平均信息量所以：四进制、八进制脉冲所含信息量分别是二进制脉冲信息量的2倍和3倍。2-9“－”用三个脉冲“●”用一个脉冲(1)I(●)=I(－)＝(2)H=2-10(2)P(黑/黑)=P(白/黑)=H(Y/黑)=(3)P(黑/白)=P(白/白)= H(Y/白)=(4)P(黑)=P(白)=H(Y)=2.11有一个可以旋转的圆盘，盘面上被均匀的分成38份，用1，…，38的数字标示，其中有两份涂绿色，18份涂红色，18份涂黑色，圆盘停转后，盘面上的指针指向某一数字和颜色。（1）如果仅对颜色感兴趣，则计算平均不确定度（2）如果仅对颜色和数字感兴趣，则计算平均不确定度（3）如果颜色已知时，则计算条件熵解：令X表示指针指向某一数字，则X={1,2,……….,38}Y表示指针指向某一种颜色，则Y={l绿色，红色，黑色}Y是X的函数，由题意可知（1）bit/符号（2）bit/符号（3）bit/符号2.12两个实验X和Y，X={x1x2x3},Y={y1y2y3},l联合概率为（1）如果有人告诉你X和Y的实验结果，你得到的平均信息量是多少？（2）如果有人告诉你Y的实验结果，你得到的平均信息量是多少？（3）在已知Y实验结果的情况下，告诉你X的实验结果，你得到的平均信息量是多少？解：联合概率为YXy1y2y3x17/241/240x21/241/41/24x301/247/24=2.3bit/符号X概率分布 Xx1x2x3P8/248/248/24bit/符号Y概率分布是=0.72bit/符号Yy1y2y3P8/248/248/242.13有两个二元随机变量X和Y，它们的联合概率为YXx1=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) 2-14(1)P(ij)=P(i/j)=(2)方法1:=方法2:2-15P(j/i)=2.16黑白传真机的消息元只有黑色和白色两种，即X={黑，白}，一般气象图上，黑色的出现概率p(黑)＝0.3，白色出现的概率p(白)＝0.7。（1）假设黑白消息视为前后无关，求信源熵H(X)，并画出该信源的香农线图（2）实际上各个元素之间是有关联的，其转移概率为：P(白|白)＝0.9143，P(黑|白)＝0.0857，P(白|黑)＝0.2，P(黑|黑)＝0.8，求这个一阶马尔可夫信源的信源熵，并画出该信源的香农线图。（3）比较两种信源熵的大小，并说明原因。解：（1）bit/符号P(黑|白)=P(黑) P(白|白)＝P(白)P(黑|黑)＝P(黑)P(白|黑)＝P(白)（2）根据题意，此一阶马尔可夫链是平稳的（P(白)＝0.7不随时间变化，P(黑)＝0.3不随时间变化）＝0.512bit/符号2.17每帧电视图像可以认为是由3Í105个像素组成的，所有像素均是独立变化，且每像素又取128个不同的亮度电平，并设亮度电平是等概出现，问每帧图像含有多少信息量？若有一个广播员，在约10000个汉字中选出1000个汉字来口述此电视图像，试问广播员描述此图像所广播的信息量是多少（假设汉字字汇是等概率分布，并彼此无依赖）？若要恰当的描述此图像，广播员在口述中至少需要多少汉字？解：1)2)3)2.20给定语音信号样值X的概率密度为,,求Hc(X)，并证明它小于同样方差的正态变量的连续熵。解： 2.24连续随机变量X和Y的联合概率密度为：，求H(X),H(Y),H(XYZ)和I(X;Y)。（提示：）解： 2.25某一无记忆信源的符号集为{0,1}，已知P(0)=1/4，P(1)=3/4。(1)求符号的平均熵；(2)有100个符号构成的序列，求某一特定序列（例如有m个“0”和（100-m）个“1”）的自信息量的表达式；(3)计算(2)中序列的熵。解：(1)(2)(3)2-26 P(i)=P(ij)=H(IJ)=2.29有一个一阶平稳马尔可夫链,各Xr取值于集合,已知起始概率P(Xr)为，转移概率如下图所示ji1231231/22/32/31/401/31/41/30(1)求的联合熵和平均符号熵(2)求这个链的极限平均符号熵(3)求和它们说对应的冗余度解：（1）符号X1，X2的联合概率分布为12311/41/81/821/601/1231/61/12012314/245/245/24X2的概率分布为那么=1.209bit/符号 X2X3的联合概率分布为12317/247/487/4825/3605/1235/365/120那么=1.26bit/符号/符号所以平均符号熵／符号（2）设a1,a2,a3稳定后的概率分布分别为W1,W2,W3,转移概率距阵为由得到计算得到又满足不可约性和非周期性/符号(3)/符号/符号/符号 2-30(1)求平稳概率P(j/i)=解方程组得到(2)信源熵为:2-31P(j/i)=解方程组得到W1=,W2=,W3= 2.32一阶马尔可夫信源的状态图如图2－13所示，信源X的符号集为（0，1，2）。（1）求信源平稳后的概率分布P(0),P(1),P(2)（2）求此信源的熵（3）近似认为此信源为无记忆时，符号的概率分布为平稳分布。求近似信源的熵H(X)并与进行比较解:根据香农线图,列出转移概率距阵令状态0,1,2平稳后的概率分布分别为W1,W2,W3得到计算得到由齐次遍历可得符号由最大熵定理可知存在极大值 或者也可以通过下面的方法得出存在极大值:又所以当p=2/3时0所以第二个实验比第一个实验好P(y1y2x)0001101101/40001001/40201/401/4（2）因为Y1和Y2相互独立，所以P(y1y2|x)000110110100010010201/201/2y1y200011011p1/41/41/41/4 bit/符号=1.5bit/符号由此可见，做两个实验比单独做Y1可多得1bit的关于X的信息量，比单独做Y2多得0.5bit的关于X的信息量。（3）=1.5-1=0.5bit/符号表示在已做Y2的情况下，再做Y1而多得到的关于X的信息量同理可得=1.5-0.5=1bit/符号表示在已做Y1的情况下，再做Y2而多得到的关于X的信息量欢迎下载！第三章3.1设二元对称信道的传递矩阵为(1)若P(0)=3/4,P(1)=1/4，求H(X),H(X/Y),H(Y/X)和I(X;Y)；(2)求该信道的信道容量及其达到信道容量时的输入概率分布；解：1) 2)其最佳输入分布为3-2某信源发送端有2个符号，，i＝1，2；，每秒发出一个符号。接受端有3种符号，j＝1，2，3，转移概率矩阵为。（1）计算接受端的平均不确定度；（2）计算由于噪声产生的不确定度；（3）计算信道容量。解：联合概率XY0则Y的概率分布为Y（1） 取2为底（2）取2为底取e为底=03.3在有扰离散信道上传输符号0和1，在传输过程中每100个符号发生一个错误，已知P(0)=P(1)=1/2，信源每秒内发出1000个符号，求此信道的信道容量。解： 由题意可知该二元信道的转移概率矩阵为：为一个BSC信道所以由BSC信道的信道容量计算公式得到：3.4求图中信道的信道容量及其最佳的输入概率分布.并求当=0和1/2时的信道容量C的大小。X0Y0111221－1－解:信道矩阵P=,此信道为非奇异矩阵,又r=s,可利用方程组求解=(i=1,2,3)解得所以C=log=log[20+2×2(1-)log(1-)+]=log[1+21-H()]=log[1+2] 而(j=1,2,3)得所以P(a1)=P(b1)=当=0时,此信道为一一对应信道,得C=log3,当=1/2时,得C=log2,,3.5求下列二个信道的信道容量，并加以比较（1）（2）其中p+=1解：（1）此信道是准对称信道，信道矩阵中Y可划分成三个互不相交的子集由于集列所组成的矩阵,而这两个子矩阵满足对称性，因此可直接利用准对称信道的信道容量公式进行计算。C1=logr-H(p1’p2’p3’)-其中r=2,N1=M1=1-2N2=M2=4所以C1=log2-H(,p-ε,2ε)-(1-2)log(1-2)-2log4=log2+()log()+(p-ε)log(p-ε)+2εlog2ε-(1-2ε)log(1-2ε)-2εlog4ε=log2-2εlog2-(1-2ε)log(1-2ε)+()log()+(p-ε)log(p-ε)=(1-2ε)log2/(1-2ε)+()log()+(p-)log(p-) 输入等概率分布时达到信道容量。（2）此信道也是准对称信道，也可采用上述两种方法之一来进行计算。先采用准对称信道的信道容量公式进行计算，此信道矩阵中Y可划分成两个互不相交的子集，由子集列所组成的矩阵为，这两矩阵为对称矩阵其中r=2,N1=M1=1-2N2=M2=2，所以C=logr-H(-,p-ε,2ε,0)-=log2+(-)log(-)+(p-ε)log(p-ε)+2εlog2ε-(1-2ε)log(1-2ε)-2εlog2ε=log2-(1-2ε)log(1-2ε)+(-)log(-)+(p-ε)log(p-ε)=(1-2ε)log2/(1-2ε)+2εlog2+(-)log(-)+(p-ε)log(p-ε)=C1+2εlog2输入等概率分布（P（a1）=P（a2）=1/2）时达到此信道容量。比较此两信道容量，可得C2=C1+2εlog23-6设有扰离散信道的传输情况分别如图3－17所示。求出该信道的信道容量。解：对称信道取2为底bit/符号 3-7(1)条件概率，联合概率，后验概率，，（2）H(Y/X)=（3）当接收为y2，发为x1时正确，如果发的是x1和x3为错误，各自的概率为：P(x1/y2)=，P(x2/y2)=，P(x3/y2)=其中错误概率为：Pe=P(x1/y2)+P(x3/y2)=（4）平均错误概率为（5）仍为0.733（6）此信道不好原因是信源等概率分布，从转移信道来看正确发送的概率x1-y1的概率0.5有一半失真x2-y2的概率0.3有失真严重x3-y3的概率0完全失真（7）H(X/Y)=3.8设加性高斯白噪声信道中，信道带宽3kHz，又设{(信号功率+噪声功率)/噪声功率}=10dB。试计算该信道的最大信息传输速率Ct。解： 3.9在图片传输中，每帧约有2.25Í106个像素，为了能很好地重现图像，能分16个亮度电平，并假设亮度电平等概分布。试计算每分钟传送一帧图片所需信道的带宽（信噪功率比为30dB）。解：3-10一个平均功率受限制的连续信道，其通频带为1MHZ，信道上存在白色高斯噪声。（1）已知信道上的信号与噪声的平均功率比值为10，求该信道的信道容量；（2）信道上的信号与噪声的平均功率比值降至5，要达到相同的信道容量，信道通频带应为多大？（3）若信道通频带减小为0.5MHZ时，要保持相同的信道容量，信道上的信号与噪声的平均功率比值应等于多大？解：（1）（2）（3）欢迎下载！第四章4.2某二元信源其失真矩阵为求这信源的Dmax和Dmin和R(D)函数。 解：因为二元等概信源率失真函数：其中n=2,所以率失真函数为：4.3一个四元对称信源，接收符号Y={0,1,2,3}，其失真矩阵为，求Dmax和Dmin及信源的R(D)函数，并画出其曲线（取4至5个点）。解：因为n元等概信源率失真函数：其中a=1,n=4,所以率失真函数为：函数曲线：其中： 4-3信源熵为Dmax=min{,,,}R(Dmax)=0Dmin=0R(Dmin)=R(0)=H(X)=log(4)=2只要满足p(y1)+p(y2)+p(y3)+p(y4)=1在[0,1]区间可以任意取值。欢迎下载！第五章5-1将下表所列的某六进制信源进行二进制编码，试问：消息概率u1u2u3u4u5u61/21/41/161/161/161/160000010100111001010010110111011110111110101101110111101111100101101110010011111100000101011011001001100101110111(1)这些码中哪些是唯一可译码？(2)哪些码是非延长码？(3)对所有唯一可译码求出其平均码长和编译效率。解：首先，根据克劳夫特不等式，找出非唯一可译码 不是唯一可译码，而：又根据码树构造码字的方法，，的码字均处于终端节点他们是即时码5-2(1)因为A,B,C,D四个字母,每个字母用两个码,每个码为0.5ms,所以每个字母用10ms当信源等概率分布时,信源熵为H(X)=log(4)=2平均信息传递速率为bit/ms=200bit/s(2)信源熵为H(X)==0.198bit/ms=198bit/s5-5 (1)H(U)=(2)每个信源使用3个二进制符号,出现0的次数为出现1的次数为P(0)=P(1)=(3)(4)相应的香农编码信源符号xi符号概率pi累加概率Pi-Logp(xi)码长Ki码字x11/20110x21/40.52210x31/80.7533110x41/160.875441110x51/320.9385511110x61/640.96966111110x71/1280.984771111110x81/1280.9927711111110相应的费诺码信源符号xi符号概率pi第一次分组第二次分组第三次分组第四次分组第五次分组第六次分组第七次分组二元码x11/200x21/41010x31/810110x41/16101110x51/321011110x61/6410111110x71/128101111110x81/128111111110 （5）香农码和费诺码相同平均码长为编码效率为：5-11（1）信源熵（2）香农编码：信源符号xi符号概率pi累加概率Pi-Logp(xi)码长Ki码字x10.3201.644200x20.220.322.1843010x30.180.542.4743100x40.160.722.6443101x50.080.883.64441110x60.040.964.644511110平均码长：编码效率为（3）费诺编码为信源符号xi符号概率pi1234编码码长x10.3200002x20.221012x30.1810102x40.16101103x50.081011104x60.04111114平均码长为：编码效率：（4）哈夫曼编码信源符号编码过程编码 xi符号概率pi码长x10.320.320.380.400.601012x20.220.220.320.380.40102x30.180.180.220.32112x40.160.160.180003x50.080.1200104x60.0400114平均码长为：编码效率：5.16已知二元信源{0，1}，其p0=1/4,p1=3/4,试用式（4.129）对序列11111100编算术码，并计算此序列的平均码长。解：根据算术编码的编码规则，可得：P(s=11111100)=P2(0)P6(1)=(3/4)6(1/4)2根据（4.129）可得：F(S)=P(0)+P(10)+P(110)+P(1110)+P(11110)+P(111110)=1–=1–P(11111111)–P(11111110)–P(11111101)–P(11111100)=1–P(111111)=1–(3/4)6=0.82202=0.110100100111又P(S)=A(S)=0.0000001011011001，所以F(S)+P(S)=0.1101010即得C=0.1101010得S的码字为1101010平均码长为0.875。欢迎下载！'