Mở ñầu
• Biến ngẫu nhiên X có các trạng thái x1, x2, , xM
với xác xuất tương ứng p1, p2, , pM
• Các từ mã cho x
1, x2, , xM là W1, W2, , WM có
9/30/2010
2
Huỳnh Văn Kha
độ dài lần lượt là n1, n2, , nM
• Tập các ký tự mã là {a1, a2, , aD}
• Ta sẽ xây dựng bộ mã để cực tiểu hóa chiều dài từ
mã trung bình
• Đầu tiên là tìm chặn dưới lớn nhất, sau đó tìm
cách tiến gần tới chặn dưới đó. Và cuối cùng là
xây dựng thuật toán để tìm bộ mã tối ưu
17 trang |
Chia sẻ: phuongt97 | Lượt xem: 588 | Lượt tải: 0
Nội dung tài liệu Bài giảng Lý thuyết thông tin - Chương 2: Bài toán mã trường hợp kênh không bị nhiễu (Phần 3), để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Chương 2:
Bài toán mã trường hợp
kênh không bị nhiễu
2.3 Định lý cho bài toán mã trong
trường hợp kênh không bị nhiễu
Mở ñầu
• Biến ngẫu nhiên X có các trạng thái x1, x2, , xM
với xác xuất tương ứng p1, p2, , pM
• Các từmã cho x1, x2, , xM là W1, W2, , WM có
9/30/2010
2
Huỳnh Văn Kha
độ dài lần lượt là n1, n2, , nM
• Tập các ký tựmã là {a1, a2, , aD}
• Ta sẽ xây dựng bộmã để cực tiểu hóa chiều dài từ
mã trung bình
• Đầu tiên là tìm chặn dưới lớn nhất, sau đó tìm
cách tiến gần tới chặn dưới đó. Và cuối cùng là
xây dựng thuật toán để tìm bộmã tối ưu
ðịnh lý 2.4 (ðịnh lý cho bài toán mã trong
trường hợp kênh không bị nhiễu)
Gọi
9/30/2010
3
Huỳnh Văn Kha
là chiều dài từmã trung bình của một bộmã
giải được bất kỳ cho biến ngẫu nhiên X. Khi
đó:
Dấu bằng xảy ra khi và chỉ khi:
Chứng minh ñịnh lý 2.4
• Đặt:
Thì các q có tổng bằng 1. Áp dụng mệnh đề 1.1
9/30/2010
4
Huỳnh Văn Kha
i
Chứng minh ñịnh lý 2.4
• Dấu bằng trong bất đẳng thức (*) xảy ra khi và chỉ
khi:
9/30/2010
5
Huỳnh Văn Kha
• Do bộmã là giải được nên
Và ta được
• Tiếp theo, nếu , thì
Chứng minh ñịnh lý 2.4
• Ngược lại, nếu thì từ (*) ta được
9/30/2010
6
Huỳnh Văn Kha
Nhưng
Vậy , và từ (**), ta được
Bộ mã tối ưu tuyệt ñối
• Bộmã làm cho dấu bằng trong định lý 2.4 xảy ra
được gọi là bộmã tối ưu tuyệt đối
• Ví dụ
9/30/2010
7
Huỳnh Văn Kha
X Xác suất Từmã
x1 1/2 0
x2 1/4 10
x3 1/8 110
x4 1/8 111
Bộ mã tối ưu tuyệt ñối
• Bộmã tối ưu tuyệt đối phải thỏa mãn
• Trong trường hợp tổng quát chưa chắc xây dựng
9/30/2010
8
Huỳnh Văn Kha
được bộmã tối ưu tuyệt đối, do các ni như trên
chưa chắc là số nguyên
• Tuy nhiên, ta hoàn toàn có thể xây dựng được bộ
mã tiền tố có chiều dài từmã trung bình gần
bằng chận dưới H(X)/log D như khẳng định của
định lý sau
ðịnh lý 2.5
Cho trước biến ngẫu nhiên X, với độ không
chắc chắn là H(X). Khi đó tồn tại bộmã
9/30/2010Huỳnh Văn Kha
9
tiền tố cho X, sao cho chiều dài từmã
trung bình thỏa mãn
Chứng minh ñịnh lý 2.5
• Chọn ni là số nguyên thỏa mãn
9/30/2010Huỳnh Văn Kha
10
• Khi đó log pi ≥ -ni log D, suy ra
• Vậy theo định lý 2.2 thì tồn tại bộmã tiền tố ứng
với các ni chọn như trên
Chứng minh ñịnh lý 2.5
• Tiếp theo, ta ước lượng chiều dài từmã trung
bình. Nhân hai vế cho pi rồi lấy tổng theo i ta
được
9/30/2010Huỳnh Văn Kha
11
• Và ta có kết luận của định lý
Mã hóa theo block
• Theo định lý 2.5, ta luôn xây dựng được bộmã
tiền tố có chiều dài trung bình nhỏ hơn chận dưới
H(X)/log D cộng thêm 1 ký tựmã
9/30/2010Huỳnh Văn Kha
12
• Tuy nhiên ta có thể làm tốt hơn thế nếu dùng
phương pháp mã hóa theo block
• Nghĩa là ta không mã hóa từng trạng thái xi của
X, mà sẽmã hóa từng nhóm s các trạng thái
• Nói cách khác, ta sẽ xây dựng bộmã cho vector
ngẫu nhiên Y = (X1, X2, , Xs). Trong đó các Xi là
độc lập và có cùng phân phối xác suất như X
Mã hóa theo block
X p Từmã
x1 3/4 0
x 1/4 1
9/30/2010Huỳnh Văn Kha
13
Y=(X1, X2) p Từmã
x1x1 9/16 0
x1x2 3/16 10
2
x2x1 3/16 110
x2x2 1/16 111
Mã hóa theo block
• Ta sẽ kiểm chứng rằng việc mã hóa theo block sẽ
làm giảm chiều dài từmã trung bình cho một
trạng thái của X
9/30/2010Huỳnh Văn Kha
14
• Theo định lý 2.5, ta sẽ xây dựng được bộmã tiền
tố cho Y với chiều dài từmã trung bình thỏa
• Nhưng do các Xi độc lập và cùng phân phối xác
suất với X nên ta có:
H(Y) = H(X1) + H(X2) + + H(Xs) = sH(X)
Mã hóa theo block
• Như vậy
9/30/2010Huỳnh Văn Kha
15
• chính là số ký tựmã trung bình đểmã hóa
một trạng thái của X
• Từ trên ta thấy có thể gần H(X)/log D tùy ý
• Vậy H(X)/log D chính là số ký tựmã trung bình
(lấy trong bộ D ký tựmã) cực tiểu dùng đểmã
hóa một trạng thái của X
Một ý nghĩa của H(X)
• Trong trường hợp D=2 , ta thấy H(X) chính là số
ký tựmã trung bình cực tiểu dùng đểmã hóa 1
trạng thái của X
9/30/2010Huỳnh Văn Kha
16
• Một bộmã nhị phân tiền tố sẽ tương ứng với một
dãy các câu hỏi “yes no” dùng để xác định trạng
thái của X
• Trong đó số câu hỏi để xác định xi chính bằng
chiều dài ni của từmã tương ứng
• Vậy H(X) có thể xem là số câu hỏi trung bình cực
tiểu dùng để xác định trạng thái của X
Ví dụ
X Từmã
x 00
9/30/2010Huỳnh Văn Kha
17
x1?
x1
x2
x
yes
yes
yes
no
1
x2 01
x3 11
x4 100
x5 101
x1
or
x2?
x4
or
x5?
x4?
x5
4
x3
yes
no
no
no
Các file đính kèm theo tài liệu này:
- bai_giang_ly_thuyet_thong_tin_chuong_2_bai_toan_ma_truong_ho.pdf