http://www.ebook.edu.vn
1
đáp án Ngành đào tạo: Điện tử viễn thông
Hệ đào tạo : Đại học
Môn học : Lý thuyết thông tin Mã số 411 LTT 340A Số ĐVHT: 4

Phần 1: lý thuyết thông tin
Câu 1:
(1 điểm): Định nghĩa lợng thông tin riêng (độ bất định) của một biến
ngẫu nhiên. Xác định các đơn vị đo
- Định nghĩa lợng thông tin riêng (độ bất định)
Lợng thông tin riêng là độ bất định tiềm năng chứa trong một biến cố ngẫu
nhiên
k
x
.
Ký hiệu
(
)
k
I
x(
)
(
)

(bít)
1
k
ln10
=

(
)
(
)
kk
Ilgp
x
x
=
(hart)
1 nat = 1,443 bít
1 hart = 3,322 bít

Câu 2:
(1 điểm) Định nghĩa entropy của nguồn rời rạc
Entropy của nguồn tin rời rạc A là trung bình thống kê của lợng thông tin
riêng của các tin thuộc A
Ký hiệu:
()
1
HA

() ()
1i

=
=


() () ()
s'
1ii
i1
HA palogpa
=
=

(bít)
http://www.ebook.edu.vn
2
Câu 3: (1 điểm) Nêu các tính chất của entropy của nguồn rời rạc
Các tính chất của
()
1
HA
- Khi
()
k
pa 1= ,
()
i
pa 0= với ik

thì
(


== (bps)
- Các tính chất:
+
'
C0
'
C0= khi A và B là độc lập (kênh bị đứt)
+
'
k
Cvlogs
'
k
Cvlogs= khi kênh không nhiễu

Câu 5
: (2 điểm) Entropy của nguồn rời rạc nhị phân. ý nghĩa của dơn vị đo bít?
- Entropy của nguồn rời rạc nhị phân.
12
aa
A
p1p

=



một nguồn rời rạc 2 phân đồng xác suất. ()
1
HA
(bits)
p
0
,
5
1
1
http://www.ebook.edu.vn
3
Câu 6: (2 điểm) Xác định hai trạng thái cực đoan của kênh rời rạc.
- Kênh bị đứt:
Các nguồn tin A và B ở hai đầu thu và phát là độc lập.

()
(
)
ij i
pa b pa=

(
)
(
)
ji i

kk
pa b 1
=

(
)
k
HAb 0
=

()
HAB 0
=

Nhận xét: Lợng thông tin tổn hao trên kênh bằng 0

Câu 7:
(2 điểm) Entropy có điều kiện
(
)
HAB: định nghĩa và nêu các tính chất
- Định nghĩa: Entropy có điều kiện về 1 trờng tin A khi đã rõ trờng tin B đợc
xác định theo công thức sau:
()
() ()
st
ij i j
i1 j1
HAB pab logpa b
==


Câu 8:
(2 điểm) Lợng thông tin chéo trung bình truyền qua kênh rời rạc: định
nghĩa và tính chất
- Định nghĩa:
()
(
)
ij
IA,B MIa,b



=



với
()
(
)
()
ij
ij
i
pa b
Ia,b log
pa
=


- Tính chất:
+
(
)
IA,B 0
+
(
)
(
)
IA,B HA

Câu 9:
(3 điểm) Cho kênh đối xứng nhị phân sau
()
1
p
ap=

(
)
2
1
p
ap
=

(
)
(


Trong đó:
() ()
()()
() ()()()()
()
()()()()
()() () ()()
()()
2t
iji ji
i1 j1
111 11 21 21
212 12 22 22
s sss ss s s
ss s s
HBA pa pb a logpb a
pa pbalogpba pbalogpba
pa pbalogpba pbalogpba
p 1 p log 1 p p logp 1 p p log p 1 p log 1 p
plogp 1 p log1 p
==
=
= +

+


=+ +


1
C
T
=
khi
s
p0=
(kênh không nhiễu)
()()
'
ss s s
'
max
C
1 p log p 1 p log 1 p
C
=+ + 2
b
1
b
2
a
1
a
s
p


() ()
ii
1
Ia logpa log 3bit
8
= = =

Để tìm đợc số đã chọn của A, B phải đặt các câu hỏi cho A để thu đợc đủ
một lợng thông tin cần thiết là 3 bít.
Mỗi câu hỏi của B (dạng lựa chọn) có thể xem là nguồn rời rạc nhị phân, bởi
vậy lợng thông tin nhận đợc sau mỗi câu trả lời tơng ứng là:

(
)
(
)
(
)
HB plogp 1 plog1 p=
Với p : xác suất nhận câu trả lời
đúng

1p : xác suất nhận câu trả lời sai
Vậy số câu hỏi cần thiết n là :
(
)
()
i
Ia
n

1bit
==
lần hỏi
Giả sử A chọn số B. Các câu hỏi b có thể đặt cho A là:
- Câu 1 - Số A chọn lớn hơn 3? Trả lời: Sai
- Câu 2 - Số A chọn lớn hơn 1? Trả lời: Đúng
- Câu 3 - Số A chọn lớn hơn 2? Trả lời: Sai
Vậy số A chọn là 3

Câu 11:
(4 điểm) Một thiết bị vô tuyến điện gồm 16 khối có độ tin cậy nh nhau
và đợc mắc nối tiếp. Ta sử dụng một thiết bị đo để đo tín hiệu ra của các khối.
Giả sử có một khối nào đó bị hỏng. Hãy tính số lần đo trung bình tối thiểu để tìm
đợc khối bị hỏng. Nêu thuật toán đo? Giả sử khối hỏng là khối thứ 6, tìm vị trí
các điểm đo cần thiết?
Theo giả thiết độ bất định của khối hỏng là:

() ()
ii
1
Ia logpa log 4bit
16
= = =

Lợng thông tin nhận đợc sau mỗi phép đo:

(
)
(
)


(
)
max
HB 1bit=

min
4bit
n4
1bit
==
lần đo
Để n
min
thuật toán đo phải đảm bảo
(
)
HB max Mỗi lần đo phải đo ở
điểm giữa của các khối cần xác định nhằm đảm bảo
1
p1p
2
=
=
.
Giả sử khối hỏng là khối 6. Các phép đo cần thiết là:
- Lần 1: Đo ở đầu ra khối 8: Không có tín hiệu, khối hỏng nằm trong các
khối từ 1
8.
- Lần 2: Đo ở đầu ra khối 4: Không có tín hiệu, khối hỏng nằm trong các

Với p : xác suất nhận câu trả lời là
đúng

1p : xác suất nhận câu trả lời là sai
Số câu hỏi cần thiết để xác định đợc quân bài A đã rút là:
(
)
()
i
Ia
n
HB
=

http://www.ebook.edu.vn
7
Ta thấy nmin khi
(
)
HB max
(
)
(
)
max
HB HB 1bit== khi
1
p1p
2
=

I(x
i
) = - log p(x
i
) = - log 1/27 = log 27 bit
Khi sử dụng cân đĩa thăng bằng, sau mỗi lần cân các sự kiện có thể có là :
- Cân thăng bằng với xác suất p
- Cân lệch trái với xác suất q
- Cân lệch phải với xác suất 1-p-q
Lợng thông tin nhận đợc sau mỗi lần cân :
H(B) = -plog p qlog q (1-p-q)log (1-p-q)
Để xác định đợc đồng xu giả tổng lợng thông tin nhận đợc sau các lần cân
phải không nhỏ hơn độ bất định của đông xu giả. Nh vậy số lần cân cần thiết
là : n = I(x
i
)/H(B)
Để n có giá trị nhỏ nhất thì H(B) phải đạt giá trị cực đại.
Ta có H(B) = H(B)
max
= log 3 khi p = q = 1-p-q = 1/3.
Khi đó n
min
= I(x
i
)/H(B)
max
= log27/log 3 = 3 lần cân.
Thuật toán cân nh sau( đảm bảo p = q = 1-p-q )
- Lần 1 : Chia 27 đồng xu thành 3 phần, mỗi phần có 9 đồng xu. Lấy 2 phần
bất kỳ đặt lên mỗi bàn cân 1 phần . Nếu cân thăng bằng thì đồng xu giả




Khi đó, trờng sự kiện đồng thời
CA.B
=
là :
()
()
ij
ij
ab
Ci,j,i1,0,j1,t
pa pb


===




Theo định nghĩa, entropie của trờng sự kiện đồng thời đợc xác định nh
sau :
()
() ()
st
ij ij
i1 j1
HC pab logpab
==

pb pa .pb a pa .pb a
1pb
=+
=+
=Phần 2: lý thuyết m hoá
Câu 1:
(1 điểm): Định nghĩa độ dài trung bình của từ mã ? Phát biểu định lý mã
hoá thứ nhất của Shannon?
Xét phép mã hoá các tin rời rạc sau:
i
n
ii
a
A
1
a
2
b
1
b
S
p
S
p

2
a




- Định nghĩa: Độ dài trung bình của từ mã là kỳ vọng của đại lợng ngẫu nhiên
i
n

()
s
ii
i1
npan
=
=


- Định lý mã hoá thứ nhất của Shannon (đối với mã nhị phân)
Luôn luôn có thể xây dựng đợc một phép mã hoá các tin rời rạc có hiệu quả
mà độ dài trung bình của từ mã có thể nhỏ tuỳ ý, nhng không nhỏ hơn
entropie xác định bởi các đặc tính thống kê của nguồn

(
)
1
nHA

Câu 2:
(1 điểm) Nêu nguyên tắc lập mã tiết kiệm?
Từ định lý mã hoá thứ 1 của Shannon:


i
W


Trọng số của 1 từ mã là số các dấu mã khác không chứa trong từ mã
- Tính chất:
+
(
)
i
n
i
0W 1
+
(
)
(
)
nn nn
ij ij
Wd,+ =

Câu 4:
(1 điểm) Nêu các định lý quy định khả năng phát hiện sai và khả năng
sửa sai của một bộ mã?
- Định lý về khả năng phát hiện sai:
Mã đều nhị phân có độ thừa với khoảng cách Hamming
0
d1>
có khả năng

Câu 5:
(2 điểm) Khoảng cách mã: định nghĩa, tính chất? Định nghĩa khoảng
cách mã tối thiểu?
- Định nghĩa:
Khoảng cách giữa hai từ mã
n
i

và
n
j

là số các dấu mã khác nhau về giá
trị tính theo cùng một thứ tự giữa 2 từ mã này.
Ví dụ:
7
i
0110100=
7
j
1010011
** ***
=()
77
ij
d, 5 =


ij jk ik
d, d, d, +
Định nghĩa khoảng cách mã tối thiểu:
d
0
= min d( a
i
n
, a
j
n
) với mọi i,j

Câu 6:
(2 điểm) Cho mã xyclic
(
)
V- n-k có đa thức sinh
()
3
g x =1+x+x
(
)
n =7, k = 4 . Hãy thiết lập ma trận sinh và ma trận kiểm tra của mã này?
Cho ma trận sinh G.

3
24
235
346

()
()
7
42
x1
xxx1
gx
+
==+++
hx
http://www.ebook.edu.vn
11

3
75442
54
532
432
42
3
3
1xx1
xxxxxx1
xx1
xxx
xxx1
xxx
xx1
xx1
0

x.h x
H

x.hx
1x x x 1011100
H x x x x 0101110
xxxx 0010111


==+++



=





+++



=+++=




+++


n-k
axx
- Bớc 3: Chia tính d:

()
43
643 3
3
3
xxx1
xxx x1
x
xx1
rx x 1
+
++
++ +
++
=+
6
x

- Bớc 4: Thiết lập từ mã f(x)

(
)
(
)
(
)

1x x 1x x++ + +
7
x+1=1+x
Hãy nêu tất cả các mã xyclic có thể có trên vành
[
]
x
7
2
Z
x+1
.

TT Đa thức sinh g(x) Mã (n, k)
0
d
1
1+x
(
)
7,6
2
2
3
1+x+x
(
)
7,4
3
3

)
7,1
7
7 1
(
)
7,7
1 Câu 9: (4 điểm) Hãy thực hiện mã hoá Shannon Fano cho nguồn rời rạc A sau:






12345 6 7 8 9 10
aaaaaa aa aa
A=
11111 1 1 1 1 1
4
4 8 8 8 32 32 32 64 64

Đánh giá hiệu quả của phép mã hoá này?
Hãy giải mã cho dãy bít nhận đợc có dạng: 101100111010101TT
i

4
a 18
1 0 1 3
5
5
a

18

1 1 0 3
6
6
a 132
1 1 1 0 0 5
7
7
a 132
1 1 1 0 1 5
8
8
a 132
1 1 1 1 0 5
9
9
a 164
1 1 1 1 1 0 6
10
10
a 164
1 1 1 1 1 1 6

2.
32
=
==+++
=

bit(
)
1
nHA= phép mã hoá là tối u
-
Giải mã cho dãy bít nhận sau:

43 842
10 1 10 0 111 0 10 1 0 1
aa aaa

Câu 10: (4 điểm) Giả sử từ mã nhận đợc của mã xyclic (7,3) với đa thức sinh
(
)
2
4
g x =1+x+x +x
có dạng sau

- Bớc 2:
()
()
0
d1 41
Wr x 3 t 1,5
22


=>= = =



- Bớc 3: (lần 1)
(
)
6543
x.v x x x x x 1=++++

()
543 3
643 2 2
52
532
3
1
xxx1xx1
xxxx xx
xx1
xxxx

xxx1xx1
xxxx xx
xxxx1
xxxx
rx 1
++++ ++
+++ +
++++
+++
=
6
x(
)
()
2
Wr x 1 t
=
=
-
Bớc 4:

()
(
)
(
)
()

)
2
34
g x =1+x +x +x .
Cho mã xyclic (7, 3) có
(
)
234
g x =1+x +x +x ma trận sinh:

234
345
2456
1x x x 1011100
G x x x x 0101110
xxxx 0010111

+++



=+++=




+++




1 x x g x 1 x x x 1100101

=+ + +
=+++
+=+++
+=+++
+=+++
++ =++ +
234
g x =1+x +x +x
http://www.ebook.edu.vn
15
Câu 12: (3 điểm) Phát biểu và chứng minh giới hạn Hamming? Định nghĩa mã
hoàn thiện?
- Giới hạn Hamming.
Với mã tuyến tính (n, k), điều kiện cần để sử đợc t sai là:

t
ink
n
i0
C2

=







-
Định nghĩa mã hoàn thiện.
Mã hoàn thiện là mã (n, k, d) đạt đợc giới hạn Hamming
Ví dụ: Mã (7, 4) có d = 3
Ta có :
d1
t1
2



==





01743
77
CC2 28
178

+ ==
+=

Vậy mã (7, 4) là 1 mã hoàn thiện.



Đặt

(
)
(
)
() ()
2
12
434
34
gX 1X gX 1X X
gX 1XX gX 1X X
=+ =+ +
=+ + =+ +http://www.ebook.edu.vn
16
TT §a thøc sinh M· (n,k)
1
()
1
gX
(15,14)
2
()
2
gX

15
g.g
(15,10)
10
23
g.g

(15,9)
11
()
24
g.g
(15,9)
12
25
g.g

(15,9)
13
34
g.g
(15,7)
14
35
g.g
(15,7)
15
45
g.g
(15,7)

g.g.g
(15,6)
24
245
g.g.g
(15,5)
25
345
g.g.g
(15,3)
26
1234
g.g.g.g
(15,4)
27
1235
g.g.g.g

(15,4)
28
1245
g.g.g.g
(15,4)
29
2345
g.g.g.g
(15,1)
30
1345
g.g.g.g

()
3
nk 6 3
aX 1 X
aX.x X X

=+
=+Trạng thái các ô nhớ
Xung
nhịp
Vào
1 2 1
Ra
1 1 1 1 0 1
2 0 0 1 1 0
3 0 1 1 1 0
4 1 0 1 1 1
5 0 0 0 1 1
6 0 0 0 0 1
7 0 0 0 0 0

Từ mã ra 0 1 1 1 0 0 1
236
XX X X+ + +

[
]
2
n
Zx
1α+() () ()
n1
i
ii
i0
X;degXn1;GF2
−
=
=≤−∈
∑
ffxf f
PhÐp céng:
() ()
n1 n1
ii
ii
i0 i0
Xa;Xb
−−
==
==
∑∑

ij ijmodn
X.X X
+
=