ĐỀ CƠ SỞ TRUYỀN TIN K55 ( Kì 20112)
Câu 1: Cho nguồn tin bao gồm các kí tự (A,B,C,E,F) với tấn suất (12,6,7,1,1)
a. Tính entropy của nguồn tin
b. Sử dụng mã thống kê Shannon-Fano để mã hóa nguồn tin trên
c. Đánh giá hiệu quả của mã Shannon-Fano
Câu 2: Cho mã vòng CRC(n=7,k=4) với đa thức sinh g(x)=a+x+x^3
Bản tin 4 bit có giá trị [1010]
a. Viết ma trận sinh dạng hệ thống của mã vòng CRC(7,4)
b. Xác định từ mã tạo ra từ bản tin trên
Câu 3: Cho mã chập với thông số bộ mã (2,1,3). Đa thức sinh
G1(x)=1+x+x^2
G2(x)= 1+x^2
a. Vẽ mạch tạo mã chập
b. Biểu diễn sơ đồ chuyển trạng thái của mã chập trên.
ĐỀ THI CƠ SỞ TRUYỀN TIN HK 20122 (ĐTVT)_K56
Câu 1: Phát biểu định lý Shannon?
Hãy tính tỷ lệ tín hiệu trên nhiễu SNR [dB], trong điều kiện kênh truyền có nhiễu theo
phân bố Gausian
(kênh AWGN), cho phép truyền luồng dữ liệu tốc độ 240kb/s với bang thông cho phép
BW=2MHz ?

Câu 2: Cho bản tin bao gồm các kí tự (A,B,D,E,F) với tần suất xuất hiện tương ứng là
(23,13,11,8,4)
a. Tính entropy của bản tin
b. Sử dụng mã thống kê Shannon-Fano để mã hóa bản tin trên
c. Đánh giá hiệu quả của mã Shannon-Fano

Câu 3: Cho mã vòng CRC(n=7,k=4) với đa thức sinh g(x)=1+x+x^3
Bản tin 4 bit có giá trị [1010]
d. Viết ma trận sinh dạng hệ thống của mã vòng CRC(7,4)
a. Xác định từ mã tạo ra ma trận bản tin trên

)
kk
Iklnp
x
x
=

- Các đơn vị đo
k1=
()
(
)
kk
Ilnp
x
x
=
(nat)
1
k
ln 2
=

()
(
)
k2k
Ilogp
x
x

1i
HA MIa

=



() () ()
12 s
12 s
aa a
A
pa pa pa

=

(
)
i
0pa 1
()
s
i
i1

(
)
(
)
11
min
HA HA 0
=
=
- Một nguồn tin rời rạc gồm s dấu đồng xác suất cho entropy cực đại. Ta có
(
)
1
max
HA logs=
- Entropy của nguồn rời rạc là một đại lợng giới nội
(
)
1
0 H a logs

Câu 4:
(1 điểm) Định nghĩa khả năng thông qua kênh rời rạc, nêu các tính chất?
- Định nghĩa: Khả năng thông qua của kênh rời rạc là giá trị cực đại của lợng
thông tin chéo trung bình truyền qua kênh trong một đơn vị thời gian lấy theo
mọi khả năng có thể có của nguồn tin A.
() ()
''
k
AA


(
)
(
)
(
)
1
max
H A plogp 1 p log 1 p
=


Khi
1
p1p
2
=
=

(
)
(
)
11
max
HA HA 1bit
=
=


ji i
pb a pa=

(
)
(
)
(
)
ij i j
pab pa pb=
Ta có:
(
)
(
)
j
HAb HA=()
(
)
HAB HA
=

Nhận xét: Lợng thông tin tổn hao trung bình đúng bằng entropy của
nguồn. Kênh không thể truyền tin đợc
- Kênh không nhiễu:
AB

==
=


- Các tính chất:
+
(
)
(
)
(
)
(
)
(
)
HAB HA HBA HB HAB=+ =+
+
(
)
(
)
0HAB HA
+
(
)
(
)
(
)


http://www.ebook.edu.vn
4
()
()
(
)
()
st
ij
ij
i1 j1
i
pa b
IA,B pab log
pa
==
=


(
)
(
)
(
)
(
)
(
)

(
)
12 21
1
s
d
p
ba pba p p==
Cho tốc độ truyền tin của kênh
1
k
vT
=

Tính khả năng thông qua
'
C của kênh này.
Giải:

Ta có
() () ()
'
AA
11
CmaxIA,B maxHBHBA
TT
==






= +




Ta thấy
(
)
HBA không phụ thuộc vào xác suất tiên nghiệm của các tin thuộc
nguồn A. Do đó:

() ()
'
A
11
C maxHB HBA
TT
=

Ta có
(
)
(
)
max
A
max H B H B log 2 1bit===
'


s
p
(
)
21 d
pb a p=

(
)
12 d
pb a p=

A B
''
max
CC
s
p
0
,
5
1
1
http://www.ebook.edu.vn
5
Câu 10: (3 điểm) A chọn ngẫu nhiên một trong các số từ 0 đến 7. Tính số câu
hỏi trung bình tối thiểu mà B cần đặt cho A để xác định đợc số mà A đã chọn.
Nêu thuật toán hỏi? Giả sử A đã chọn số 3, hãy đặt các câu hỏi cần thiết?
Độ bất định của số đợc chọn ngẫu nhiên:

n
HB
=

Số câu hỏi trung bình tối thiểu là:
(
)
()
i
min
max
Ia
n
HB
=(
)
max
HB
khi
1
p1p
2
= =min
3bit

)
(
)
HB plogp 1 plog1 p=
http://www.ebook.edu.vn
6
Với p : xác suất có tín hiệu

1p : xác suất không có tín hiệu
Để xác định đợc khối hỏng (khử hết độ bất định) số phép đo cần thiết n là:

(
)
()
i
min
max
Ia
n
HB
=(
)
HB max khi
1
p1p
2
= =

- 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
khối từ 5
8.
- Lần 3: Đo ở đầu ra khối 6: Không có tín hiệu, khối hỏng nằm trong khối 5
hoặc 6.
- Lần 4: Đo ở đầu ra khối 5: Có tín hiệu. Vậy khối hỏng là khối 6

Câu 12:
(4 điểm) Trong bộ tú lơ khơ 52 quân (không kể făng teo), A rút ra một
quân bài bất kỳ. Tính số câu hỏi trung bình tối tiểu mà B cần đặt cho A để xác
định đợc quân bài mà A đã rút. Nêu thuật toán hỏi? Giả sử A rút ra 7 quân rô,
hãy nêu các câu hỏi cần thiết?
Độ bất định về quân bài mà A đã rút:

() ()
ii
1
Ia logpa log 6bit
52
= = <

Giả sử B đặt cho A câu hỏi dạng lựa chọn, khi đó lợng thông tin nhận đợc
sau mỗi câu trả lời của A là:

(
)
(
)
(
)

=
=
Số câu hỏi trung bình tối thiểu là:
min
log 52 bit
n6
1bit
=
< lần
Thuật toán phải đảm bảo
1
p1p
2
=
=
.
Giả sử A rút ra 7 rô. Các câu hỏi cần thiết có thể nh sau:
- Câu 1: Quân A rút là quân đỏ? Đúng
- Câu 2: Quân A rút là quân cơ? Sai
- Câu 3: Quân A rút có giá trị 7? Đúng (giả sử J = 11, Q = 12, K = 13,
At=1)
- Câu 4: Quân A rút có giá trị 3? Sai
- Câu 5: Quân A rút có giá trị 5? Sai
- Câu 6: Quân A rút là 6 rô? Sai
Vậy quân A rút là 7 rô

Câu 13
:(4 điểm) Trong 27 đồng xu có 1 đồng xu giả nhẹ hơn. Để tìm đợc
đồng xu giả ngời ta sử dụng một cân đĩa thăng bằng. Hãy tính số lần cân
trung bình tối thiểu để xác định đợc đồng xu giả. Nêu thuật toán câ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ả
http://www.ebook.edu.vn
8
nằm trong 9 đồng xu cha cân. Ngợc lại, tuỳ theo cân lệch trái hay lệch
phải ta cũng xác định đợc phần có chứa đồng xu giả.
- Lần 2 : Chia 9 đồng có chứa đồng xu giả thành 3 phần nh nhau, mỗi phần
có 3 đồng xu. Đặt 2 phần bất kỳ lên 2 bàn cân. Kết quả của phép cân sẽ
giúp ta xác định đợc 3 đồng xu có chứa đông xu giả.
- Lần 3 : Lấy 2 đồng xu bất kỳ trong 3 đồng xu có chứa đồng xu giả đặt lên
2 đĩa cân. Sau lần cân này ta sẽ xác định đợc đồng xu giả.

Câu 14
: (2 điểm) Tính entropie của trờng sự kiện đồng thời ?
Xét 2 trờng sự kiện A và B sau :
()
()
j
i
i
j
b
a
Ai1,0B j1,t
pa
pb



== ==


==
=
Câu 15:
(2 điểm) Cho kênh nhị phân đối xứng không nhớ sau (hình vẽ).
Hãy tính phân bố xác suất của các tin ở đầu ra?
Biết rằng p(a
1
)=p ; p(a
2
)=1-p.

Theo công thức xác suất đầy đủ ta có:
(
)
(
)
(
)
(
)
(
)
() ()()()()
()
1111212
2121222
1

a
(
)
21 d
pb a p=
(
)
12 d
pb a p=
B
http://www.ebook.edu.vn
9

()
()
i
n
i
i
i
i
a
AV
pa
pa


==




() () () ()
ss
ii 1 i i
i1 i1
npanHA palogpa
==
==


ta có:
()
i
i
1
nlog
pa


Nguyên tắc:
Các tin có xác suất xuất hiện lớn đợc mã hoá bằng các từ mã có
độ dài nhỏ và ngợc lại các tin có xác suất xuất hiện nhỏ đợc mã hoá bằng các từ
mã có độ dài lớn.

Câu3:
(1 điểm) Trọng số của từ mã: định nghĩa và tính chất?
- Định nghĩa trọng số của từ mã:
(
)
i

có khả năng
phát hiện t sai thoả mãn điều kiện
0
td 1

.
- Định lý về khả năng sửa sai:
http://www.ebook.edu.vn
10
Mã đều nhị phân có độ thừa với khoảng cách Hamming
0
d3 có khả năng
sửa đợc t sai thoả mãn điều kiện:
0
d1
t
2








. Trong đó
[]
x
ký hiệu phần
nguyên của số x.


- Tính chất:
+
(
)
nn
ij
d, 0
(
)
nn
ij
d, 0 = khi
nn
ij


+
(
)
nn
ij
d, n
+ Tính chất tam giác:
(
)
(
)
(
)

346
1101000
xx
0110100
xx x
0011010
xxx
0001101
xxx

++



++


=


++



++


1
G=
Ma trận kiểm tra H :

0
+++
++ +++
++
++
+++
++
++
++
7
x(
)
()
(
)
()
()
()
deg h x
*1432
*
*
r1 *
234
345
2456
hX X hX x x x 1




Ta có
T
G.H 0=

Câu 7: (2 điểm) hãy thiết lập từ mã hệ thống của bộ mã xyclic (7,4) có đa thức
sinh
()
3
g x =1+x+x tơng ứng với đa thức thông tin
(
)
3
a x = x + x . (Sử dụng
thuật toán 4 bớc).
- Bớc 1:
()
3
ax=x+x
- Bớc 2: Nâng bậc
(
)
(
)
37464
xxx xx

=

)
()
nk
64
66
axx rx
xxx1 1100101
x x

=+
=+++
f
f
x
xhttp://www.ebook.edu.vn
12
Câu 8: (2 điểm) Cho phân tích
7
x
+1 nh sau

(
)
(
)
(
)

3
23
1+x +x

(
)
7,4
3
4
24
1+x+x +x
(
)
7,3
4
5
234
1+x +x +x
(
)
7,3
4
6


6
i
i=0
x


i
a
(
)
p
i
a
Từ mã

i
n
i

i
n
1
1
a 14
0 0 2
2
2
a

14

0 1 2
3
3
a 18
1 0 0 3

1 1 1 1 1 1 6
http://www.ebook.edu.vn
13
- Đánh giá hiệu quả:

()
10
ii
i1
11 1 1
n p a n 2.2. 3.3. 3.5. 2.6.
483264
915 6 25
12.
83232 32
=
==+++
=+ + + =

dấu

() ()
()
10
1i
i1
i
11 1 1 1
H A p a log 2. .log 4 3. log8 3. log32 2. log 64
pa 4 8 32 64

có dạng sau
(
)
65432
v x =x +x +x +x +x
. Hãy sử dụng
thuật toán chia dịch vòng để tìm đợc từ mã đã phát, biết rằng mã (7, 3) này có
0
d=4.
-
Bớc 1: Chia v(x) cho g(x)

()
54323
643 2 2
5
532
32
0
xxxxxx1
xxxx xx
x
xxxx
rx x x x
++++ ++
+++ +
+++
=++
6
x

xxxx
rx x x 1
++++ ++
+++ +
++
+++
=++
6
x(
)
(
)
1
Wr x 3 t 1=>= Bớc 3
http://www.ebook.edu.vn
14
- Bớc 3: (lần 2):
(
)
2654
x.vx x x x x 1=++++

()
54 3
643 2 2
532
532

()
2
654
^
2
22
^
6432
*
xvx r x
xxxx
x
xx
x x x x x 0011101
+
+
++
==
=+++
f
f

Sai ở
5
x đã đợc sửa
Câu 11: (3 điểm) Hãy xác định tập tất cả các từ mã của bộ mã xyclic (7, 3) có đa
thức sinh


Tập
3
28==
k
2 từ mã, trong đó 7 từ mã khác không là tập các tổ hợp tuyến
tính các hàng của ma trận G

(
)
()
()
()()
()
()
()
()
()
()
345
22456
25
2356
2236
246
101110 0
xg x x x x x 0101110
xgxxxxx 0010111
1xgx 1x x x 1110010
1 x g x 1 x x x 1001011


Chứng minh: Số các kiểu sai có trọng số i là
i
n
C
Số các kiểu sai có trọng số t là:
t
01 t i
nn n n
i0
CC C C
=
+++=


Số các trạng thái khác nhau của các dấu kiểm tra là:
rnk
22

=
Để sửa đợc sai, mỗi trạng thái của các dấu kiểm tra chỉ đợc gán tối đa
cho 1 kiểu sai.
Vậy để sửa đợc tất cả các kiểu sai có trọng số
t ta có:
t
ink
n
i0
C2


Câu 13: (4 điểm) Cho phân tích của x
15
+1 nh sau :
X
15
+1=(1+x)(1+x+x
2
)(1+x+x
4
)(1+x
3
+x
4
)(1+x+x
2
+x
3
+x
4
)
Hãy nêu tất cả các mã xyclic có độ dài 15 trên vành Z
2
[x]/x
15

gX
(15,13)
3
()
3
gX
(15,11)
4
()
4
gX
(15,11)
5
()
5
gX
(15,11)
6
12
g.g
(15,12)
7
13
g.g

(15,10)
8
14
g.g
(15,10)

(15,7)
16
123
g.g.g
(15,8)
17
124
g.g.g
(15,8)
18
125
g.g.g
(15,8)
19
234
g.g.g
(15,5)
20
235
g.g.g
(15,5)
21
134
g.g.g
(15,6)
22
135
g.g.g
(15,6)
23

g.g.g .g

(15,2)
31 1 (15,15)

http://www.ebook.edu.vn
17

Câu 14:(3 điểm) Mô tả sơ đồ chức năng thiết bị mã hoá theo phơng pháp chia
cho mã xyclic hệ thống (7,4) có đa thức sinh g(x)=1+x+x
3
. Tìm từ mã đầu ra của
thiết bị này khi đa thức thông tin đầu vào a(x)=1+x
3
.

Mã (7, 4) có
(
)
3
gX 1 X X=+ + (

17
ữ
1
V
Vào
1 2
+
3
+
57
ữ

2
V
14
ữ
RA
http://www.ebook.edu.vn
18
C©u 15: (2 ®iÓm) M« t¶ vµnh ®a thøc víi 2 phÐp to¸n céng vµ nh©n c¸c ®a thøc
theo modulo x
n
+1


∑∑
axbx

() () ()
n1
i
i
i0
cX aX bX c
−
=
=+=
∑
x
trong ®ã
iii
cabmod2
=
+
PhÐp nh©n:
(
)
(
)
(
)
(
)
n
aX.bX aX.bXmodX 1=+