Cơ sở Lý thuyết Truyền tin-2004
Hà Quốc Trung
1
1
Khoa Công nghệ thông tin
Đại học Bách khoa Hà nội
Chương 5: Mã hóa nguồn 0.
1/ 64
Chương 5: Mã hóa nguồn
1
Mã hóa nguồn rời rạc không nhớ
2
Mã hóa cho nguồn dừng rời rạc
3
Cơ sở lý thuyết mã hóa nguồn liên tục
4
Các kỹ thuật mã hóa nguồn liên tục
Chương 5: Mã hóa nguồn 0.
2/ 64
Khái niệm chung
Là phép biến đổi đầu tiên cho nguồn tin nguyên thủy
Đầu vào của phép biến đổi này có thể là: nguồn tin rời rạc
hoặc nguồn tin liên tục
Trong cả hai trường hợp mục đích chính của phép mã hóa
nguồn là biểu diễn thông tin với tài nguyên tối thiểu
Các vấn đề cần nghiên cứu
Mã hóa nguồn rời rạc
Mã hóa nguồn liên tục
Nén dữ liệu
Chương 5: Mã hóa nguồn 1. Một số khái niệm chung
3/ 64

Cơ sở lý thuyết mã hóa nguồn liên tục
4
Các kỹ thuật mã hóa nguồn liên tục
Chương 5: Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ
5/ 64
Mô hình toán học nguồn rời rạc
Với nguồn rời rạc cần quan tâm
Entropy của nguồn tin nguyên thủy
Entropy của nguồn sau khi mã hóa
Hiệu quả của phép mã hóa
Giới hạn của hiệu quả mã hóa
Xét một nguồn rời rạc không nhớ, sau một thời gian t
s
tạo ra
ký hiệu x
i
trong L ký hiệu với các xác suất xuất hiện là P(i)
Để cho đơn giản, chỉ xét trường hợp mã hiệu nhị phân. Khi
đó: lượng tin=lượng bít= số ký hiệu nhị phân
Với mã hiệu có cơ số lớn hơn 2, có thể mở rộng các kết quả
thu được.
Chương 5: Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ
6/ 64
2.2.Mã hóa với từ mã có độ dài cố định
Nguyên tắc: Mã hóa một ký hiệu nguồn thành một chuỗi ký
hiệu mã có độ dài xác định R
Để đảm bảo phép mã hóa là 1-1, một ký hiệu nguồn tương
ứng với 1 chuỗi ký hiệu nhị phân. Số lượng chuỗi nhị phân
phải lớn hơn số ký hiệu nguồn
2

H(X) + 1
Để tăng hiệu quả, cần tăng lượng tin cho mỗi lần mã hóa:
mã hóa cùng một lúc J ký hiệu. Hiệu quả mã hóa
JH(X)
JH(X) + 1
≥
JH(X)
JH(X) + 1
Biểu thức trên tiến tới 1 khi J tiến tới vô cùng
Kết quả này chỉ đúng cho nguồn đẳng xác suất.
Phép mã hóa không có sai số, mỗi chuỗi ký hiệu nguồn
luôn luôn tương ứng với 1 từ mã duy nhất.
Chương 5: Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ
8/ 64
Tăng hiệu quả bằng mã hóa có sai số
Trong trường hợp nguồn không đẳng xác suất, để có thể
tiệm cận với hiệu quả tối đa (1), cần chấp nhận một sai số
nào đó
Xét L
J
chuỗi ký hiệu nguồn có độ dài J, mã hóa bằng chuỗi
các ký hiệu nhị phân có độ dài R, 2
R
< L
J
Như vậy còn L
J
− 2
R
tổ hợp ký hiệu nguồn không có từ mã

thì sai số sẽ tiến tới 1 khi J tiến tới vô hạn
Tốc độ lập tin của đầu ra luôn luôn lớn hơn của đầu vào
Chương 5: Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ
10/ 64
Chứng minh định lý
Chứng minh.
Phần thuận
Coi tập hợp các chuỗi ký hiệu nguồn mà
|
I(u
J
)
J
− H(U)| ≥ 
là các chuỗi ký hiệu nguồn ánh xạ vào cùng một từ mã.
Cần chứng minh
1
Xác suất xuất hiện của các từ mã nói trên có thể bé tùy ý
khi L lớn tùy ý (hiển nhiên, lim
J→∞
I(u
J
)
J
= H(U) )
2
Các chuỗi ký hiệu còn lại có thể được mã hóa chính xác
(1-1) với R =
N
J

≥ H(X) + 
Phần đảo: Chứng minh xác suất sai số tiến đến 1 (?)
Chương 5: Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ
11/ 64
Chứng minh định lý
Chứng minh.
Phần thuận
Coi tập hợp các chuỗi ký hiệu nguồn mà
|
I(u
J
)
J
− H(U)| ≥ 
là các chuỗi ký hiệu nguồn ánh xạ vào cùng một từ mã.
Cần chứng minh
1
Xác suất xuất hiện của các từ mã nói trên có thể bé tùy ý
khi L lớn tùy ý (hiển nhiên, lim
J→∞
I(u
J
)
J
= H(U) )
2
Các chuỗi ký hiệu còn lại có thể được mã hóa chính xác
(1-1) với R =
N
J

≥ H(X) + 
Phần đảo: Chứng minh xác suất sai số tiến đến 1 (?)
Chương 5: Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ
11/ 64
Chứng minh định lý
Chứng minh.
Phần thuận
Coi tập hợp các chuỗi ký hiệu nguồn mà
|
I(u
J
)
J
− H(U)| ≥ 
là các chuỗi ký hiệu nguồn ánh xạ vào cùng một từ mã.
Cần chứng minh
1
Xác suất xuất hiện của các từ mã nói trên có thể bé tùy ý
khi L lớn tùy ý (hiển nhiên, lim
J→∞
I(u
J
)
J
= H(U) )
2
Các chuỗi ký hiệu còn lại có thể được mã hóa chính xác
(1-1) với R =
N
J

)) ≥ M
T
2
−J(H(U)+)
Có
M
T
≤ 2
J(H(U)+)
Vậy nếu chọn chuỗi nhị phân có độ dài tối thiểu là
N
m
in = log
2
2
J(H(U)+)
= J(H(U) + )
sẽ có ánh xạ 1-1 giữa T và tập các từ mã N ký hiệu nhị
phân Phép ánh xạ chung sẽ có sai số nhỏ tùy ý
P
e
= |
I(u
J
)
J
− H(U)| ≥ 
Chương 5: Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ
12/ 64
Chứng minh phần đảo

Ý nghĩa định lý
Phép mã hóa với từ mã có độ dài không đổi nói chung bảo
toàn độ bất định của nguồn
H(U) là số ký hiệu nhị phân nhỏ nhất có thể sử dụng để
biểu diễn nguồn tin nguyên thủy một cách chính xác
Trong trường hợp tổng quát, số ký hiệu nhỏ nhất đó có thể
đạt được khi mã hóa một khối có chiều dài vô tận các ký
hiệu nguồn
Định lý có thể mở rộng cho mã hiệu cơ số lớn hơn 2.
Chương 5: Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ
14/ 64
2.3.Mã hóa với từ mã có độ dài thay đổi
Mục tiêu: mã hóa ký hiệu với số lượng ký hiệu nhị phân tối
thiểu
Xét truờng hợp nguồn có phân bố xác suất không đều
Các ký hiệu nguồn có xác suất xuất hiện lớn cần được mã
hóa với các từ mã có độ dài nhỏ và ngược lại. Số ký hiệu
trung bình cho mỗi ký hiệu của nguồn:
R =
L

1
n
k
P(u
k
)
sẽ có giá trị tối ưu
Mã hiệu sử dụng trong trường hợp này cần có tính prefix
(giải mã được) được thể hiện bằng bất đẳng thức Kraft

. Đường dẫn tới nút đó lấy làm từ mã.
Toàn bộ cây con trên nút đó coi là đã sử dụng (gồm 2
n−n
1
nút cuối)
Tiếp tục chọn một nút ở mức n
2
. Loại bỏ toàn bộ cây con
của nút đó (gồm 2
n−n
1
nút cuối).
Nếu vẫn còn nút cuối chưa sử dụng, còn có thể chọn được
một nút ở mức bất kỳ
Khi chọn nút n
j
số lượng các nút đã sử dụng là
L

k=1
2
n−n
k
= 2
n
L

k=1
2
−n

n
hay
L

k=1
2
−n
k
≤ 1
Chương 5: Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ
18/ 64
Định lý mã hóa nguồn 2
Theorem
Cho X là một nguồn rời rạc không nhớ. Có thể mã hóa nguồn X
bằng một mã hiệu nhị phân không đều, có tính prefix và có độ
dài trung bình R của các từ mã thỏa mãn điều kiện
H(X) ≤ R < H(X) + 1
Chương 5: Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ
19/ 64
Chứng minh cận dưới
Có
H(X) − R =
L

k=1
p
k
log
2
1

p
k
(
2
−n
k
p
k
−1)(log
2
e)(
L

k=1
2
−n
k
−1) ≤ 0
Dấu bằng xảy ra khi p
k
= 2
−n
k
∀1 ≤ k ≤ L
Chương 5: Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ
20/ 64
Chứng minh cận trên
Cần tìm một mã hiệu sao cho R < H(X) + 1
Chọn n
k

(1 − log
2
p
k
) = 1 + H(X)
Chương 5: Mã hóa nguồn 2. Mã hóa nguồn rời rạc không nhớ
21/ 64