《信息论、编码与密码学》课后习题答案Word格式.doc
《《信息论、编码与密码学》课后习题答案Word格式.doc》由会员分享，可在线阅读，更多相关《《信息论、编码与密码学》课后习题答案Word格式.doc（48页珍藏版）》请在冰点文库上搜索。
则熵为：
=？
1.8计算概率分布函数为
的均匀分布随机变量的微分熵。
画出相对于参数的平面图，并对结果进行评论。
根据公式（1-21）可知，微分熵为：
当时，，则
当或时，，则
根据得到的结果可以画出相应的平面图，由图可以看到随着的增加，即的减小，微分熵相应的增加。
0.1
10
1.9考虑一个信源的概率为的DMS。
（1）给出此信源的霍夫曼码。
（2）计算出这些码子的平均码长。
（3）这个码的效率是多少？
1）依题意，由霍夫曼编码的规则，得：
1.00
0.65
0.40
0.20
0.35
0.25
0.20
0.15
0.05
表格如下：
符号
概率
自信息
码字
0.35
1.515
0.25
2.000
01
2.322
000
0.15
2.738
0010
0.05
4.322
0011
2）由平均码长公式,代入数据，得：
3）首先，该信源的熵为：
该码的效率为：
1.10考虑一个信源概率为{0.35，0.20，0.15，0.15，0.10，0.10，0.05，0.05}的DMS。
（1）给出此信源的一种有效定长码。
（2）给出此信源的霍夫曼码。
（3）比较这两种码并给出评论。
1）空
2）依题意，由霍夫曼编码的规则，得:
001
100
0.10
1.000
101
110
1110
1111
3）空
1.11一个DMS只有三个输出符号，它们的概率为{0.5，0.4，0.1}。
（1）给出此信源的霍夫曼码并确定编码效率。
（2）每次考虑两个符号时，给出此信源的霍夫曼码并确定编码效率。
（3）每次考虑三个符号时，给出此信源的霍夫曼码并确定编码效率。
（1）本题的霍夫曼编码如下图所示：
0.5
0.4
1.0
图1.11霍夫曼编码
则霍夫曼码如下表：
x1
x2
00
x3
该信源的熵为：
平均每个符号的比特数为：
该码的效率为：
（2）把符号每两个分一组，重新应用霍夫曼编码算法，如下表所示：
符号对
x1x1
x1x2
010
x2x1
011
x2x2
0.16
1010
x1x3
x3x1
x2x3
0.04
1011
x3x2
x3x3
0.01
每个组的平均比特数为:
故该码的效率为：
（3）依题意，把符合每三个分成一组，再重新应用霍夫曼编码算法，得:
编码表格如下：
0.1250
2.7090
0.1000
3.3223
0000
0001
0.0800
3.6443
0100
0101
0.0640
3.9662
0.0250
5.3223
10110
10111
11100
0.0200
5.6444
11101
11110
11111
001000
001001
001010
0.0160
5.9664
001011
101000
101001
0.0050
7.6646
1010101
10101000
10101001
0.0040
7.9666
10101100
10101101
10101110
0.0010
9.9668
10101111
1.14确定下列比特流的Lempel-Ziv码：
01001111100101000001010101100110000从码字流恢复原来的序列。
根据Lempel-Ziv算法列出下表：
字典位置
字典内容
定长码字
00000
00001
00010
11
00101
111
01001
0110
00111
0111
00011
1000
00110
1001
01100
00100
10101
1101
10100
01000
10000
第2章信道容量和编码
2.1考虑图2-10所示的二元信道，设发送二元符号的先验概率为P0和P1，其中P0+P1=1，求后验概率和。
P0
P1
1-q
p
q
1-p
2.5
（1）一个电话信道具有带宽3000Hz,且SNR=20dB.求信道容量。
（2）若SNR增加到25dB,求信道容量。
（1）
SNR=20dB=100
信道容量=Wlog2（1+SNR/W）（b/s）
=3000*log2（1+100/3000）
=142（b/s）
（2）SNR=25dB=316
=3000*log2（1+316/3000）
=413（b/s）
2.7假定一个电视每秒钟显示30个画面，每个画面大约有个像素，每个像素需要16比特的彩色显示。
假定SNR为25dB，计算支持电视信号传输所需要的带宽（利用信息容量定理）
根据题意，该电视信号所需的信息容量为：
根据信息容量定理：
，其中为信噪比，据题意
据上式解得带宽
2.8考虑图2-15所示的Z型信道。
（1）求获得信道容量所需要的输入概率。
（2）若将N个这样的信道相级联，证明联合信道可以用一个信道转移概率为的等价Z信道表示。
（3）当时联合信道的容量是什么？
图2-15
（1）w为带宽
信道容量（b/s）
（2）由图可知信道转移概率为P
那么N级级联的信道转移概率
（3）当时
级联信道的信道容量为每一次使用该信道时的最大平均互信息。
其中最大值是在所有可能的输入概率上求得的即：
2.10
（1）证明对有限方差，高斯随机变量具有所有随机变量可能获得的最大微分熵。
（2）证明该熵由公式给出。
（1）由题意可知，高斯随机变量获得的微分熵为：
则有：
即其平均功率为：
对于有限方差的高斯随机变量，即当平均功率受限时，有：
即有：
综上可得，对于平均功率受限的连续随机变量，当服从高斯分布时具有最大微分熵。
（2）随机变量的微分熵为：
（1）
对于高斯分布，我们有：
（2）
其中，m为数学期望。
将
（2）式代入
（1）可得：
（3）
由（3）式可以推出：
（4）
故（4）式即为本题所证。
2.11
第3章纠错控制编码
3.1证明是一个线性码。
它的最小距离是什么？
由书中的定义3.8可知，线性码应该满足一下条件：
（1）两个属于该码的码字的和仍然是一个属于该码的码字，
（2）全零字总是一个码字，
（3）两个码字之间的最小距离等于任何非零码字的最小重量，即
设，即，，，，
首先证明条件
（1）：
，，，，，，
很明显，条件
（1）是满足的。
条件
（2）也是显然成立的。
最后证明条件（3）：
不难看出最小距离，并且最小重量，即
综上，三个条件都满足，那么就是一个线性码，它的最小距离是2。
3.3考虑GF
（2）上的下列生成矩阵
3）用此矩阵生成所有可能的码字。
4）求奇偶校验矩阵H。
5）求与其等价的一个系统码的生成矩阵。
6）构造该码的标准阵列。
7）这个码的最小距离是多少。
8）这个码能检测多少错误。
9）写出这个码能检测的所有错误模式。
10）这个码能纠多少个错误。
11）如果我们用此编码方案，那么符号错误概率是多少？
将它与末尾的错误概率进行比较。
12）这是一个线性码？
（1）=
=
此矩阵生成的码为：
{00000，01010，10011，11001，10100，11110，00111，01101}
（2）
又在二元情况下，
奇偶校验矩阵可写为：
（4该码的标准阵列
（5）奇偶校验矩阵H的第1、3列的和为零向量，
因此，这个码的最小距离为：
d*=2。
（6）一个码至少可以检测所有重量小于或等于（d*-1）的非零错误模式。
这个码的最小距离为：
d*=2，所以重量为1的错误模式可以检测得到。
（7）这个码能检测的所有错误模式
{00001，00010，00100，01000，10000}
（8）能纠正不多于t个错误应满足
又d*=2
所以
即
这个码能纠0个错误
（9）才vv
（10）{00000，01010，10011，11001，10100，11110，00111，01101}
线性码的性质：
1、两个属于该码的码字的和仍是属于该码的码字
00000+01010=01010 00000+11001=11001
00000+10011=1001100000+10100=10100
00000+11110=1111000000+00111=00111
00000+01101=01101
01010+10011=1100101010+11001=10011
01010+10100=1111001010+11110=10100
01010+00111=0110101010+01101=00111
10011+11001=0101010011+10100=00111
10011+11110=0110110011+00111=10100
10011+01101=11110
11001+10100=0110111001+11110=00111
11001+00111=1111011001+01101=10100
10100+11110=0101010100+00111=10011
10100+01101=11001
11110+00111=1100111110+01101=10011
00111+01101=01010
满足第一条性质
2、全零码字总是一个码字
{00000，01010，10011，11001，10100，11110，00111，01101}
满足第二条性质
3、一个线性码的两个码字之间的最小距离等于任何非零码字的最小重量，
即d*=w*
D（00000，01010）=2D（00000，10011）=3
D（00000，11001）=3 D（00000，10100）=2
D（00000，11110）=4 D（00000，00111）=3
D（00000，01101）=3
D（01010，10011）=3 D（01010，11001）=2
D（01010，10100）=4D（01010，11110）=2
D（01010，00111）=3D（01010，01101）=3
{00000，01010，10011，11001，10100，11110，00111，01101}
D（10011，11001）=2D（10011，10100）=3
D（10011，11110）=3 D（10011，00111）=2
D（10011，01101）=4
D（11001，10100）=3 D（11001，11110）=3
D（11001，00111）=4D（11001，01101）=2
D（10100，11110）=2D（10100，00111）=3
D（10100，01101）=3
D（11110，00111）=3 D（11110，01101）=3
D（00111，01101）=2
这个码的最小距离为2等于该码的最小重量
满足第三条性质
所以，这个码是线性码。
3.4构造C={00000，10101，01010，11111}的生成矩阵。
因为这个G不是唯一的，给出另一个能生成这个码字集合的生成矩阵。
设生成矩阵是G=，由题知，m=2,n=5,
c=iGi=（0,0）（0,1）,（1,0）,（1,1）
生成矩阵G=
3.7对下列每一个集合S，列出扩张码<
S>
:
（1）S={0101，1010，1100}
（2）S={1000，0100，0010，0001}
（3）S={11000，01111，11110，01010}
解:
（1）0101+1010=1111，0101+1100=1001
1010+1100=0110，0101+1010+1100=0011
再补上0000及原先3个公共组成
第二，三问步骤省略
<
为{1111，1001，0110，0011，0000，0101，1010，1100}
（2）
为{1100，1010，1001，0110，0101，0011，1110，1011，0111，1101，1111，0000，1000，0100，0010，0001}
（3）
为{10111，00110，10010，10001，00101，10100，01001，11000，01111，11110，01010，00000，11011，01100，11101}
3.8考虑（23，12，7）二元码。
证明若它被用在一个比特错误概率为p=0.01的二元对称信道（BSC）中，字错误概率将约为0.00008
由题可得其转移概率p=0.01，在（23.12.7）二元码中其可以纠出
2t+1>
=7t=3位错误
即在码元中出现4个错才会使得其出现误码率，出现3个以上错误的概率为
则出现的误字率为0.00008
所以得证。
3.9假设是一个二元码，它的奇偶校验矩阵为。
证明由通过添加整体奇偶校验比特得到的扩展码的奇偶校验矩阵为
.
根据题意，扩展码为:
又得奇偶校验矩阵为，。
，
即扩展码的奇偶校验矩阵为。
证毕。
3.11设C是长度为n,最小距离为7的二元完备码。
证明n=7或n=23。
由完备码的定义可知，一个完备码必须满足下列条件：
（1）
由题意可知：
，其中
当n=7时，由
（1）式可得，
右式展开得：
同理，可证得n=23时，同样满足
（1）式。
故可证明当n=7或n=23时，C是二元完备码。
3.12用来表示二元汉明码的码率，求。
根据二元汉明码的性质可知：
其中m是任意正整数。
则由码率的定义可知：
第4章循环码
4.1下面的哪个码是（a）循环码，（b）与一个循环码等价？
（1）上的。
（2）上的。
（3）上的。
（4）上的。
（5）长度为的-元重复码。
由书中定义4.1可知，循环码需要满足两个条件，
（1）首先它必须是一个线性码，
（2）其次它的一个码字的任意循环移位的结果还是一个码字，即若为其中的一个码字，则也是其中一个码字。
下面一一证明：
（1）首先证明是一个线性码：
设，则
，，，，，
，，，，，，，，，
显然不满足线性码的第一个条件，则它不是一个线性码，就不可能是一个循环码。
（2）首先证明是一个线性码：
，，，，
满足线性码的第一个条件，显然第二个条件也满足。
中的最小距离，最小重量，即，也满足第三个条件，可知是一个线性码。
下面证明是循环的，，经过循环移位之后得到的码字是，这个码字不是中的码字，即不满足循环码的第二个条件。
综上可知，不是一个循环码，但是它与一个循环码等价。
（3）首先证明是一个线性码：
（4）首先证明是一个线性码：
，，，
，，
（5）长度为的-元重复码，
假设，，则，可知其不为线性码，也定不为循环码。
4.2为下列定义的多项式环构造加法和乘法表
+
X+1
1+x
乘法表如下：
（2）加法表如下：
2
X+2
2x
2x+1
2x+2
升级会员 