7/2/2010
1
Chương 2:
Bài toán mã trường hợp
kênh không bịnhiễu
2.4 Xây dựng bộmã tối ưu
Bổñề2.6
Giảsửbộmã Clà tối ưu trong họcác các bộmã
tiền tốcho phân bốxác suất p1, p2, …, pM; nói
cách khác, giảsửkhông bộmã tiền tốnào có
chiều dài từmã trung bình nhỏhơn của C. Khi
đó Clà tối ưu trong họcác bộmã giải được
7/2/2010Huỳnh Văn Kha
2
Bổđề2.6 cho phép ta thay vì tìm bộmã tối ưu
trong tập các bộmã giải được, ta chỉcần tìm bộ
mã tối ưu trong tập nhỏhơn, tập các bộmã tiền tố
7/2/2010
2
Chứng minh bổñề2.6
•Giảsửtồn tại bộmã giải được C’ có chiều dài từ
mã trung bình nhỏhơn của C. Gọi n’1, n’2, …, n’M
là các độdài từmã của C’
•Theo định lý 2.3
•Theo định lý 2.2 thì tồn tại bộmã tiền tốC’’ với
chiều dài từmã lần lượt là: n’1, n’2, …, n’M
•Nhưvậy có bộmã tiền tốC’’ có chiều dài từmã
trung bình nhỏhơn của C(vô lý)
7/2/2010
3
Huỳnh Văn Kha
Bổñề2.7
•Cho Clà bộmã tiền tốnhịphân với chiều dài các
từmã là n1, n2, …, nM.
•Giảsửcác trạng thái được sắp xếp theo thứtự
giảm dần theo xác suất (nghĩa là p1≥ p2≥ … ≥
pM) và trong mỗi nhóm có cùng xác suất, các
trạng thái được xếp thứtựtăng dần theo chiều
dài từmã, nghĩa là nếu pi= pi+1 = … = pi+r thì ni≤
ni+1 ≤ … ≤ ni+r
•Nếu Clà tối ưu trong họcác bộmã tiền tốthì Ccó
các tính chất sau:
7/2/2010
4
Huỳnh Văn Kha
7/2/2010
3
Bổñề2.7
a) Trạng thái có xác suất cao thì từmã tương ứng
có độdài ngắn hơn, nghĩa là pj> pkkéo theo nj
≤ nk
b) Hai từmã của hai trạng thái cuối có độdài bằng
nhau, nghĩa là nM-1 = nM
c) Trong sốcác từmã có chiều dài nM, có ít nhất
hai từmã giống nhau hoàn toàn, ngoại trừký tự
cuối cùng của chúng
7/2/2010
5
Huỳnh Văn Kha
Ví dụ
•Xét bộmã nhịphân sau
•Bộmã này không tối ưu
X Từmã
x10
x2100
x3101
x41101
x51110
7/2/2010
6
Huỳnh Văn Kha
7/2/2010
4
Chứng minh bổñề2.7
•Chứng minh a): Nếu pj> pknhưng nj> nkthì
chỉcần đổi các từmã ởvịtrí thứjvà kcho nhau
ta sẽđược bộmã C’ có chiều dài từmã trung bình
nhỏhơn. Thật vậy:
•Chứng minh b): Chú ý rằng nM-1 ≤ nM. Nếu nM
> nM-1, chỉcần bỏđi ký tựcuối của từmã thứM
thì ta được bộmã tiền tốtốt hơn
7/2/2010
7
Huỳnh Văn Kha
Chứng minh bổñề2.7
•Chứng minh c): Giảsửngược lại, mọi cặp từ
mã độdài nMđều có ít nhất một ký tựmã (không
là ký tựcuối) khác nhau. Khi đó chỉcần bỏđi ký
tựmã cuối cùng của một trong các từmã đó, ta sẽ
được bộmã (vẫn là tiền tố) tốt hơn
Chú ý: Đểđơn giản ta chỉnói vềcách xây dựng bộ
mã tiền tốnhịphân tối ưu. Cách xây dựng bộmã
với nhiều ký tựmã hơn có thểxem trong tài liệu
tham khảo
7/2/2010
8
Huỳnh Văn Kha
7/2/2010
5
Xây dựng bộmã tối ưu (Huffman)
•Sắp xếp các xitheo thứtựxác suất tăng dần
•Ghép hai trạng thái xM-1 và xMthành một trạng
thái, gọi là xM,M-1, với xác suất pM+ pM-1
•Giảsửta xây dựng được bộmã tiền tốtối ưu C2
cho tập trạng thái mới
•Xây dựng C1cho tập trạng thái ban đầu nhưsau:
▫ Các từmã cho x1, x2, …, xM-2 vẫn nhưtrong C2
▫ Từmã cho xM-1 và xMđược tạo thành bằng cách
thêm lần lượt 0, 1 vào từmã của xM,M-1 trong C2
7/2/2010
9
Huỳnh Văn Kha
Xây dựng bộmã tối ưu (Huffman)
X p C1n X p C2n
x1p1W1n1x1p1W1n1
x2p2W2n2x2p2W2n2
…
…
…
…
…
…
…
…
xM,M-1 pM+pM-1 WM,M-1 nM,M-1
…
…
…
…
xM-2 pM-2 WM-2 nM-2
xM-1 pM-1 [WM,M-1 0]nM-1 xM-2 pM-2 WM-2 nM-2
xMpM[WM,M-1 1]nM
7/2/2010
10
Huỳnh Văn Kha