Trang chủ Kỹ Thuật Số Phương pháp mã hóa Shannon – Fano và phương pháp Huffman – Luận văn, đồ án, đề tài tốt nghiệp

Phương pháp mã hóa Shannon – Fano và phương pháp Huffman – Luận văn, đồ án, đề tài tốt nghiệp

– Giải quyết kém hiệu suất cao so với những loại độ dư thừa khác ( ví dụ điển hình như độ dư thừa vị trí ). – Tốn nhiều thời hạn kiến thiết xây dựng cây mã. – Cấu trúc của cây mã hoặc bộ từ mã đã dùng để mã hóa phải được gởi đi cùng với số liệu đã được mã hóa .

docx9 trang |

Chia sẻ: tienthan23

| Lượt xem : 32321

| Lượt tải: 4

download

Bạn đang xem nội dung tài liệu Phương pháp mã hóa Shannon – Fano và phương pháp Huffman, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên

Bài luận bàn Môn : Lý thuyết thông tin Nhóm đàm đạo : Câu hỏi đàm đạo : Phương pháp mã hóa Shannon – Fano và chiêu thức Huffman. Mục lục Mã thống kê tối ưu 3 hương pháp mã hóa Shannon – Fano Phương pháp Shannon 4 Phương pháp Fano. 5 Phương pháp Huffman .. 7 Ứng dụng. 9 I > Mã thống kê tối ưu Là phép mã hóa mà tác dụng là một bộ mã có chiều dai trung bình là nhỏ nhất trong toàn bộ những phép mã hóa hoàn toàn có thể có trong nguồn. Bộ mã của phép mã hóa tối ưu cho nguồn được gọi là mã hóa tối ưu. Ba phép mã hóa : Shannon, Fano, Huffman. Trong mỗi phép mã hóa tất cả chúng ta sẽ mã hóa với cơ số mã m = 2. Ta xét phép mã hóa sau so với những tin của nguồn rời rạc A : f : aI → αIni Mỗi tin ai được mã hóa bằng một tổng hợp mã ( từ mã ) αIni ( αini là một tổng hợp mã gồm ni dấu mã ). Ta xét trường hợp mã nhị phân tức là mỗi dấu mã chỉ nhận một trong hai giá trị 0 và 1. Độ dài của trung bình của một tổng hợp mã được xác lập bởi công thức : = i = 1 snip ( ai ) Một phép mã hóa được gọi là tối ưu nếu nó làm cực tiểu giá trị. II > Phương pháp mã hóa Shannon – Fano Phương pháp Shannon Các bước triển khai mã hóa theo giải pháp Shannon : B1 : Sắp xếp những Phần Trăm theo thứ tự giảm dần. Không mất tính tổng quát giả sử P1 > P2 > > Pk. B2 : Định nghĩa q1 = 0, qi = j = 1 i – 1P j với mọi i = 1,2, , k. B3 : Đổi qi sang cơ số 2 ( màn biểu diễn qi trong cơ số 2 ) sẽ được một chuỗi nhị phân. B4 : Từ mã được gán cho ai và li ký hiệu lấy từ vị trí sau dấu phẩy của chuỗi nhị phân tương ứng với qi, trong đó li = [ – log2pi ]. Ví dụ : Mã hóa nguồn S = { a1 ; a2 ; a3 ; a4 ; a5 ; a6 ; a7 ; a8 } với những Xác Suất lần lượt là 0,25 ; 0.125 ; 0.0625 ; 0.0625 ; 0.25 ; 0.125 ; 0.0625 ; 0.0625. Tin ai Xác suất pi qi = j = 1 i – 1P j Biểu diễn nhị phân li = [ – log2pi ] Từ mã wi a1 0.25 0 0.0000000 2 00 a5 0.25 0.25 0.0100000 2 01 a2 0.125 0.5 0.1000000 3 100 a6 0.125 0.625 0.1010000 3 101 a3 0.0625 0.75 0.1100000 4 1100 a4 0.0625 0.8125 0.1101000 4 1101 a7 0.0625 0.875 0.1110000 4 1110 a8 0.0625 0.9375 0.1111000 4 1111 Độ dài trung bình của từ mã : = 0.25 * 2 + 0.25 * 2 + 0.125 * 3 + 0.125 * 3 + 0.0625 * 4 + 0.0625 * 4 + 0.0625 * 4 + 0.0625 * 4 = 2.75 Entropie của nguồn tin : H ( s ) = – [ 0.25 * log20. 25 + 0.25 * log20. 25 + 0.125 * log20. 125 + 0.125 * log20. 125 + 0.0625 * log20. 0625 + 0.0625 * log20. 0625 + 0.0625 * log20. 0625 + 0.0625 * log20. 0625 ] = 2.75 Hiệu suất lập mã : h = H ( s ) = 2.752.75 = 1 Phương pháp Fano Các bước triển khai mã hóa theo chiêu thức Fano : B1 : Sắp xếp những Phần Trăm theo thứ tự giảm dần. Không mất tính tổng quát giả sử P1 > P2 >> Pk. B2 : Phân những Tỷ Lệ thành hai nhóm có tổng Tỷ Lệ gần bằng nhau. B3 : Gán cho hai nhóm lần lượt những ký hiệu 0 và 1. B4 : Lặp lại B2 cho những nhóm con cho tới khi không hề liên tục được nữa. B5 : Từ mã ứng với mỗi tin là chuỗi gồm có những ký hiệu theo thứ tự lần lượt được gán cho những nhóm có chứa Phần Trăm tương ứng của tin. Ví dụ : Mã hóa nguồn S = { a1, a2, a3, a4, a5, a6, a7, a8 } với những Xác Suất lần lượt là 0.25 ; 0.125 ; 0.0625 ; 0.0625 ; 0.25 ; 0.125 ; 0.0625 ; 0.0625 Tin ai P. ( ai ) Lần 1 Lần 2 Lần 3 Lần 4 Từ mã a1 0.25 0 0 00 a2 0.25 0 1 01 a3 0.125 1 0 0 100 a4 0.125 1 0 1 101 a5 0.0625 1 1 0 0 1100 a6 0.0625 1 1 0 1 1101 a7 0.0625 1 1 1 0 1110 a8 0.0625 1 1 1 1 1111 Độ dài trung bình của từ mã : = 0.25 * 2 + 0.25 * 2 + 0.125 * 3 + 0.125 * 3 + 0.0625 * 4 + 0.0625 * 4 + 0.0625 * 4 + 0.0625 * 4 = 2.75 Entropie của nguồn tin : H ( s ) = – [ 0.25 * log20. 25 + 0.25 * log20. 25 + 0.125 * log20. 125 + 0.125 * log20. 125 + 0.0625 * log20. 0625 + 0.0625 * log20. 0625 + 0.0625 * log20. 0625 + 0.0625 * log20. 0625 ] = 2.75 Hiệu suất lập mã : h = H ( s ) = 2.752.75 = 1 Nhận xét : Hai giải pháp Shannon và Fano thực ra là một, đều kiến thiết xây dựng trên cùng một cơ sở độ dài từ mã tỉ lệ nghịch với Phần Trăm Open, không được cho phép lập mã một cách duy nhất vì sự chia nhóm trên cơ sở đồng đều và tổng Phần Trăm nên hoàn toàn có thể có nhiều cách chia. Sự lập mã theo cách chia nhóm trên cơ sở đồng Xác Suất tạo cho bộ mã có tính Prefix. Phương pháp mã hóa từng tin của nguồn tin chỉ có hiệu suất cao khi entropie của nguồn lớn hơn 1 ( H ( u ) > 1 ). Trường hợp H ( u ) < 1 thì giải pháp mã hóa từng tin riêng không liên quan gì đến nhau không đưa đến nâng cấp cải tiến tốt tính tối ưu của mã. Trong trường hợp này dùng giải pháp mã hóa từng khối tin. III > Phương pháp Huffman Các bước triển khai giải pháp Huffman : B1 : Khởi động một list những cây nhị phân một nút chứa những khối lượng p1, p2, , pn cho những tin a1, a2, , an. B2 : Thực hiện những bước sau n-1 lần : Tìm hai cây T ’ và T ’ ’ trong list với những nút gốc có khối lượng tối thiểu p ’ và p ’ ’. Thay thế hai cây này bằng cây nhị phân với nút gốc có khối lượng p ’ + p ’ ’ và có những cây con là T ’ và T ”. p ’ + p ’ ’ Đánh dấu những mũi tên chỉ đến những cây con 0 và 1 T ’ ’ T ’ B3 : Mã số của tin ai là dãy những bit được lưu lại trên đường từ gốc của cây nhị phân ở đầu cuối tới nút ai. Ví dụ : Xét những ký tự A, B, C, D có những Tỷ Lệ Open tương ứng là 0.25, 0.125, 0.125, 0.5. B1 : 0.25 0.5 0.125 0.125 B C A D 1 B2 : 0.5 0.25 0.5 0.25 0.125 0.125 B C A D B3 : Ký tự A B C D Mã tương ứng 01 000 001 1 ni 2 3 3 1 Nhận xét : Ưu điểm Xử lý khá tốt độ dư thừa phân bổ kí tự. Quá trình mã hóa và giải thuật tương đối đơn thuần. Cho mã có độ dài tối ưu. Hạn chế Giải quyết kém hiệu suất cao so với những loại độ dư thừa khác ( ví dụ điển hình như độ dư thừa vị trí ). Tốn nhiều thời hạn thiết kế xây dựng cây mã. Cấu trúc của cây mã hoặc bộ từ mã đã dùng để mã hóa phải được gởi đi cùng với số liệu đã được mã hóa. Điều này làm giảm hiệu suất nén. IV > Ứng dụng Lưu trữ. Truyền dữ liệu. Dùng trong những chương trình nén như : compress, pack trong Unit và winzip, winrar trong Windowns .

Các file đính kèm theo tài liệu này :

  • docxma_thong_ke_toi_uu_5768.docx
Phương pháp mã hóa Shannon – Fano và phương pháp Huffman – Luận văn, đồ án, đề tài tốt nghiệp
Bài viết liên quan
Sửa máy giặt
Bài Mới Nhất
Hotline 24/7: O984.666.352
Alternate Text Gọi ngay