7/2/2010
1
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ã
Giới thiệu bài toán mã
•Biến ngẫu nhiên Xnhậ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ủaXgọ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 xitươ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)
7/2/2010Huỳnh Văn Kha
2
7/2/2010
2
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 Xsinh 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 xilà ni, i = 1, 2, …, M.
Mục tiêu là cực tiểu hóa:
7/2/2010Huỳnh Văn Kha
3
Mã tiền tốvà mã giải ñược
•Xét bộmã nhịphân
•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ã
7/2/2010Huỳnh Văn Kha
4
x10
x2010
x301
x410
7/2/2010
3
Mã tiền tốvà mã giải ñược
•Bộmã gọi là giải đượcnế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 Agọi là tiền tốcủa dãy Bnếu dãy Bcó thể
được viết dưới dạng AC, với Clà 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
7/2/2010Huỳnh Văn Kha
5
Mã tiền tốvà mã giải ñược
•Bộmã sau là bộmã tiền tố
•Bộmã sau là giải được nhưng không là tiền tố
7/2/2010Huỳnh Văn Kha
6
x10
x2100
x3101
x411
x10
x201
7/2/2010
4
Giải thuật kiểm tra tính giải ñược
•Gọi S0là 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, Wjsao cho Wj= WiA, cho hậu tốAvào
tập S1
•Giảsửcó tập Sn-1 (n>1). Nếu có Wtrong S0và A
trong Sn-1 sao cho A=WB, cho Bvào Sn. Nếu có
W’ trong Sovà 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
7/2/2010Huỳnh Văn Kha
7
Thuật toán kiểm tra tính giải ñược
x1a
x2c
x3ad
x4abb
x5bad
x6deb
x7bbcde
7/2/2010Huỳnh Văn Kha
8
7/2/2010
5
Thuật toán kiểm tra tính giải ñược
S0S1S2S3S4S5S6S7
a d eb de b ad d eb
c bb cde bcde
ad
abb
bad
deb
bbcde
7/2/2010Huỳnh Văn Kha
9
•Snrỗng với mọi n>7
•ad thuộc S5nên bộmã là không
giải được
•abbcdebad có thểgiải mã thành
x1x7x5hoặc x4x2x6x3
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ửSnchứa từmã W. Tiến hành ngược lại, ta
tìm được dãy:
A0, W0, A1, W1, …, An, Wn
7/2/2010Huỳnh Văn Kha
10