Mô tả:
Bài thảo luận
Môn: Lý thuyết thông tin
Nhóm thảo luận:
1.
2.
3.
4.
5.
1
Câu hỏi thảo luận: Phương pháp mã hóa Shannon – Fano và
phương pháp Huffman.
Mục lục
I>
Mã thống kê tối ưu………………………………………………………
3
II> hương pháp mã hóa Shannon – Fano
1. Phương pháp Shannon……………………………………………
4
2. Phương pháp Fano………………………………………………….
5
2
III> Phương pháp Huffman………………………………………………..
7
IV> Ứng dụng…………………………………………………………………….
9
3
I>Mã thống kê tối ưu
- Là phép mã hóa mà kết quả là một bộ mã có chiều dai
trung bình là nhỏ nhất trong tất cả các phép mã hóa 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 chúng ta sẽ mã hóa với cơ số mã
m=2.
4
Ta xét phép mã hóa sau đối với các 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ổ hợp mã (từ mã) αIni
(αini là một tổ 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ổ hợp mã được xác định
bởi công thức:
=∑
ip(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ị
.
5
II> Phương pháp mã hóa Shannon – Fano
1. Phương pháp Shannon
Các bước thực hiện mã hóa theo phương pháp Shannon:
B1: Sắp xếp các xác suất 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=∑
với mọi i= 1,2,…,k.
B3: Đổi qi sang cơ số 2 (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].
6
Ví dụ: Mã hóa nguồn S={a1;a2;a3;a4;a5;a6;a7;a8} với các 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 qi=∑
pi
Biểu diễn
li=[-
Từ mã
nhị phân
log2pi]
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
7
Độ 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=
=
=1
2. Phương pháp Fano
Các bước thực hiện mã hóa theo phương pháp Fano:
B1: Sắp xếp các xác suất theo thứ tự giảm dần. Không mất tính
tổng quát giả sử P1>P2>…>Pk.
8
B2: Phân các xác suất thành hai nhóm có tổng xác suất gần bằng
nhau.
B3: Gán cho hai nhóm lần lượt các ký hiệu 0 và 1.
B4: Lặp lại B2 cho các nhóm con cho tới khi không thể tiếp tục
được nữa.
B5: Từ mã ứng với mỗi tin là chuỗi bao gồm các ký hiệu theo
thứ tự lần lượt được gán cho các nhóm có chứa xác suất tương
ứng của tin.
Ví dụ: Mã hóa nguồn S={a1,a2,a3,a4,a5,a6,a7,a8} với các 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
9
Tin ai
P(ai)
Lần 1
Lần 2
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ã:
10
Lần 3
Lần 4
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=
=
=1
Nhận xét:
11
- Hai phương pháp Shannon và Fano thực chất là một, đều
xây dựng trên cùng một cơ sở độ dài từ mã tỉ lệ nghịch với
xác suất xuất hiện, không 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 xác suất
nê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
quả khi entropie của nguồn lớn hơn 1 ( H(u) > 1). Trường
hợp H(u) < 1 thì phương pháp mã hóa từng tin riêng biệt
không đưa đến cải tiến tốt tính tối ưu của mã. Trong
trường hợp này dùng phương pháp mã hóa từng khối tin.
III> Phương pháp Huffman
12
Các bước thực hiện phương pháp Huffman:
B1: Khởi động một danh sách các cây nhị phân một nút chứa các
trọng lượng p1, p2, …, pn cho các tin a1, a2, …, an.
B2: Thực hiện các bước sau n-1 lần:
1) Tìm hai cây T’ và T’’ trong danh sách với các nút gốc có
trọng lượng tối thiểu p’ và p’’.
2) Thay thế hai cây này bằng cây nhị phân với nút gốc có
trọng lượng p’ + p’’ và có các cây con là T’ và T”.
Đánh dấu các mũi tên chỉ đến các cây con 0 và 1
p’+p’’
T’
T’’
13
B3: Mã số của tin ai là dãy các bit được đánh dấu trên đường từ
gốc của cây nhị phân cuối cùng tới nút ai.
Ví dụ: Xét các ký tự A, B, C, D có các xác suất xuất hiện tương
ứng là 0.25, 0.125, 0.125, 0.5.
B1:
0.125
B
0.125
0.5
0.25
C
A
D
1
B2:
14
0.5
0.25
0.125
0.125
B
0.5
0.25
C
A
D
C
D
B3:
Ký tự
A
B
15
Mã tương
01
000
001
1
2
3
3
1
ứng
ni
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 mã tương đối đơn giản.
- Cho mã có độ dài tối ưu.
Hạn chế
16
- Giải quyết kém hiệu quả đối với các loại độ dư thừa khác
(chẳng hạn như độ dư thừa vị trí).
- Tốn nhiều thời gian 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 các chương trình nén như: compress, pack
trong Unit và winzip, winrar trong Windowns.
17
- Xem thêm -