Bài giảng Lý thuyết thông tin (Information Theory) - Chương 5: Mã tuyến tính nhị phân

Nội dung text: Bài giảng Lý thuyết thông tin (Information Theory) - Chương 5: Mã tuyến tính nhị phân

1. Chương 5. Mã tuyến tính nhị phân ntnhut@hcmus.edu.vn 1
2. Phép toán nhị phân • ĐN phép toán cộng (+) và nhân (.) trên bảng ký tự nhị phân 0, 1 như sau: • 1 = 1
   ‘cộng’ giống ‘trừ’ ntnhut@hcmus.edu.vn 2
3. Mã tuyến tính nhị phân Đ : Một mã K là mã tuyến tính (linear code) nếu: – Tổng a + b của hai codeword bất kỳ cũng là một codeword. – Tích k.a (với k = const và codeword a) cũng là một codeword. Đ : Mã nhị phân K là mã nhị phân tuyến tính (binary linear code) nếu tổng a + b của hai codeword bất kỳ cũng là một codeword. ntnhut@hcmus.edu.vn 3
4. Ví dụ mã nhị phân tuyến tính 1. Mã lặp K N = {‘00 0’, ‘11 1’}. 2. Mã kiểm chẵn lẻ (tổng số bit 1 là chẵn) ntnhut@hcmus.edu.vn 4
5. Hamming weight Định nghĩa : – Trọng số Hamming (Hamming weight) của một codeword a, ký hiệu w(a) , là số lượng các bit khác 0 của a. – Với mỗi mã K, trọng số Hamming nhỏ nhất của các codeword khác 0 = ‘00 0’ được gọi là trọng số nhỏ nhất (minimum weight) của K, ký hiệu w(K) . Ví dụ : Từ mã a = ‘11000’ có w(a) = 2; a là một codeword của mã kiểm chẵn lẻ độ dài 5. Mọi codeword a của mã kiểm chẵn lẻ K này có w(a) bằng 2 hoặc 4. Nên w(K) = 2. ntnhut@hcmus.edu.vn 5
6. Ma trận kiểm tra tính chẵn lẻ Đ : Một ma trận nhị phân H được gọi là ma trận kiểm chẵn lẻ (parity check matrix) của mã khối K độ dài n nếu với mọi từ mã x của mã K ta có Hx T = 0. Ví dụ : Một ma trận kiểm chẵn lẻ của mã kiểm chẵn lẻ là H = [1 1 1]. ntnhut@hcmus.edu.vn 6
7. Sửa lỗi Định lý : Một mã nhị phân tuyến tính K sửa được ít nhất một lỗi khi và chỉ khi mọi ma trận kiểm chẵn lẻ của K có các cột đôi một khác nhau và khác 0. Chứng minh: (xem sách).
   Mã kiểm chẵn lẻ không sửa được lỗi. ntnhut@hcmus.edu.vn 7
8. Mã Hamming Đ : Một mã nhị phân tuyến tính độ dài 2 m – 1 được gọi là mã Hamming nếu nó có một ma trận kiểm chẵn lẻ H kích thước m x 2 m – 1 thoả mọi từ nhị phân khác 0 độ dài m đều là một cột của H. ntnhut@hcmus.edu.vn 8
9. Ví dụ ntnhut@hcmus.edu.vn 9
10. Tính chất của một mã Hamming 1. Độ dài các từ mã n = 2 m – 1. 2. Số bit mang thông tin: k = 2 m – m – 1. 3.
    Tỷ lệ thông tin R = k/n = . 4. Khoảng cách nhỏ nhất của mã: d = 3. 5.
    sửa được ít nhất một lỗi. ntnhut@hcmus.edu.vn 10
11. Giải mã • Khi chuỗi nhận được là w = w 1w2 w n, • Tính s = Hw T. • Nếu s = 00 0: không có lỗi. • Nếu s ≠ 00 0. Vị trí của s trong ma trận H chính là vị trí bị lỗi. • Ta gọi s là syndrome . •
    ‘Giải mã bằng syndrome ’ ntnhut@hcmus.edu.vn 11
12. Ví dụ • Truyền 1111111, nhưng nhận w = 1110111. • Syndrome là s = Hw T. • s = (100). Vị trí bị lỗi là vị trí số 4. • Sửa 111 0111 là 111 1111. ntnhut@hcmus.edu.vn 12
13. Không phát hiện được lỗi • K là mã tuyến tính. • Giả sử truyền từ mã v ∈K, nhận w (w ≠v) cũng là từ mã ∈K •
    có lỗi nhưng không phát hiện được. • Tính xác suất không phát hiện được lỗi? ntnhut@hcmus.edu.vn 13
14. • Đặt e = w – v (= w + v). 1. e = 0  w = v : không có lỗi. 2. e ≠ 0: Nếu e là codeword thì không phát hiện được lỗi. – Giả sử w(e) = i (truyền v có i bit bị lỗi) –
    Xác suất xảy ra = p iqni. • Đặt A i = #{từ mã x có w(x) = i}. • Xác suất không phát hiện được lỗi ntnhut@hcmus.edu.vn 14
15. Ví dụ ntnhut@hcmus.edu.vn 15
16. Cách tính P und . ntnhut@hcmus.edu.vn 16
17. Ví dụ ntnhut@hcmus.edu.vn 17
18. Tóm tắt • Mã tuyến tính nhị phân • Hamming weight w(a) • Parity check matrix • Mã Hamming • Xác suất không phát hiện được lỗi P und . ntnhut@hcmus.edu.vn 18
19. Homework • Đọc lại và làm bài tập – Chương 5 [1] – Chương 1 [2] • Đọc trước chương 6+7 [1] ntnhut@hcmus.edu.vn 19
20. Bài tập • ‘Palindrome’ = chuỗi đối xứng (đọc xuôi đọc ngược như nhau). • VD: ‘was it a rat I saw’ • Xét mã nhị phân đối xứng K. Hỏi K có thể là một mã tuyến tính không? Nếu có, K có thể phát hiện được bao nhiêu lỗi. ntnhut@hcmus.edu.vn 20
21. Bài tập • Lập mã K nhị phân độ dài 7 như sau: – Bit thứ ba kiểm chẵn lẻ 2 bit đầu – Bit thứ sáu kiểm chẵn lẻ bit 4 và bit 5. – Bit thứ bảy kiểm chẵn lẻ toàn bộ từ mã. • Tính số lỗi mà K có thể: – Phát hiện được – Sửa được ntnhut@hcmus.edu.vn 21
22. Bài tập • Tính P err (K) của mã Hamming K (7,4) với p = 0.01. • Tổng quát, Tính P err (K) của mã Hamming K độ dài 2 m – 1 theo p và m. m • Tính P und (K) của mã Hamming K độ dài 2 – 1 ntnhut@hcmus.edu.vn 22