信息论第四章习题解答

码
(5) 系统码和非系统码 (略)。
(P 175)
19
习题解答
第 4.13 已知 (7, 4) 循环码的生成多项式为 g( x) = x3 x2 1,
四
当收到一循环码字为 0010011 时，根据校验子判断有
章
无错误？哪一位错了？
抗 解 (1) 求校验子 干 扰 二 元 编 码
c0 位错 c1 位错 c2 位错 c3 位错 c4 位错 c5 位错 c6 位错
11
习题解答
第 4.8 若已知 (7, 3) 增余汉明码的监督矩阵为：
四
1111111
章
[H]= 1 1 0 1 0 0 0 ，
0110100
抗
1010010
干
经过信道干扰后，接收到的两个码字分别为 0000111 和
扰
0010111, 问这两个码字有无错误? 如何判断和纠正错误?
二 解 (1) 对码字 0000111，
(2) 译码表 (略)。
3
习题解答
第 4.3 已知码字集合的最小码距为 d ，问利用该组码字集合可以
四
检测(纠正)几个错误？可以发现几个错误？
章 解 (1) 作为检错码：可以发现 d - 1 位错误。
抗
(2) 作为纠错码：
干 扰
当
d
为奇数时，可以纠正

d
2
1

位错误；
二
元 编
当
d
为偶数时，可以纠正
元
纠正或者发现，因此漏检概率为：
编
10
码
P漏 = C1n0 Pen (1 - Pe)10-n
n=3
C130 Pe3 (1 - Pe)7= 1.210-10 .
9
习题解答
第 4.7 写出信息位 k = 6 且能纠正 1 个错的汉明码。
四 解 (1) 要能纠一位错，监督位数 r 必须满足 2r n 1,
17
习题解答
第 4.12 写出 (7, 4) 循环码的生成多项式、生成矩阵、标准生成阵
四
和监督阵，并分别写出系统码和非系统码。
章 解 已知 x7 - 1 = ( x 1)( x3 x 1)( x3 x2 1)
抗
(1) 生成多项式 g( x) = x3 x 1 .
干
(2) 生成矩阵
设等效误码率为 P~e，由于不纠错，故出错概率为：
扰 二
P2 = 5 C5k P~ek (1 - P~e)5-k
k =1
元 编
5P~e , (当 P~e 1 时 )
码
令 P2 = P1 , 有 5P~e = 610-8 ,
即得 P~e = 1.2 10-8.
7
习题解答
第 4.6 试分析用于电报系统的纠错码 正反码的检错和纠错
元 编 码
1111111 1101000 0110100 1010010

0 0 0 0 1 1 1

=

1110
,
该码字的第三位错， 正确码字：0010111。
12
习题解答
第 4.8 若已知 (7, 3) 增余汉明码的监督矩阵为：
四
当收到一循环码字为 0010011 时，根据校验子判断有
章
无错误？哪一位错了？
抗解 干 扰 二 元 编 码
(2) 判断码字 0010011 有无错误？ 该码字码多项式为 C( x) = x4 x 1, 用 C( x) 除以 g( x) 可得： C( x) x2(mod g( x)) = s2( x), 故可知 c2 位错，正确码字应为：0010111.
习题解答
第 四 章
抗 干
第四章 习题解答
扰
二
元
编
码
1
习题解答
第 4.1 写出与 10011 的汉明距离为 3 的码字。
四 章
解
从五位中取三位，使之与 10011 不一样，
抗
共得
C53 =
5! 3!(5 - 3)!
= 10 种取法：
干
扰
01111，01001，01010，00101，00110，
二
00000，11101，11110，11000，10100。
1000 011
码
[G] = 0 0 1 1 0 0 1 0100101
0 1 0 0 1 0 1 = [G~] 0010 110
1110000
0001 111
16
习题解答
第 解 (2) 由标准 (典型) 生成矩阵得到标准监督阵：
四 章
[H~ ] =
0111 1011
100 010

0 0

四
系统纠错方式，问这时系统的等效(实际)误码率为多少？
章 解 (1) 五三定比码不能发现的错误为：
抗
偶数位错，且一半为 0 出错，一半为 1 出错。
干
故其漏检概率为：
扰
二
P1
=
C21C
1 3
Pe
2
(1
-
Pe)3

C22C
2 3
Pe
4
(1
-
Pe)
元
6Pe2 = 610-8.
编
码
(2) 由于采用 ARQ 系统纠错, 故只要发现错误就能纠正。
d
2
2
位错误，
码
且发现

d
2
2


1
位错误。
4
习题解答
第 4.4 试计算 ( 8, 7 ) 奇偶校验码的漏检概率和编码效率，
四
已知码元的错误概率为 Pe = 10-4 .
章 解 (1) 奇偶校验码不能发现偶数位错误，其漏检概率为：
抗
[n / 2]
P =
C
2i n
1101 001
0
抗
干
校验子 s1 s2 s3 s4 s5 s6 s7
s0
扰
二
对于收到的码字 C = ( x1 x2 x3 x4 x5 x6 x7 ) ,
元 编 码
若 [H~ ]CT = si , 则第 i 位错 ( i = 1, 2, 3, 4, 5, 6, 7)； 若 [H~ ]CT = s0 , 则无错。
四
和监督阵，并分别写出系统码和非系统码。
章 解 (3) 由生成矩阵作行变换即得标准生成矩阵：
抗
1000 101
干
[G~] =
0100 0010
111 110
(P 187)
扰
0001 011
二 元
1110 100 (4) 监督阵 [H ] = 0 1 1 1 0 1 0 (P 179)
编
1101 001
四
1111111
章
[H]= 1 1 0 1 0 0 0 ，
0110100
抗
1010010
干
经过信道干扰后，接收到的两个码字分别为 0000111 和
扰
0010111, 问这两个码字有无错误? 如何判断和纠正错误?
二 解 (2) 对码字 0010111，
元 编 码
1111111 1101000 0110100 1010010
21
习题解答
第 4.14 写出所有码长 n =7 的本原 BCH 码的生成多项式，
四
并说明其最小码距和纠错能力？
章 解 x7 - 1 = ( x 1)( x3 x 1)( x3 x2 1) = g0( x)g1( x)g3( x)
抗
其中， g0( x) = 0 的根的指数为 ( 0 )；

0 0 1 0 1 1 1

=

0 0 0 0

,
该码字正确。
13
习题解答
第 4.9 已知系统汉明码的监督矩阵为：
四
1110 100
章
[H]= 0 1 1 1 0 1 0 ，
1101 001
抗
(1) 写出其生成矩阵；
干
(2) 当有一序列 110101101010 送入时，写出编码器编出的
元
编
码
2
习题解答
第 4.2 求 000000、110110、011101、101010 四码字的汉明距离，
四
并据此拟出校正错误用的译码表。
章 解 (1) 分别令四个码字为 A、B、C、D， 则有
抗
码距 A B C D
干
A 0443
扰
B 4043
二
C 4405
元
D 3350
编
码
故最小码距为 3，可纠一位错。
四
能力。若已知信道的误码率 Pe = 10-4 , 求系统的正确接
章
收概率和漏检概率。
抗 解 (1) 正反码的最小码距为 dmin = 4 .
干
作为检错码，可以发现 3 位错误；
扰
作为纠错码，可以纠正 1 位错误且发现 2 位错误。
二
元
注：实际上，正反码仅仅用作纠错码 。
编
码
8
习题解答
第 4.6 试分析用于电报系统的纠错码 正反码的检错和纠错
章
[H]= 1 0 1 1 1 0 0 ，
1110010
抗
0111001
干
试将其化为标准阵。
扰 二
解
对监督矩阵作行变换即可化为标准阵。
元
1111111
110 1000
编 码
[H]= 1 0 1 1 1 0 0 1110010 0111001
0 1 1 0 1 0 0 = [H~ ] 111 0010 101 0001
四
能力。若已知信道的误码率 Pe = 10-4 , 求系统的正确接
章
收概率和漏检概率。
抗 干
解
(2) 当收到的码字无错或者一位错时, 能够正确接收, 因此正确接收的概率为：
扰
P正 = (1 - Pe)10 C110 Pe (1 - Pe)9 = 0.99999955024;
二
(3) 当收到的码字出现三位以及三位以上的错误时, 不能
码
10
习题解答
第 4.7 写出信息位 k = 6 且能纠正 1 个错的汉明码。
四 解 (1) 要能纠一位错，监督位数 r 必须满足 2r n 1,
章
由 n = 6 r 可求得满足该条件的最小的 r 为 r = 4 .
抗
故需构造 (10, 6 ) 码。
干
(2) 可以构造出多种 (10, 6 ) 码，下面仅给出其中的一种。
扰
100000 1001
二
010000 1100
元 编
生成阵 [G] =
001000 000100
1110 1111
= [I6 PT ]
000010 0111
码
000001 0011
生成码字 [ x1 x2 x3 x4 x5 x6 x7 x8 x9 x10] = [ x1 x2 x3 x4 x5 x6][G].
干
g1( x) = 0 的根的指数为 ( 1, 2, 4 )；
扰
g3( x) = 0 的根的指数为 ( 3, 5, 6 )。
二 元
(1) 取生成多项式为 g( x) = g1( x), 构成 (7, 4) 循环码，
因此，上述漏检概率就是收到码字后的出错概率。
6
习题解答
第 4.5 已知信道的误码率 Pe = 10-4 , 若采用五三定比码和 ARQ
四
系统纠错方式，问这时系统的等效(实际)误码率为多少？
章 解 (3) 所谓系统的等效(实际)误码率，是指如果不纠错的话，
抗
到底以多大的误码率会产生同样的出错概率。
干
扰
汉明码序列。
二
解
(1) 生成矩阵 [G] =
1000 101 0100 111
元
0010 110
编
0001 011
码
(2) 编码序列 1 1 0 1 1 1 0 1 0 0 1
0110 0110001
1010 1010011
14
习题解答
第 4.10 已知 (7, 3) 汉明码的监督矩阵为：
四
1111111
Pe 2i
(1
-
Pe ) n- 2 i
干
i =1
扰

C
2 n
Pe
2
,
(当 Pe 1 时)
二
(2) 对于 ( 8, 7 ) 奇偶校验码，其漏检概率为：
元 编
P

C
Baidu Nhomakorabea
2 8
Pe
2
=
8! 10-8 2!6!
=
2.8 10-7.
码
(3) 编码效率为： = 7 = 87.5%.
8
5
习题解答
第 4.5 已知信道的误码率 Pe = 10-4 , 若采用五三定比码和 ARQ
x 3g(x)
x6 x4 x3
扰 二
[G( x)] =
x 2g(x) x g( x)
=
x5 x3 x2 x4 x2 x
元
g( x)
x3 x 1
编
1011000
码
[G] =
0101100 0010110
0001011
18
习题解答
第 4.12 写出 (7, 4) 循环码的生成多项式、生成矩阵、标准生成阵
15
习题解答
第 4.11 已知 (7, 4) 汉明码的生成矩阵为：
四
0010110
章
[G] = 0 0 1 1 0 0 1
0100101
抗
1110000
干
(1) 写出其标准 (典型) 生成矩阵。
扰
(2) 写出纠错校验表。
二 元 解 (1) 对生成矩阵作行变换即可化为标准 (典型) 生成矩阵。
编
0010110
无错
e( x)
1 x x2 x3 x4 x5 x6
0
校验子
s0( x) = 1 s1( x) = x s2( x) = x2 s3( x) = x2 1 s4( x) = x2 x 1 s5( x) = x 1 s6( x) = x2 x
s无 ( x) = 0
20
习题解答
第 4.13 已知 (7, 4) 循环码的生成多项式为 g( x) = x3 x2 1,
章
由 n = 6 r 可求得满足该条件的最小的 r 为 r = 4 .
抗
故需构造 (10, 6 ) 码。
干
(2) 可以构造出多种 (10, 6 ) 码，下面仅给出其中的一种。
扰
111100 1000
二 元
监督阵 [H ] =
011110 001111
0100 0010
= [P I4]
编
100111 0001