Bài giảng Lý thuyết thông tin - Chương 7: Mã tuyến tính

Nội dung text: Bài giảng Lý thuyết thông tin - Chương 7: Mã tuyến tính

1. Chương 7. Mã tuyến tính ntnhut@hcmus.edu.vn 1
2. Mã tuyến tính Đ : Cho F là một trường hữu hạn. Mã tuyến tính là một không gian con của không gian F n các từ độ dài n. Nói cách khác, một KG con k chiều của F n là một mã (n,k) trên bộ ký tự F. Lưu ý: • Một mã tuyến tính (n,k) có k bit mang thông tin và n – k bit kiểm tra. • Nếu F có r ký tự, thì bộ mã có r k từ mã. ntnhut@hcmus.edu.vn 2
3. Ma trận sinh Đ : Cho K là một mã tuyến tính và B = {e 1, e 2, , e k} là một cơ sở của K. Một ma trận sinh (generator matrix) G ứng với cơ sở B của K là ma trận VD : Một ma trận sinh của mã Hamming (7,4) ntnhut@hcmus.edu.vn 3
4. Ví dụ • Mã kiểm chẵn kẻ độ dài 4 có một ma trận sinh • Mỗi ma trận G’ thu được từ các phép biến đổi dòng sơ cấp của ma trận G cũng là ma trận sinh của cùng một mã. ntnhut@hcmus.edu.vn 4
5. Mã tuyến tính hệ thống • Đ : Một mã tuyến tính được gọi là hệ thống (systematic) nếu ma trận sinh G = [I | B], trong đó I là ma trận đơn vị. • Hai mã K và K’ được gọi là tương đương (equivalent) nếu chúng chỉ khác nhau ở thứ tự của các ký tự trong từ mã. Tức là, tồn tại một hoán vị (p 1, p2, , p n) của (1, 2, , n) sao cho v1v2 v n là từ mã của K ⇔ vp1 vp2 v pn là từ mã của K’. ntnhut@hcmus.edu.vn 5
6. Ví dụ • Mã Hamming (7,4) có ma trận sinh G sau là hệ thống • Mệnh đề: Mọi mã tuyến tính đều tương đương với một mã hệ thống. ntnhut@hcmus.edu.vn 6
7. Ma trận kiểm chẵn lẻ Đ : Cho K là một mã tuyến tính độ dài n trên trường F. Một ma trận H có n cột trên F được gọi là ma trận kiểm chẵn lẻ (parity check matrix) của K nếu v là từ mã của K ⇔ Hv = 0. Ma trận kiểm chẵn lẻ H thoả : GH T = 0. Mệnh đề: Một mã hệ thống với ma trận sinh G = [I | B ] thì có ma trận kiểm chẵn lẻ H = [ BT | I ]. gược lại, nếu H = [A | I ] thì G = [I | AT]. ntnhut@hcmus.edu.vn 7
8. Syndrome Đ: Cho K là một mã tuyến tính có ma trận kiểm chẵn lẻ H kích thước m x n. Syndrome của từ w là s = Hw. Giải mã : Khi nhận từ w, tính syndrome s = Hw. Chọn từ có trọng Hamming nhỏ nhất có syndrome như thế. ntnhut@hcmus.edu.vn 8
9. Phát hiện và sửa lỗi Mệnh đề : Trọng nhỏ nhất d của mã tuyến tính (n,k) thoả d ≤ n – k + 1. hắc lại : Một mã K phát hiện được t lỗi nếu khoảng cách nhỏ nhất của K lớn hơn t. Ta mong muốn : 1. Khoảng cách nhỏ nhất (d) lớn. 2. Số bit mang thông tin (k) lớn. Lưu ý: Hai mã tương đương nhau K và K’ thì có cùng các thông số n, k, d. ntnhut@hcmus.edu.vn 9
10. Giải mã bằng syndrome • Mã tuyến tính K (n,k) có ma trận kiểm chẵn lẻ H. • Khi truyền v, ta nhận được w = e + v. Trong đó e được gọi là error pattern . • Các từ cùng một lớp ghép (coset) có cùng syndrome. 1. Khi nhận w, tính s = Hw. 2. Tìm coset leader e tương ứng với s. 3. Suy ra v = w – e. ntnhut@hcmus.edu.vn 10
11. Ví dụ • Giả sử mã K độ dài 5 định nghĩa bởi • Có ma trận ntnhut@hcmus.edu.vn 11
12. • Giả sử nhận w = 11111. • Tính s: • Suy ra: e = 10000 • Suy ra: v = w – e = 01111. ntnhut@hcmus.edu.vn 12
13. Xác định bảng sau như thế nào? • Syndrome gồm tất cả các từ s độ dài n – k. • Coset leader là các nghiệm e có trọng Hamming nhỏ nhất của pt He = s. e 1  • VD : e  2  0  e+ e + e = 0 e  = ⇔ 1 2 4 3      0 e+ e = 0 e    3 5 4  e  5  ntnhut@hcmus.edu.vn 13
14. Phát hiện và sửa lỗi ngay • Mã Hamming (7,4) có d = 3, có thể phát hiện 2 lỗi nhưng chỉ sửa được 1 lỗi (không sửa được 2 lỗi). • VD : truyền 0000000 nhưng nhận 1010000. Theo cách giải mã bằng syndrome: – syndrome là 010. – Bit số 2 bị lỗi – Giải mã là 1110000. (không phải 0000000) ntnhut@hcmus.edu.vn 14
15. Phát hiện và sửa lỗi ngay Đ : Mã K được gọi là phát hiện được s lỗi và sửa được t lỗi ngay nếu với mọi từ mã v ta có: từ w có d(w,v) ≤ s thì có d(w,v’) > t với các từ mã v’ khác v. Hoạt động của mã K theo ĐN trên như sau: – Khi nhận từ w – Tìm từ mã v có khoảng cách Hamming với w là nhỏ nhất – Nếu d(w,v) ≤ t thì sửa được trở lại thành v. – Nếu d(w,v) > t thì thông báo rằng có ít nhất s lỗi xảy ra. ntnhut@hcmus.edu.vn 15
16. Phát hiện và sửa lỗi ngay Mệnh đề : Một mã có thể phát hiện được s lỗi và sửa được t lỗi ngay nếu và chỉ nếu d ≥ t + s + 1. ntnhut@hcmus.edu.vn 16
17. Cho G không hệ thống, tính H? • VD : trên Z3, cho ma trận sinh của một mã như sau • Ta chuyển thành ma trận sinh của mã hệ thống tương đương bằng một phép hoán vị p=(1,4,6,2,5,3) các cột về dạng [I | B]. • Ta tính được H* tương ứng với G* là • Tính H bằng hoán vị ngược p 1. • Thử lại: GH T = 0. ntnhut@hcmus.edu.vn 17
18. Tóm tắt • Mã tuyến tính • Ma trận sinh • Mã tuyến tính hệ thống • Parity check matrix • Syndrome • Phát hiện và sửa lỗi ngay ntnhut@hcmus.edu.vn 18
19. Homework • Đọc và làm chương 8 [1] ntnhut@hcmus.edu.vn 19
20. Bài tập 1. Cho ma trận sinh của một mã tuyến tính trên Z5 bên. Tìm ma trận kiểm chẵn lẻ H. 2. Tính toán lại bài 1 trên Z7. 3. Cho ma trận sinh của một mã tuyến tính nhị phân K bên. Hỏi K có hệ thống không? Nếu không, tìm mã hthống tương đương K’. 4. Lập bảng mã ứng với hai mã K và K’ trong bài 3. ntnhut@hcmus.edu.vn 20