Bài giảng Lý thuyết thông tin - Chương 3: Nén dữ liệu (Data compression) và entropy

Nội dung text: Bài giảng Lý thuyết thông tin - Chương 3: Nén dữ liệu (Data compression) và entropy

1. Chương 3. Nén dữ liệu (data compression) và entropy [email protected] 1
2. Ví dụ “3.1” về nén dữ liệu • Chuỗi nhị phân, số ký tự ‘0’ nhiều gấp 9 lần ‘1’: – P(‘0’) = 0.9, P(‘1’) = 0.1. • Chia chuỗi thành từng khối để mã hoá. • Trường hợp một khối = 2 ký tự: • Mã Huffman: • Độ dài mã TB: [email protected] 2
3. • Trường hợp một byte = 2 ký tự: – Cần TB khoảng 1.29 bits để mã hoá 2 ký tự, hay 1.29/2 = 0.645 bits/ký tự. • Trường hợp 1 byte = 3 ký tự: Câu hỏi : chúng ta có thể nén đến mức nào? Có thể nén 0.5 bits/ký tự hay ít hơn nữa được không? [email protected] 3
4. Ý tưởng về entropy • 1948, Claude E. Shannon. • Nén dựa vào tính cú pháp (syntactic) của văn bản, không phải tính ngữ nghĩa (semantic) . • Entropy của một nguồn thông tin S, H(S): – H(S) = lượng thông tin cần thiết để xác định một ký tự nguồn. • Tính chất của H(S): – H(S) = H(p 1, p 2, , p n). – H(S) dương, liên tục, đối xứng . [email protected] 4
5. Định nghĩa entropy Định nghĩa : Entropy của nguồn thông tin S có các phân phối xác suất p 1, , p n là: Ví dụ: Tung đồng xu, xác suất 2 mặt là như nhau. Entropy của nguồn thông tin này là [email protected] 5
6. Entropy nhị phân đối xứng Chuỗi nhị phân, số ký tự ‘0’ nhiều gấp 9 lần ‘1’ Nguồn thông tin với 2 ký tự và xác suất (p,1 – p): [email protected] 6
7. Entropy cực tiểu và cực đại Định lý : (1) Entropy cực tiểu = 0 khi S chỉ có 1 ký tự. (2) Entropy đạt cực đại = log 2n bits khi xác suất của các ký tự bằng nhau = 1/n. Chứng minh : (1) pi, log 2(1/p i) ≥ 0. ‘=’ khi p i = 0 hay 1/p i = 1. (2) (bài tập). [email protected] 7
8. Mở rộng của nguồn thông tin Định nghĩa : Cho S là nguồn thông tin {a 1, , a n}. Mở rộng bậc k của S , ký hiệu S k, là nguồn thông tin có các ký tự dạng ‘a i1 ai2 a ik ’ với các xác suất P(a i1 ai2 a ik ) = P(a i1 )P(a i2 ) P(a ik ). Trong đó, i 1, i 2, , i k ∈{1, 2, , n}. Ví dụ 3.1 (tiếp): S: {0,1}; P(0) = 0.9; P(1) = 0.1. S2 và S3: [email protected] 8
9. Mối liên hệ giữa Entropy và Độ dài mã trung bình Định lý : mọi mã tức thời nhị phân của nguồn S đều có độ dài mã trung bình không nhỏ hơn entropy của S: L ≥ H(S). Chứng minh : (bài tập) [email protected] 9
10. Định lý mã không nhiễu của Shannon • Trong Ví dụ 3.1: – H(S) = 0.469 (bits) 2 – Lmin (S )/2 = 0.645 bits/symbol 3 – Lmin (S )/3 = 0.533 bits/symbol – ≥ H(S). Định lý : Với mọi nguồn S, độ dài mã Huffman nhị phân L min (S) thoả : H(S) ≤ Lmin (S) ≤ H(S) + 1. Với mở rộng S k của nguồn S ta có : Chứng minh: (bài tập) [email protected] 10
11. Tóm tắt 1. Với mỗi nguồn S, entropy H(S) là lượng thông tin trung bình (tính bằng bit) của một ký tự. H(S) là số bit trung bình tối ưu để nén S. 2. Mã Huffman của S k là cách nén tối ưu nhất. 3. Với bảng mã có r>2 ký tự mã: [email protected] 11
12. Homework • Đọc lại: – Chương 3 [1]. – Chương 2 [2]. • Đọc trước: – Chương 4 [1] [email protected] 12
13. Bài tập 1 • Một văn bản được viết bằng bảng ký tự {A, B, C, D}, trong đó ký tự A xuất hiện nhiều gấp 7 lần mỗi ký tự còn lại. Tìm một mã nhị phân sử dụng trung bình không quá 1.4 bits/ký tự. • Gợi ý: dùng mở rộng S k. [email protected] 13
14. Bài tập 2 • Tính entropy của nguồn thông tin sau • Bài tập Thực hành: Tính entropy của một nguồn thông tin cho trước. [email protected] 14
15. Bài tập 3 • Một kênh truyền các ký tự 0 và 1 đồng xác suất. Tính xác suất nhận được chuỗi ‘01101’. Tính entropy của một văn bản dùng các chuỗi 5 ký tự. [email protected] 15
16. Bài tập 4 • Một nguồn thông tin gồm 128 ký tự đồng xác suất. Tính độ dài của chuỗi có entropy bằng 42 bits. [email protected] 16
17. Bài tập 5 • Hiệu quả E(S) của một nguồn thông tin S được định nghĩa là tỷ số giữa entropy H(S) và độ dài trung bình của mã Huffman nhị phân L min (S). a) CMR: 0 ≤ E(S) ≤ 1. b) Nhận xét các cực trị của E(S). c) Tính E(S) của các nguồn sau [email protected] 17
18. Bài tập 6 • Một văn bản nhị phân dài chứa số ký tự ‘0’ nhiều gấp đôi ‘1’. Tìm mã nén: a) Sử dụng tối đa 0.94 bits/ký tự b) Sử dụng tối đa 0.9 bits/ký tự. [email protected] 18