《信息论、编码与密码学》课后习题答案

《信息论、编码与密码学》课后习题答案

第1章信源编码

1.1考虑一个信源概率为｛0.30，0.25，0.20，0.15，0.10｝的DMS。求信源嫡

H(X)。

5

解：信源炳H(X)=-£pklog2(Pk)

k=\

H(X)=-[0.30*(-l.737)+0.25*(-2)+0.2*(-2.322)+0.15*(-2.737)+0,1*

(-3.322)]

=[0,521+0.5+0.464+0.411+0.332]

=2.228(bit)

故得其信源嫡H(X)为2.228bit

1.2证明一个离散信源在它的输出符号等概率的情况下其嫡达到最大值。

解：若二元离散信源的统计特性为

P+Q=lH(X)=-[P*log(P)+(l-P)*log(l-P)]

对H(X)求导求极值，由dH(X)/d(P)=0可得

p

log--------o

1一。

-^=1

\一P

1

P=­

2

可知当概率P=Q=l/2时，有信源嫡"(X)max=1S")

对于三元离散信源，当概率［=g=A=1/3时，信源嫡

"(X)max=L585c，

此结论可以推广到N元的离散信源。

1.3证明不等式InxWx-1。画出曲线x=lnx和%=x—l的平面图以表明上述不

等式的正确性。

证明：

fix')=lnx-x+l(x>0)

fM'=-

X

令/(X)，=o,X=1又有x>0.-.0<x<1时/(x)'>0

此时/•(》)《篇”0

也即InxKx-1

当尤>耐同理可得此时Inx<x-1

综上可得In光<x—l证毕

绘制图形说明如下

可以很明确说明上述

不等式的正确性。

Y=lnx

1.4证明/(x；y)20。在什么条件下等号成立?

/(X；丫)=z£pa，x)/a，x)

i=\j=\

尸(知力)

，匕)log

/=1j=lP(x,)P(匕)

当和相互独立时等号成立。

1.5有一个信源X＞它有无穷多个可能的输出，它们出现的概率为P(Xi)

=2'T,i=l,2,3,….，这个信源的平均自信息H(X)是什么？

解：因为P(Xi)=2':i=l,2,3,…

所以H(X)=-汽p3)logp(»)

/=|

=-log2(2+2.22+3,夕+…..+n.2n)

=2-(1-n)2用

1.6考虑另一个几何分布的随机变量X，满足P(Xi)=P(l-P)ii=l,2,3,…

这个信源的平均自信息H(X)是什么？

解：因为P(Xi)=P(1-P)二i=l,2,3,

所以H(X)=-£〃O)k)gpO)

/=1

=-logp(1-p)[p(1-p)+2p(l-p)2+3p(1-p)3+...+np(l-p)n]

-(l-n)(l-p)n+l-^^

P

1.7考虑一个只取整数值的随机变量X，满足P(X=〃)=,，，，其中

Anlogn

A=y―，〃=2,3,...,8。求嫡“(X)。

„=2〃」Og〃

解：为了方便计算，设B="log2〃>则A-'P(X=〃)=」一；

"=2BAB

/(x)=lo4忐卜。g(AM；

根据公式计算自信息量为：

则嫡为：H(x)=£p(x)/(x)=fWlog(43)=£曾经

=?

n=2n=2A/y”=2A"

1.8计算概率分布函数为

0<x<a

p(x)=<a~'

0(否则)

的均匀分布随机变量x的微分嫡”(x)。画出“(X)相对于参数a(0.1<a<10)的

平面图，并对结果进行评论。

-KC

解：根据公式(1-21)可知，微分嫡为："(X)=-Jp(x)logp(x)dx

-OO

当0<x<〃时，p(x)=a~l»则

H(X)=-ja-'loga''dx=—­log«-[x]p=-)e；—•a~loga

oaa

当x<0或x>a时，p(x)=0，则”(X)foo

根据得到的结果可以画出相应的平面图，由图可以看到随着a的增加，即p(x)的

减小，微分嫡H(X)相应的增加。

“(X)

1.9考虑一个信源的概率为｛0.35,0.25,0.2Q0.15,0.05｝的DMS。

(1)给出此信源的霍夫曼码。

(2)计算出这些码子的平均码长R。

(3)这个码的效率〃是多少？

解：1)依题意，由霍夫曼编码的规则，得：

11.00

0.65

00.400

0.3500.200

x20.2511

X30.20

%40.15

九50.05

表格如下：

符号概率自信息码字

0.351.5151

x20.252.00001

0.202.322000

%40.152.7380010

%50.054.3220011

2)由平均码长公式R=Z"%)•P〈Xk),代入数据，得：

k=\

—5

R=Z九(4)•0(4)=1(0.35)+2(0.25)+3(0.20)

k=i

+4(0.15)+5(0.05)=0.35+0.5+0.6+0.6+0.25

=2.3。")

3)首先，该信源的嫡为：

5

H(X)=-^2PkPk=-(0-35xlog20.35+0.25xlog20.25

k=l

+0.20xlog20.20+0.15xlog20.15+0.05xlog20.05)

=-(-0.35x1.515-0.25x2.0-0.20x2.322

-0.15x2.738-0.05x4.322)

=-(-0.5303-0.5-0.4644-0.4107—0.216D

=-(-2.1215)=2.12150/0

该码的效率为：

77=丝2=(2.1215/2.300)=0.9224

R

1.10考虑一个信源概率为｛0.35>0,20'0.15，0.15，0.10，0.10，0.05，0.05)

的DMS。

(1)给出此信源的一种有效定长码。

(2)给出此信源的霍夫曼码。

(3)比较这两种码并给出评论。

解：1)空

2)依题意，由霍夫曼编码的规则，得:

X0201

0.55

x0.20

200.350

r01510

1.00

入4U・J

00.25

_nin0

了5U.1U

10.45

01

4r6Uo・JLiUn

0.20

x0r\.05

700.101

1

X“g0C\.0A5C

1

符号概率自信息码字

为0.202.32201

x20.202.322000

%30.152.738001

%40.152.738100

%50.101.000101

40.101.000110

0.054.3221110

0.054.3221111

3）空

1.11一个DMS只有三个输出符号，它们的概率为｛0.5，0,4，0.1｝。

(1)给出此信源的霍夫曼码并确定编码效率。

(2)每次考虑两个符号时，给出此信源的霍夫曼码并确定编码效率。

(3)每次考虑三个符号时，给出此信源的霍夫曼码并确定编码效率。

解：

(1)本题的霍夫曼编码如下图所示：

0.5-------------------qi.o

04--------~().5

o.i——0

图1.11霍夫曼编码

则霍夫曼码如下表：

符号概率码字

X10.51

X20.400

X30.101

该信源的嫡为：

3

H(X)=£pjGg2Pk

k=i

=-(0.5log20.5+0.41og20.4+0.1log,0.1)

=0.5000+0.5288+0.3322

=1.3610(Z?z7)

平均每个符号的比特数为：

R=£nQQpQk)

*=i

=1(0.5)+2(0.4)+2(0.1)

=0.5+0.8+0.2

=1.5000(次〃符号)

该码的效率为：

7=1.3160/1.5000=0.9073

(2)把符号每两个分一组，重新应用霍夫曼编码算法，如下表所示：

符号对概率码字

X1X10.2500

X1X20.20010

X2X10.20011

X2X20.161010

X1X30.05100

X3XI0.05110

X2X30.041011

X3X20.041110

X3X30.011111

该信源的嫡为：

2H(X)=-ZpJog20=2/7219(初，)

A=1

=>//(%)=1.3610(^)

每个组的平均比特数为：

___9

&=z〃(”(/)

hl

=2(0.25)+3(0.2)+3(0.2)+4(0.16)+3(0.05)+3(0.05)+4(0.04)+4(0.04)+4(0.01)

=3.00(次〃符号X寸)

n元=3乂)0/2=1.5000(沅〃符号)

故该码的效率为：

7=1.3160/1.5000=0.9073

(3)依题意，把符合每三个分成一组，再重新应用霍夫曼编码算法，得:

xxx0.1250

lll0

xixlx20.10(X)00.2000

10

x2xixl0.10(X)0

x^xxO.O8OO

22]0.2400

xxx0.0800

2l200.16001

1

%土玉O.O8OO0

x2x2x20.0640

0.185010.5800

.石七0.025000.05CX)0

1

XjXjX10.0250

0.34(X)1.0000

x^x}xt0.02500.04500.1400I0

x{x2x30.02000.08500.4200

0

xixyx20.02000.0400

0.2350

1

x2x^x30.020()

0.02(X)0.0400

0

10

0.02000.0760

0.1l(X)

0

占占20.02000.0360

1

11

x2x2x30.0160

0.0320

x2x3x20.01600

i0

编码表格如下：

符号对概率自信息码字

0.12502.7090100

—九20.10003.32230000

王々玉0.10003.32230001

0.10003.3223110

X2XiXx

0.08003.6443on

XxX2X2

0.08003.64430100

x2xtx2

0.08003.64430101

x2x2x{

*^20.06403.96620011

0.02505.322310110

XxX3X10.02505.322310111

0.02505.322311100

x}x2x30.02005.644411101

0.02005.644411110

X2X1X30.02005.6444mu

x2x3x]0.02005.6444001000

«^20.02005.6444001001

0.02005.6444001010

•^2*^2*^30.01605.9664001011

«^2*^3*^20.01605.9664101000

符号对概率自信息码字

0.01605.9664101001

XL0.00507.66461010101

七%%0.00507.664610101000

七七%0.00507.664610101001

々七七0.00407.966610101100

*^30.00407.966610101101

0.00407.966610101110

%3*3%30.00109.966810101111

1.14确定下列比特流的Lempel-Ziv码：

01001111100101000001010101100110000从码字流恢复原来的序列。

解：根据Lempel-Ziv算法列出下表：

字典位置字典容定长码字

0001000000

0010100001

00110000010

01001100101

010111101001

011000100111

01110100011

100000000110

1001001001100

10101000100

101110110101

110110010100

111011001000

mi00010000

第2章信道容量和编码

2.1考虑图2-10所示的二元信道，设发送二元符号的先验概率为P。和R，其中

p°+Pi=i,求后验概率尸(x=o|y=i)和p(x=i|y=i)。

解：p{x=o}=poP{X=1}=P1

P{Y=1|X=O}=Pp{Y=qX=l}=q

p{Y=qX=o}=l-pp{y=l|X=l}=l-q

p{x=o,Y=0}=p{x=0}P{Y=O|x=o}=P{Y=0}p{x=0|Y=o}

P{X=O}.P{Y=O|X=O}p°(l—p)

p{x=qY=o}=

P{Y=O}p°(i-p)+pq

P{Y=0}=p{x=0卜P{Y=Qx=o}+p{x=I}P{Y=qx=1}

=Po(i-p)+pq

P{X=I,Y=I}=P{X=I}-P{Y=I|X=I}=P{Y=I}-P{X=I|Y=I}

Pi(i-q)

p仅小力空健产

PoP+p』i—q)

P{Y=I}=P{X=O}P{Y=1|X=o}+p{x=1}P{Y=1|X=1}

=PoP+Pi。—q)

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

信道容量小log2(1+SNR/W)(b/s)

=3000*log2(1+316/3000)

=413(b/s)

2.7假定一个电视每秒钟显示30个画面,每个画面大约有2x10、个像素,每个

像素需要16比特的彩色显示。假定SNR为25dB，计算支持电视信号传输所需

要的带宽(利用信息容量定理)

解：根据题意，该电视信号所需的信息容量为：

C=30X2X105X16/J/7/5=9.6X107^7/5

根据信息容量定理：C=Wlog,(l+—匕)，其中二为信噪比，据题意

N°WNo

P

——=25dB

N°

•据上式解得带宽CB1.15X1()7”Z

2.8考虑图2-15所示的Z型信道。

(1)求获得信道容量所需要的输入概率。

(2)若将N个这样的信道相级联，证明联合信道可以用一个信道转移概率

为pZ的等价Z信道表示。

(3)当N-8时联合信道的容量是什么？

解：

(1)w为带宽

信道容量C=Wlog2(l+-^-)(b/s)

C=Blog2(l+^)

(2)由图可知信道转移概率为P

々0|l)=々1|O)=P

那么N级级联的信道转移概率

pN级级联,pW

(3)当N->00时P(011)

级联信道的信道容量为每一次使用该信道时的最大平均互信息。其中最大值是在

所有可能的输入概率上求得的即：

C=max/(x;y)

P(Xj)

厂\r>(I\1

c=叫a个ZZP(x)P(y,IX-)log—]

夕⑸)MMp(x)

2.10(1)证明对有限方差/，高斯随机变量具有所有随机变量可能获得的最大

微分嫡。

(2)证明该嫡由公式l/21og2(2%ecr2)给出。

证明：

(1)由题意可知，高斯随机变量获得的微分嫡为：

1,

2

//(X)=-log2(2^a)

则有：

即其平均功率为：

J_e2H(X)

17ie

对于有限方差的高斯随机变量，即当平均功率受限时，有：

[p(<x)dx=1,f(x-m)2p(x)dx=cr2.

J-00J-CO

即有：

H(X)<log2飞2兀eo

综上可得，对于平均功率受限的连续随机变量，当服从高斯分布时具有最大微分

嫡°

(2)随机变量的微分嫡为：

H(X)=-匚p(x)log2P(x)公⑴

对于高斯分布，我们有：

11,

/7(%)=-r—~exp{--(x-m)-}(2)

42g2a

其中，m为数学期望。

将(2)式代入(1)可得：

H(X)=-f-7=----(3)

—2CT2

由(3)式可以推出：

"(X)=glog2(2万纳2)(4)

故(4)式即为本题所证。

2.11

写一个程序，它在输入信道转移矩阵后计算出信道容量？

解：依据设定情况在一般的二元通信信道

输入前只有两种状态，0和1，假设传输发生错误概率为P,正确

概率为bp.这只是假定的i种情况，其实在程序中可看作这儿

个参量为个数组。CP口及WP口。再根据计算信道容量公式

maxVY。(巧.)p(y/X')log，输出对应的信道容量值。

/=oi=op(y)

第3章纠错控制编码

3.1证明C={OOOQlioqOOH1111}是一个线性码。它的最小距离是什么？

证明：由书中的定义3.8可知，线性码应该满足一下条件：

(1)两个属于该码的码字的和仍然是一个属于该码的码字，

(2)全零字总是一个码字，

(3)两个码字之间的最小距离等于任何非零码字的最小重量，即d*=vv*

1

设C={q,c2,c3,c4]即q=0000，c2=1100,c3=0011,c4=1111)

首先证明条件(1)：

C|+c=+，3=C4)

C,+c2=1100=c2'30011=c3'C]+c4=1111=c4，01111=

c2+c4=00U=c3，C3+C4=1100=c2，

很明显，条件(1)是满足的。条件(2)也是显然成立的。

最后证明条件(3)：

不难看出最小距离d*=2，并且最小重量w*=2，即〃*=卬*

综上，三个条件都满足，那么C就是一个线性码，它的最小距离是2。

3.3考虑GF(2)上的下列生成矩阵

'10100、

G=10011

、01010,

3)用此矩阵生成所有可能的码字。

4)求奇偶校验矩阵H。

5)求与其等价的一个系统码的生成矩阵。

6）构造该码的标准阵列。

7）这个码的最小距离是多少。

8）这个码能检测多少错误。

9）写出这个码能检测的所有错误模式。

10）这个码能纠多少个错误。

11）如果我们用此编码方案，那么符号错误概率是多少？将它与末尾的错误概率

进行比较。

12）这是一个线性码？

'10100'

解：⑴5=(000)10011=(0000o)

^01010

‘10100、

c2=(001)10011=(0101o)

、01010,

’10100、

c3=(O10)10011=(10011)

、01010,

’10100、

c4=(O11)10011=(11001)

k01010?

’10100、

c5=000)10011=(1010o)

、01010,

’10100、

c6=001)10011=(1111o)

k01010?

’10100、

c7=010)10011=(00111)

k01010?

’10100、

c8=(l11)10011=(o1101)

、01010,

此矩阵生成的码为:{00000，01010，10011，11001'10100-11110'00111'

01101)

'10100][10011,

(2)G=10011=01010

、O101oj[o

0I-I-I,

,11]

P=10PT=|1!

L-Jb。又在二元情况下，1=—1

pT

=Co；)

奇偶校验矩阵可写为：H=(-PT|I)

1iio)

—[1010J

(4该码的标准阵列

0011、

G=01010

、001-1-1,

(5)奇偶校验矩阵H的第1、3列的和为零向量'

因此5这个码的最小距离为：d*=2°

(6)一个码至少可以检测所有重量小于或等于(d*-l)的非零错误模式。

这个码的最小距离为：d*=2，所以重量为1的错误模式可以检测得到。

(7)这个码能检测的所有错误模式

{00001>00010，00100，01000'10000)

(8)能纠正不多于t个错误应满足d*N2t+l

又d*=2

所以222t+1

即t4—

2

这个码能纠0个错误

(9)才vv

(10){00000，01010'10011-11001-10100>11110，00111-01101)

线性码的性质：

1、两个属于该码的码字的和仍是属于该码的码字

00000+01010=0101000000+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*

DC00000，01010)=2DC00000'10011)=3

DC00000'11001)=3DC00000'10100)=2

DC00000-11110)=4DC00000，00111)=3

DC00000，01101)=3

DC01010'10011)=3DC01010'11001)=2

DC01010'10100)=4DC01010-11110)=2

DC01010，00111)=3D(01010，01101)=3

{00000，01010'10011,11001>10100'11110，00111，01101)

D(10011'11001)=2DdOOll>10100)=3

D(10011'11110)=3DdOOll>00111)=2

DdOOll，01101)=4

D(11001'10100)=3DdlOOl'11110)=3

D(11001，00111)=4DdlOOl-01101)=2

DC10100'11110)=2DC10100,00111)=3

D(10100，01101)=3

D(11110，00111)=3DCllllO，01101)=3

DCOOlll，01101)=2

这个码的最小距离为2等于该码的最小重量

满足第三条性质

所以，这个码是线性码。

3.4构造C={00000'10101-01010，11111}的生成矩阵。因为这个G不是唯一

的，给出另一个能生成这个码字集合的生成矩阵。

a\\a\n

解：设生成矩阵是6=1由题知，m=2,n=5,

a”门

c=i.Gi=(0,0)(0,1),(1,0),(1,1)

’01010、

生成矩阵6=

JO1O1,

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)

<S>为{1100>1010-1001-0110>0101-0011>1110'1011>0111>1101-1111，

0000'1000,0100,0010，0001)

(3)

<S>为{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+l>=7t=3位错误

即在码元中出现4个错才会使得其出现误码率，出现3个以上错误的概率为

2323

*犷(1-〃产二2禺犷

=I-C«A23-C^V2-^A21-C^V°

=0.00008

则出现的误字率为0.00008

所以得证。

3.9假设C是一个二元码，它的奇偶校验矩阵为“。证明由C通过添加整体

奇偶校验比特得到的扩展码C,的奇偶校验矩阵为

10

10

%H

10

iii|i

证明：根据题意，扩展码G为：

10

10

Gc,又c得奇偶校验矩阵为H，,CHr=0。

10

ii110

II

II

H：HT

II

o00

0

0

cH；CHT=0

o

oooo

即扩展码G的奇偶校验矩阵为“I。

证毕。

3.11设C是长度为n,最小距离为7的二元完备码。证明n=7或n=23。

证明：由完备码的定义可知，一个完备码必须满足下列条件：

2…主C：⑴

i=0

由题意可知：d^>2t+\，其中d*=7

即有：/<3

当n=7时，由(1)式可得，

27T=文0

/=()

右式展开得：

3

2a=3+C；+C；+G

z=o

=1+7+21+35

=64=左式

同理，可证得n=23时，同样满足(1)式。

故可证明当n=7或n=23时，C是二元完备码。

3.12用5来表示二元汉明码的码率，求lim5。

解：根据二元汉明码的性质可知：

(n,k)=(2m-l,2m-l-m)

其中m是任意正整数。

则由码率的定义可知：

k2m-l-m

%=7=21n-1

则有：

lim%=lim2TF=1

kfgkT82m—1

第4章循环码

4.1下面的哪个码是(a)循环码，(b)与一个循环码等价？

⑴GF⑵上的｛OOOQ011Q110Q0011100*。

(2)GF⑵上的｛0000Q1011Q0110J1101｝。

(3)G尸(3)上的｛0000Q10UQ011011101，。

(4)GE(3)上的｛000Q1122221上

(5)长度为〃的4-元重复码。

解：由书中定义4.1可知，循环码需要满足两个条件，

(1)首先它必须是一个线性码，

(2)其次它的一个码字的任意循环移位的结果还是一个码字，即若

为其中的一个码字，则a”」%，…4-2也是其中一个码字。

下面一一证明：

(1)首先证明G是一个线性码：设G={q，。2，c，3，c4,%}，则

q=0000，c2=0110>c3=1100，c4=0011，c5=1001，

Cj+c2=0110=c2，q+c3=1100=c3，q+c4=0011=c4，c]+c5=1001=c5，

c2+c3=1010=?，c2+c4=01