Bài giảng: Hệ thống viễn thơng 2
Trường Đại học Giao Thơng Vận Tải Tp.HCM
1.2 TRUYỀN TIN TRÊN KÊNH RỜI RẠC
1.2.1
L
ượ
ng tin t
ươ
ng h
ỗ
Xét h
ệ
th
ố
ng truy
ề
n tin nh
ư
trong hình bên. M
ộ
t ngu
ồ
n r
ờ
i r
ạ
c ch
ọ
n các ký t
ự
t
ừ
b
ả
ng ch
ữ
các X
để
truy
ề
n qua kênh. Lý t
ưở
ng, kênh truy
ề
n ph
ả
i tái t
ạ
o t
ạ
i
đ
íchký t
ự
đượ
c phát t
ạ
i
nguồn. Tuy nhiên, nhiễu và các suy hao truyền khác làm khác đi ký tự nguồn và kết quả là
thu
đượ
c b
ả
ng ký t
ự
Y t
ạ
i
đ
ích. Ta mu
ố
n
đ
o l
ượ
ng tin truy
ề
n
đ
i trong tr
ườ
ng h
ợ
p này.
Nhiều loại xác suất ký tự khác nhau được sử dụng liên quan đến hai nguồn trên, một số
đượ
c
đị
nh ngh
ĩ
a nh
ư
sau:
P(x
i
) là xác su
ấ
t mà ngu
ồ
n ch
ọ
n ký t
ự
truy
ề
n x
i
P(y
i
) là xác su
ấ
t ký t
ự
y
i
đượ
c nh
ậ
n t
ạ
i
đ
ích.
P(x
i
y
i
) là xác suất để x
i
được phát và y
i
được nhận.
P(x
i
/y
i
) là xác suất có điều kiện khi truyền đi x
i
và nhận được y
i
P(y
i
/x
i
) là xác su
ấ
t có
đ
i
ề
u ki
ệ
n khi y
i
đượ
c nh
ậ
n và ký t
ự
truy
ề
n
đ
i là x
i
.
L
ượ
ng tin t
ươ
ng h
ỗ
đượ
c
đị
nh ngh
ĩ
a nh
ư
sau:
)(
)|(
log);(
i
ji
ji
xP
yxP
yxI
=
bit
L
ượ
ng tin t
ươ
ng h
ỗ
th
ể
hi
ệ
n l
ượ
ng tin truy
ề
n
đ
i khi phát x
i
và thu
đượ
c y
i
.
Ngồi ra, ng
ườ
i ta còn
đị
nh ngh
ĩ
a l
ượ
ng tin t
ươ
ng h
ỗ
trung bình.
Đạ
i l
ượ
ng này
đặ
c tr
ư
ng
cho lương tin nguồn trung bình đạt được trên mỗi ký tự được nhận.
∑
=
ji
jiji
yxIyxPYXI
,
);()();
(
Qua m
ộ
t vài phép bi
ế
n
đổ
i ta
đượ
c:
)|()();(
YXHXHYXI
−=
Trong đó:
∑
=
ji
ji
ji
yxP
yxPYXH
,
)|(
1
log)()|(
Là lượng tin mất đi trên kênh nhiễu.
1.2.2
Dung l
ượ
ng kênh thơng tin r
ờ
i r
ạ
c
Dung l
ượ
ng kênh
đượ
c
đị
nh ngh
ĩ
a là l
ượ
ng tin c
ự
c
đạ
i
đượ
c truy
ề
n qua trên m
ỗ
i ký t
ự
kênh:
(bit/symbol)
);(max
)(
YXIC
i
xP
s
=
Ngồi ra, người ta còn đo dung lượng kênh theo tốc độ tin. Nếu gọi s là tốc độ ký tự tối đa
cho phép bởi kênh thì dung lượng trên mỗi đơn vị thời gian được tính như sau:
C = sC
s
(bit/sec)
Định lý cơ bản của Shannon đối với một kênh truyền có nhiễu được phát biểu như sau:
Nếu một kênh có dung lượng kênh C và một nguồn có tốc độ tin R ≤ C thì tồn tại một hệ
thống mã hố để ngõ ra của nguồn có thể được phát qua kênh với một tần số lỗi rất nhỏ.
Ngược lại, nếu R > C thì khơng thể truyền tin mà khơng có lỗi.
5
VIENTHONG05.TK
Bài giảng: Hệ thống viễn thơng 2
Trường Đại học Giao Thơng Vận Tải Tp.HCM
1.3 MÃ HỐ NGUỒN TIN
1.3.1
Mã hi
ệ
u
1) Mã hiệu và các thông số cơ bản của mã hiệu:
•
Cơ số của mã (m) là số các
ký hiệu khác nhau trong bảng
chữ của mã. Đối với
mã nhò phân m= 2.
•
Độ dài của mã n là số ký hiệu trong một từ mã. Nên độ dài các từ mã như nhau
ta gọi là mã đều, ngược lại là mã không đều.
• Độ dài trung bình của bộ mã:
∑
=
=
1
)(
i
ii
nxpn
(1)
+ p(x
i
): xác suất xuất hiện tin x
i
của nguồn X được mã hóa.
+ n
i
: độ dài từ mã tương ứng với tin x
i
.
+ N: Tổng số từ mã tương ứng
với tổng số các tin của x
i
•
Tổng hộp các tổ hợp mã có thể có được: N
0
=2
n
., nếu:
+ N<N
0
ta gọi là mã với.
+ N>N
0
ta gọi là mã đầy
2) Điều kiện thiết lập mã hiệu:
• Điều kiện chung cho các loại mã là quy luật đảm bảo sự phân tích các tổ hợp
mã.
• Điều kiện riêng cho các loại mã:
+ Đối với mã thống kê tối ưu: độ
dài trung bình tối thiểu của mã.
+ Đối với mã sửa sai: khả na
êng phát hiện và sửa sai cao.
3)
PHƯƠNG PHÁP BIỂU DIỄN MÃ.
a-
Các bảng mã:
Tin a
1
a
2
a
3
a
4
a
5
Từ mã
00
01
100
1010
1011
Mặt tạo độ mã:
∑
=
−
=
n
K
K
Ki
b
1
1
2
σ
(1)
σ
K
=0 hay 1;
K: số thứ tự của ký hiệu trong từ mã
b- Đồ hình mã:
6
VIENTHONG05.TK
Bài giảng: Hệ thống viễn thơng 2
Trường Đại học Giao Thơng Vận Tải Tp.HCM
Cây mã
0
1
1
0
1
2
0
3
0
1
0
1
a
1
(00)
a
2
(01)
a
3
(100)
a
4
(1010)
a
5
(1011)
1
2
3
4
0
0V1
0
1
0v1
Đồ hình kết cấu
0
c-
Hàm cấu trúc của mã:
2 Khi n
i
= 2
G(n
i
) = 1 Khi n
i
= 3
2 Khi n
i
= 4
4)
Điều kiện để mã phân tách được :
• Mã có tính Prêphic
-
Bất kỳ dãy các từ mã na
øo của bộ mã cũng không
được trùng với một dãy từ
mã khác của cùng bộ mã.
-
Mã có tính prêphic nếu bất kỳ tổ hợp mã
nào cũng không phải
là prêphic của
một tổ hợp nào khác cùng bộ mã.
Điều kiện để mã có tính prêphic:
∑
=
−
≤
n
j
j
jG
1
1)(2
•
Mã hệ thống có tính phêph
ic được xây dựng từ một
mã prêphic nào đó bằng
cách lấy một số tổ hợp của mã prêphic gố
c làm tổ hợp sơ đẳng và các tổ hợp
còn lại làm tổ hợp cuối. Ghép các tổ hợp sơ đẳng với nhau và nối một trong
các tổ hợp cuối vào thành tổ hợp mã mới gọi là mã hệ thống có tính prêphic.
•
Ví dụ: Lấy bộ mã prêphic 1,00,010,011
- Các tổ hợp sơ đẳng: 1,00,010
- Một tổ hợp cuối: 011
• Gọi :
-
n
1
, n
2,
…, n
i
là độ dài các
tổ hợp sơ đẳng
- λ
1
, λ
2
,…, λ
k
là độ dài các tổ hợp cuối
- Số có thể có được các dãy ghép bằng các tổ hợp sơ đẳng có độ dài n
j
bằng :
g(n
j
) = g(n
j
-n
1
) + g(n
j
-n
2
) + …+ g(n
j
-n
i
) (1)
Trong đó: n
j
≥ 1; g(0) = 1 ; g(n
j
< 0) = 0
• Nếu chỉ dùng một tổ hợp cuối λ, hàm cấu trúc mã sẽ là:
G(n
j
) = g(n
j
- λ) (2)
7
VIENTHONG05.TK
Bài giảng: Hệ thống viễn thơng 2
Trường Đại học Giao Thơng Vận Tải Tp.HCM
8
+ Từ (1) và (2) ta có công thức truy chứng tính G(n
j
)
G(n
j
) = G(n
j
-n
1
) + G(n
j
-n
2
) + …+ G(n
j
-n
i
) (3)
Trong đó: n
j
≥ λ+1; G(n
j
= λ) = 1; G(n
j
< λ) = 0
+ Từ (1) ta có: n
1
=1, n
2
=2, n
3
=3 và
λ
=3
⇒
g(n
j
) = g(n
j
-1) + g(n
j
-2) + g(n
j
-3)
g(n
j
=1) = g(0) + g(-1) + g(-2) = 1 → có 1 dãy 1
g(n
j
=2) = g(1) + g(0) + g(-1) = 2
→
có 2 dãy: 00 và 11
g(n
j
=3) = g(2) + g(1) + g(0) = 4
→
có 4 dãy: 111, 100, 001, 010
+ Từ (3) ta có:
G(n
j
) = G(n
j
-1) + G(n
j
-2) +G(n
j
-3)
Trong đó: n
j
=
λ
+1=4 ; G(n
j
=3) = 1 ; G(n
j
<3) = 0
G(4) = G(3) + G(2) + G(1) = 1
→
có 1dãy 1011
G(5) = G(4) + G(3) + G(2) = 2
→
có 2 dãy: 11011 và 00011
G(6) = G(5) + G(4) + G(3) = 4 → có 4 dãy: 111011, 100011, 001011, 010011
G(7) = G(6) + G(5) + G(4) = 7
+ Ta có thể tìm G(n
j
) từ công thức (2) :
G(n
j
) = g(n
j
-3)
G(4) = g(4-3) = g(1) = 1
G(5) = g(5-3) = g(2) = 2
G(6) = g(6-3) = g(3) = 4
•
Nếu dùng nhiều tổ hơ
ïp cuối để ghép
λ
1
,
λ
2
, …
λ
I
, cách ghép các dãy tổ hợp sơ
đẳng với một trong các tổ hợp cuối có nhiều cách.
G(n
j
) = g(n
j
-
λ
1
)
+
g(n
j
-
λ
2
) + ….+ g(n
j
-
λ
k
) (4)
-
Ví dụ
: Với bộ mã ở trên ta lấy
+ Hai tổ hợp sơ đẳng : 1, 00 ⇒ n
1
= 1, n
2
= 2
+ Hai tổ hợp cuối: 010, 011
⇒
λ
1
=
λ
2
= 3
+ Từ (1) ta tính được số có thể có được các dãy ghép bằng các tổ hợp sơ đẳng có độ
dài n
j
bằng:
g(n
j
) = g(n
j
–1) + g(nj-2)
Trong đó n
j
≥1, g(0) = 1, g (0) = 0
g(1) = g(0) + g(-1) = 1 ⇒ 1dãy :1
g(2) = g(1) + g(0) = 2 ⇒ 2 dãy :11 và 00
g(3) = g(2) + g(1) = 3 ⇒ 3 dãy :111, 100, 001
g(4) = g(3) + g(2) = 5 ⇒ 5dãy :1111, 0000, 1100, 0011, 1001
+ Từ (2) ta có:
VIENTHONG05.TK
Bài giảng: Hệ thống viễn thơng 2
Trường Đại học Giao Thơng Vận Tải Tp.HCM
G(n
j
) = 2g(n
j
-3) trong đó n
j
≥4; G(3) =1; G(<3) =0
G(4) = 2g(1) = 2x1 = 2 ⇒ 1010 và 1011
G(5) = 2g(2) = 2x2 = 4 ⇒ 11010, 00010, 11011, và 00011
G(6) = 2g(3) = 2x3 = 6 ⇒ 111010, 100010, 001010, 111011, 100011, và 001011
G(7) = 2g(4) = 2x5 = 10
1.3.2
Các lo
ạ
i mã th
ố
ng kê t
ố
i
ư
u (TKT
Ư
)
1) Một số đònh lý cơ bản của mã TKTƯ
•
Đònh lý giới hạn về độ dài
trung bình của từ mã:
n
H(U) ≤
n
≤ H(U) +1 (1)
⇒
mã thống kê có hai đặc điểm sau:
-
Các ký hiệu khác nhau của bo
ä chữ phải đồng xác suất.
- Xác suất xuất hiện các ký hiệu trong từ mã không phụ thuộc sự có mặt của các
ký hiệu ra trước.
•
Tiêu chuẩn mã kinh tế tối ưu:
−
=
n
UH
)(
ρ
(2) H(U): Entrôpi của nguồn
n
: độ dài trung bình của từ mã.
⇒ ρ càng tiến tới 1 tính kinh tế của mã càng cao.
•
Mã thống kê có tính prephic.
• (3) & (4)
)(2
i
n
up
i
≤
−
12
1
≤
∑
=
−
N
i
n
i
2)
Mã Thống kê tối ưu Sannon:
Các bước thực hiện mã
thống kê tối ưu Sannon:
Bước 1: Liệt kê các tin của nguồn U
i
và các xác suất p
i
tương ứng theo xác suất
giảm dần.
Bước 2: Ứng với mỗi hàng u
i
, p
i
ghi một số P
i
theo biểu thức:
P
i
= p
1
+ p
2
+….+ p
i-1
Bước 3: Đổi các số thập phân P
i
thành các số nhò phân
Bước 4: Tính độ dài từ mã:
(2)
ii
n
i
n
up
−−
≤≤
1
2)(2
Bước 5: Từ mã (n
i
, b
i
) sẽ là n
i
ký hiệu nhò phân (kể từ số lẻ trở đi) của số nhò
phân P
i
Ví dụ: lập mã cho nguồn U có sơ đồ thống kê:
U
i
U
i
U
2
U
3
U
4
U
5
U
6
U
7
p
i
0,34 0,23 0,19 0,1 0,07 0,06 0,01
9
VIENTHONG05.TK
Bài giảng: Hệ thống viễn thơng 2
Trường Đại học Giao Thơng Vận Tải Tp.HCM
U
i
p
i
P
i
Số nhò phân P
i
n
i
Từ mã
U
i
0,34
0
0,0000
2
00
U
2
0,23
0,34
0,0101
3
010
U
3
0,19
0,57
0,1001
3
100
U
4
0,1
0,76
0,1100
4
1100
U
5
0,07 0,86 0,11011 4 1101
U
6
0,06 0,93 0,11101 5 11101
U
7
0,01
0,99
0,111
1110
7
1111110
+ P
i
được tính theo bước 2: i = 1
→
P
1
= p
0
= 0
i = 2→ P
2
= p
1
= 0,34
i =3→ P
3
= p
1
+ p
2
= 0,57
+ Đổi P
i
sang số nhò phân:
P
i
= 0,34
x 2
0,68
→
0
x 2
1,36 → 1
- 1
0,36
x 2
0,72 → 0
x 2
1,44 → 1
Khi đó P
i
= 0,34
→
0,0101
P
i
= 0,86
x 2
1,72
→
1
- 1
0,72
x 2
1,44
→
1
- 1
0,44
x 2
0,88
→
0
x 2
1,76
→
1
- 1
0,76
x 2
1,52
→
1
Khi đó P
i
= 0,86 → 0,11011
+ Tính n
i
theo (2)
n
i
= 1
⇒
2
-1
= 0,5 > p
i
=0,34
⇒
bò loại
n
i
= 2 ⇒ 2
-2
= 0,25 < p
i
=0,34 < 3
1-2
=0,5
⇒ thỏa mãn ⇒ vậy ta lấy n
i
= 2 suy ra từ
mã: 00
n
i
= 3 ⇒ 2
-3
= 0,125 < p
i
=0,23 <0,25 ⇒ lấy n
i
=3 ⇒ 010
• Tính kinh tế của mã:
[]
37,201,0log01,0 34,0log34,0log)(
222
7
1
≈++−=−=
∑
=
i
i
i
ppUH
10
VIENTHONG05.TK
Bài giảng: Hệ thống viễn thơng 2
Trường Đại học Giao Thơng Vận Tải Tp.HCM
()()()
∑
=
=+++==
7
1
99,2701,0 323,0234,0
i
ii
x
xxnpn
⇒ 81,0
99,2
37,2)(
===
n
UH
p
3)
Mã thống kê tối ưu Fano:
Các bước thực hiện mã hoá mã thống kê tối ưu Fano:
Bước 1: Liệt kê các tin n
i
trong một cột theo thứ tự p
i
giảm dần.
Bước 2: Chia làm 2 nhóm có tổng xác suất gần bằng nhau nhất. Ký hiệu mã dùng
cho nhóm đầu là 0, thì nhóm thứ 2 là 1.
Bước 3: Mỗi nhóm lại chia thành hai
nhóm nhỏ có xác su
ất gần bằng nhau nhất
(ký hiệu 0 và 1). Quá trì
nh cứ tiếp tục cho đến khi chỉ còn một ký hiệu thì kết
thúc.
U
i
p
i
1
2
3
4
5
Từ mã
U
1
0,34 0 0 00
U
2
0,23
0
1
01
U
3
0,19
1
0
10
U
4
0,1
1
1
0
110
U
5
0,07
1
1
1
0
1110
U
6
0,06
1
1
1
1
0
11110
U
7
0,01
1
1
1
1
1
11111
• Thực hiện bước 2:
-
Cách 1
:
p
1
+ p
2
= 0,34 + 0,23 = 0,57
p
3
+ p
4
+ p
5
+ p
6
+ p
7
= 0,43
Độ chênh lệch : 0,14
-
Cách 2:
p
1
+ p
2
+ P
3
= 0,76
p
4
+ p
5
+ p
6
+ p
7
=
0,24
Độ chênh lệch : 0,52
Vậy cách chia thứ nhất có xác suất ga
àn bằng nhau hơn cách
chia thứ hai, nên
ta chọn cách chia thứ nhất. Quá trình cứ thế tiếp diễn.
• Thực hiện bước 3:
- Cách 1:
p
3
= 0,19
p
4
+ p
5
+ p
6
+ p
7
= 0,24
Độ chênh lệch : -0,05
- Cách 2:
p
3
+ p
4
= 0,29
p
5
+ p
6
+ p
7
= -0,14
11
VIENTHONG05.TK
Bài giảng: Hệ thống viễn thơng 2
Trường Đại học Giao Thơng Vận Tải Tp.HCM
Độ chênh lệch : 0,15
Vậy ta chọn cách thứ nhất.
()()()(
()()()
41,2501,0506,0407,0
31,0219,0223,0234,0
7
1
=+++
+++==
∑
=
xxx
xxxxnpn
i
ii
)
p= 98,0
41,2
37,2)(
==
n
UH
⇒ có thể vẽ cây mã cho TKTƯ Fano.
• Nhận xét về mã thống kê tối ưu Fano:
Ưu
: Với cách chia nhóm đồng xác suất, sự lập mã TK tối ưu đồng thời cũng là mã
prêphic.
Khuyế
t:
Không cho phép lập mã duy nhất, ng
hóa là có nhiều mã tương đương về
tính kinh tế.
Ví dụ: đối với nguồn tin dưới đây ít nhất có hai cách chia có tính kinh tế như sau:
U
i
p
i
Cách chia
1
Từ mã Cách chia 2 Từ mã
U
1
0,19
0 0
0 0
0 0 0
0 0 0
U
2
0,19 0 1 0 0 1 0 0 0 1 0 0 1
U
3
0,19 0 1 1 0 1 1 0 1 0 1
U
4
0,19
1 0
1 0
1 0
1 0
U
5
0,08
1 1 0
1 1 0
1 1 0 0
1 1 0 0
U
6
0,08 1 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1
U
7
0,08 1 1 1 1 1 1 1 1 1 1 1 1 1 1
==
∑
=
7
1
1
i
ii
npn
(0,19x2) + (0,19x3) + (0,19x3) + (0
,19x2) + (0,08x3) + (0,08x4) +
(0,08x4) = 2,46
==
∑
=
7
1
2
i
ii
npn
(0,19x3) + (0,19x3) +
(0,19x2) + (0,19x2) + (0,08x4) + (0,08x4) +
(0,08x3) = 2,46
Cùng một bộ mã nên H(u
1
) = H(u
2
) suy ra
ρ
1
=
ρ
2.
• Để khắc phục nhược điểm của mã thống kê tối ưu Fano ta nghiên cứu mã
thống kê tối ưu Huffman.
12
VIENTHONG05.TK
Bài giảng: Hệ thống viễn thơng 2
Trường Đại học Giao Thơng Vận Tải Tp.HCM
0
0
0
0
0
0
1
1
1
1
1
u1
u2
u3 u4
u5
u6
u7
Cách chia 2
0
0
1
1
1
1
1
1
0
0
0
0
u1
u2 u3
u4
u5
u6
u7
0
0
0
0
0
0
1
1
1
1
1
1
u1
u2
u3
u5
u6 u7
u4
Cách chia 1
4) Mã TK tối ưu Huffman
:
Theo Hốpman để có một bộ mã Prephic có độ
dài từ mã tối thie
åu, điều kiện cần
và đủ là thỏa mãn 3 tính chất sau:
1-
Tính thứ tự độ dài các từ mã: p
i
≥
p
j
với i <j thì n
i
≤
n
j
.
2-
Tính những từ cuối: có độ dài bằng nhau,
chỉ khác nhau về trọng số của ký
hiệu cuối cùng.
3-
Tính liên hệ giữa những từ cuối và từ trước cuối.
•
Các bước thực hiện mã hóa TK tối ưu Hốpman.
Bước 1: Các nguồn tin được liệt kê trong
cột theo thứ tự xác suất xuất hiện giảm
dần.
Bước 2: Hai tin cuối có xác suất bé nhất được hợp thành tin phụ mới có xác suất
bằng tổng xác suất các tin hợp thành.
Bước 3: Các tin còn lại (N-2) với tin phụ mới được liệt kê trong cột phụ thứ nhất
theo thứ tự xác suất giảm dần.
Bước 4: Quá trình cứ thế tiếp tục cho đến khi hợp thành một tin phụ có xác suất
xuất hiện bằng 1.
13
VIENTHONG05.TK
Bài giảng: Hệ thống viễn thơng 2
Trường Đại học Giao Thơng Vận Tải Tp.HCM
•
Từ mã được đọc ngược từ đầu ra về đa
àu vào. Cũng có thể dùng
cây mã để xác
đònh mã Hốp nam:
0
0
0
1
1
10
0,42
1
0,42
0
0
1
1
0,14
0,07
u1(0,34)
u2(0,23)
u3(0,19)
u4(0,1)
u5(0,07)
u6(0,06)
u7(0,01)
gèc
•
Tính kinh tế:
ρ
= 0,98
Mặc dù tối ưu hơn so với mã Sannon và
Fano, nhưng khi bộ mã nguồn có nhiều tin
thì bộ mã trở nên cồng kềnh. Khi đó người ta kết hợp 2 phương pháp mã hóa: Mã
Hốp man + mã đều.
14
VIENTHONG05.TK
Không có nhận xét nào:
Đăng nhận xét