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

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ã 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 9/30/2010Huỳnh Văn Kha 2 • 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) 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ã 9/30/2010Huỳnh Văn Kha 3 • 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: Mã tiền tố và mã giải ñược • Xét bộmã nhị phân 9/30/2010Huỳnh Văn Kha 4 x1 0 x 010 • 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ã 2 x3 01 x4 10 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ể 9/30/2010Huỳnh Văn Kha 5 đượ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 Mã tiền tố và mã giải ñược • Bộmã sau là bộmã tiền tố 9/30/2010Huỳnh Văn Kha 6 x1 0 • Bộmã sau là giải được nhưng không là tiền tố x2 100 x3 101 x4 11 x1 0 x2 01 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 S (n>1). Nếu có W trong S và A 9/30/2010Huỳnh Văn Kha 7 n-1 0 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 Thuật toán kiểm tra tính giải ñược x1 a x2 c x ad 9/30/2010Huỳnh Văn Kha 8 3 x4 abb x5 bad x6 deb x7 bbcde 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 9/30/2010Huỳnh Văn Kha 9 ad abb bad deb bbcde • Sn rỗng với mọi n>7 • ad thuộc S5 nên bộmã là không giải được • abbcdebad có thể giải mã thành x1x7x5 hoặc x4x2x6x3 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 9/30/2010Huỳnh Văn Kha 10 • 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 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 9/30/2010Huỳnh Văn Kha 11 Wi = AiAi+1 • Ví dụ trên, ta có: A5 = ad ε S5 W5 = ad A4 = b ε S4 W4 = bad A3 = de ε S3 W3= deb A2 = cde ε S2 W2 = c A1 = bb ε S1 W1 = bbcde A0 = a W0 = abb 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 9/30/2010Huỳnh Văn Kha 12 • 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 Tìm dãy mã không giải ñược • A0W1 = abbcde W0 = abb • W1 = A1A2
thêm W2 vào W0 • A W = abbcde W W = abbc 9/30/2010Huỳnh Văn Kha 13 0 1 0 2 • 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 • Chú ý: Ta thêm các Wi vào các dãy ngắn hơn 9/30/2010Huỳnh Văn Kha 14 x1 abc 010 x2 abcd 0001 x3 e 0110 x4 dba 1100 x5 bace 00011 x6 ceac 00110 x7 ceab 11110 x8 eabd 101011