信息论与编码第六章课后习题答案

第六章课后习题

【6.1】设有一离散信道，其信道传递矩阵为

121613

并设P(x1)=

1

31216

161 312

11

，P(x2)=P(x3)=，试分别按最小错误概率准则与最大似然译码24

准则确定译码规则，并计算相应的平均错误概率。 解：

假设输入符号集和输出符号集分别为{x1,x2,x3}和{y1,y2,y3}。

按照最大似然译码规则，选择如下：

F(y1)=x1

F(y2)=x2 F(y3)=x3

平均错误概率为：

PE

=∑

XY−x对应的yj

*

∑P(x)P(y

i

j

|xi)

111111=+++2362361=2

如果需要按照最小错误概率译码，需要首先求出其联合概率矩阵：

14124112

1

618124

1121 1218

最小错误概率译码规则应如下：

F(y1)=x1F(y2)=x1 F(y3)=x3

此时错误概率为：

PE

=∑=∑

XY−x对应的yj

*

*

∑P(x)P(y

i

j

|xi)

XY−x对应的yj

∑P(x,y

i

j

)

111111=+++++[1**********]11=24

【6.2】计算码长n=5的二元重复码的译码错误概率。假设无记忆二元对称信道中正确传递概率为，错误传递概率为p=1−。此码能检测出多少错误？又能纠正多少错误。若p=0.01，译码错误概率是多大？ 解：

将0和1编成00000和11111后，当传输过程中产生1位至4位错误时均可

检测出，但产生5位错误却无法检测出，同时，如果输入等概率分布，当传输过程中存在1位错误以及2位错误时，可以自动纠正。此时的错误概率为：

错3位的概率为：C53p32； 错4位的概率为：C54p4； 错5位的概率为：C55p5

因此，译码错误概率为：

33255C5p+C54p4+C5p=1.02961×10−5

【6.3】设某二元码为C={11100,01001,10010,00111} （1） 计算此码的最小距离dmin；

（2） 计算此码的码率R，假设码字等概率分布；

（3） 采用最小距离译码准则，试问接收序列10000，01100和00100应译成什

么码字？

（4） 此码能纠正几位码元的错误？ 解：

（1） 此码字的最小距离dmin=3； （2） 此码字的码率R=

logM2

=比特/码符号； n5

（3） 采用最小距离译码，10000应译成10010；01100应译成11100；00100

译成11100、00111均可；

（4） 由于dmin=3=2×1+1，因此此码能纠正1位码元的错误。

【6.4】设无记忆二元对称信道的正确传递概率为,错误传递概率为p=1−

PE=1−

证明：

构造函数f(x)=pxn−x，有

f′(x)=pxn−xlnp−pxn−xln

因此该函数为减函数，即当D*j≤Dij时，有p

D*j

1

M

∑p

i

D*j

n−D*j

n−D*j

≥pijn−Dij。因此按照

D

最小距离选择的译码规则F(βj)=α*，使D*j≤Dij成立，必然会有p

D*j

n−D*j

≥pijn−Dij，即

E≥E

D

其中E为最小距离译码得到的正确概率，而E则是其他译码得到的正确概率，

进一步可以得到运用最小距离译码得到的错误概率为最小。 【6.5】对于离散无记忆强对称信道，信道矩阵为：

p

−1pr−1p1−pP=r−1

MMpp

r−1r−1

pp

Lr−1r−1pp

L

r−1r−1 MM

p

L1−pr−1

试证明对于此信道，最小距离译码准则等价于最大似然译码准则。 证明：

当信道发送符号序列为αi=ai1ai2Lain，接收符号序列为βj=bj1bj2Lbjn

时，信道矩阵中的条件概率为：

P(βj|αi)=Pbj1bj2Lbjn|ai1ai2Lain

()

()

()

)

=P(bj1|ai1)P(bj2|ai2)LPbjn|ainp

=r−1

D(αi,βj)

(

i

(1−p)n−D(α,β)

j

按照最大似然译码规则，选择F(βj)=α*，使P(βj|α*)>P(βj|αi)成立，即

p



r−1

D(α*,βj)

(1−p)

n−D(α*,βj)

p>r−1

D(αi,βj)

(1−p)n−D(α,β)

i

j

因此有

p

1r−

D(α*,βj)−D(αi,βj)

>(1−p)

D(α*,βj)−D(αi,βj)

一般情况下，=1−p>小距离译码规则。

1

，因此有D(α*,βj)≤D(αi,βj)成立，而这即为最2

1

【6.6】某一信道，其输入X的符号集为{0,,1}，输出Y的符号集为{0,1}，信道

2矩阵为

11P=

20

01 21

现有四个消息的信源通过这信道传输（消息等概率出现）。若对信源进行编码，我们选这样一种码

11

C:{(x1,x2,,)}，xi∈0或1（i=1,2）

22

其码长为n=4，并选取这样的译码规则

11

f(y1,y2,y3,y4)=(y1,y2,,)

22

（1） 这样编码后信道的信息传输率等于多少？ （2） 证明在选用的译码规则下，对所有码字PE=0。 解：

输入码字不同的个数共有4个，因此编码后信道的信息传输率为

log41

=比特/码符号 R=

可以看出，通过上述译码，对每一个输出都有一个输入与其对应，通过计算，可得其平均错误概率PE=0。

【6.7】考虑一个码长为4的二元码，其码字为W1=0000，W2=0011，W3=1100，W4=1111。假设码字送入一个二元对称信道（其单符号错误概率为p，且p

P(W1)=

1111

，P(W2)=，P(W3)=，P(W4)= 2884

试找出一种译码规则使平均错误概率PE最小。 解：

设接收码字为Vi，则一共可能有16种不同的码字序列，而

P(Vj|Wi)=列出所有的输出，如下表所示。

n−D(Vj,Wi)

p

D(Vj,Wi)

【6.8】设一种离散无记忆信道，其信道矩阵为

120P=0

012

（1） 计算信道容量C；

1

。（2） 找出一个码长为2的重复码，其信息传输率为log5（即5个码字）

2

如果按最大似然译码准则设计译码器，求译码器输出端的平均错误概率PE（输入码字等概率）。

（3） 有无可能存在一个码长为2的码，使Pe(i)=0（i=1,2,3,4,5），即PE=0，

如存在的话请找出来。

解：

（1）观察该信道，其每一行数据都是第一行数据的置换，每一列数据都是

1

212000

0121200

0012120

000 1212

第一列数据的置换，因此该信道是对称信道，其信道容量为：

11

C=logr−H(,,0,0,0)=log5−1=1.322比特/码符号

22

（2）假设信道中的输入符号集和输出符号集为{0,1,2,3,4}，进行二次重复码，

编得

00、11、22、33、44

其码率为R=

H(S)1

=log5比特/码符号。 n2

此时，输出方可能有25种可能性，进行最大似然译码，如下表所示。

错误概率为

1111111PE=++++=

5444444

输出序列

输入序列

00 01 02 03 04 10 11 12 13 14 20 21 22 23 24 30 31 32 33 34 40 41 42 43 44

00 1/4 1/4 0 0 0 1/4 1/4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 0 0 0 0 0 0 1/4 1/4 0 0 0 1/4 1/4 0 0 0 0 0 0 0 0 0 0 0 0 22 0 0 0 0 0 0 0 0 0 0 0 0 1/4 1/4 0 0 0 1/4 1/4 0 0 0 0 0 0 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1/4 1/4 0 0 0 1/4 1/4 44 1/4 0 0 0 1/4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1/4 0 0 0 1/4

译码

00/44 00

均可 均可

44 00 00/11 11

均可 均可 均可

11 11/22 22

均可 均可 均可

22 22/33 33 44

均可 均可

33 33/44

（3）将25个长度为2的序列排成一方块图，如下所示：

00 10 20 30 40 00

01 11 21 31 41 01

02 12 22 32 42 02

03 13 23 33 43 03

04 14 24 34 44 04

00 10 20 30 40 00

为使平均错误概率为0，须充分利用译码规则，假如选择了一个码字，则在

接收序列中与这个码字对应的条件概率不为零的肯定不能出现在所选的码组中，对应上图，即是如果一个码字被选定了，则以它为左上角的正方形中的四个码字均不能出现在这个码组中，因此可以选择{00，12，24，31，43}，可以保证平均错误概率为0。

【6.9】证明二元(2n+1,1)重复码当采用最大似然译码准则时，译码的平均错误概率为

PE=

2n+1

kk2n+1−k

Cp ∑2n+1k=n+1

式中，p为二元对称信道的错误传输率，并计算当n=5,7,9,11时PE的近似值。 证明：

对于二元(2n+1,1)重复码，采用最大似然译码规则时，收到的码字序列可能

有22n+1个，此时可以自动纠正1位至n位错误，因此平均错误概率为：

PE=C

n+1

2n+1

p

n+1

+L+C

n

2n+12n+1

p

2n+1

=

2n+1

k=n+1

∑C

k2n+1

pk2n+1−k

当n=2时，PE=1×10−5； 当n=3时，PE=3.42×10−7； 当n=4时，PE=1.22×10−8； 当n=5时，PE=4.43×10−10。

【6.10】对二元(2n,1)重复码，设计一种合适的译码规则，并求出它的译码平均错误概率PE。

解：此题在关键在于对于错了n位时的处理方法。

显然，对于错误小于n位时，我们可以自动纠正其错误，而对于错n位时，只能人为指定一个。因此错误概率为

2n12nkk2n−k2n−knnnkk+C2np+∑C2PE=∑C2nppn2k=n+1k=n+1

=1nnnkk2n−k+CpC2np∑2n2k=n+12n

第六章课后习题

【6.1】设有一离散信道，其信道传递矩阵为

121613

并设P(x1)=

1

31216

161 312

11

，P(x2)=P(x3)=，试分别按最小错误概率准则与最大似然译码24

准则确定译码规则，并计算相应的平均错误概率。 解：

假设输入符号集和输出符号集分别为{x1,x2,x3}和{y1,y2,y3}。

按照最大似然译码规则，选择如下：

F(y1)=x1

F(y2)=x2 F(y3)=x3

平均错误概率为：

PE

=∑

XY−x对应的yj

*

∑P(x)P(y

i

j

|xi)

111111=+++2362361=2

如果需要按照最小错误概率译码，需要首先求出其联合概率矩阵：

14124112

1

618124

1121 1218

最小错误概率译码规则应如下：

F(y1)=x1F(y2)=x1 F(y3)=x3

此时错误概率为：

PE

=∑=∑

XY−x对应的yj

*

*

∑P(x)P(y

i

j

|xi)

XY−x对应的yj

∑P(x,y

i

j

)

111111=+++++[1**********]11=24

【6.2】计算码长n=5的二元重复码的译码错误概率。假设无记忆二元对称信道中正确传递概率为，错误传递概率为p=1−。此码能检测出多少错误？又能纠正多少错误。若p=0.01，译码错误概率是多大？ 解：

将0和1编成00000和11111后，当传输过程中产生1位至4位错误时均可

检测出，但产生5位错误却无法检测出，同时，如果输入等概率分布，当传输过程中存在1位错误以及2位错误时，可以自动纠正。此时的错误概率为：

错3位的概率为：C53p32； 错4位的概率为：C54p4； 错5位的概率为：C55p5

因此，译码错误概率为：

33255C5p+C54p4+C5p=1.02961×10−5

【6.3】设某二元码为C={11100,01001,10010,00111} （1） 计算此码的最小距离dmin；

（2） 计算此码的码率R，假设码字等概率分布；

（3） 采用最小距离译码准则，试问接收序列10000，01100和00100应译成什

么码字？

（4） 此码能纠正几位码元的错误？ 解：

（1） 此码字的最小距离dmin=3； （2） 此码字的码率R=

logM2

=比特/码符号； n5

（3） 采用最小距离译码，10000应译成10010；01100应译成11100；00100

译成11100、00111均可；

（4） 由于dmin=3=2×1+1，因此此码能纠正1位码元的错误。

【6.4】设无记忆二元对称信道的正确传递概率为,错误传递概率为p=1−

PE=1−

证明：

构造函数f(x)=pxn−x，有

f′(x)=pxn−xlnp−pxn−xln

因此该函数为减函数，即当D*j≤Dij时，有p

D*j

1

M

∑p

i

D*j

n−D*j

n−D*j

≥pijn−Dij。因此按照

D

最小距离选择的译码规则F(βj)=α*，使D*j≤Dij成立，必然会有p

D*j

n−D*j

≥pijn−Dij，即

E≥E

D

其中E为最小距离译码得到的正确概率，而E则是其他译码得到的正确概率，

进一步可以得到运用最小距离译码得到的错误概率为最小。 【6.5】对于离散无记忆强对称信道，信道矩阵为：

p

−1pr−1p1−pP=r−1

MMpp

r−1r−1

pp

Lr−1r−1pp

L

r−1r−1 MM

p

L1−pr−1

试证明对于此信道，最小距离译码准则等价于最大似然译码准则。 证明：

当信道发送符号序列为αi=ai1ai2Lain，接收符号序列为βj=bj1bj2Lbjn

时，信道矩阵中的条件概率为：

P(βj|αi)=Pbj1bj2Lbjn|ai1ai2Lain

()

()

()

)

=P(bj1|ai1)P(bj2|ai2)LPbjn|ainp

=r−1

D(αi,βj)

(

i

(1−p)n−D(α,β)

j

按照最大似然译码规则，选择F(βj)=α*，使P(βj|α*)>P(βj|αi)成立，即

p



r−1

D(α*,βj)

(1−p)

n−D(α*,βj)

p>r−1

D(αi,βj)

(1−p)n−D(α,β)

i

j

因此有

p

1r−

D(α*,βj)−D(αi,βj)

>(1−p)

D(α*,βj)−D(αi,βj)

一般情况下，=1−p>小距离译码规则。

1

，因此有D(α*,βj)≤D(αi,βj)成立，而这即为最2

1

【6.6】某一信道，其输入X的符号集为{0,,1}，输出Y的符号集为{0,1}，信道

2矩阵为

11P=

20

01 21

现有四个消息的信源通过这信道传输（消息等概率出现）。若对信源进行编码，我们选这样一种码

11

C:{(x1,x2,,)}，xi∈0或1（i=1,2）

22

其码长为n=4，并选取这样的译码规则

11

f(y1,y2,y3,y4)=(y1,y2,,)

22

（1） 这样编码后信道的信息传输率等于多少？ （2） 证明在选用的译码规则下，对所有码字PE=0。 解：

输入码字不同的个数共有4个，因此编码后信道的信息传输率为

log41

=比特/码符号 R=

可以看出，通过上述译码，对每一个输出都有一个输入与其对应，通过计算，可得其平均错误概率PE=0。

【6.7】考虑一个码长为4的二元码，其码字为W1=0000，W2=0011，W3=1100，W4=1111。假设码字送入一个二元对称信道（其单符号错误概率为p，且p

P(W1)=

1111

，P(W2)=，P(W3)=，P(W4)= 2884

试找出一种译码规则使平均错误概率PE最小。 解：

设接收码字为Vi，则一共可能有16种不同的码字序列，而

P(Vj|Wi)=列出所有的输出，如下表所示。

n−D(Vj,Wi)

p

D(Vj,Wi)

【6.8】设一种离散无记忆信道，其信道矩阵为

120P=0

012

（1） 计算信道容量C；

1

。（2） 找出一个码长为2的重复码，其信息传输率为log5（即5个码字）

2

如果按最大似然译码准则设计译码器，求译码器输出端的平均错误概率PE（输入码字等概率）。

（3） 有无可能存在一个码长为2的码，使Pe(i)=0（i=1,2,3,4,5），即PE=0，

如存在的话请找出来。

解：

（1）观察该信道，其每一行数据都是第一行数据的置换，每一列数据都是

1

212000

0121200

0012120

000 1212

第一列数据的置换，因此该信道是对称信道，其信道容量为：

11

C=logr−H(,,0,0,0)=log5−1=1.322比特/码符号

22

（2）假设信道中的输入符号集和输出符号集为{0,1,2,3,4}，进行二次重复码，

编得

00、11、22、33、44

其码率为R=

H(S)1

=log5比特/码符号。 n2

此时，输出方可能有25种可能性，进行最大似然译码，如下表所示。

错误概率为

1111111PE=++++=

5444444

输出序列

输入序列

00 01 02 03 04 10 11 12 13 14 20 21 22 23 24 30 31 32 33 34 40 41 42 43 44

00 1/4 1/4 0 0 0 1/4 1/4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 0 0 0 0 0 0 1/4 1/4 0 0 0 1/4 1/4 0 0 0 0 0 0 0 0 0 0 0 0 22 0 0 0 0 0 0 0 0 0 0 0 0 1/4 1/4 0 0 0 1/4 1/4 0 0 0 0 0 0 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1/4 1/4 0 0 0 1/4 1/4 44 1/4 0 0 0 1/4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1/4 0 0 0 1/4

译码

00/44 00

均可 均可

44 00 00/11 11

均可 均可 均可

11 11/22 22

均可 均可 均可

22 22/33 33 44

均可 均可

33 33/44

（3）将25个长度为2的序列排成一方块图，如下所示：

00 10 20 30 40 00

01 11 21 31 41 01

02 12 22 32 42 02

03 13 23 33 43 03

04 14 24 34 44 04

00 10 20 30 40 00

为使平均错误概率为0，须充分利用译码规则，假如选择了一个码字，则在

接收序列中与这个码字对应的条件概率不为零的肯定不能出现在所选的码组中，对应上图，即是如果一个码字被选定了，则以它为左上角的正方形中的四个码字均不能出现在这个码组中，因此可以选择{00，12，24，31，43}，可以保证平均错误概率为0。

【6.9】证明二元(2n+1,1)重复码当采用最大似然译码准则时，译码的平均错误概率为

PE=

2n+1

kk2n+1−k

Cp ∑2n+1k=n+1

式中，p为二元对称信道的错误传输率，并计算当n=5,7,9,11时PE的近似值。 证明：

对于二元(2n+1,1)重复码，采用最大似然译码规则时，收到的码字序列可能

有22n+1个，此时可以自动纠正1位至n位错误，因此平均错误概率为：

PE=C

n+1

2n+1

p

n+1

+L+C

n

2n+12n+1

p

2n+1

=

2n+1

k=n+1

∑C

k2n+1

pk2n+1−k

当n=2时，PE=1×10−5； 当n=3时，PE=3.42×10−7； 当n=4时，PE=1.22×10−8； 当n=5时，PE=4.43×10−10。

【6.10】对二元(2n,1)重复码，设计一种合适的译码规则，并求出它的译码平均错误概率PE。

解：此题在关键在于对于错了n位时的处理方法。

显然，对于错误小于n位时，我们可以自动纠正其错误，而对于错n位时，只能人为指定一个。因此错误概率为

2n12nkk2n−k2n−knnnkk+C2np+∑C2PE=∑C2nppn2k=n+1k=n+1

=1nnnkk2n−k+CpC2np∑2n2k=n+12n