7/2/2010
1
Chương 2:
Bài toán mã trường hợp
kênh không bịnhiễu
2.2 Sựtồn tại của bộmã tiền tốvà
giải được
Mởñầu
•Cho biến ngẫu nhiên Xcó các giá trịx1, x2, …, xM.
Tập các ký tựmã a1, a2, …, aD
•Cho trước các sốnguyên dương n1, n2, …, nM
•Bài toán đặt ra là: có thểxây dựng bộmã giải
được sao cho từmã ứng với xkcó chiều dài là nk?
•Mã tiền tốcó thểgiải mã từng bước
•Trong bài toán kênh không bịnhiễu, mã giải
được có thểquy vềmã tiền tố
•Đầu tiên ta sẽxét sựtồn tại của bộmã tiền tố, sau
đó mởrộng cho bộmã giải được
7/2/2010
2
Huỳnh Văn Kha
7/2/2010
2
Ví dụ
•Ví dụ1:
M = 3, D = 2, n1= 1, n2= 2, n3= 3
Có thểchọn bộmã {0, 10, 110}
•Ví dụ2: M = 3, D = 2, n1= n2= 1, n3= 2
Không có bộmã giải được nào thỏa yêu cầu bài
toán (sẽchứng minh sau)
•Khi nào có thểxây dựng được bộmã thỏa yêu
cầu, khi nào không?
7/2/2010
3
Huỳnh Văn Kha
ðịnh lý 2.2
Một bộmã tiền tốvới chiều dài các từmã n1,
n2, …, nMlà tồn tại khi và chỉkhi
Trong đó Dlà sốcác ký tựmã
7/2/2010
4
Huỳnh Văn Kha
7/2/2010
3
Chứng minh ñịnh lý 2.2
•Cây bậc D kích thước k là một hệthống các điểm
và đoạn thẳng
•Mỗi dãy sđược tạo thành từcác ký tựtrong {0, 1,
…, D – 1} có chiều dài không lớn hơn kđược biểu
diễn bởi một điểm Vskhác nhau
•Nếu dãy tcó được do thêm duy nhất một ký tự
vào sau sthì nối Vsvà Vtbằng một đoạn thẳng
•Các điểm ứng với dãy có chiều dài kgọi là các
điểm ngọncủa cây kích thước k
7/2/2010
5
Huỳnh Văn Kha
Chứng minh ñịnh lý 2.2
0
00
01
000
001
010
011
1
10
11
100
101
110
111
Cây bậc 2
kích thước 3
0
00
01
02
1
10
11
12
2
20
21
22
Cây bậc
3 kích
thước 2
7/2/2010
6
Huỳnh Văn Kha
7/2/2010
4
Chứng minh ñịnh lý 2.2
•Giảsửn1≤ n2≤ … ≤ nM
•Mỗi từmã được đồng nhất với một điểm trên cây
bậc Dkích thước nM
0
1
10
11 111
Cây ứng với bộ
mã {0, 10, 111}
7/2/2010
7
Huỳnh Văn Kha
Chứng minh ñịnh lý 2.2
•Do bộmã là tiền tốnên khi điểm Pđại diện cho
một từmã, thì không điểm nào trên nhánh bắt
đầu từPđại diện cho một từmã khác
•Điểm ứng với từmã chiều dài nksẽche
điểm ngọn của cây
•Sốđiểm ngọn bịtoàn bộbộmã che ≤ Tổng sốcác
điểm ngọn của cây
7/2/2010
8
Huỳnh Văn Kha
7/2/2010
5
Chứng minh ñịnh lý 2.2
•Ngược lại, giảsửvà n1≤ n2≤ … ≤ nM
•Chọn điểm bất kỳ trên cây ứng với dãy có chiều
dài n1. Điểm này che điểm ngọn
•Còn lại ít nhất 1 điểm ngọn, chọn được điểm ứng
với n2. Lúc đó, do ta
chọn được điểm ứng với n3. Và cứthếcho đến hết
7/2/2010
9
Huỳnh Văn Kha
Định lý 2.3:
Nếu bộmã giải được có chiều dài từmã lần
lượt là n1, n2, …, nMthì:
Mởrộng cho bộmã giải ñược
•Điều kiện ởđịnh lý 2.2 cũng là điều kiện cần và
đủcho sựtồn tại của bộmã giải được
•Do bộmã tiền tốlà giải được nên chỉcần chứng
minh định lý sau là đủ.
7/2/2010
10
Huỳnh Văn Kha