Chương 2
MÃ HÓA NGUỒN
Nội dung:
2.1 Mô hình toán học của nguồn tin
2.2 Đo lượng tin của nguồn tin
2.3 Các kỹ thuật mã hóa nguồn rời rạc
2.4 Các kỹ thuật mã hóa nguồn tương tự
2.5.Lấy mẫu và điều chế xung
2.6 Điều chế xung mã
Bài tập
1

1
Chương 2 MÃ HÓA NGUỒN
2.1 Mô hình toán học của nguồn tin:

Nguồn tin: Nguồn tương tự: tín hiệu ngõ ra có dạng liên tục
Nguồn rời rạc: tín hiệu ngõ ra có dạng rời rạc

Nguồn tin tạo ra các bản tin một cách ngẫu nhiên. Với nguồn rời rạc (Discrete
source), ngõ ra là chuỗi các biến ngẫu nhiên rời rạc.

Mô hình cho nguồn rời rạc:
Giả sử nguồn rời rạc gồm L ký hiệu :{x
1
, x
2
,…, x
L
}, với xác suất tương ứng là
{p

2.2 Đo lượng tin của nguồn tin:


Tin tức liên quan đến sự ngạc nhiên mà chúng ta cảm nhận khi nhận được bản
tin. Bản tin ít có khả năng xảy ra sẽ mang nhiều tin tức hơn. Từ đó, người ta đưa ra
khái niệm lượng tin.

Lượng tin:

'()*+,-()./*01*.

 .123!.

#
•
Đơn vị của lượng tin: Tùy vào cơ số hàm logarit (cơ số 2: đơn vị là bit, cơ số
e: đơn vị là nat, cơ số 10: Hartley)
•
Tính chất: i/
ii/
3

3
1
( ) log log ( )
( )
i i
i
I x P x
P x

Nhận xét: i/ Khi X, Y độc lập thống kê: I(x
i
,y
j
) = 0
ii/ I(x
i
,y
j
) = I(y
j
,x
i
)  lượng tin về sự kiện X = x
i
có được từ việc
xảy ra sự kiện Y = y
j
giống với lượng tin về sự kiện Y = y
j
có được
từ việc xảy ra sự kiện X = x
i
.
4

4
( | ) log ( | )
i j i j
I x y P x y= −

Lượng tin tương hỗ trung bình:
5

5
1
( ) ( )log ( )
L
i i
i
I X P x P x
=
= −
∑
1 1
( , ) ( , ) ( , )
L K
i j i j
i j
I X Y P x y I x y
= =
=
∑∑
1 2 1 2
( ) log [ ( )] log (0.01) 6.5 [ / ]I x p x bits symbol= − = − =
2 2
( ) 0.99log (0.99) 0.01log (0.01) 0.081 [ / ]I X bits symbol= − − =
Chương 2 MÃ HÓA NGUỒN
2.2 Đo lượng tin của nguồn tin (tt):
L=M;(&N=-,
F6'5&

2(1 )
2
(0,0) log [ ]. (1,0) log [ ]
1 1
P y X p
P Y P y X P X P y X P X
p p p p
p
p
I bits I bits
p p p p
= = = −
= = = = = + = = =
= − + = − +
−
⇒ = =
− + − +
N(I*3

Channel











L
i
i
P x i L H X L
L L L
=
= = ⇒ = − =
∑
1 1
( ) ( )log ( ) ( ) ( )
L L
i i i i
i i
H X P x P x P x I x
= =
= − =
∑ ∑
( ) 0H X ≥
Chương 2 MÃ HÓA NGUỒN
!" #)*

Entropy đồng thời:

Entropy có điều kiện:

Công thức liên hệ:
8

8
1 1

= −
= + −
+)*
+)*
,)-*
+)-*
Chương 2 MÃ HÓA NGUỒN
2.2 Đo lượng tin của nguồn tin (tt):
L=F6,
.5/*./*-*5
-()M*1(01&
NS #FS 6T#FS F6#U0*V
Lời giải:
&N,
H
C2

9

9
1 1 2
( 0) ( 0, 0) ( 0, 1)
3 3 3
P X P X Y P X Y= = = = + = = = + =
Y \ X 0 1
0 1/3 0
1 1/3 1/3
2
2 2 2
1

2
2
2
2
( , ) ( , )log ( , )
( 0, 0)log ( 0, 0)
( 0, 1)log ( 0, 1)
( 1, 0)log ( 1, 0)
( 1, 1)log ( 1, 1)
1 1
3 log 1.585 [ ]
3 3
i j i j
i j
H X Y P x y x y
P X Y P X Y
P X Y P X Y
P X Y P X Y
P X Y P X Y
bits
= =
= −
= − = = = =
− = = = =
− = = = =
− = = = =
= − × =
∑∑
Chương 2 MÃ HÓA NGUỒN
.!" #/0

−∞
= −
∫
2 2 2
0
1 1
( ) ( )log ( ) log log
a
H X p x p x dx dx a
a a
∞
−∞
= − = − =
∫ ∫
Chương 2 MÃ HÓA NGUỒN
2.3 Các phương pháp mã hóa nguồn rời rạc (Nén dữ liệu)

Giả sử nguồn rời rạc X gồm L ký hiệu {x
1
, x
2
,…, x
L
}, với xác suất xuất hiện các ký
hiệu tương ứng là {p
1
,p
2
,…,p
L

H(X): entropy của nguồn X.
: chiều dài trung bình của từ mã.
12

12
( )H X
R
η
=
Nguồn rời
rạc X
{x
i
}
{b
i
}: 0/1
Mã hóa
nguồn
1
0
L
i i
i
R p R
−
=
=
∑
R

2
log , 2 ,
log 1 ,
m
L L m
R
L otherwise

= ∈

=

+
 

 

¥
2 2
2
log log
1 100%
log
L L
R L
η
= = = ↔
Chương 2 MÃ HÓA NGUỒN
.1%2 %3 45%6789456%:;<=%)*
o

14

14
2 2
2
log log
1
log 1
L L
R L
η
= = <
+
 
 
2
log 1N J L= +
 
 
2
2
log
( ) ( )
log 1
J L
H X JH X
R N J L
η
= = =
+

( )
94.91%
7
L
H X
R R
η
= = = =
2 2
2
log 3log 100
99.66%
log 1 20
J L
J L
η
= = =
+
 
 
2 2
log 1 log 100 1 7R L= + = + =
   
   
2 2
log 1 3log 100 1 20R J L= + = + =
   
   
Chương 2 MÃ HÓA NGUỒN
.1%2 %3 45%6789456%:;%#>?)@A/;

1/8
1/8
1
00
01
10
0
10
110
111
Chương 2 MÃ HÓA NGUỒN
)*

E%D"& 45""%""%


D

%

D

%
""%""%


D

_


Ví dụ: Ni8%{1,00,01,10}:M,*`f.
Ni8%{0,10,110,111}:,*`f.
17

17
1
2 1
k
L
R
k
−
=
≤
∑
Chương 2 MÃ HÓA NGUỒN
.1%2 %3 45%6789456%:;%#>?)*
1%2 %3 45%6F%"G"

H3<8%I%J

K*+5*`=*<*3.5/*1j

L5',==*k.5/*@X,'j
0]/*&W,-j'"F,'%&

N=X,''*,g,.5/*j0]
/*&l5*;<*m*=-mno>**;m**p&

BAC,^H.5/*./*(

Ký hiệu
u
i
Xác suất
p
i
L n ầ
chia 1
L n ầ
chia 2
L n ầ
chia 3
L n ầ
chia 4
L n ầ
chia 5
Töø maõ
u
1
0.34
u
2
0.23
u
3
0.19
u
4
0.10
u

L n ầ
chia 5
Töø maõ
u
1
0.34 0
u
2
0.23 0
u
3
0.19 1
u
4
0.10 1
u
5
0.07 1
u
6
0.06 1
u
7
0.01 1
Chương 2 MÃ HÓA NGUỒN
1%2 %3 45%6F%"G")*
Lời giải:
& <K%L
21


u
5
0.07 1 1
u
6
0.06 1 1
u
7
0.01 1 1
Chương 2 MÃ HÓA NGUỒN
1%2 %3 45%6F%"G")*
Lời giải:
& <K%L
22
Ký hiệu
u
i
Xác suất
p
i
L n ầ
chia 1
L n ầ
chia 2
L n ầ
chia 3
L n ầ
chia 4
L n ầ
chia 5

Xác suất
p
i
L n ầ
chia 1
L n ầ
chia 2
L n ầ
chia 3
L n ầ
chia 4
L n ầ
chia 5
Töø maõ
u
1
0.34 0 0
u
2
0.23 0 1
u
3
0.19 1 0
u
4
0.10 1 1 0
u
5
0.07 1 1 1 0
u

1
0.34 0 0
u
2
0.23 0 1
u
3
0.19 1 0
u
4
0.10 1 1 0
u
5
0.07 1 1 1 0
u
6
0.06 1 1 1 1 0
u
7
0.01 1 1 1 1 1
Chương 2 MÃ HÓA NGUỒN
1%2 %3 45%6F%"G")*
Lời giải:
& <K%L
25

25
Ký hiệu
u
i

6
0.06 1 1 1 1 0 11110
u
7
0.01 1 1 1 1 1 11111