Bài giảng Lý thuyết thông tin - Chương 4: Truyền tin trên kênh nhiễu

Nội dung text: Bài giảng Lý thuyết thông tin - Chương 4: Truyền tin trên kênh nhiễu

1. Chương 4. Truyền tin trên kênh nhiễu ntnhut@hcmus.edu.vn 1
2. Mã dùng để phát hiện và tự sửa lỗi • Kênh truyền hay thiết bị lưu trữ thông tin không tránh khỏi bị nhiễu/lỗi. • Lý thuyết mã có thể dùng để phát hiện lỗi và tự sửa lỗi. Mã tự sửa (errorcorrecting code) ntnhut@hcmus.edu.vn 2
3. Giải pháp ntnhut@hcmus.edu.vn 3
4. Kênh đối xứng nhị phân 1. Inputs = ouputs = {0,1} 2. P(nhận 1| truyền 0) = P(nhận 0| truyền 1) = f error probability . 3. P(nhận 1| truyền 1) = P(nhận 0| truyền 0) = 1 – f. ntnhut@hcmus.edu.vn 4
5. Tỷ lệ nhiễu/lỗi Hình 1. Ảnh nhị phân kích thước 10.000 bits truyền trên kênh nhị phân đối xứng với tỷ lệ nhiễu/lỗi f = 0.1 (cứ khoảng 10 bit thì có 1 bit bị lỗi 0 1). ntnhut@hcmus.edu.vn 5
6. Bài toán tính xác suất nhận đúng tín hiệu • Tín hiệu nhị phân: – Một tín hiệu được tạo thành từ những bit 0,1. Qua thống kê, ta biết do nhiễu, bình quân 1/5 số bit 0 và ¼ số bit 1 bị lỗi. – Biết rằng tỷ số số bit 0 và 1 truyền đi là 5:3. Tính xác suất nhận đúng tín hiệu phát đi. • Ký hiệu: – T0 = “phát bit 0”, T 1 = “phát bit 1” – N0 = “nhận bit 0”, N 1 = “nhận bit 1”. • Tính: – P(T 0 | N 0) = ? – P(T 1 | N 1) = ? ntnhut@hcmus.edu.vn 6
7. Cách giải bài toán tín hiệu nhị phân • Tính các xác suất: – P(T 0), P(T 1) – P(N 0 | T 0), P(N 0 | T 1), P(N 1 | T 1), P(N 1 | T 0), • Dùng công thức Bayes • Tính – P(T | N ) = ? 0 0 Bài tập – P(T 1 | N 1) = ? ntnhut@hcmus.edu.vn 7
8. VD cách khắc phục lỗi: Mã lặp • Ví dụ mã hoá hiễu ntnhut@hcmus.edu.vn 8
9. Giải mã mã lặp theo luật đa số • Luật đa số (Majority vote rule) ntnhut@hcmus.edu.vn 9
10. Giải mã, phát hiện và tự sửa lỗi ntnhut@hcmus.edu.vn 10
11. Lỗi khi tự sửa ntnhut@hcmus.edu.vn 11
12. Xác suất giải mã bị lỗi p err (K) • t = “a 1a2a3” r = “b 1b2b3”. • Giải mã theo “luật đa số” bị lỗi khi: 3 – bi ≠ ai, ∀i. Xác suất: f . – Có 2 vị trí bị lỗi. 3 trường hợp xác suất = 3f 2(1 – f). 3 2 2 3 • perr (K 3) = f + 3f (1 – f) = 3f – 2f ntnhut@hcmus.edu.vn 12
13. VD giảm lỗi: Mã lặp K 5 • Xác suất giải mã bị lỗi • Ít lỗi hơn K 3. ntnhut@hcmus.edu.vn 13
14. Bài tập • Tính xác suất giải mã bị lỗi của mã lặp K N perr (K N) • BT Thực hành: tạo hàm mã hoá và giải mã nhị phân mã lặp: – Mã hoá t = EncodeK(N,x), – Tạo nhiễu ngẫu nhiên tỷ lệ f r = AddNoise(t,f) – Giải mã y =DecodeK(N,r). – Tính tỷ lệ lỗi p sau khi so sánh x và y. ntnhut@hcmus.edu.vn 14
15. Tỷ lệ thông tin • Mã khối nhị phân K có các từ mã dài n bits: – Chỉ có k bits “mang thông tin”. – n – k bits kiểm tra lỗi. – Có tất cả 2 k từ mã. • VD: Mã lặp K n: – Chỉ có 1 bit ý nghĩa R(K ) = 1/n – n – 1 bits còn lại lặp lại bit đầu tiên. n Định nghĩa : Tỷ lệ thông tin (information rate) của mã khối K độ dài n của nguồn r ký tự có r k từ mã là R(K) = k/n. ntnhut@hcmus.edu.vn 15
16. Tính chất của tỷ lệ thông tin • 0 ≤ R(K) = k/n ≤ 1. • R(K) = 0 khi k = 0: không có thông tin. • R(K) = 1 khi k = n: mã không phát hiện + sửa được lỗi. • R(K) 0 : không hiệu quả về mặt chi phí nhưng phát hiện + sửa lỗi hiệu quả. • R(K) 1 : hiệu quả về mặt chi phí nhưng phát hiện + sửa lỗi không hiệu quả. ntnhut@hcmus.edu.vn 16
17. Ví dụ tỷ lệ thông tin cao: Mã kiểm chẵn lẻ • R(K) = (n – 1)/n • Có thể phát hiện 1 bit lỗi. ntnhut@hcmus.edu.vn 17
18. Bài toán lập mã tự sửa Lập mã tự sửa K thoả: 1. Biết trước xác suất lỗi khi truyền mỗi bit = p. 2. Xác suất giải mã bị lỗi không quá p err (K). 3. Tỷ lệ thông tin không dưới R(K). 4. Phát hiện/sửa lỗi được càng nhiều càng tốt. ntnhut@hcmus.edu.vn 18
19. Ví dụ mã K 4* Cho p = 0.001, p err (K) ≤ 0.0002, R(K) ≥ 0.5. VD với mã K 4* (lặp 3 lần bit thứ hai) • Giải mã chính xác khi: – cả 4 bit đều đúng (xác suất q 4 = (1 – p) 4 ) hoặc – bit đầu + 2 bit còn lại đúng (xác suất q3pq 2 = 3pq 3). 4 3 • perr (K 4*) = 1 – (q + 3pq ) = 1 – (0.999 4 + 3(0.001)0.999 3) ≅ 0.0003. (> p err (K) ) K4* chưa tốt ntnhut@hcmus.edu.vn 19
20. Ví dụ mã K 6* • Các từ mã của K 6* khác nhau đôi một ít nhất 3 bit. phát hiện + tự sửa được chính xác 1 bit lỗi. VD : nhận “010100”, không có trong bộ từ mã có lỗi. • “010100” Chỉ khác 1 bit đối với từ mã “010101”. giải mã thành “010”. 6 5 • Giải mã chính xác khi: perr (K 6*) = 1 – (q + 6pq ) ☺ – Cả 6 bit đều đúng (q 6), hoặc ≅ 0.00015 (< p err (K) ). 5 – Chỉ có 1 bit sai (6pq ) ntnhut@hcmus.edu.vn 20
21. Khoảng cách Hamming Định nghĩa : Khoảng cách Hamming của hai từ a=a 1a2 a n và b=b 1b2 b n là số vị trí mà a và b khác nhau, ký hiệu d(a,b). d(a,b) = #{i | a i ≠ bi}. Ví dụ : K * • Mã lặp K N có khoảng cách 6 Hamming giữa các từ mã bằng N. • Mã K 6* có khoảng cách Hamming giữa các từ mã là 3. ntnhut@hcmus.edu.vn 21
22. Tính chất của d(a,b) Với mọi từ a, b, c cùng độ dài n trong một bảng ký tự Σ, d(a,b) là một metric : 1. d(a,a) = 0; và với a ≠ b thì d(a,b) > 0. 2. d(a,b) = d(b,a). 3. d(a,b) + d(b,c) ≥ d(a,c). Chứng minh : (bài tập) ntnhut@hcmus.edu.vn 22
23. Giải mã hợp lý nhất • Nếu từ nhận được, r, không có trong bộ mã chọn từ mã có khoảng cách Hamming nhỏ nhất để giải mã maximum likelihood decoding . ntnhut@hcmus.edu.vn 23
24. Khoảng cách nhỏ nhất Định nghĩa : khoảng cách nhỏ nhất d(K) của mã khối K là khoảng cách Hamming nhỏ nhất giữa hai từ mã khác nhau bất kỳ, d(K) = min{d(a,b) | a ≠ b ∈ K}. Ví dụ: • Mã lặp có d(K N) = N. • Mã K 6* có d(K 6*) = 3. • Mã kiểm chẵn lẻ có d(K) = 2. ntnhut@hcmus.edu.vn 24
25. Phát hiện lỗi Mệnh đề : Mã K phát hiện được t lỗi khi và chỉ khi d(K) > t. Chứng minh: (bài tập) ntnhut@hcmus.edu.vn 25
26. Sửa lỗi • Ý tưởng: – Mã K sửa được t lỗi nếu mỗi chuỗi ký tự a’ nhận được từ việc gây lỗi ở 1, hoặc 2, , hoặc t ký tự của từ mã a thì vẫn giải mã được duy nhất là a. – Nói cách khác: ∀a ∈ K, ∀ a ' : 1≤daa (,') ≤⇒ t daa (,') ≤ dba (,'), ∀≠∈ ba K ntnhut@hcmus.edu.vn 26
27. Sửa lỗi Mệnh đề: Một mã sửa được t lỗi khi và chỉ khi khoảng cách nhỏ nhất của nó lơn hơn 2t.
28. Tóm tắt • Tỷ lệ nhiễu f • Bài toán tín hiệu nhị phân • Mã lặp K n • Xác suất giải mã bị lỗi p err • Tỷ lệ thông tin R(K) = k/n. • Khoảng cách Hamming d(a,b) • Khoảng cách nhỏ nhất d(K) ntnhut@hcmus.edu.vn 28
29. Dung lượng kênh truyền ntnhut@hcmus.edu.vn 29
30. Kênh truyền • Kênh truyền rời rạc: • Biết tính năng của – Inputs: x 1, x 2, , x n. kênh truyền như thế – Outputs: y 1, y 2, , y m. nào? • Không nhớ: – thông qua thử nghiệm – Output tại một thời điểm việc truyền mỗi x j, với mọi j = 1, 2, , n. yt chỉ phụ thuộc input x t tại thời điểm đó. Không – Kết quả của việc thử cho phụ thuộc các inputs ta các phân phối xác suất trước. P(y 1 | x j), P(y 2 | x j), , P(y m | x j) với mỗi input xj. ntnhut@hcmus.edu.vn 30
31. Kênh thông tin rời rạc không nhớ Đ : Kênh thông tin rời rạc không nhớ gồm tập các ký tự input {x 1, x 2, , x n}, tập các ký tự outputs {y 1, y 2, , y m} cùng với các phân phối xác suất P(y i | x j) ứng với mỗi j = 1 nthoả m ∑P( yi | x j )= 1 i=1 VD : 1. Với n = m = 2 và P(y 2 | x 1) = P(y 1 | x 2) = p là kênh đối xứng nhị phân. 2. Một kênh truyền theo thống kê thấy 1% input cho output ERROR và 99% truyền đúng. ntnhut@hcmus.edu.vn 31
32. Nhắc lại một số công thức xác suất ntnhut@hcmus.edu.vn 32
33. VD Tính các xác suất ntnhut@hcmus.edu.vn 33
34. Entropy điều kiện và thông tin chung Đ : Cho một nguồn thông tin S và một kênh thông tin với inputs là các ký tự của S. – Entropy có điều kiện , ký hiệu H(X|Y), là giá trị – Lượng thông tin , ký hiệu I(X,Y), là giá trị ntnhut@hcmus.edu.vn 34
35. Ví Dụ ntnhut@hcmus.edu.vn 35
36. Dung lượng kênh truyền Đ: Dung lượng (capacity) kênh truyền C là giá trị cực đại của lượng thông tin ntnhut@hcmus.edu.vn 36
37. Dung lượng kênh truyền nhị phân đối xứng Định lý : Dung lượng của một kênh nhị phân đối xứng là ntnhut@hcmus.edu.vn 37
38. Ví Dụ 1 • Kênh nhị phân đối xứng với tỷ lệ lỗi p = 0.001 có dung lượng • Kênh nhị phân đối xứng với tỷ lệ lỗi p = 0.5 có dung lượng ntnhut@hcmus.edu.vn 38
39. Ví Dụ 2 • Giá trị cực đại của H(S) là 1bit, nên có dung lượng C = 0.99 bits. ntnhut@hcmus.edu.vn 39
40. Định lý cơ bản của Shannon ĐL : Mọi kênh nhị phân đối xứng với dung lượng C > 0 cho trước có thể được mã hoá với độ tin cậy cao và tỷ lệ thông tin gần bằng C. Nói cách khác, tồn tại dãy các mã K 1, K 2, có độ dài mã tương ứng là 1, 2, sao cho ntnhut@hcmus.edu.vn 40
41. ĐL đảo của ĐL Shannon ĐL : Trong mỗi kênh nhị phân đối xứng với dung lượng C cho trước, nếu mã K n (độ dài mã bằng n) có tỷ lệ thông tin lớn hơn C, thì mã có xu hướng không tin cậy. Nói cách khác: ntnhut@hcmus.edu.vn 41
42. Ví Dụ Kênh nhị phân đối xứng với tỷ lệ lỗi p = 0.001 có dung lượng C = 0.989. 1. Tồn tại mã có độ tin cậy bất kỳ với tỷ lệ thông tin R = 0.9 ( C) không thể có độ tin cậy cao. ntnhut@hcmus.edu.vn 42
43. Tóm tắt • Kênh rời rạc không nhớ • Xác suất, xác suất có điều kiện • Entropy có điều kiện H(X|Y) • Lượng thông tin I(X,Y) • Dung lượng kênh truyền I max . • ĐL của Shannon ntnhut@hcmus.edu.vn 43
44. Homework • Đọc lại và làm bài tập: – Chương 4 [1] – Chương 1 [2] • Đọc trước chương 5 [1] ntnhut@hcmus.edu.vn 44
45. Bài tập 1 Cho một nguồn thông tin nhị phân có P(0) = p, P(1) = q = 1 – p. Giả sử n ký tự được truyền đi. • CM xác suất một từ nhị phân độ dài n xuất hiện ký tự 0 ở các vị trí i 1, i 2, , i k, còn lại là các ký tự 1 là p kqnk. • Suy ra xác suất một từ xuất hiện ký tự 0 ở k vị trí bất kỳ là ntnhut@hcmus.edu.vn 45
46. Bài tập 2 Trong một kênh nhị phân đối xứng có tỷ lệ lỗi p = 0.1 1. Tìm độ dài mã lặp K thoả xác suất giải mã lỗi 4 Perr (K) < 10 . 2. Tính P err (K 6*) ntnhut@hcmus.edu.vn 46
47. Bài tập 3 CM lượng thông tin có các tính chất sau • I(X,Y) ≥ 0. Dấu = xảy ra khi nào. • I(X,Y) ≤ H(S). Dấu = xảy ra khi nào. ntnhut@hcmus.edu.vn 47