Trang 1
Đại học Quốc gia Tp. Hồ Chí Minh Đề Thi Học Kỳ 1/2003
Trường Đại Học Bách Khoa Môn Lý Thuyết Thông Tin - 501037
Khoa Công Nghệ Thông Tin Ngày 15/01/2004 - Thời gian 90 phút
---oOo---
ĐỀ 0001

Họ tên: ....................................................... MSSV:.........................
Lưu ý: 1. Sinh viên trả lời vào PHIẾU TRẢ LỜI TRẮC NGHIỆM. Sinh viên phải điền đầy đủ các thông tin vào
PHIẾU TRẢ LỜI TRẮC NGHIỆM chú ý MSMH: 501037.
2. Sinh viên phải điền họ tên và MSSV của mình vào đề thi. Sinh viên được phép giữ lại đề thi.
3. Đề gồm 4 trang, 50 câu.
4. Sinh viên chỉ được phép sử dụng tài liệu trong ba tờ giấy khổ A4.
Dành cho câu 1 đến câu 9: Cho nguồn X = {a
1
, a
2
, a
3
, a
4
, a
5
, a
6
, a
7
, a
8
} có các xác suất lần lượt như sau: 0,2; 0,18;
0,15; 0,14; 0,12; 0,09; 0,08; 0,04. Mã hoá nguồn này bằng hai phương pháp Fano và Huffman với qui ước sau: Đối

6
được mã hoá thành
(A). 110 (B). 101 (C). 111 (D). 010 (E). 011
8. Tin a
7
được mã hoá thành
(A). 1001 (B). 1100 (C). 1011 (D). 1111 (E). 1000
9. Chiều dài trung bình của bộ mã là
(A). 2,86 (B). 2,92 (C). 2,9 (D). 2,88 (E). 2,84
Dành cho câu 10 đến câu 14: Cho nguồn X = {0, 1}. Mã hoá các dãy tin của X bằng phương pháp phổ quát với
chiều dài dãy tin là N = 8 với qui ước sau: Vectơ tần suất (
N
N 0
,
N
N1
) biểu diễn những dãy có N
0
kí hiệu 0 và N
1
kí
hiệu 1 (N
0
+ N
1
= N). Các vectơ tần suất được sắp thứ tự theo chiều tăng của N
0
và được mã hoá dựa vào thứ tự này
của vectơ tần suất. Ngoài ra, các dãy trong một vectơ tần suất sẽ được sắp xếp theo thứ tự sau: các dãy có các kí
hiệu 0 đi đầu sẽ đứng trước các dãy có các kí hiệu 0 đi sau. Ví dụ trong vectơ tần suất (

16. Nếu chuỗi bit được truyền đi có chiều dài 1 Kbyte (1024 bytes) thì bên nhận sẽ nhận sai trung bình bao nhiêu
bit (lấy số nguyên cận trên)
(A). 17 (B). 15 (C). 16 (D). 18 (E). 19
17. Nếu chuỗi bit được truyền đi có chiều dài 1 Kbyte thì theo định lý kênh bên nhận sẽ nh
ận được bao nhiêu bit
đúng (lấy số nguyên cận dưới)
(A). 8012 (B). 8102 (C). 8120 (D). 8021 (E). 8210
Dành cho câu 18 đến câu 20. Kí hiệu n là chiều dài từ mã, k là số bit thông báo, d là khoảng cách Hamming của
bộ mã.
18. Một mã tuyến tính có n = 10, d = 2 có tối đa bao nhiêu từ mã
(A). 64 (B). 256 (C). 512 (D). 128 (E). 1024
19. Một mã tuyến tính có n = 15, d = 3 có tối đa bao nhiêu từ mã
(A). 1024 (B). 2048 (C). 512 (D). 4096 (E). 256
20. Một mã tuyến tính có k = 16, d = 3 có chiều dài từ mã tối thiểu là bao nhiêu
(A). 21 (B). 20 (C). 22 (D). 19 (E). 18
Dành cho câu 21 đến câu 28: Cho một mã tuyến tính C(7, 4) có ma trận
sinh bên.
Kí hiệu u = a
1
a
2
a
3
a
4
là thông báo, w = b
1
b
2
b

21. Thông báo u = 1010 sẽ được mã hoá thành từ mã
(A). 1011001 (B). 0100011 (C). 1100011 (D). 1010001 (E). 1000111
22. Từ mã w = 1100011 sẽ được giải mã thành thông báo
(A). 1001 (B). 0110 (C). 0111 (D). 1010 (E). 1110
23. Ma trận nào sau đây là ma trận kiểm tra của bộ mã trên
(A).
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
1
0
1
1
0
0
1
1
0
0
1
0
0
1

1
1
1
0
1
1
0
0
1
(C).
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
1
1
1
0
1
1
1
0
1
0

1
0
1
0
1
1
1
0
1
1
1
0
1

(E). Tất cả đều sai.
24. Tổ hợp nào sau đây không phải là từ mã
(A). 0111001 (B). 1111111 (C). 0101110 (D). 0011100 (E). 0101101
25. Tổ hợp nhận 1100100 có syndrome là
(A). 100 (B). 011 (C). 101 (D). 111 (E). 110
26. Cho biết bộ mã trên có d = 3 và kênh truyền sai tối đa 1 bit. Tổ hợp nhận 1010100 sai ở bit số mấy
(A). 2 (B). 3 (C). 4 (D). 5 (E). Tất cả đều sai.
27. Ma tr
ận nào sau đây là ma trận hệ thống của bộ mã trên với phần ma trận đơn vị nằm trước
(A).
⎥
⎥
⎥
⎥
⎦
⎤

0
0
0
1
(B).
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
1
1
1
0
1
1
0
1
0
1
1
1
1

1
0
1
1
0
1
0
1
1
1
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
(D).
⎥
⎥
⎥

0
1
0
0
0
0
1

(E). Tất cả đều sai.
28. Mã hoá thông báo u = 1110 thành từ mã hệ thống có phần thông báo nằm trước sẽ được từ mã hệ thống là
(A). 1110100 (B). 1110101 (C). 1110110 (D). 1110111 (E). 1110011

Trang 3
Dành cho câu 29 đến câu 32: Cho một mã tuyến tính C(8, 4) có ma trận
kiểm tra như bên.
Kí hiệu u = a
1
a
2
a
3
a
4
là thông báo, w = b
1
b
2
b
3
b

⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
=
×
01010101
01100110
01111000
10000000
84
H

29. Bit kiểm tra b
2
sẽ được tính theo các bit thông báo bằng công thức nào sau đây
(A). b
3
+ b
5
+ b
6
+ b
7

⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
1
1
1
0
0

0
0
0
1
0
0
0
0
1
0
1
1
1
0
0
0
0
1
0
1
0
1
1
0
1
1
(C).
⎥
⎥
⎥

0
0
1
1
1
0
1
1
0
1
1
(D).
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
0
0
0
0
1
0

33. Đa thức nào sau đây có thể làm đa thức sinh cho mã vòng (12, 8)
(A). 1 + x + x
3
+ x
4
(B). 1+ x
3
+ x
4
(C). 1 + x + x
4
(D). 1 + x
2
+ x
3
+ x
4
(E). Tất cả đều sai.
34. Có bao nhiêu đa thức khác nhau có thể làm đa thức sinh cho mã vòng (24, 19).
(A). 4 (B). 2 (C). 1 (D). 3 (E). 5
35. Đa thức nào sau đây là ước số của đa thức x
9
+ 1
(A). 1 + x + x
3
(B). 1 + x
2
+ x
3
(C). 1 + x + x

(A). 01100110 (B). 00110011 (C). 10011001 (D). 11101110 (E). 11001100
38. Mã hoá thông báo u = 10100 thành từ mã hệ thống có phần thông báo nằm sau sẽ được từ mã hệ thống là
(A). 10010100 (B). 10110100 (C). 01110100 (D). 01010100 (E). 11010100
39. Ma trận nào sau đây có thể làm ma trận kiểm tra cho bộ mã trên
(A).
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
1
0
0
1
1
0
0
1
1
1
0
1
0
1
0

0
1
0
0
0
1
0
0
0
1
0
0
0
1
(C).
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
1
0
0
1
1

1
0
0
0
1
0
1
0
1
0
1
0
0
0
1
1
0
0
0
1
0
0
0
1

(E). Tất cả đều sai.
40. Tổ hợp nào sau đây không phải là một từ mã của mã vòng trên
(A). 10100100 (B). 10110100 (C). 01011010 (D). 10001000 (E). 10100101
Dành cho câu 41 đến câu 45: Cho trường GF(2
m


Vectơ 0000 1000 0100 0010 0001 1001 1101 1111
Luỹ thừa
a
7
a
8
a
9
a
10
a
11
a
12
a
13
a
14

Đa thức 1 + a + a
2
a + a
2
+ a
3
1 + a
2
a + a
3

(B). 1 + x + x
4
(C). 1 + x
3
+ x
4
(D). 1 + x + x
2
+ x
3
+ x
4
(E). Tất cả đều sai.
Trang 4
43. Đa thức sinh của mã vòng cần xây là
(A). 1 + x
3
+ x
4
(B). 1+x + x
2
+ x
4
+ x
8
(C). 1 + x + x
4
(D). 1 + x + x
2
+ x

(A). G (B).
K (C). A (D). T (E). Tất cả đều sai.
50. Mật mã hoá thông báo bằng phương pháp khoá tự động (autokey) với khoá mồi k = MATMA. Bảng chữ cái
gồm từ A đến Z và được đánh số như trên. Thông báo m = DETHIHOCKY sẽ được mã hoá thành chuỗi
mật mã nào
(A). BEFFIZWHKO (B). BEFFIWSODG (C). PEMTIWSODG (D). PEMTIZWHKO (E). Tất cả đều sai.

HẾT
Trang 5
ĐÁP ÁN
1 B 11 E 21 D 31 A 41 A
2 C 12 A 22 B 32 A 42 D
3 A 13 C 23 B 33 A 43 B
4 C 14 A 24 E 34 D 44 A
5 A 15 C 25 D 35 E 45 B
6 D 16 A 26 A 36 C 46 C
7 B 17 D 27 C 37 E 47 A
8 E 18 C 28 A 38 B 48 D
9 B 19 B 29 E 39 C 49 E
10 C 20 A 30 C 40 A 50 C