Trang 100
Bài 7 Mã hóa tối ưu
nguồn rời rạc không nhớ
7.1 Các định lý về giới hạn trên và dưới của chiều dài trung
bình
7.2 Mã hoá theo Shannon và Fano
7.3 Phương pháp mã hoá tối ưu theo Huffman
Trang 101
Các định lý về giới hạn trên và dưới của
chiều dài trung bình

Định lý 7.1

Cho nguồn tin X = {
a
1
, ...,
a
K
} với các xác suất tương ứng
p
1
,
...,
p
K
. Một bộ mã phân tách được bất kỳ cho nguồn này với cơ
số mã
m
, chiều dài trung bình từ mã sẽ thoả (trong đó
H

m
pmlpppmlXH
i
111
lnlnlnln)(
01111
11
=−≤−
⎟
⎠
⎞
⎜
⎝
⎛
=
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−≤
∑∑
=
−
=
−
K

, có thể xây dựng một mã prefix với cơ số m sao cho

Chứng minh

Chọn chiều dài l
i
của từ mã cho tin a
i
theo qui tắc

Chúng ta có
( )
1
log
X
+<
m
H
l
1=
−
i
l
p
m
i
i
l
i
mp

−
loglog
Trang 103
Chứng minh định lý (tt)

Vì các chiều dài được chọn này thoã bất đẳng thức Kraft nên
tồn tại một mã prefix tương ứng có các chiều dài này.

Tiếp tục chúng ta có

Điều này hoàn tất chứng minh của chúng ta.
⎡⎤
1loglog +−<⇒−=
ii
p
mi
p
mi
ll
∑∑∑
===
+−<
K
i
i
K
i
p
mi
K

K
i
ii
Trang 104
Hệ quả

Có thể mã hoá một nguồn mà có chiều dài trung bình tiếp cận
đến
với sai số nhỏ tuỳ ý.

Chúng ta thực hiện điều này bằng cách mã hoá các dãy N tin
của nguồn X = {a
1
, ..., a
K
} theo Định lý 7.2.

Lúc này chúng ta có nguồn mới với kích thước là K
N
, mỗi phần
tử là một dãy của N tin được lấy độc lập từ nguồn X.

Entropy của nguồn mới này là NH(X) và chiều dài trung bình
các từ mã của nó theo định nghĩa sẽ là N lần chiều dài trung
bình các từ mã của nguồn ban đầu, .

Áp dụng Định lý 7.1 và Định lý 7.2 đối với nguồn mới chúng ta
có
( )
m

NH
( ) ( )
Nm
H
l
m
H 1
log
X
log
X
+<≤
⇒
l
( )
l
H
h
X
=
Trang 106
Mã hóa tối ưu

Là phép mã hóa mà kết quả là một bộ mã có chiều dài trung
bình là nhỏ nhất trong tất cả các phép mã hóa có thể có cho
nguồn.

Bộ mã của phép mã hóa tối ưu cho nguồn được gọi là bộ mã tối
ưu.


i
, trong đó l
i
=
∑
−
=
1
1
i
j
j
p
⎥
⎥
⎤
⎢
⎢
⎡
−
i
p
2
log
Trang 108
Ví dụ

Hãy mã hoá nguồn S = {a
1
, a

i
Xác suất
p
i
Biểu diễn
nhị phân
Từ mã
w
i
a
1
0,3 0 0,00 2 00
a
2
0,25 0,3 0,01001... 2 01
a
3
0,2 0,55 0,10001... 3 100
a
4
0,12 0,75 0,11000... 4 1100
a
5
0,08 0,87 0,11011... 4 1101
a
6
0,05 0,95 0,111100... 5 11110
l
Trang 109
Nhận xét - Bài tập

= {a
1
, a
2
, a
3
, a
4
, a
5
, a
6
, a
7
, a
8
} với các xác suất lần lượt là
0,21; 0,18; 0,15; 0,14; 0,12; 0,01; 0,06 ; 0,04.

S
3
= {a
1
, a
2
, a
3
, a
4
, a