Bài giảng Kỹ thuật truyền dữ liệu - Chương 8 Tìm đường trong mạng chuyển mạch (Phần 2)

BK TP.HCM 2008 dce Nén và mã hóa dữ liệu Nén dữ liệu Mã hóa dữ liệu 2008 dce 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 2008 dce 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 +3Flag +4 +5 +5 +4 +3 Flag All difference values binary-encoded in a single (signed) byte 2008 dce 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 2008 dce 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 2008 dce CT 25 Prob 0.21 24 26 0.17 0.15 23 0.12 27 22 0.10 0.06 28 0.05 21 29 0.05 0.04 20 0.03 30 0.02 0 1 0.05 0.04 0 1 0.05 0.05 0 1 0.09 0.06 0 1 0.10 0.10 0 1 0.15 0.12 0 1 0.17 0.15 0 1 0.21 0.2 0 1 0.32 0.27 0 1 0.59 0.41 0 1 0.09 0.06 0.10 0.15 0.12 0.20 0.17 0.15 0.27 0.21 0.20 0.32 0.27 0.41 25 24 26 23 27 22 28 21 29 20 30 CT 0 1 0 0 0 1 Huffman code 0 1 0 0 0 0 0 1 0 0 1 1 1 1 1 1 1 1 0 0 1 0 1 1 1 0 0 1 1 0 0 1 0 0 0 1 0 21 23 29 27 29 25 20 15 10 5 Probability distribution 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 Nén dữ liệu Huffman Code 2008 dce 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ã 2008 dce 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 2008 dce 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 2008 dce 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 2008 dce 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 2008 dce 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 Cộng thêm 9 vào mỗi giá trị rồi modulo 26 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 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 2008 dce 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) 2008 dce Mật mã hóa số liệu Mật mã hóa công khai Mã hóa 2008 dce Mật mã hóa số liệu Mật mã hóa công khai Tạo chữ ký số 2008 dce Mật mã hóa số liệu Mật mã hóa công khai Thỏa thuận khóa 2008 dce Đọc thêm • Information Theory, Robert B.Ash • Introduction to Information Theory, Masud Mansuripur • www.wikipedia.org ©2008, Dr. Dinh Duc Anh Vu 17Data Communication and Computer Networks