信息论与编码C

《信息论与编码C》由会员分享，可在线阅读，更多相关《信息论与编码C（7页珍藏版）》请在装配图网上搜索。

1、制作人：陈瑞焦良葆年月曰填空题（本题15空，每空1分，共15分）设信源X包含n个不同离散消息，当且仅当X中各个消息出现的概率（相等）时,信源熵达到最大值，为（log2n ）。丄迓H （X离散平稳有记忆信源的平均符号熵Hn （X）的表达式为（N “=1| X nT)1 )，极限熵H的表达式为（oolim h( x i X N-1)N 1N s）。如纠错码的最小距离为d .，则可以检出任意小于等于（d 1 ） inmin个随机差错,可以纠正任意小于等于（d i 1） /2 ）个随机差错。min一个（2， 1， 3）卷积码的约束长度为（3 ），共有（8 ）种状态。卷积码的自由距离的定义为（任意长度卷

2、积码编码后序列之间的最小汉明距离），可用（网格图）法和（梅森公式）法计算自由距离。根据密码算法所使用的加密密钥和解密密钥是否相同，可将密码体制分成（对称密码体制）和（非对称密码体制）。算术编码是发展迅速的一种（无）失真信源编码方法，其基本思想是（将一定精度的数值作为序列的编码）。一 判断题（本题10小题,每小题1分，共10分）1. 72. 73. 74. 75. x6. x7. 78. x9. 710. x（1）离散信源的最大熵的值取决于符号状态数，状态数越多，熵越大。（）（2）只要已知某一个信源符号的先验概率及相应的转移概率，就可以得到相应的互信息量。（）（3）限失真信源编码逆定理说明在允许

3、失真D的条件下，信源最小的、可达的信息传输率是信源的R（D）。（）（4） 如X可以唯一确定Y,则H（Y/X）=O。（）（5）马尔可夫序列的联合概率具有时间推移不变性。（）（6） 码组0，01，011，0111属于不等长的即时码。（）（7） 极限熵H =有记忆信源的最小平均消息熵。（）00（8）若码么=101111，111100，则和P之间的汉明距离为D，P）二3。（）（9）设（7, 4）循环码的生成多项式为g（x）=x3+x+1，当接收码字为0010011时，接收码字中有错。（）（10）条件熵H（Y/X）称为疑义度，可疑度，它表示接收者收到Y后，对信源X仍然存在的平均不确定度。（）三 名词解释

4、（本题4小题,每小题5分，共20分）1汉明码汉明码失纠错能力t=1的一类码的统称，其n，k的值服从规律：（n,k）=（2m-1,2m-1-m）。2算术编码从全序列出发，将各信源序列的概率映射到0，1区间，使每个序列对应到区间上的一点, 这些点将区间分成若干小段，每段的长度对应某一序列的概率。再在段内取一个二进制小 数，其长度与该序列的概率匹配，达到高效率编码的目的。3检错重传在接收端根据编码规则进行检查，如果发现规则被破坏，则通过反向信道要求发送端重新 发送，直到接收端检查无误为止。4噪声熵条件熵H（Y/X）可看作唯一地确定信道噪声所需要的平均信息量，因此也称为噪声熵或散 步度。四计算题（本题

5、3小题，共25分）1.设（7, 4）循环码的生成多项式g（x） = x3 + x +1，求：1）监督多项式；2）此循环码的生成矩阵（非系统码和系统码形式）；3）一致监督矩阵；4）若输入u（x）二1 + x2 + x3，试求系统码形式的输出码字。（2+4+2+2=10 分）解：1）已知循环码（7,4），用1 + x + x3去除1 + x7得到监督多项式h x）2）非系统码的生成矩阵G=x 3.g ( x)x3 + x 4 + x 6x 2.g ( x)x 2 + x3 + x5x.g (x)x + x 2 + x 4_ g (x)_1 + x + x3x 6 + r (x)6x 6 + x 2

6、 + 1xn-1 + r(x)n-1x 5 + r (x)5x5 + x2 + x + 1xn - 2 + r(x)n-2x 4 + r (x)4x 4 + x 2 + x系统G=xn - k + r(x)一n 一 k一=x 3 + r (x)L3J=x 3 + x + 1rn - i是g （X）除xn-i所得的余式3)H=x2 - h(x)x - h( x) h( x)x 6 + x 4 + x 3 + x 2x 5 + x 3 + x 2 + xx 4 + x 2 + x + 1C(X)=r(x)+ xn-ku(x) xn-ku(x) = x j4 . (x3 + x2 + 1) = x6

7、 + x5 + x3r(x)= xn-ku(x)mod g (x) = x6 + x5 + x3 + 1=11010011）信道容量C的定义式什么？2） 求该信道的信道容量C。（3+3=6分）c = max i （ x ； y ）解：1）信道容量的定义式为：p（xi）（3分）1已知离散无记忆信源s -_ P(s)_1)求信源熵H (S)；2)进行哈夫曼编码，并求平均码长和编码效率;c = max i( x ； y)丄丄丄丄 12)p(xi)=log24H( 2 4 8 8 )=2 2 log22 4 log24 8 log28 8 log28=0.25 3 已知 X, YW0, 1, XY 构

8、成的联合概率为 p (00) =p (11) =1/8, p (01) =p (10)=3/8，试计算熵 H (X), H (XY), H (X/Y)。(9 分) 解：p(0)=p(00)+p(01)=l/8+3/8=l/2 p(l)=p(10)+p(ll)=l/8+3/8=l/2 q(0)=p(00)+p(10)=l/8+3/8=l/2 q(1)=p(01)+p(11)=3/8+1/8=1/2 H(X)=1/21og22+1/21og22=1bit/ 符号H(XY)=2 X 1/8log28+2 X 3/8log28/3=1.8bit/ 符号H(X/Y)=左1譬log嚳dog竺芻og竺j=0

9、 i=0 曲)曲)2X 1/2 S/8+2X 1/2 幻/8 2.89bit/ 符号五综合题(本题3小题，共30分)vS小S . S彳S lS /*123. 45603020150.150101，试求.3)哈夫曼编码是否唯一？如果不唯一，哪种编码方法更佳？ (3+4+3=10分)-Y P(s)log P(s)解：1)H(S)= i= - 0.3l og20.3 - 0.2log20.2 - 2 X 0.15log20.15 - 2 X 0.1log20.1=2.47bit/ 符号2)符号s5s6概率编码0001011K=0.3 X 2+0.2 X 2+0.15 X 3+0.15 X 3+0.1

10、 X 3+0.1 X 3=2.5H (S)2.47q =K = 2.5 =98.8%3)由于按照概率大小顺序排队方法的不惟一，哈夫曼编码不惟一。将新合并的等概率消息 排列到上支路(即大概率位置)，可以证明它将有利于缩短码长的方差，即编出的码更接 近于等长码，这种编码方法更佳。2 一个二进制(r=2)二阶(m=2)马尔柯夫信源的原始信源为X0, 1,这时的状态空间为: S=S口其一步转移概率为：0/0000p(0/00)P(0/SJP(S1/S1)=0.81/0001p(1/00)P(1/SJp(S2/S1)=0.20/0110p(0/01)P(0/S2)P(S3/S2)=0.51/0111p(

11、1/01)P(1/S2)p(S4/S2)=0.50/1000p(0/10)P(0/S3)p(S1/S3)=0.51/1001p(1/10)P(1/S3)p(S2/S3)=0.50/1110p(0/11)P(0/S4)p(S3/S4)=0.21/1111p(1/11)P(1/S4)p(S4/S4)=0.8试：1)画出信源的状态转移图；2) 求各状态的稳态概率Wi；3) 计算该马尔可夫信源的极限熵。(3+3+4=10分)阵为：0.80.200000.50.5P(1)=0.50.500000.20.8根据各态历经定理的有:p(S1)0.800.50p(S2)0.200.50p(S3)00.500.5

12、p(S4)00.500.8p(Sl)+p(S2)+p(S3)+p(S4)=lp(S1)p(S2)p(S3)p(S4)和 p(Si)0 (i=1,2,3,4)2)由状态图可以判断，这是一个非周期不可闭集，具有各态历经性, 方法同样可以判断，存在状态极限概率。其约束条件为：解得其极限概率分别为：p(S1)=p(S4)=5/14; p(S2)=p(S3)=2/143)由极限概率和状态转移概率就可以计算马尔柯夫信源的极限熵:於 4 p (Si) p (Sj / Si) log p (Sj / Si) = 0.8bit / fuhaoi=1 j=13已知一个(7, 3)线性分组码的生成矩阵为1)2)3)4)，求:求一致校验阵H； 求出码字空间集合； 计算该线性分组码的最小距离d.。min接收到的码字为R1=0010100，如何判断是否有错?(3+3+2+2=10 分)1011000111010011000100110001解：1) H=2) C=u G=(u0u1u2)G=(0000000)(0011101)(0100111)(0111010)(1001110)(1010011)(1101001) (1110100)3) d(C,c2) =W(C C2)=44) TR-HF=(0010100) R有错。1110011011011000010000100001=101工0