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

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

Thêm vào BST

Báo xấu

117
lượt xem 10
download

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

Chương 4 của bài giảng Lý thuyết thông tin trình bày những kiến thức về mã sửa sai. Trong chương này chúng ta sẽ tìm hiểu về khoảng cách Hamming, chận Hamming và kênh nhị phân đối xứng. Mời các bạn cùng tham khảo để nắm bắt các nội dung chi tiết.

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 4.1 - ThS. Huỳnh Văn Kha

Chương 4: Mã sửa sai 4.1 Khoảng cách Hamming và chận Hamming
2 Huỳnh Văn Kha 9/30/2010 Giới thiệu • Ở chương này ta chỉ xét kênh nhị phân đối xứng • Các input của kênh được chọn từ một tập các từ mã nhị phân chiều dài n, nghĩa là tập các dãy n ký tự 0 và 1 • Giả sử các từ mã xuất hiện với xác suất bằng nhau • Do lỗi có thể xảy ra ở bất cứ vị trí nào của chuỗi input nên output là tập 2n dãy nhị phân độ dài n • Bài toán đầu tiên là tìm phương án giải mã tối ưu cho bộ mã nói trên
3 Huỳnh Văn Kha 9/30/2010 Giới thiệu • Ký hiệu các từ mã và các chuỗi output lần lượt là w1, w2, …., ws và v1, v2, … • Phương án giải mã tối ưu là phương án làm cực tiểu xác suất sai • Khi nhận được v, như ta đã biết, phương án giải mã tối ưu là chọn w sao cho p(w|v) cực đại • Nhưng do các từ mã có cùng xác suất nên cực đại p(w|v) tương đương với việc cực đại p(v|w)
4 Huỳnh Văn Kha 9/30/2010 Khoảng cách Hamming • Ta định nghĩa khoảng cách d(v1, v2) giữa hai dãy nhị phân n ký tự v1, v2 là số vị trí mà ở đó ký tự mã của v1, v2 khác nhau • Ví dụ: v1 = 011011, v2 = 110001 Thì d(v1, v2) = 3 • Nếu input là w và output là v thì khi đó kênh đã truyền sai đúng d(w, v) ký tự. Do đó nếu xác suất truyền sai của kênh là β, thì
5 Huỳnh Văn Kha 9/30/2010 Cực ñại p(v|w) • Ta sẽ so sánh p(v|w1) và p(v|w2) • Đặt d1 = d(w1,v), d2 = d(w2,v), ta có • Chú ý, đối với kênh nhị phân đối xứng ta luôn giả sử 0< β < ½, và do đó (1 - β)/β >1. Vậy p(v|w1) > p(v|w2) khi và chỉ khi d1 < d2 • Vậy p(v|w) cực đại khi d(v,w) cực tiểu
6 Huỳnh Văn Kha 9/30/2010 ðịnh lý 4.1 Giả sử bộ mã cho kênh nhị phân đối xứng gồm s từ mã độ dài n có xác suất như nhau. Phương án giải mã tối ưu là phương án làm cực tiểu khoảng cách. Nghĩa là với mỗi dãy v nhận được, bộ giải mã sẽ chọn từ mã w sao cho khoảng cách d(w,v) là nhỏ nhất Nếu có nhiều hơn một cực tiểu thì chọn từ mã nào trong số đó cũng không ảnh hưởng đến xác suất sai
7 Huỳnh Văn Kha 9/30/2010 Ví dụ • Cho bộ mã w1 = 00000 w2 = 10011 w3 = 11100 w4 = 01111 • Tìm phương án giải mã tối ưu khi nhận được v = 01011, v’ = 00110?
8 Huỳnh Văn Kha 9/30/2010 Tính chất của khoảng cách Ta có thể kiểm chứng rằng khoảng cách Hamming là một metric, nghĩa là thỏa các tính chất sau a. d(v1, v2) ≥ 0, d(v1, v2) = 0 khi và chỉ khi v1 = v2 b. d(v1, v2) = d(v2, v1) c. d(v1, v3) ≤ d(v1, v2) + d(v2, v3) Bất đẳng thức cuối cùng là bất đẳng thức tam giác • Do ta giải mã dãy v thành từ mã gần với v nhất nên xuất hiện khái niệm bộ mã “tốt” là bộ mã có các từ mã “ở xa” nhau
9 Huỳnh Văn Kha 9/30/2010 Bổ ñề 4.2 Gọi w1, w2, …, ws là các từ mã nhị phân chiều dài n, và e là một số nguyên dương. Giả sử d(wi, wj) ≥ 2e + 1, với mọi i ≠ j Thì khi đó, mọi sự truyền sai không quá e bit đều có thể sửa được. Nếu d(wi, wj) ≥ 2e, với mọi i ≠ j, thì mọi sự truyền sai không quá e-1 bit đều có thể sửa được và mọi sự truyền sai e bit đều có thể phát hiện được, nhưng chưa chắc sửa được
10 Huỳnh Văn Kha 9/30/2010 Bổ ñề 4.2 Ngược lại, bộ mã có tính chất mọi sự truyền sai không quá e bit đều sửa được thì phải thỏa mãn d(wi, wj) ≥ 2e + 1, với mọi i ≠ j Một bộ mã có tính chất mọi sự truyền sai không quá e-1 bit đều sửa được, và mọi sự truyền sai không quá e bit đều phát hiện được thì phải thỏa mãn d(wi, wj) ≥ 2e , với mọi i ≠ j
11 Huỳnh Văn Kha 9/30/2010 Chứng minh bổ ñề 4.2 wi wj wi wj d(wi, wj) = 2e+1 d(wi, wj) = 2e • Giả sử w được truyền và chuỗi nhận được là v. Xét w’ là từ mã khác w • Đầu tiên giả sử khoảng cách cực tiểu của hai từ mã ít nhất là 2e+1, ta có d(w,v) + d(w’,v) ≥ d(w,w’) ≥ 2e+1
12 Huỳnh Văn Kha 9/30/2010 Chứng minh bổ ñề 4.2 • Để bộ giãi mã v thành w’ thì d(w,v) ≥ e + 1. Nghĩa là để giải mã sai thì phải truyền sai ít nhất e + 1 ký tự • Nếu khoảng cách giữa hai từ mã ít nhất là 2e thì d(w,v) + d(w’,v) ≥ d(w,w’) ≥ 2e • Nếu sai đúng e ký tự và d(w’,v) = e thì giải mã thành w hay w’ đều được, nghĩa là có thể sai • Nếu sai ít hơn e ký tự thì d(w,v) là nhỏ nhất và sẽ giải mã đúng. • Chiều ngược lại tương tự
13 Huỳnh Văn Kha 9/30/2010 Chận Hamming Khi e lớn thì khoảng cách giữa các từ mã cũng lớn hơn và dẫn tới số từ mã ít đi. Câu hỏi đặt ra là có nhiều nhất bao nhiêu từ mã trong một bộ mã có thể sửa được mọi sự truyền sai không quá e ký tự Định lý 4.3: Nếu bộ mã chứa s dãy nhị phân chiều dài n có thể sửa sai mọi sự truyền sai không quá e ký tự, thì:
14 Huỳnh Văn Kha 9/30/2010 Chứng minh ñịnh lý 4.3 • Gọi các từ mã là w1, w2, …, ws. Vẽ các “mặt cầu” “tâm” wi “bán kính” e. Mỗi “mặt cầu” như vậy chứa tất cả dãy nhị phân v thỏa d(wi,v) ≤ e • Do bộ mã sửa được mọi sự truyền sai e ký tự nên các “mặt cầu” là rời nhau • Số dãy nhị phân trong mỗi mặt cầu là • Do đó
15 Huỳnh Văn Kha 9/30/2010 Chú ý • Cố định e, n và gọi s là số nguyên lớn nhất thỏa điều kiện định lý 4.3 thì chưa chắc tồn tại bộ mã sửa sai được e ký tự chứa s từ mã chiều dài n • Ví dụ, nếu e = 1, n = 4 ta có 2n/(1+n) = 16/5 và số nguyên lớn nhất thỏa là s = 3 • Tuy nhiên không có bộ mã nào sửa sai được 1 ký tự mà có số từ mã nhiều hơn 2 (kiểm tra) • Vậy chận Hamming là điều kiện cần nhưng chưa đủ cho sự tồn tại của của bộ mã sửa sai e ký tự