Bài giảng Kỹ thuật truyền số liệu - Chương 8: Tìm đường trong mạng chuyển mạch (tt)

Bài giảng "Kỹ thuật truyền số liệu - Chương 8: Tìm đường trong mạng chuyển mạch" phần tiếp theo trình bày các nội dung liên quan đến vấn đề nén và mã hóa dữ liệu bao gồm: Nén dữ liệu, mã hóa dữ liệu. Hi vọng đây sẽ là một tài liệu hữu ích dành cho các bạn sinh viên Công nghệ thông tin dùng làm tài liệu tham khảo phục vụ học tập và nghiên cứu.
Nội dung trích xuất từ tài liệu:
Bài giảng Kỹ thuật truyền số liệu - Chương 8: Tìm đường trong mạng chuyển mạch (tt) 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 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 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 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 dce 2008 Nén dữ liệu Huffman encoding (Statistical Methods) Chiều dài từ mã trung bình Lavg = Σl x p i i li : chiều dài nguồn tin Xi pi : xác suất xuất nguồn tin Xi 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 0.06 0.09 0 0.10 1 CT Huffman code 28 0.05 0.05 0 0.06 1 25 1 0 21 0.05 0.05 0 0.05 1 24 0 0 0 29 0.04 0.04 1 26 0 0 1 20 0.03 0 25 Probability distribution 23 0 1 1 30 0.02 1 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 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+ 20 0 1 0 0 0 0 5.0,04+6.0.03+6.0,02 = 3,18 bits 30 0 1 0 0 0 1 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ã 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 ...