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.
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
1
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
III> Phương pháp Huffman………………………………………………..
7
IV> Ứng
dụng……………………………………………………………………. 9
2
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.
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ị .
3
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].
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 aiXác suất piqi= Biểu diễn
nhị phân
li=[-log2pi] Từ mã wi
a10.25 0 0.0000000 2 00
a50.25 0.25 0.0100000 2 01
a20.125 0.5 0.1000000 3 100
a60.125 0.625 0.1010000 3 101
a30.0625 0.75 0.1100000 4 1100
a40.0625 0.8125 0.1101000 4 1101
a70.0625 0.875 0.1110000 4 1110
a80.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
4
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.
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
Tin aiP(ai) Lần 1 Lần 2 Lần 3 Lần 4 Từ mã
a10.25 0 0 00
a20.25 0 1 01
a30.125 1 0 0 100
a40.125 1 0 1 101
5