Bài giảng Lý thuyết thông tin: Chương 2.1 - ThS. Huỳnh Văn Kha

Chia sẻ: Ngocnga Ngocnga | Ngày: | Loại File: PDF | Số trang:14

Thêm vào BST

Báo xấu

74
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Lý thuyết thông tin - Chương 2 cung cấp cho người học những kiến thức về bài toán mã trường hợp kênh không bị nhiễu. Trong phần này người học sẽ tìm hiểu về tính giải được của một bộ mã với các nội dung cụ thể như: Giới thiệu bài toán mã, mã tiền tố và mã giải được, giải thuật kiểm tra tính giải được,... Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Lý thuyết thông tin: Chương 2.1 - ThS. Huỳnh Văn Kha

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ã
2 Huỳnh Văn Kha 9/30/2010 Giới thiệu bài toán mã • Biến ngẫu nhiên X nhậ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ủa X gọ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 xi tươ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)
3 Huỳnh Văn Kha 9/30/2010 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 X sinh 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 xi là ni, i = 1, 2, …, M. Mục tiêu là cực tiểu hóa:
4 Huỳnh Văn Kha 9/30/2010 Mã tiền tố và mã giải ñược • Xét bộ mã nhị phân x1 0 x2 010 x3 01 x4 10 • 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ã
5 Huỳnh Văn Kha 9/30/2010 Mã tiền tố và mã giải ñược • Bộ mã gọi là giải được nế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 A gọi là tiền tố của dãy B nếu dãy B có thể được viết dưới dạng AC, với C là 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
6 Huỳnh Văn Kha 9/30/2010 Mã tiền tố và mã giải ñược • Bộ mã sau là bộ mã tiền tố x1 0 x2 100 x3 101 x4 11 • Bộ mã sau là giải được nhưng không là tiền tố x1 0 x2 01
7 Huỳnh Văn Kha 9/30/2010 Giải thuật kiểm tra tính giải ñược • Gọi S0 là 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, Wj sao cho Wj = WiA, cho hậu tố A vào tập S1 • Giả sử có tập Sn-1 (n>1). Nếu có W trong S0 và A trong Sn-1 sao cho A=WB, cho B vào Sn. Nếu có W’ trong So và 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
8 Huỳnh Văn Kha 9/30/2010 Thuật toán kiểm tra tính giải ñược x1 a x2 c x3 ad x4 abb x5 bad x6 deb x7 bbcde
9 Huỳnh Văn Kha 9/30/2010 Thuật toán kiểm tra tính giải ñược S0 S1 S2 S3 S4 S5 S6 S7 a d eb de b ad d eb c bb cde bcde ad • Sn rỗng với mọi n>7 abb • ad thuộc S5 nên bộ mã là không bad giải được deb • abbcdebad có thể giải mã thành bbcde x1x7x5 hoặc x4x2x6x3
10 Huỳnh Văn Kha 9/30/2010 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ử Sn chứa từ mã W. Tiến hành ngược lại, ta tìm được dãy: A0, W0, A1, W1, …, An, Wn
11 Huỳnh Văn Kha 9/30/2010 Tìm dãy mã không giải ñược • A0, W0, W1, …, Wn là các từ mã, Ai ε Si (i = 1, 2, …, n), W0 = A0A1, An = Wn • Với mỗi i = 1, 2, …, n-1 thì hoặc Ai = WiAi+1 hoặc Wi = AiAi+1 • Ví dụ trên, ta có: A5 = ad ε S5 A4 = b ε S4 A3 = de ε S3 W5 = ad W4 = bad W3= deb A2 = cde ε S2 A1 = bb ε S1 A0 = a W2 = c W1 = bbcde W0 = abb
12 Huỳnh Văn Kha 9/30/2010 Tìm dãy mã không giải ñược • Ta xây dựng hai dãy, một dãy bắt đầu với A0W1, dãy kia bắt đầu với W0 • Nếu Ai = WiAi+1, thêm Wi+1 vào cuối dãy chứa Wi • Nếu Wi = AiAi+1, thêm Wi+1 vào cuối dãy không chứa Wi • Tiếp tục như vậy đến Wn • Người ta chứng minh được rằng hai dãy tạo thành như trên là một, và chính là dãy mã không giải được cần tìm
13 Huỳnh Văn Kha 9/30/2010 Tìm dãy mã không giải ñược • A0W1 = abbcde W0 = abb • W1 = A1A2 thêm W2 vào W0 • A0W1 = abbcde W0W2 = abbc • A2 = W2A3 thêm W3 vào W0W2 • A0W1 = abbcde W0W2W3 = abbcdeb • W3 = A3A4 thêm W4 vào A0W1 • A0W1W4 = abbcdebad W0W2W3 = abbcdeb • W4 = A4A5 thêm W5 vào W0W2W3 • A0W1W4 = abbcdebad W0W2W3W5 = abbcdebad
14 Huỳnh Văn Kha 9/30/2010 • Chú ý: Ta thêm các Wi vào các dãy ngắn hơn x1 abc 010 x2 abcd 0001 x3 e 0110 x4 dba 1100 x5 bace 00011 x6 ceac 00110 x7 ceab 11110 x8 eabd 101011