Trường ĐH Điện Lực
Khoa : ĐTVT
Bài thuyết trình môn:
Kĩ thuật truyền số liệu
Đề tài:
NÉN DỮ LIỆU
1
Nén dữ liệu
Tổng quát
Phương pháp mã
hóa độ dài loạt
Phương pháp
mã hóa
Huffman
Mã shannon-
fanon
Mã vi phân
Phương pháp
nén LZW
2
Tổng kết
1.Tổng quát
3
Định nghĩa nén dữ liệu

Nén là quá trình làm giảm số lượng bit cần biểu diễn thông "n truyền đi ở mức độ chấp nhận được.
Mục đích của việc nén dữ liệu

Lưu trữ dữ liệu được nhiều hơn.

Tiết kiệm được vùng nhớ.

- Độ dài mã tỷ lệ nghịch với xác suất xuất hiện của ký tự.
- Từ mã được giải mã một cách duy nhất
Thuật toán:
Xác định các tần suất, xác suất xuất hiện của các ký tự trong bản tin.
Sắp xếp các ký tự theo trình tự tần suất xuất hiện giảm dần.
Các ký tự sẽ là các nút của cây Huffman
7
Phương pháp mã hóa Human
Mã hóa bắt đầu với hai ký tự có xác suất nhỏ nhất. Hai ký tự được hợp lại , hai nhánh được gán ký hiệu 0 hoặc 1.
Nút của hai nhánh được coi là 1 ký hiệu mới có xác suất bằng tổng hai xác suất xuất hiện của hai ký tự tạo ra nút.
Tiếp tục quá trình trên với 2 nút có xác suất xuất hiện nhỏ nhất.
Từ mã ứng với mỗi ký hiệu nguồn là tổ hợp của các ký hiệu mã ở các nhánh tính từ gốc.
8
9
Phương pháp mã hóa Human
Xác suất của các kí tự
Kí tự sau khi mã hóa
Tỉ lệ nén:
4. Mã shannon- fanon
Nguyên lý:
- Các từ mã có độ dài biến thiên.
- Độ dài mã tỷ lệ nghịch với xác suất xuất hiện của ký tự.
- Từ mã được giải mã một cách duy nhất.
Thuật toán:
- Xác định các tần suất, xác suất xuất hiện của các ký tự trong bản "n.
Sắp xếp các ký tự theo trình tự tần suất xuất hiện giảm dần.
Phân chia các ký tự thành hai nhóm có tổng xác suất xấp xỉ nhau (nếu dùng mã nhị phân thì phân chia làm hai nhóm, nếu mã cơ số m thì chia làm m nhóm).
10
Mã shannon- fanon
Phần bên trái của danh sách được gán chữ số nhị phân 0, và phần bên phải được gán chữ số 1.

5129765586
552968951
Khung thứ 1 Khung thứ 2 Khung thứ 3
0000000000
00010000-10
0000000000
0000000010
0000000000
0000000000
0010000100
0000000000
0000-100010
0000000000
14
6. Phương pháp nén LZW
•
Từ Điển Mã Hóa LZW.
→Do kích thước bộ nhớ không phải vô hạn và để đảm bảo tốc độ tìm kiếm, từ điển chỉ giới hạn 4096 ở phần tử dùng để lưu lớn nhất là 4096 giá
trị của các từ mã.
→ Cấu trúc từ điển như sau:
256 từ mã đầu tiên theo thứ tự từ 0…255 chứa các số nguyên từ 0…255. Đây là mã của 256 ký tự cơ bản trong bảng mã ASCII.
Từ mã thứ 256 chứa một mã đặc biệt là “mã xoá” (CC- Clear Code).
Từ mã thứ 257 chứa mã kết thúc thông tin (EOI – End of information). Mã này có giá trị là 257.
Các từ mã còn lại (từ 258 đến 4095) chứa các mẫu thường lặp lại trong ảnh.
15
Phương pháp nén LZW
Giá Trị Của Các Chuỗi Trong Từ Điển.
→Các từ mã từ 512 đến 1023 biểu diễn bởi 10 bit.
→Từ 1024 đến 2047 biểu diễn bởi 11 bit.
→Từ 2048 đến 4095 biểu diễn bởi 12 bit.

Những hạn chế của 2 ma shan-non và Huffman
•
Trong quá trình nén cần đến 2 lần duyệt file dẫn đến chi phí nén cao
•
Cần phải lưu trữ thông tin để giải nén dẫn đến là việc tăng kích thước dữ liệu nén
•
Dữ liệu nén cần phải có sẵn.
21