信息科学基础20**年A'卷及答案

河北科技大学2012——2013 学年第一学期

《信息科学基础》试卷（A ′）

学院 理学院 班级 姓名 学号

一、简答题（共8题，每题5分）

1. 居住某一地区的女孩中有25%是大学生，在女大学生中有75%是身高1.6米以上的，而女孩中身高1.6米以上的占总数一半。假如我们得知“身高1.6米以上的女孩是大学生”的消息，问获得多少信息量？

2．有一个马尔可夫信源，已知转移概率为p (S 1/S 1) =

23

，p

(S 2/S 1) =

13

，

p (S 1/S 2) =1，p (S 2/S 2) =0。试画出状态转移图，并求出信源熵。

⎡2⎢3

3. 设二进制对称信道的传递矩阵为⎢

⎢1⎢⎣31⎤

3⎥⎥ 2⎥3⎥⎦

（1）若P(0)=3/4,P(1)=1/4,求H(X)、H(X/Y)、H(Y/X)和I(X；Y) ； （2）求该信道的信道容量及其达到信道容量的输入概率分布。

4. 求以下三个信道的信道容量：

，

，

5. 有一信源，它有6个可能的输出，其概率分布如下表所示，表中给出了对应的码A ，B ，C ，D ，E 和F 。

(1)求这些码中哪些是唯一可译码； (2)求哪些是非延长码（即时码）； (3)对所有唯一可译码求出其平均码长L

6. 解释等长信源编码定理和无失真变长信源编码定理，说明对于等长码和变长码，最佳码的每符号平均码长最小为多少？编码效率最高可达多少？

7. 设某二元码书C={111000，001011，010110，101110}，

。

①假设码字等概率分布，计算此码的编码效率？

②采用最小距离译码准则，当接收序列为110110时，应译成什么码字？

⎡1⎢2⎢1

8. 设有一离散无记忆信道，其信道矩阵为P =⎢

⎢6⎢1⎢⎢⎣3

p (x 2) =p (x 3) =

14

131216

1⎤

6⎥⎥1⎥1

，若p (x 1) =，3⎥2⎥1⎥2⎥⎦

。试求最佳译码时的平均错误概率。

二、综合题（共6题，每题10分）

⎧⎩

1

⎫⎭

1. 某一信道，其输入X 的符号集为⎨0, ,1⎬，输入Y 的符号集为{0,1}, 信道矩阵

2

⎡1

⎢1

为P =⎢

⎢2⎢0⎣

0⎤⎥1⎥2⎥1⎥⎦

，现有4个消息的信源通过这信道传输（消息等概率出现），若

对信源进行编码，我们选这样一种码，C :{(x 1, x 2, , )} x i =0或1(i =1, 2)

22

11

11

其码长为n =4。并选取这样的译码规则f (y 1, y 2, y 3, y 4) =(y 1, y 2, , )

22

（1） 这样编码后信息传输率等于多少？

（2） 证明在选用的译码规则下，对所有码字有P E =0

2、二元平稳马氏链，已知P （0/0）=0.8，P （1/1）=0.7，求：每三个符号合成一个来编二进制Huffman 码, 试建立新信源的模型，给出编码结果。

0⎡q

3. 设某齐次马氏链的一步转移概率矩阵为⎢

1q ⎢2⎢⎣0

1p 0q

20⎤

⎥ p ⎥p ⎥⎦

试求：（1）该马氏链的二步转移概率矩阵；

（2）平稳后状态“0”，“1”，“2”的极限概率。

⎡X ⎤⎡x 1

4. 设有一离散无记忆信源，其概率空间为⎢⎥=⎢

⎣P ⎦⎣0.6

x 2⎤⎥0.4⎦

，它们通过一干扰信

道，信道输出端的接受符号集为Y =[y 1, y 2]，信道传递概率如图所示。

求：（1）信源X 中事件x 1和x 2分别含有的自信息；

（2）收到信息y j (j =1, 2) 后，获得的关于x i (i =1, 2) 的信息量； （3） 信源X 和信源Y 的信息熵；

（4） 信道疑义度H (X /Y ) 和噪声熵H (Y /X ) ； （5） 接收到信息Y 后获得的平均互信息。

5. 设输入符号集为X={0,1},输出符号集为Y={0,1}。定义失真函数为d(0,0)=d(1,1)=0, d(0,1)=d(1,0)=1, 试求失真矩阵D.

6. 设消息集合共有7个元素，它们分别被编码为{a,c, ad, abb,bad,deb, bbcde}, 试利用惟一可译码判别准则判定它是否为惟一可译码。

河北科技大学2012——2013 学年第一学期

《信息科学基础》答案（A ′）

一、

简答题（共8题，每题5分）

1. 答：设A 表示“大学生”这一事件，B 表示“身高1.60m 以上”这一事件，

则p (A ) =0.25，p (B ) =0.5，p (B /A ) =0.75

故

p (A /B ) =

p (AB ) p (B )

=

p (A ) p (B /A )

p (B )

1

=0.375

I (A /B ) =log 2

1p (A /B )

=log 2

0.375

=1.42(bit )

⎡2

2. 答：状态转移矩阵P =⎢3

⎢⎣1

⎡7

1⎤

⎢92⎥3 P =⎢

⎥⎢20⎦

⎢⎣32⎤

9⎥

⎥，故该马尔可夫信源是遍历的。

1⎥3⎥⎦

设W =[W 1

⎧2

W 1+W 2=W 1⎪⎪3

W 2] 由W P =W 即⎨ W 1+W 2=1

1⎪W 1=W 2

⎪3⎩

3⎧

W =1⎪⎪4

求得⎨ 所以信源熵为H (X ) =

⎪W =12⎪⎩4

2

∑

i =1

p (S i ) H (X /S i )=0.688（bit/符号）

3.（1）答 ：联合概率矩阵P XY

⎡1

⎢2=⎢⎢1⎢⎣121⎤

4⎥⎥ 1⎥6⎥⎦

边缘概率分布为P X =[p (0)

⎡7

p (1)] P Y =

⎢12⎣5⎤

⎥12⎦

（1）H(X)= -p (0)log 2p (0)-p (1)log 1p (1)=0.811(bit )

又因为信道传递矩阵P Y /X

⎡2

⎢3=⎢⎢1⎢⎣31⎤

3⎥⎥ 2⎥3⎥⎦

22

故H (Y /X ) =-∑∑p (x i y i ) log p (y i /x i ) =0.918(bit ) H (Y ) =0.98(bit )

i =1

j =1

H (X /Y ) =H (X , Y ) -H (Y ) =0.749(bit ) I (X ; Y ) =H (X ) -H (X /Y ) =0.06(bit )

22

（2）设P X =[w

]，其中H (Y /X ) =-∑

i =1

∑

j =1

p (x i y i ) log p (y i /x i ) =0.918(bit )

又由最大熵定理得H (Y ) ≤log M =log 22=1(bit )

所以有I (X ; Y ) =H (Y ) -H (Y /X ) ≤0.082(bit ) 故C =max{I (X ; Y )}=0.082(bit )

p (x )

而上述等号成立的条件为p (y 1) =p (y 2)

又因为P Y =⎢w +3⎣3

⎡2113

w +

21121⎤

⎥ ，所以须w +=w + ，w ==

333323⎦

2

因此达到信道容量时，信道输入概率为P X =⎢⎣2

⎡1

1⎤2⎥⎦

4.答：P1为一一对应确定信道，因此有P2为具有归并性能的信道，因此有P3为具有发散性能的信道，因此有

。 。 。

5. 答：（1）惟一可译码有A ，B 和C 。（2） 即时码有A 和C 。（3L A =3(码元/信源符号) 同理得L B =

178

(码元/信源符号) ，L C =

178

(码元/信源符号)

6. 答：等长信源编码定理：

对于任意当L 足够长时必可使译码差错

。

，只要，则

变长信源编码定理：只要，一定存在一种无失真编码。

等长码和变长码的最小平均码长均为，编码效率最高可达100%。

7. 答：（1）（2）令接收序列为

，

则有

，

，

，

，故接收序列应译为010110。

8. 答：用极大似然译码规则译码，先写出输入输出的联合概率分布

⎡1

⎢4⎢1

P (X , Y ) =⎢

⎢24⎢1⎢⎢⎣12

1618124

1⎤

12⎥⎥1⎥

12⎥⎥1⎥8⎥⎦

1124

平均译码错误概率为p E =

二、综合题（共6题，每题10分）

1. 答：(1)对信源四个消息进行编码，选择码长n =4，这组码为

C :{(x 1, x 2,

11

, )} x i =0或1(i =1, 2) 22

所以，码字为C :{⎛ 00

⎝

12

1⎫⎛

⎪, 02⎭⎝12

1

12

1⎫⎛⎪, 12⎭⎝

12

1⎫⎛

⎪, 112⎭⎝

12

1⎫⎪} 2⎭

编码后信息传输率R =

H (S ) L

=

（bit/码元符号）

（2）设接收序列β=(y 1y 2y 3y 4) ，y i ∈{0,1}(i =1, 2, 3, 4) ，根据信道的传输特性，接受序列β共有16个，正好分成4个互不相交的子集，每一个码字只传输到其中对应的一个子集：α1= 00

⎝

⎛⎝

1212

⎛

12

1⎫

⎪→(00y 3y 4) ，2⎭

12

1⎫

⎪→(10y 3y 4) 2⎭

α2= 0

1

1⎫⎛⎪→(01y 3y 4) ，α3= 12⎭⎝

，

α4= 11

⎝

⎛

1⎫

⎪→(11y 3y 4) y 3, y 4∈{0,1} 2⎭

具体传输信道如下：

⎡000011⎢00122⎢

⎢411

⎢01

22⎢011⎢10⎢22⎢011⎢11⎢220

⎢⎣

000114000

001014000

001114000

010001400

010101400

011001400

011101400

100000140

100100140

101000140

101100140

110000014

110100014

111000014

1111⎤

⎥⎥0

⎥⎥0⎥

⎥⎥0⎥

⎥1⎥

⎥4⎦

所以根据选取的译码规则f (y 1y 2y 3y 4) =(y 1y 2

1122

)

正好将接受序列译成所发送的码字。可计算对于每个码字引起的错误概率

p E =[∑p (β/αi ), F (β) ≠αi ]=0 (i =1, 2, 3, 4)

(i )

Y

所以有P E =

∑

C

p (αi ) p E =0

(i )

2.

答：由

限概率：p(0)=0.6, p(1)=0.4 新信源共8个序列，各序列的概率为

信源模型为⎨

⎧

P（0/0）=0.8，P （1/1）=0.7, 得极

⎫⎬

⎩0.3840.0960.0360.0840.0960.0240.0840.196⎭

一种编码结果（依信源模型中的序列次序）为0,001,10101,1101,1011，00101,0011,111.

3.答：（1）由一步转移概率矩阵与二步转移概率矩阵的公式P 2=P ⨯P 得

⎡q 2+pq ⎢22

P =⎢q

⎢q 2⎣

pq 2pq pq

⎤⎥2

p ⎥2

p +pq ⎥⎦p

2

（2）设平稳状态W ={W 1, W 2, W 3}，马尔可夫信源性质知W P =W

，即

⎧qW 1+qW 2=W 1

⎪

⎪pW 1+qW 3=W 2⎨

⎪pW 2+pW 3=W 3⎪W +W +W =1

23⎩1

2

⎧q ⎪W 1=2

1-p +p ⎪

⎪pq ⎪

求解得稳态后的概率为⎨W 2=2

1-p +p ⎪

2⎪p

⎪W 3=2

1-p +p ⎪⎩

4.答：（1）

I (x 1) =-log p (x 1) =0.737(bit ) I (x 2) =-log p (x 2) =1.322(bit )

（2）

I (x 1; y 1) =log I (x 1; y 2) =log

p (y 1/x 1) p (y 1) p (y 2/x 1) p (y 2) p (y 1/x 2) p (y 1)

=0.059(bit ) =0.263(bit )

=0.093(bit ) =0.322(bit )

I (x 2; y 1) =log I (x 2; y 2) =log

p (y 2/x 2) p (y 2)

2

（3）信源X 和信源Y 的信息熵H (X ) =-∑p (x i ) log p (x i ) =0.97(bit )

i =1

2

H (Y ) =-∑p (y j ) log p (y j ) =0.722(bit )

j =1

（4）信道疑义度

H (X /Y ) =H (X , Y ) -H (Y ) =H (X ) +H (Y /X ) -H (Y ) =0.963(bit )

（5）平均互信息I (X , Y ) =H (X ) =H (X /Y ) =0.007(bit )

⎡0

5.答：D =⎢

⎣11⎤⎥0⎦

6. 答：S0 S1 S2 S3 S4 S5 S6 S7 a d eb d eb c bb cde de b ad

abb bad ad deb

bbcde bcde

S1到S7中都不包含S0中的元素，因此，S0是惟一可译码。