Bài giảng Lý thuyết thông tin - Chương 2 cung cấp cho người học những kiến thức về bài toán mã trường hợp kênh không bị nhiễu. Trong phần này người học sẽ tìm hiểu về tính giải được của một bộ mã với các nội dung cụ thể như: Giới thiệu bài toán mã, mã tiền tố và mã giải được, giải thuật kiểm tra tính giải được,... Mời các bạn cùng tham khảo.
Nội dung Text: Bài giảng Lý thuyết thông tin: Chương 2.1 - ThS. Huỳnh Văn Kha
Chương 2:
Bài toán mã trường hợp
kênh không bị nhiễu
2.1 Tính giải được của một bộ mã
2
Huỳnh Văn Kha 9/30/2010
Giới thiệu bài toán mã
• Biến ngẫu nhiên X nhận các giá trị x1, x2, … , xM
(gọi là các trạng thái của X) với xác suất tương
ứng p1, p2, …., pM
• Dãy hữu hạn các giá trị của X gọi là mẫu tin
(message)
• Tập hợp {a1, a2, …, aD} gọi là tập các ký tự mã
(code character)
• Mỗi xi tương ứng với một dãy hữu hạn các ký tự
mã gọi là từ mã (character word)
• Tập các từ mã gọi là bộ mã (code)
3
Huỳnh Văn Kha 9/30/2010
Giới thiệu bài toán mã
• Giả sử các từ mã là khác nhau
• Mẫu tin do biến X sinh ra được mã hóa thành
một dãy các từ mã
• Mục tiêu của bài toán là cực tiểu hóa chiều dài
trung bình của mã
• Chiều dài của từ mã ứng với xi là ni, i = 1, 2, …, M.
Mục tiêu là cực tiểu hóa:
4
Huỳnh Văn Kha 9/30/2010
Mã tiền tố và mã giải ñược
• Xét bộ mã nhị phân
x1 0
x2 010
x3 01
x4 10
• Dãy 010 có thể tương ứng với một trong ba mẩu
tin: x2, x3x1, x1x4. Nên không thể giải mã
• Cần có một số giới hạn trên các từ mã của 1 bộ mã
5
Huỳnh Văn Kha 9/30/2010
Mã tiền tố và mã giải ñược
• Bộ mã gọi là giải được nếu mỗi dãy hữu hạn các
từ mã đều tương ứng với nhiều nhất một mẫu tin
• Dãy A gọi là tiền tố của dãy B nếu dãy B có thể
được viết dưới dạng AC, với C là một dãy nào đó
• Bộ mã tiền tố là bộ mã có tính chất: không từ mã
nào là tiền tố của từ mã khác
• Bộ mã tiền tố là giải được, nhưng bộ mã giải được
chưa chắc là bộ mã tiền tố
• Bộ mã tiền tố có thể được giải mã từng bước
6
Huỳnh Văn Kha 9/30/2010
Mã tiền tố và mã giải ñược
• Bộ mã sau là bộ mã tiền tố
x1 0
x2 100
x3 101
x4 11
• Bộ mã sau là giải được nhưng không là tiền tố
x1 0
x2 01
7
Huỳnh Văn Kha 9/30/2010
Giải thuật kiểm tra tính giải ñược
• Gọi S0 là tập các từ mã ban đầu
• Xét tất cả các cặp từ mã trong S0. Nếu có các từ
mã Wi, Wj sao cho Wj = WiA, cho hậu tố A vào
tập S1
• Giả sử có tập Sn-1 (n>1). Nếu có W trong S0 và A
trong Sn-1 sao cho A=WB, cho B vào Sn. Nếu có
W’ trong So và A’ trong Sn-1 sao cho W’=A’B’, cho
B’ vào Sn
• Định lý 2.1:
Một bộ mã là giải được nếu và chỉ nếu không
tập nào trong các tập S1, S2, S3, … chứa bất
kỳ từ mã nào
8
Huỳnh Văn Kha 9/30/2010
Thuật toán kiểm tra tính giải ñược
x1 a
x2 c
x3 ad
x4 abb
x5 bad
x6 deb
x7 bbcde
9
Huỳnh Văn Kha 9/30/2010
Thuật toán kiểm tra tính giải ñược
S0 S1 S2 S3 S4 S5 S6 S7
a d eb de b ad d eb
c bb cde bcde
ad
• Sn rỗng với mọi n>7
abb • ad thuộc S5 nên bộ mã là không
bad giải được
deb • abbcdebad có thể giải mã thành
bbcde x1x7x5 hoặc x4x2x6x3
10
Huỳnh Văn Kha 9/30/2010
Tìm dãy mã không giải ñược
• Dãy các ký tự mã có thể đại diện cho 2 mẫu tin
được gọi là dãy mã không giải được
• Ta sẽ không chứng minh định lý 2.1 nhưng sẽ chỉ
ra cách tìm dãy mã không giải được
• Giả sử Sn chứa từ mã W. Tiến hành ngược lại, ta
tìm được dãy:
A0, W0, A1, W1, …, An, Wn
11
Huỳnh Văn Kha 9/30/2010
Tìm dãy mã không giải ñược
• A0, W0, W1, …, Wn là các từ mã, Ai ε Si (i = 1, 2, …,
n), W0 = A0A1, An = Wn
• Với mỗi i = 1, 2, …, n-1 thì hoặc Ai = WiAi+1 hoặc
Wi = AiAi+1
• Ví dụ trên, ta có:
A5 = ad ε S5 A4 = b ε S4 A3 = de ε S3
W5 = ad W4 = bad W3= deb
A2 = cde ε S2 A1 = bb ε S1 A0 = a
W2 = c W1 = bbcde W0 = abb
12
Huỳnh Văn Kha 9/30/2010
Tìm dãy mã không giải ñược
• Ta xây dựng hai dãy, một dãy bắt đầu với A0W1,
dãy kia bắt đầu với W0
• Nếu Ai = WiAi+1, thêm Wi+1 vào cuối dãy chứa Wi
• Nếu Wi = AiAi+1, thêm Wi+1 vào cuối dãy không
chứa Wi
• Tiếp tục như vậy đến Wn
• Người ta chứng minh được rằng hai dãy tạo
thành như trên là một, và chính là dãy mã không
giải được cần tìm
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
