Kỹ thuật truyền số liệu - Nén và mã hóa dữ liệu

Nội dung text: Kỹ thuật truyền số liệu - Nén và mã hóa dữ liệu

1. dce 2008 Nén và mã hóa dữ liệu Nén dữ liệu BK TP.HCM Mã hóa dữ liệu
2. dce 2008 Nén dữ liệu Run-length encoding (packed decimal) Là phương pháp rất đơn giản sử dụng cho dạng dữ liệu mà trong đó chứa nhiều chuỗi dữ liệu giống nhau Sử dụng các chữ số để thể hiện số lần lặp của chuỗi ký thự đó Ví dụ: chuỗi wwwwbbbbcccccdd có thể được biểu diễn như sau: 4w4b6c2d
3. dce 2008 Nén dữ liệu Differenial encoding (relative encoding) Chỉ gửi phần thay đổi so với giá trị cũ Original 1509 1506 1508 1510 1511 1509 1513 Encoded 1509 -3 +2 +2 +1 -2 +4 STX ‘+’ ’1’ ’‘ ‘+’ ‘2’ ‘’ ‘+’ ‘’ ETX BCC End-of-value delimiters Flag +3 +4 +5 +5 +4 +3 Flag All difference values binary-encoded in a single (signed) byte
4. dce 2008 Nén dữ liệu Huffman encoding (Statistical Methods) Đặc điểm Đây là mã thống kê (phương pháp nén mã tối ưu) Mã hóa dựa trên xác suất sử dụng của các ký tự Những ký tự được dùng nhiều nhất sẽ có từ mã ngắn nhất Không có tính prefix Giải thuật Sắp xếp các nguồn tin có xác suất giảm dần Một cặp bit 0-1 được gán cho 2 nguồn tin có xác suất nhỏ nhất 2 nguồn tin này được kết hợp, tạo thành nguồn tin mới có xác suất bằng tổng xác suất của 2 nguồn tin thành phần Sắp xếp lại các nguồn tin theo thứ tự giảm dần của xác suất Quá trình trên được lặp lại đến khi 2 nguồn tin cuối cùng được kết hợp Từ mã cho mỗi nguồn tin được viết theo thứ tự từ gốc đến ngọn
5. dce 2008 Nén dữ liệu Huffman encoding (Statistical Methods) Chiều dài từ mã trung bình Lavg = Σli x pi li : chiều dài nguồn tin Xi pi : xác suất xuất nguồn tin Xi
6. dce 2008 Nén dữ liệu Huffman Code CT Prob 25 0.21 0.27 0.32 0.41 0.59 0 24 0.17 0.20 0.21 0.27 0.32 0 0.41 1 26 0.15 0.17 0.20 0.21 0 0.27 1 23 0.12 0.15 0.15 0.17 0 0.2 1 27 0.10 0.12 0.15 0 0.15 1 22 0.06 0.09 0.10 0.10 0 0.12 1 CT Huffman code 28 0.05 0.06 0.09 0 0.10 1 25 1 0 21 0.05 0.05 0 0.06 1 24 0 0 0 29 0.04 0.05 0 0.05 1 26 0 0 1 20 0.03 0 0.04 1 Probability distribution 23 0 1 1 30 0.02 1 25 20 27 1 1 0 15 22 0 1 0 1 10 5 28 1 1 1 0 21 1 1 1 1 21 23 29 27 29 29 0 1 0 0 1 20 0 1 0 0 0 0 Lavg=2.0,21+3.0,17+3.0,15+3.0,12+3.0,1+4.0,06+4.0,05+4.0,05+ 5.0,04+6.0.03+6.0,02 = 3,18 bits 30 0 1 0 0 0 1
7. dce 2008 Nén dữ liệu Shannon-Fano encoding (Statistical Methods) Đặc điểm Mã tối ưu Không có tính prefix Giải thuật Sắp xếp các nguồn tin theo thứ tự giảm dần về xác suất Chia các nguồn tin thành hai phần có xác suất xấp xỉ nhau và gán 0 cho phần trên, gán 1 cho phần dưới Lặp lại bước trên cho mỗi phần cho đến khi chỉ còn một nguồn tin Ghi ra các từ mã
8. dce 2008 Nén dữ liệu Shannon – Fano Các nguồn tin và xác suất xuất hiện của các nguồn tin tương ứng X1 (30%), X2 (20%), X3 (10%), X4 (10%), X5 (20%), X6 (5%), X7 (3%), X8 (2%) Lavg = 2.0,3+2.0,2+3.0,2+3.0,1+3.0,1+4.0,05+5.0,03+5.0,02 = 2,65 bits Initial Sorted Shannon-Fano code Code word STT Xi % Xi % Step 1 Step 2 Step 3 Step 4 Step 5 1 X1 30 X1 30 0 0 00 2 X2 20 X2 20 0 1 01 3 X3 10 X5 20 1 0 0 100 4 X4 10 X3 10 1 0 1 101 5 X5 20 X4 10 1 1 0 110 6 X6 5 X6 5 1 1 1 0 1110 7 X7 3 X7 3 1 1 1 1 0 11110 8 X8 2 X8 2 1 1 1 1 1 11111
9. dce 2008 Mật mã hóa số liệu Tại sao đường truyền số liệu một số ứng dụng cần phải bảo mật ? Ví dụ: Quốc phòng, ngân hàng Phương pháp mật mã: Mật mã cổ điển Mật mã khóa công khai
10. dce 2008 Mật mã hóa số liệu Mật mã hóa cổ điển Một hệ thống mật mã hóa cổ điển là một tập có 5 thành phần (P,C,K,E,D) trong đó: P là tập hữu hạn các bản gốc có thể C là tập hữu hạn các bản mã có thể K là tập khóa có thể Đối với mỗi k ∈ K – Có một luật mật mã ek: P→C (ek∈E) – Có một luật giải mã tương ứng dk: C→P(dk∈D) – ek và dk: là những ánh xạ sao cho: dk (ek(x))=x ∀ x ∈ P Các phương pháp mật mã cổ điển: Mã dịch vòng, Mã thay thế, mã Affine
11. dce 2008 Mật mã hóa số liệu Mật mã hóa cổ điển Phương pháp mã dịch vòng Cơ sở là phép toán modulo Ví dụ: Mật mã trên bộ chử cái tiếng Anh gồm 26 chữ cái ek(x)=x + K mod 26 dk(y)=y – K mod 26 A B C D E F G H I J K L M 0 1 2 3 4 5 6 7 8 9 10 11 12 N O P Q R S T U V W X Y Z 13 14 15 16 17 18 19 20 21 22 23 24 25
12. dce 2008 Mật mã hóa số liệu Mật mã hóa cổ điển Phương pháp mã dịch vòng Ví dụ: Văn bản gốc: gonewiththewind Khóa của mã dịch vòng là 9 Đổi văn bản gốc thành các số nguyên G O N E W I T H T H E W I N D 6 14 13 4 22 8 19 7 19 7 4 22 8 13 3 Cộng thêm 9 vào mỗi giá trị rồi modulo 26 15 23 22 13 5 17 2 16 2 16 13 5 17 22 12 P X W N F R C Q C Q N F R W M
13. dce 2008 Mật mã hóa số liệu Mật mã hóa công khai Mật mã hóa khóa công khai cho phép người sử dụng trao đổi các thông tin mật mà không cần phải trao đổi các khóa bí mật trước đó. Sử dụng một cặp khóa có quan hệ toán học với nhau là khóa công khai và khóa cá nhân (hay khóa bí mật). Thuật ngữ mật mã hóa khóa bất đối xứng thường được dùng đồng nghĩa với mật mã hóa khóa công khai (hai khái niệm không hoàn toàn tương đương) Hệ thống mật mã hóa khóa công khai có thể dùng với các mục đích: Mã hóa Tạo chữ ký số Thỏa thuận khóa RSA (1977: - Ron Rivest, Adi Shamir, and Leonard Adleman at MIT) Diffie-Hellman algorithm (1975: Whitfield Diffie and Martin Hellman)
14. dce 2008 Mật mã hóa số liệu Mật mã hóa công khai Mã hóa
15. dce 2008 Mật mã hóa số liệu Mật mã hóa công khai Tạo chữ ký số
16. dce 2008 Mật mã hóa số liệu Mật mã hóa công khai Thỏa thuận khóa
17. dce 2008 Đọc thêm • Information Theory, Robert B.Ash • Introduction to Information Theory, Masud Mansuripur • www.wikipedia.org Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 17