Bài giảng Lý thuyết thông tin - Chương 1: Mã hoá và giải mã

Nội dung text: Bài giảng Lý thuyết thông tin - Chương 1: Mã hoá và giải mã

1. Chương 1. Mã hoá và giải mã Encoding and decoding [Chap 1. Jiri Adamek, Foundations of Coding ] ntnhut@hcmus.edu.vn 1
2. Vấn đề chính của lý thuyết thông tin hiễu (noisy) Truyền đi (transmit) a 5 MB én an 100 KB image (compress) image Mất chi tiết (loss of details) ntnhut@hcmus.edu.vn 2
3. oisy channels ntnhut@hcmus.edu.vn 3
4. Cách khắc phục (solution) ntnhut@hcmus.edu.vn 4
5. Các khái niệm cơ sở • Ký tự (letter) : ‘A’, ‘B’, • Bảng ký tự (alphabet) = {các ký tự} – Source alphabet: bảng ký tự nguồn. – Code alphabet: bảng ký tự mã. • Từ (word) = “ANHLAAI” • Binary
   bảng ký tự đang xét chỉ có 2 ký tự – Thường dùng ‘0’, ‘1’ ntnhut@hcmus.edu.vn 5
6. Mã hoá (encoding) • A = {A 1, , A p}: source alphabet • B = {B 1, , B q}: code alphabet • Phép mã hoá là một đơn ánh K đi từ tập A đến tập các từ trong B, K : A
   
   
   B* • K(A i) = “B i1 B ik ” : từ mã (code word) • Mã (code) = {K(A 1), , K(A p)} Ký tự nguồn Mã hoá Từ mã ntnhut@hcmus.edu.vn 6
7. Ví dụ Mã “2outof5” • Chuỗi “173” được mã hoá thành “110001000101100” • Giải mã thử chuỗi “100100100101010” ntnhut@hcmus.edu.vn 7
8. Giải mã (decoding) “AH” Mã hoá “0001 001 00 ” “AH” Giải mã “0001 001 00 ” Giải mã duy nhất ntnhut@hcmus.edu.vn 8
9. Giải mã không duy nhất “AH” Mã hoá “000100100 ” “CHI” Giải mã “000100100 ” Giải mã không duy nhất • Mã 2outof5 có giải mã duy nhất không? ntnhut@hcmus.edu.vn 9
10. Ví dụ giải mã không duy nhất • Xét mã sau • Giải mã thử “10110” ntnhut@hcmus.edu.vn 10
11. Mã khối và mã tức thời • Mã khối (block code): – Các từ mã khác nhau từng đôi một có cùng độ dài – Dễ giải mã – Dùng cho mã tự sửa lỗi (error correcting code) . • Mã tức thời (instantaneous code): – Mỗi từ mã không là tiền tố (prefix) của các từ mã khác. – Độ dài mỗi từ mã có thể khác nhau . –– Dùng cho mã nén (compressing code) ntnhut@hcmus.edu.vn 11
12. Ví dụ mã tức thời – mã Morse ntnhut@hcmus.edu.vn 12
13. Ví dụ mã khối • Mã octal ntnhut@hcmus.edu.vn 13
14. Mã ASCII (American Standard Code for Information Interchange ) • 27 = 128 ký tự nguồn: Parity check – {A, B, , Z} – {a, b, , z} – {0, 1, , 9} – {@, %, (, <, } • 0: even number of 1’s. • Từ mã nhị phân độ dài 8: • 1: odd number of 1’s. – 7 bit mang thông tin – 1 bit kiểm tra chẵn lẻ (parity check). ntnhut@hcmus.edu.vn 14
15. • Ghi chú: ntnhut@hcmus.edu.vn 15
16. Mã ISBN (international standard book number) • Bảng ký tự mã = {0, 1, , 9, X} • Từ mã độ dài 10 (kiểu mới có độ dài 13) • ội dung: – Mã quốc gia/mã ngôn ngữ – Nhà xuất bản – Mã ấn phNm – Check number chia hết cho 11 ntnhut@hcmus.edu.vn 16
17. Short break ntnhut@hcmus.edu.vn 17
18. Xây dựng mã tức thời Bài toán : xây dựng bộ mã tức thời cho các ký tự nguồn. – Yêu cầu : độ dài các từ mã bằng các giá trị d 1, d 2, , d n nguyên dương cho trước. Ví dụ : mã hoá nhị phân các ký tự {0, 1, 2, 3} bằng mã tức thời với độ dài các từ mã là 1, 2, 3, 3. ntnhut@hcmus.edu.vn 18
19. Cách xây dựng mã tức thời • Giả sử d 1 ≤ d2 ≤ ≤ dn. • Chọn một từ mã K(a 1) nào đó có độ dài d 1. • Chọn một từ mã K(a ) có độ dài 2 K(a 11)) d2 thoả không chứa K(a 1) là tiền tố. K(a 22)) • Tiếp tục quá trình trên cho d 3, , d n. Khả thi không? ntnhut@hcmus.edu.vn 19
20. • Tổng số từ có độ dài d 2 chứa K(a 1) làm tiền tố: 2d2 – d1 . • Mà 2d2 ≥ 2d2 – d1 + 1
    
    
    Tồn tại ít nhất một từ mã K(a 2) thoả yêu cầu. • K(a 3)? – không chứa K(a 1) hay K(a 2) làm tiền tố. – Tồn tại K(a 3) nếu 2d3 ≥ 2d3 – d1 + 2 d3 – d2 + 1. – Chia hai vế cho 2 d3 : 1 ≥ 2–d1 + 2 –d2 + 2 –d3 .
    
    
    Tổng quát? ntnhut@hcmus.edu.vn 20
21. Bất đẳng thức Kraft Định lý : Với bảng ký tự nguồn có n ký tự, bảng ký tự mã có k ký tự. Để xây dựng được mã tức thời với các độ dài mã d 1, d2, , dn cho trước, bất đẳng thức Kraft sau phải thoả: k–d1 + k –d2 + + k –dn ≤ 1. Ví dụ : Mã hoá nhị phân {0, 1, 2, 3} với các độ dài mã 1, 2, 3, 3 là khả thi vì: 2–1 + 2 –2 + 2 –3 + 2 –3 ≤ 1. Chẳng hạn ntnhut@hcmus.edu.vn 21
22. • BĐT Kraft kiểm tra sự tồn tại hay không của một mã tức thời thoả các điều kiện độ dài từ mã cho trước. • N gược lại, cho trước một mã giải mã duy nhất bất kỳ, các độ dài từ mã có thoả BĐT Kraft không? ntnhut@hcmus.edu.vn 22
23. Định lý McMillan Định lý : Mọi mã giải mã duy nhất đều thoả bất đẳng thức Kraft : k–d1 + k –d2 + + k –dn ≤ 1. Ví dụ : • Mã khối • Mã 2outof5: n = 10, k = 2, d i = 5 ∀i. 10(2 –5) ≤ 1 ! • Mã tức thời • ntnhut@hcmus.edu.vn 23
24. Tóm tắt • LT thông tin nghiên cứu cách : – Mã hoá thông tin có thể tự sửa lỗi nhiễu – N én dữ liệu • Khái niệm cơ bản : – Ký tự, bảng ký tự – Từ mã – Giải mã duy nhất – Mã khối – Mã tức thời – BĐT Kraft ntnhut@hcmus.edu.vn 24
25. Homework • [1] Jiri Adamek, Foundations of Coding • Đọc lại chương 1 [1] và làm các bài tập cuối chương. • Đọc trước chương 2 [1] Mã Huffman. • Đăng ký thành viên trên web môn học • Đăng ký nhóm tối đa 3SV/nhóm. ntnhut@hcmus.edu.vn 25
26. Bài tập 1 • N ếu dùng mã khối thì độ dài mã ngắn nhất có thể dùng là bao nhiêu để mã hoá bảng ký tự nguồn {A, B, , Z} bằng bảng ký tự mã {•, ─, ‘ ’} giống mã Morse. ntnhut@hcmus.edu.vn 26
27. Bài tập 2 a) Xét tính giải mã duy nhất của các mã trong hai hình bên? Chỉ ra một đoạn mã làm phản ví dụ cho trường hợp giải mã không duy nhất. b) Chúng có là mã tức thời không? Giải thích. c) Thay thế chúng bằng các mã tức thời khác có cùng các độ dài mã. ntnhut@hcmus.edu.vn 27
28. Bài tập 3 • Dùng bất đẳng thức Kraft để xét tính giải mã duy nhất của các mã sau ntnhut@hcmus.edu.vn 28
29. Bài tập 4 • Xây dựng mã nhị phân tức thời cho bảng ký tự nguồn sau với độ dài mã tương ứng ntnhut@hcmus.edu.vn 29
30. Bài tập 5 • Để mã hoá bảng ký tự nguồn sau với độ dài mã tương ứng, cần ít nhất bao nhiêu ký tự mã. ntnhut@hcmus.edu.vn 30