Giáo trình Lý thuyết thông tin

họn đa thức gm(x)=a0 + a1x+ a2 x2+ …+am-1xm-1 + xm 
⇒ a0, a1, a2,…, am-1 
⇒ Sinh nhanh k từ mã độc lập tuyến tính với từ mã sinh độc lập tuyến tính đầu tiên có 
dạng: w1=a0a1a2…am-11000…00 ⇒ Bộ mã xoay vòng. 
 k-1 bit 0 
Cách 3: chọn hk(x)=h0 + h1x+ h2x2 + …+hk-1xk-1 + xk làm đa thức sinh ma trận kiểm tra 
chẵn lẻ cho bộ mã vòng có dạng: 
⎟⎟
⎟⎟
⎟⎟
⎠
⎞
⎜⎜
⎜⎜
⎜⎜
⎝
⎛
−−−−−−
−−−−−−
−−−−−−−−−−−−−−
−−−−−−
−−−−−−
−
−
−
−
00001
00010
01000
10000
011
011
011
011
hhh
hhk
hhh
hhh
k
k
k
k
 m 
 (m-1) bits 
⇒ Sinh bộ mã xoay vòng theo Phương pháp sinh nhanh bộ mã xoay vòng. 
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 88
Giáo trình: Lý thuyết thông tin. 
Nhận xét: kết quả theo 3 cách sinh bộ mã xoay vòng nói trên la như nhau (cho cùng bộ mã). 
Ví dụ minh họa 1 
Thiết kế thanh ghi và sinh ma trận kiểm tra chẵn lẻ. 
Chọn đa thức gm(x)= 1+x+x4 ⇒ a0 = 1, a1 = 1, a2 = 0, a3 = 0 
+ F3 F0 F1 F2 
Ma trận đặc trưng của thanh ghi: T= 
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
0011
1000
0100
0010
Tìm chu kỳ của thanh ghi: 
Chọn giá trị khởi tạo x(0)=1= 
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
1
0
0
0
x(1)=T.x(0)= ; x
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
0
1
0
0
(2)=Tx(1)= ; x
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
0
0
1
0
(3)=Tx(2)= ; x
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
1
0
0
1
(4)=Tx(3)= ; x
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
1
1
0
0
(5)=Tx(4)= 
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
0
1
1
0
x(6)=Tx(5)= ; x
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
1
0
1
1
(7)=Tx(6)= ; x
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
0
1
0
1
(8)=Tx(7)= ; x
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
1
0
1
0
(9)=Tx(8)= ; x
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
1
1
0
1
(10)=Tx(9)= 
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
1
1
1
0
x(11)=Tx(12)= ;x
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
1
1
1
1
(12)=Tx(11)= ;x
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
0
1
1
1
(13)=Tx(12)= ;x
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
0
0
1
1
(14)=Tx(13)= ; x
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
0
0
0
1
(15)=T.x(14) = = x
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
1
0
0
0
(0)
Ma trận kiểm tra chẳn lẻ : 
 A= 
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
000111101011001
001111010110010
011110101100100
111101011001000
⇒ Bộ mã xoay vòng vớin=14, m=4, k=11. 
Ví dụ minh họa 2 
Chọn đa thức gm(x)= 1+x+x4 ⇒ a0 = 1, a1 = 1, a2 = 0, a3 = 0. 
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 89
Giáo trình: Lý thuyết thông tin. 
Bước 1: Sinh mã xoay vòng đầu tiên 
w1 =110010000000000 
 Bước 2: Sinh k -1 từ mã độc lập tuyến tính còn lại 
w2 =011001000000000 
w3 =001100100000000 
w4 =000110010000000 
w5 =000011001000000 
w6 =000001100100000 
w7 =000000110010000 
w8 =000000011001000 
w9 =000000001100100 
w10=000000000110010 
w11=000000000011001 
 Bước 3: Xác định các từ mã còn lại của bộ mã 
(215 - 11) từ mã còn lại được xác định bằng cách cộng tổ hợp 2, 3, 4,.., k = 11 từ 
mã từ k=11 từ mã độc lập tuyến tính. 
Ví dụ minh họa 3 
Chọn hk(x)= 1+ x + x2 + x3 +x5 + x7 + x8 + x11 làm đa thức sinh ma trận kiểm tra chẵn lẻ cho bộ mã 
vòng ⇒ h0 = 1, h1 = 1, h2 = 1, h3 = 1, h4 = 0, h5 = 1, h6 = 0, h7 = 1, h8 =1, h9 = 0, h10 = 0. 
 A= ⇒ Bộ mã xoay vòng 
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
000111101011001
001111010110010
011110101100100
111101011001000
Bảng liệt kê một số đa thức đặc trưng 
M Đa thức M Đa thức 
3 1+x+x3 14 1+x+x6+x10+x14
4 1+x+x4 15 1+x+x15
5 1+x2+x5 16 1+x+x3+x12+x16
6 1+x+x6 17 1+x3+x7
7 1+x3+x7 18 1+x7+x18
8 1+x2+x3+x4+x8 19 1+x+x2+x5+x19
9 1+x4+x9 20 1+x3+x20
10 1+x3+x10 21 1+x2+x21
11 1+x2+x11 22 1+x+x22
12 1+x+x4+x6+x12 23 1+x3+x23
13 1+x+x3+x4+x13 24 1+x+x2+x7+x24
Bài tập 
1. Tìm bộ mã vòng có độ dài 7 bit. 
2. Tìm thanh ghi sinh bộ mã vòng có độ dài 15 bit. 
3. Tìm thanh ghi sinh bộ mã vòng có độ dài 31 bit. 
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 90
Giáo trình: Lý thuyết thông tin. 
BÀI TẬP TỔNG HỢP 
Mục tiêu 
Sau khi hoàn tất bài học này bạn có thể: 
- Hiểu rõ hơn về nội dung môn học. 
- Vận dụng nội dung môn học để giải quyết một số bài tập tổng hợp. 
Bài 1 
Xét một mô hình chẩn đoán bệnh từ các triệu chứng: A, B và C; để chẩn đoán 1 trong 4 bệnh: 1, 
2, 3 và 4 với ma trận chẩn đoán (hay ma trận truyền tin). 
 Bệnh 
Triệu chứng 
1 2 3 4 
A 0,6 0,3 0 0,1 
B 0,2 0,6 0,2 0 
C 0 0 0,3 0,7 
Yêu cầu: 
Câu 1: Vẽ sơ đồ mô tả mô hình chẩn đoán bệnh trên và diễn giải các ý nghĩa của sơ đồ. 
Câu 2: Nếu phân phối của Triệu chứng có dạng: 
Triệu chứng A B C 
P 0,5 0,3 0,2 
Tính các lượng sau : 
¾ Lượng ngẫu nhiên (Entropy) của Triệu chứng . 
¾ Lượng ngẫu nhiên của Bệnh. 
¾ Lượng ngẫu nhiên của Bệnh khi biết Triệu chứng. 
¾ Lượng chẩn đoán đúng.(Lượng thông tin biết về Bệnh thông qua Triệu chứng) và tỷ lệ 
chẩn đoán đúng là bao nhiêu phần trăm. 
Câu 3: Bây giờ người ta sử dụng 2 bit để mã thông tin về Triệu chứng (có 1 triệu chứng dự trữ) và 
5 bit để mã các triệu chứng khi chẩn đoán bệnh trực tuyến. Mô tả các đoạn của dãy 5 bit trong 
phương pháp kiểm tra chẵn lẻ. 
Câu 4: Nếu sử dụng ma trận kiểm tra chẵn lẻ dạng: 
 1 1 1 0 1 
0 1 0 1 1 
1 0 0 1 1 
A = 
Tính các từ mã. 
Xây dựng Bộ sửa lỗi 1 bit dùng cho tự động sửa lỗi tối ưu trong quá trình chẩn đoán trực tuyến. 
Cho một ví dụ. 
Bài 2 
Xét một kênh truyền tin đặc biệt dạng : Truyền X Æ Nhận Y. 
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 91
Giáo trình: Lý thuyết thông tin. 
Truyền một giá trị của X có thể nhận được nhiều giá trị khác nhau của Y với các xác suất khác 
nhau. Bảng xác suất truyền X và nhận các Y khác nhau được cho dưới đây: 
 Y 
X 
y1 y2 y3 y4 y5 y6
x0 0,6 0,1 0,1 0,05 0,05 0,1 
x1 0,1 0,05 0,6 0,1 0,1 0,05 
x2 0,05 0,1 0,1 0,05 0,6 0,1 
x3 0,1 0,05 0,05 0,1 0,1 0,6 
Yêu cầu: 
Câu 1: Vẽ sơ đồ mô tả kênh truyền tin trên và diễn giải các ý nghĩa của sơ đồ. 
Câu 2: Nếu phân phối của X có dạng : 
X x0 x1 x3 x4
P 0.5 0.25 0.15 0.1 
tính thông lượng về X truyền trên kênh. 
Câu 3: Phân phối của X cần có dạng như thế nào để thông lượng truyền trên kênh là lớn nhất. 
Tính dung lượng kênh truyền. 
Câu 4: Bây giờ người ta sử dụng 2 bit để mã thông tin về X và 4 bit để mã các giá trị truyền trên 
kênh. Mô tả các đoạn của dãy 4 bit trong phương pháp kiểm tra chẵn lẻ. 
Câu 5: Nếu sử dụng ma trận kiểm tra chẵn lẻ dạng: 
 1 1 1 0 
0 1 0 1 A = 
Tính các từ mã. 
Xây dựng Bộ sửa lỗi dùng cho tự động sửa lỗi tối ưu trong quá trình truyền tin. Cho một ví dụ. 
Bài 3 
Người ta cần đánh giá kênh truyền tin và chuẩn bị thực hiện truyền một loại tín hiệu đặc biệt: X = 
{x0, x1, x2, x3} 
Công việc đầu tiên là phải khảo sát kênh truyền. Kết quả khảo sát cho thấy: 
Kênh có thể truyền nhận được 8 giá trị khác nhau, để có khả năng phát hiện lỗi hoặc điều chỉnh 
lỗi. Ma trận truyền tin có dạng: 
 Y 
X 
y1 y2 y3 y4 y5 y6 y7 y8
x0 0,6 0,1 0,05 0,05 0,05 0,05 0,05 0,05 
x1 0,05 0,05 0,6 0,1 0,05 0,05 0,05 0,05 
x2 0,05 0,05 0,05 0,05 0,6 0,1 0,05 0,05 
x3 0,05 0,05 0,05 0,05 0,05 0,05 0,6 0,1 
Yêu cầu: 
Câu 1: Vẽ sơ đồ mô tả kênh truyền tin trên và diễn giải các ý nghĩa của sơ đồ. Nếu phân phối của 
X có dạng : 
X x0 x1 x3 x4
P 0.5 0.25 0.15 0.1 
tính thông lượng về X truyền trên kênh. 
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 92
Giáo trình: Lý thuyết thông tin. 
Câu 2: Phân lớp các giá trị của Y về các lớp B0, B1, B2, và B3 dùng để giải mã tối ưu Y tốt nhất 
về các giá trị tương ứng của X. 
Câu 3 : Bây giờ người ta sử dụng 2 bit để mã thông tin về X và 4 bit để mã các giá trị truyền trên 
kênh. Mô tả các đoạn của dãy 4 bit trong phương pháp kiểm tra chẵn lẻ. 
Câu 4: Nếu sử dụng ma trận kiểm tra chẵn lẻ dạng: 
 1 0 0 1 
0 1 1 1 A = 
Tính các từ mã. 
Xây dựng Bộ sửa lỗi dùng cho tự động sửa lỗi tối ưu trong quá trình truyền tin. Cho một ví dụ. 
Bài 4 
Xét một mô hình chẩn đoán bệnh từ các triệu chứng: A, B và C; để chẩn đoán 1 trong 4 bệnh: 1, 
2, 3 và 4 với ma trận chẩn đoán (hay ma trận truyền tin) 
 Bệnh 
Triệu chứng 
1 2 3 4 
A 0,5 0,3 0 0,2 
B 0,1 0,2 0,7 0 
C 0 0,1 0,3 0,6 
Yêu cầu: 
Câu 1: Giả sử người ta biết thêm 3 triệu chứng gây bệnh khác đó là : D, E và F và muốn ghi lại 
các triệu chứng này thông qua bảng ký hiệu A = {+, - }. 
Hãy kiểm tra tính tách được của bảng mã sau : 
Triệu chứng : X A B C D E F 
Mã : W + -+ ++- --+- ++-+ -- 
Câu 2: Nếu các triệu chứng ở câu 1 có phân phối : 
Triệu chứng : X A B C D E F 
P 0.5 0.2 0.2 0.05 0.03 0.2 
Giử sử có một người bệnh với 1 trong 5 triệu chứng trên đến khám bệnh và bác sĩ sẽ hỏi bệnh với 
nguyên tắc, sao cho người bệnh chỉ trả lời bằng 2 câu : Đúng hoặc Sai. 
¾ Tìm phương pháp hỏi bệnh với số câu hỏi trung bình ít nhất. 
¾ Tính số câu hỏi trung bình. 
¾ Tính lượng ngẫu nhiên của Triệu chứng. 
¾ Nhận xét gì về số câu hỏi trung bình và lượng ngẫu nhiên của triệu chứng. 
Câu 3: Bây giờ sử dụng mô hình 3 triệu chứng {A, B, C} và 4 bệnh. Vẽ sơ đồ mô tả mô hình 
chẩn đoán bệnh và diễn giải các ý nghĩa của sơ đồ. 
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 93
Giáo trình: Lý thuyết thông tin. 
Câu 4: Từ kết quả câu 3, người ta sử dụng 2 bit để mã thông tin về Triệu chứng (có 1 triệu chứng 
dự trữ) và 5 bit để mã các triệu chứng khi chẩn đoán bệnh trực tuyến. Mô tả các đoạn của dãy 5 
bit trong phương pháp kiểm tra chẵn lẻ. 
Câu 5: Nếu sử dụng ma trận kiểm tra chẵn lẻ dạng: 
1 1 1 0 1 
0 1 0 1 1 
1 0 0 1 1 
A = 
 Tính các từ mã. 
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 94
Giáo trình: Lý thuyết thông tin. 
TÀI LIỆU THAM KHẢO 
12. G.J.ChaiTin, Algorithmic Information Theory, CamBridge University Express-1992. 
13. David J.C. Mackey, Information Theory, Infernce, and Learning Algorithms, CamBridge 
University Express-2003. 
14. Sanford Goldman, Information Theory. 
15.  
16.  
17.  
18.  
19.  
20.  
21.  
22.  
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. 95