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 2)

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 X có 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 9/30/2010 2 Huỳnh Văn Kha • 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 xk có 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 Ví dụ • Ví dụ 1: M = 3, D = 2, n1 = 1, n2 = 2, n3 = 3
Có thể chọn bộmã {0, 10, 110} 9/30/2010 3 Huỳnh Văn Kha • 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? ðịnh lý 2.2 Một bộmã tiền tố với chiều dài các từmã n1, n2, , nM là tồn tại khi và chỉ khi 9/30/2010 4 Huỳnh Văn Kha Trong đó D là số các ký tựmã 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, 9/30/2010 5 Huỳnh Văn Kha , 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 Vs khác nhau • Nếu dãy t có được do thêm duy nhất một ký tự vào sau s thì nối Vs và Vt bằng một đoạn thẳng • Các điểm ứng với dãy có chiều dài k gọi là các điểm ngọn của cây kích thước k Chứng minh ñịnh lý 2.2 0 00 000 001 010 0 00 01 02 10 9/30/2010 6 Huỳnh Văn Kha 01 011 1 10 11 100 101 110 111 Cây bậc 2 kích thước 3 1 11 12 2 20 21 22 Cây bậc 3 kích thước 2 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 D kích thước nM 9/30/2010 7 Huỳnh Văn Kha 0 1 10 11 111 Cây ứng với bộ mã {0, 10, 111} 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 9/30/2010 8 Huỳnh Văn Kha • Điểm ứng với từmã chiều dài nk sẽ 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 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 9/30/2010 9 Huỳnh Văn Kha 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 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 9/30/2010 10 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, , nM thì: minh định lý sau là đủ. Chứng minh ñịnh lý 2.3 • Gọi ωj là số từmã chiều dài j và r là chiều dài lớn nhất của các từmã, ta có: 9/30/2010 11 Huỳnh Văn Kha • Với mỗi số tự nhiên n cho trước, nhân phân phối và rút gọn, ta được: Chứng minh ñịnh lý 2.3 • Trong đó: 9/30/2010 12 Huỳnh Văn Kha • Nk chính là tổng sốmẫu tin được tạo thành từ n trạng thái xi sao cho đoạn mã của các mẫu tin này đều có chiều dài k • Bộmã là giải được nên mỗi dãy ký tựmã tương ứng với nhiều nhất một mẫu tin • Nk không vượt quá tổng số các dãy ký tựmã có chiều dài k Chứng minh ñịnh lý 2.3 • Như vậy Nk ≤ Dk và ta có: 9/30/2010 13 Huỳnh Văn Kha • Lấy căn bậc n: • Cho n tiến ra vô cực ta được điều cần chứng minh