Bài giảng Truyền dẫn số: Chương 2

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

Bài giảng môn học

TRUYỀN DẪN SỐ

BM: TH & HT

KHOA: VT1

Giảng viên: Vũ Thị Thúy Hà

1 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

2 2/11/2017

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

 Mô hình cho nguồn 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.

Giả sử nguồn rời rạc gồm L ký hiệu :{x1, x2,…, xL}, với xác suất tương ứng là

{p1,p2,…,pL}. Lúc đó:

Ví dụ: Nguồn rời rạc nhị phân X sẽ gồm hai ký hiệu: {0,1} và P(X=0)+ P(X=1)=1.

 Nguồn rời rạc không nhớ DMS (Discrete Memoryless Source): phát ra chuỗi ký hiệu là độc lập thống kê, nghĩa là:

3 2/11/2017

Chương 2

MÃ HÓA NGUỒN

2.2 Đo lượng tin của nguồn tin:

2.2.1 Lượng tin của nguồn rời rạc:

 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:

 lượng tin riêng có được khi xuất hiện bản tin xi (xảy ra sự kiện X= xi )

• Đơ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)

ii/

• Tính chất: i/

4 2/11/2017

Chương 2

MÃ HÓA NGUỒN

2.2 Đo lượng tin của nguồn tin (tt):

 Lượng tin có điều kiện:

 Lượng tin tương hỗ:

 lượng tin có được khi sự kiện X = xi xảy ra sau khi quan sát sự kiện Y = yj đã xảy ra.

 lượng tin có được về sự kiện X =xi từ việc xảy ra sự kiện Y=yi.

 Nhận xét: i/ Khi X, Y độc lập thống kê: I(xi,yj) = 0

ii/ I(xi,yj) = I(yj,xi)  lượng tin về sự kiện X = xi có được từ việc xảy ra sự kiện Y = yj giống với lượng tin về sự kiện Y = yj có được từ việc xảy ra sự kiện X = xi.

5 2/11/2017

Chương 2

MÃ HÓA NGUỒN

2.2 Đo lượng tin của nguồn tin (tt):

 Lượng tin trung bình:

 Nhận xét: lượng tin trung bình phản ánh được giá trị tin tức của cả nguồn tin.

 lượng tin trung bình chứa trong một ký hiệu bất kỳ của nguồn

Lượng tin riêng của x1:

Ví dụ: Một nguồn DMS gồm 2 ký hiệu {x0,x1} với xác suất xuất hiện các ký hiệu tương ứng là 0.99 và 0.01.

Lượng tin trung bình của nguồn:

 Lượng tin tương hỗ trung bình:

6 2/11/2017

Chương 2

MÃ HÓA NGUỒN

2.2.2 Entropy của nguồn rời rạc:

 Nhận xét:

 Giả sử nguồn rời rạc X gồm L ký hiệu {x1, x2,…, xL}, Entropy của nguồn X được định nghĩa là:

• Entropy của nguồn chính là lượng tin trung bình của nguồn đó.

.Nếu các ký hiệu của nguồn có xác suất xuất hiện

• bằng nhau thì Entropy sẽ đạt giá trị cực đại.

. Dấu = xảy ra khi một ký hiệu có xác suất xuất hiện bằng 1,

• còn xác suất xuất hiện của các ký hiệu còn lại là 0.

7 2/11/2017

Chương 2

MÃ HÓA NGUỒN

2.2.3 Entropy của nguồn liên tục:

 Giả sử nguồn liên tục X(t) có hàm mật độ phân bố xác suất của hàm mẫu x(t) là p(x). Lúc đó, Entropy của nguồn X được định nghĩa là:

Ví dụ: Cho nguồn liên tục X có :

Tìm H(X) khi a=1; a=4.

Lời giải:

Entropy của nguồn:

Khi a= 1: H(X)=log21=0 [bits]

Khi a= 4: H(X)=log24=2 [bits]

8 2/11/2017

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 {x1, x2,…, xL}, với xác suất xuất hiện các ký hiệu tương ứng là {p1,p2,…,pL}. Mã hóa nguồn X chính là quá trình biểu diễn các ký hiệu xi của nguồn bởi các chuỗi bi có chiều dài Ri. (bi = [b1,b2,…,bRi], bi = 0/1)

{xi}

{bi}: 0/1

Nguồn rời rạc X Mã hóa nguồn

 Yêu cầu của bộ mã hóa nguồn:

• Các từ mã biểu diễn ở dạng nhị phân.

• Quá trình mã hóa sao cho việc giải mã là duy nhất.

 Đánh giá hiệu quả của bộ mã hóa nguồn:

• Thông qua việc so sánh số lượng bit trung bình dùng để biểu diễn từ mã.

H(X): entropy của nguồn X.

• Hiệu suất mã hóa:

: chiều dài trung bình của từ mã.

9 2/11/2017

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 (tt)

2.3.1 Phương pháp mã hóa với từ mã có chiều dài bằng nhau:

 Tất cả các ký hiệu của nguồn được mã hóa bằng các từ mã có chiều dài bằng nhau [từ mã R bit].

 Ví dụ: mã ASCII, mã EBCDIC, mã Baudot,vv…

 Quá trình mã hóa không tổn hao, và việc giải mã là dể dàng và duy nhất.

 Quá trình mã hóa:

• Chọn giá trị của R:

• Giả sử nguồn gồm L ký hiệu đồng xác suất. Ta muốn mã hóa dùng R bit ?

• Lúc đó, hiệu suất mã hóa:

o Khi L lũy thừa của 2:

10 2/11/2017

Chương 2

MÃ HÓA NGUỒN

2.3.1 Phương pháp mã hóa với từ mã có chiều dài bằng nhau (tt):

o Khi L không phải là lũy thừa của 2:

Khi L lớn thì log2L lớn hiệu suất cao. Ngược lại, khi L nhỏ, hiệu suất sẽ rất thấp  mã hóa từng khối J ký hiệu một lúc.

 Quá trình mã hóa J ký hiệu cùng một lúc:

• Chọn chiều dài từ mã mã hóa: N. Yêu cầu giá trị của N phải thỏa:

• Số ký hiệu có thể có của nguồn: LJ .

2N  LJ  N  log2LJ = Jlog2L

Do N phải là số nguyên, nên:

• Hiệu suất mã hóa:

 chọn J lớn thì hiệu suất sẽ cao (dù cho L nhỏ)

11 2/11/2017

Chương 2

MÃ HÓA NGUỒN

2.3.1 Phương pháp mã hóa với từ mã có chiều dài bằng nhau (tt)

Ví dụ: Cho nguồn DMS có 100 ký hiệu đồng xác suất.

a. Khi mỗi một ký hiệu được mã hóa tại một thời điểm. Tìm R=? =?

• Chiều dài của từ mã:

• Hiệu suất mã hóa:

 Mỗi ký hiệu được biểu diễn bằng từ mã có chiều dài 7 bit.

• Chiều dài của từ mã:

b. Khi 3 ký hiệu được mã hóa cùng một lúc. Tìm N=? =?

• Hiệu suất mã hóa:

Nhận xét: khi xác suất xuất hiện các ký hiệu không bằng nhau, hiệu suất sẽ thấp

hơn (do lúc đó H(X) < log2L)  dùng phương pháp mã hóa khác

12 2/11/2017

Chương 2

MÃ HÓA NGUỒN

 Các ký hiệu của nguồn được mã hóa bằng các từ mã có chiều dài thay đổi.

2.3.2 Phương pháp mã hóa với từ mã có chiều dài thay đổi (còn gọi là phương pháp mã hóa thống kê tối ưu hay mã hóa entropy)

 Các ký hiệu có xác suất xuất hiện lớn sẽ được mã hóa bằng từ mã có chiều dài nhỏ, và ngược lại. Kết quả là, chiều dài trung bình của từ mã sẽ nhỏ   cao.

 Ví dụ: mã Morse, mã Huffman, mã Shannon-Fano,vv…

 Vấn đề giải mã khi từ mã có chiều dài thay đổi:

Ví dụ: Nguồn DMS có 4 ký hiệu, được mã hóa theo bảng sau:

Tập mã 1

Tập mã 2

Ký hiệu ai

Xác suất pi

1/2 1/4 1/8 1/8

1 00 01 10

0 10 110 111

a1 a2 a3 a4

Giả sử chuỗi thu được: 001001…. Xác định ký hiệu đã mã hóa ?????

13 2/11/2017

Chương 2

MÃ HÓA NGUỒN

Ví dụ (tt):

 Theo tập mã 1: 00 1 00 1 a2a1a2a1

00 10 01 a2a4a3

quá trình giải mã là không duy nhất

giải mã duy nhất

 Theo tập mã 2: 0 0 10 0 1 a1a1a2a1

 Để giải mã duy nhất mã phân tách được mã có tính prefix mã phải thỏa bất đẳng thức Kraft:

 Mã có tính prefix: không có từ mã nào có chiều dài n giống với n bit đầu tiên của từ mã có chiều dài m (m>n).

Ví dụ: Tập mã 1: {1,00,01,10}: không có tính prefix

Tập mã 1: {0,10,110,111}: có tính prefix

14 2/11/2017

Chương 2

MÃ HÓA NGUỒN

2.3.2 Phương pháp mã hóa với từ mã có chiều dài thay đổi (tt)

a. Phương pháp mã hóa Shannon-Fano:

 Các bước thực hiện:

 Liệt kê các ký hiệu theo thứ tự xác suất giảm dần

bằng nhau nhất. Ký hiệu nhóm đầu là 0, nhóm sau là 1.

 Chia các ký hiệu làm hai nhóm sao cho tổng xác suất của mỗi nhóm là gần

 Trong mỗi nhóm lại lại chia thành hai nhóm nhỏ có xác suất gần bằng nhau nhất. Quá trình cứ tiếp tục cho đến khi chỉ còn một ký hiệu thì kết thúc.

 Ví dụ: Nguồn DMS có 7 ký hiệu với xác suất xuất hiện như sau:

ui u1 u2 u3 u5 u6 u7 u4

Hãy thực hiện quá trình mã hóa Fano và tính hiệu suất mã hóa?

0.34 0.23 0.19 0.07 0.06 0.01 0.1 pi

15 2/11/2017

Chương 2

MÃ HÓA NGUỒN

a. Phương pháp mã hóa Shannon-Fano (tt):

Lời giải:

Lập bảng như sau:

Töø maõ

Lần chia 1 Lần chia 2 Lần chia 3 Lần chia 4 Lần chia 5

Xác suất pi 0.34 Ký hiệu ui u1

0.23 u2

0.19

0.10

u3 u4

0.07 u5

0.06

0.01

u6 u7

16 2/11/2017

Chương 2

MÃ HÓA NGUỒN

a. Phương pháp mã hóa Shannon-Fano (tt):

Lời giải:

Lập bảng như sau:

Töø maõ

Lần chia 1 Lần chia 2 Lần chia 3 Lần chia 4 Lần chia 5

Xác suất pi 0.34

0

Ký hiệu ui u1

0.23 0 u2

0.19 1

0.10

1

u3 u4

0.07 1 u5

0.06 1

0.01

1

u6 u7

Nhóm 1: p = 0.57, nhóm 2: p = 0.43:  = |0.57-0.43 |= 0.14: nhỏ nhất

17 2/11/2017

Chương 2

MÃ HÓA NGUỒN

a. Phương pháp mã hóa Shannon-Fano (tt):

Lời giải:

Lập bảng như sau:

Töø maõ

Lần chia 1 Lần chia 2 Lần chia 3 Lần chia 4 Lần chia 5

Xác suất pi 0.34

0

Ký hiệu ui u1

0.23 0 1 u2

0.19 1 0

0.10

1

u3 u4

0.07 1 1 u5

0.06 1 1

0.01

1

u6 u7

18 2/11/2017

Chương 2

MÃ HÓA NGUỒN

a. Phương pháp mã hóa Shannon-Fano (tt):

Lời giải:

Lập bảng như sau:

Töø maõ

Lần chia 1 Lần chia 2 Lần chia 3 Lần chia 4 Lần chia 5

Xác suất pi 0.34

0

Ký hiệu ui u1

0.23 0 1 u2

0.19 1 0

0.10

1

0

u3 u4

0.07 1 1 1 u5

0.06 1 1 1

0.01

1

u6 u7

19 Chương 2

MÃ HÓA NGUỒN

a. Phương pháp mã hóa Shannon-Fano (tt):

Lời giải:

Lập bảng như sau:

Töø maõ

Lần chia 1 Lần chia 2 Lần chia 3 Lần chia 4 Lần chia 5

Xác suất pi 0.34

0

Ký hiệu ui u1

0.23 0 1 u2

0.19 1 0

0.10

1

0

u3 u4

0.07 1 1 1 0 u5

0.06 1 1 1 1

0.01

1

u6 u7

20 Chương 2

MÃ HÓA NGUỒN

a. Phương pháp mã hóa Shannon-Fano (tt):

Lời giải:

Lập bảng như sau:

Töø maõ

Lần chia 1 Lần chia 2 Lần chia 3 Lần chia 4 Lần chia 5

Xác suất pi 0.34

0

Ký hiệu ui u1

0.23 0 1 u2

0.19 1 0

0.10

1

0

u3 u4

0.07 1 1 1 0 u5

0.06 1 1 1 1 0

0.01

1

u6 u7

21 2/11/2017

Chương 2

MÃ HÓA NGUỒN

a. Phương pháp mã hóa Shannon-Fano (tt):

Lời giải:

Lập bảng như sau:

Töø maõ

Lần chia 1 Lần chia 2 Lần chia 3 Lần chia 4 Lần chia 5

Xác suất pi 0.34

0

00

Ký hiệu ui u1

0.23 0 1 01 u2

0.19 1 0 10

0.10

1

110

0

u3 u4

0.07 1 1 1110 1 0 u5

0.06 1 1 11110 1 1 0

0.01

1 11111

1

u6 u7

22 2/11/2017

Chương 2

MÃ HÓA NGUỒN

a. Phương pháp mã hóa Shannon-Fano (tt):

Lời giải (tt):

 Kết quả giải mã: u1: 00 u4: 110

u2: 01 u5: 1110

 Hiệu suất mã hóa:

u3: 10 u6: 11110 u7: 11111

• Entropy của nguồn:

= 2.38

= -[0.34log20.34 + 0.23log20.23 + …..+ 0.01log20.01]

• Chiều dài trung bình của từ mã:

• Hiệu suất:

= (0.34x2) + (0.23x2) + …. + (0.01x5) = 2.45

23 2/11/2017

Chương 2

MÃ HÓA NGUỒN

2.3.2 Phương pháp mã hóa với từ mã có chiều dài thay đổi (tt)

b. Phương pháp mã hóa Huffman:

 Các bước thực hiện:

 Liệt kê các ký hiệu theo thứ tự xác suất giảm dần

suất mới bằng tổng hai xác suất.

 Hai ký hiệu cuối có xác suất bé nhất được hợp thành ký hiệu mới có xác

 Các ký hiệu còn lại cùng với ký hiệu mới lại được liệt kê theo thứ tự xác

suất giảm dần.

xuất hiện bằng 1.

 Quá trình cứ tiếp tục cho đến khi hợp thành một ký hiệu mới có xác suất

 Ví dụ: Nguồn DMS có 7 ký hiệu với xác suất xuất hiện như sau:

0.34

0.23

0.19

0.07

0.06

0.01

0.1

ui u1 u2 u3 u5 u6 u7 u4

Hãy thực hiện quá trình mã hóa Huffman và tính hiệu suất mã hóa?

24 2/11/2017

Chương 2

MÃ HÓA NGUỒN

b. Phương pháp mã hóa Huffman:

Lời giải:

Quá trình được thực hiện như sau:

25 2/11/2017

Chương 2

MÃ HÓA NGUỒN

b. Phương pháp mã hóa Huffman (tt):

Lời giải (tt):

 Kết quả giải mã:

u1 00

u2 10

u3 11

u4 011

u5 0100

u6 01010

u7 01011

ui Tạo mã

 Hiệu suất mã hóa:

• Entropy của nguồn:

= 2.38

= - [0.34log20.34 + 0.23log20.23 + …..+ 0.01log20.01]

• Chiều dài trung bình của từ mã:

• Hiệu suất:

= (0.34x2) + (0.23x2) + …. + (0.01x5) = 2.45

26 2/11/2017

c. Mã hóa số học (Arithmetic Coding)

1

Arithmetic Coding là gì

2

Điểm khác biệt với mã Huffman

Các bước tiến hành mã hóa

3

. Ví dụ

4

2/11/2017

27 c. Mã hóa số học

Phương pháp mã hóa dữ liệu tạo ra mã có chiều dài thay đổi

Arithmetic Coding

Được sử dụng trong phương pháp Lossless data compression

2/11/2017

Ngày càng được sử dụng phổ biến

28

c. MÃ HÓA SỐ HỌC

Mã hóa số học là kĩ thuật nén dữ liệu mà cho phép mã hóa dữ liệu bằng cách tạo ra một chuỗi mã (code string). Chuỗi này biểu diễn một giá trị thập phân nằm trong khoảng giữa 0 và 1.

Mô hình là cách tính toán phân bố các xác suất cho kí hiệu tiếp theo sẽ được mã hóa, sao cho bộ giải mã tìm ra được phân bố xác suất y hệt như thế. Có hai loại mô hình được sử dụng trong mã hóa số học:

1. Mô hình cố định: Trong mô hình này, cả bộ mã hóa và bộ giải mã biết được xác suất đã gán cho mỗi kí hiệu. Những xác suất này có thể được xác định bằng cách đo đạc các tần số trong các mẫu đại diện sắp được mã và các tần số kí hiệu

2. Mô hình thích nghi: xác suất được gán có thể thay đổi khi mỗi kí hiệu được mã hóa, dựa trên các tần số kí hiệu thấy được.

Nguyên lý

Ý tưởng cơ bản của mã hóa số học là sử dụng khoảng chia giữa 0 và 1 để biểu diễn các khoảng mã hóa. Rõ ràng hàm mật độ xác xuất tích lũy của tất cả các kí hiệu sẽ bằng 1. Khi bản tin càng dài thì các khoảng để biểu diễn bản tin đó càng ngắn, và số các bít cần để xác định khoảng đó càng tăng.

29

c. MÃ HÓA SỐ HỌC ( Arithmetic Coding)

Bước 1

Bước 2

Thực hiện quá trình mã hóa

Phân tích các số giới hạn trong khoảng [0,1)

2/11/2017

30 c. Arithmetic Coding

Arithmetic coding

Huffman coding

Arithmetic coding sử dụng mỗi từ mã để mã cho cả chuỗi .

Mã Huffman sử dụng từng từ mã riêng biệt cho mỗi ký tự.

2/11/2017

31 Thuật toán mã hóa ( tham khảo)

2/11/2017

Thuật toán giải mã

2/11/2017

Hàm phân phối tích lũy CDF (Cumulative distribution function)

2/11/2017

34 Ví dụ: Mã hóa bản tin M=[abaaeaaba]

2/11/2017

35 Mã hóa

2/11/2017

36 Mã hóa

2/11/2017

37 Mã hóa

2/11/2017

Mã hóa

2/11/2017

Mã hóa

2/11/2017

Giải mã bản tin

2/11/2017

Giải mã bản tin

2/11/2017

Giải mã bản tin

2/11/2017

43

d. Mã hóa từ điển (Lempel-Zip Coding)

 Thuật toán LZ (Lempel-Zip) là thuật toán nén dữ liệu theo từ điển cơ sở (Dictionary-based compression) .  Sử dụng một bảng chứa tất cả các chuỗi ký tự có thể xuất hiện trong văn bản và được chứa trên cả bộ mã hóa và giải mã.

 Bộ mã hóa thay vì gửi các từ riêng lẻ, nó chỉ gửi chỉ

số của từ được lưu trong bảng. Bộ giải mã sẽ truy cập vào bảng xử lý để tái tạo lại văn bản đó.

2/11/2017

44 d. Lempel-Zip Coding

 Được Jacob Braham Ziv đưa ra lần đầu tiên năm 1977, sau

đó phát triển thành một họ giải thuật nén từ điển là LZ.

 Năm 1984, Terry Welch cải tiến giải thuật LZ thành một

giải thuật tốt hơn :LZW

 Dùng để giảm dư thừa trong pixel  Không cần biết trước xác suất phân bố của các pixel  Được ứng dụng rộng rãi trong nén số liệu các file máy tính,

các tiện ích nén/giãn trong UNIX.

 Thường được dùng để nén các loại văn bản, ảnh đen trắng, ảnh màu, ảnh đa mức xám... Và là chuẩn nén cho các dạng ảnh GIF và TIFF.

d. Lempel-Zip Coding

 Phương pháp :  Xây dựng 1 từ điển

Cấu trúc từ điển

d. Lempel-Zip Coding

 Từ điển được xây dựng đồng thời với quá trình đọc dữ liệu. Sự có mặt của một chuỗi con trong từ điển khẳng định rằng chuỗi đó đã từng xuất hiện trong phần dữ liệu đã đọc.

 Thuật toán liên tục “tra cứu ” và cập nhật từ điển sau

mỗi lần đọc một kí tự ở dữ liệu đầu vào.

 Do kích thước bộ nhớ không phải vô hạn và để đảm bảo tốc độ tìm kiếm, từ điển chỉ giới hạn 4096 ở phần tử dùng để lưu lớn nhất là 4096 giá trị của các từ mã. Như vậy độ dài lớn nhất của mã là 12 bít(4096= 212).

Thuật toán mã hóa Lempel-Zip

output the code for P add P + C to the string table

1 Initialize table with single character strings 2 P = first input character 3 WHILE not end of input stream 4 C = next input character 5 IF P + C is in the string table 6 P = P + C 7 ELSE 8 9 10 P = C 11 END WHILE

12 output code for P

IF NEW is not in the string table

S = S + C

S = translation of NEW

Thuật toán giải nén Lempel-Zip 1 Initialize table with single character strings 2 OLD = first input code 3 output translation of OLD 4 WHILE not end of input stream 5 NEW = next input code 6 7 S = translation of OLD 8 9 ELSE 10 11 output S 12 C = first character of S 13 OLD + C to the string table 14 OLD = NEW 15 END WHILE

Ví dụ

 Example

Consider the following 4 x 4 8 bit image

Dictionary Location Entry

39 39 126 126

255

256

Initial Dictionary

511

39 39 126 126

50 LZW Coding

39 39 126 126

•Is 39 in the dictionary……..Yes

39 39 126 126

•What about 39-39………….No 39 39 126 126

•And output the last recognized symbol…39

•Then add 39-39 in entry 256

Dictionary Location Entry

. 39-39

255

256

511

51

LZW Coding

52 Ví dụ :

Ví dụ: Nguồn DMS phát ra chuỗi dữ liệu nhị phân như sau:

10101101001001110101000011001110101100011011

Hãy thực hiện quá trình mã hóa LZW?( trang 105 tài liệu truyền dẫn số Digital

Communications by John Proakis)

 Chia dữ liệu ngõ vào thành các cụm:

Lời giải:

1 0 10 11 01 00 100 111 010 1000 011 001 110 101 10001 1011

 Lập bảng mã hóa như hình sau:

Có 16 cụmdùng 4 bit để biểu diễn vị trí trong từ điển.

• Cột vị trí: điền giá trị nhị phân 4 bit tăng dần, loại trừ 0000.

• Cột nội dung: điền vào giá trị các cụm, mỗi cụm trên một hàng.

53 2/11/2017

mã hóa LZW ( Lempel-Ziv-Welch )

 Để mã hóa những chuỗi này:

 Các từ mã được xác định qua việc liệt kê vị trí từ điển (ở dạng nhị phân) của chuỗi trước đó giống hệt với chuỗi mới chỉ khác vị trí cuối cùng + mã hóa ký tự sai khác .

 Khởi đầu, vị trí 0000 được sử dụng để mã hóa một chuỗi chưa xuất hiện trước đó.

 Bộ giải mã nguồn cần phải xây dựng lại từ điển ở phía thu giống như ở phía phát và sau

 Nhận xét:

 Ví dụ trên mã hóa 44 ký hiệu nhị phân của nguồn thành 16 từ mã, mỗi từ mã có độ

đó giải mã lần lượt các từ mã nhận được.

 Thuật toán sẽ hiệu quả hơn và có nén số liệu ở đầu ra của nguồn khi chuỗi ký hiệu đủ

lớn.

dài 5 bit. Ở ví dụ này không thực hiện nén số liệu , do chuỗi ký hiệu quá ngắn.

54 Phương pháp mã hóa LZW:

Thứ tự

Từ mã

Vị trí trong từ điển

Nội dung từ điển

0000

1 0001

1 0000

2 0010

0

3 0011

10

4 0100

11

Giá trị khởi động

5 0101

01

6 0110

00

7 0111

100

8 1000

111

9 1001

010

10 1010

1000

11 1011

011

12 1100

001

13

110

14 1110

101

15 1111

10001

16 1011

55 2/11/2017

55 Phương pháp mã hóa LZW:

Thứ tự

Vị trí trong từ điển

Nội dung từ điển

Tạo mã

00001

1 0001

1

2 0010

0

3 0011

10

4 0100

11

5 0101

01

6 0110

00

7 0111

100

8 1000

111

9 1001

010

10 1010

1000

11 1011

011

12 1100

001

13 1101

110

14 1110

101

15 1111

10001

16 1011

56 2/11/2017

Phương pháp mã hóa LZW:

Vị trí trong từ điển

Nội dung từ điển

Tạo mã

Thứ tự

00001

1 0001

1 00000

2 0010

0

3 0011

10

4 0100

11

5 0101

01

6 0110

00

7 0111

100

8 1000

111

9 1001

010

10 1010

1000

11 1011

011

12 1100

001

13 1101

110

14 1110

101

15 1111

10001

16 1011

57 2/11/2017

Phương pháp mã hóa LZW:

Vị trí trong từ điển

Nội dung từ điển

Tạo mã

Thứ tự

00001

1 0001

1 00000

2 0010

0 00010

3 0011

10

4 0100

11

5 0101

01

6 0110

00

7 0111

100

8 1000

111

9 1001

010

10 1010

1000

11 1011

011

12 1100

001

13 1101

110

14 1110

101

15 1111

10001

16 1011

58 2/11/2017

Phương pháp mã hóa LZW:

Vị trí trong từ điển

Nội dung từ điển

Tạo mã

Thứ tự

00001

1 0001

1 00000

2 0010

0 00010

3 0011

10 00011

4 0100

11

5 0101

01

6 0110

00

7 0111

100

8 1000

111

9 1001

010

10 1010

1000

11 1011

011

12 1100

001

13 1101

110

14 1110

101

15 1111

10001

16 1011

59 2/11/2017

2.4 Các phương pháp mã hóa nguồn tương tự:

2.4.1 Phương pháp mã hóa miền thời gian:

 Phương pháp mã hóa PCM

 Phương pháp mã hóa PCM vi sai (DPCM)

 Phương pháp mã hóa delta DM

 Phương pháp mã hóa PCM vi sai thích nghi (ADPCM)

 Phương pháp mã hóa băng con SBC (Sub- Band Coding)

2.4.2 Phương pháp mã hóa miền tần số:

 Tín hiệu được lọc vào một số dải tần con dùng giàn lọc, hay FFT,…

 Sau đó dữ liệu ở tất cả các băng con sẽ được đóng gói lại.

 Tín hiệu trong mỗi dải con sẽ được mã hóa một cách độc lập.

 Dùng trong mã hóa thoại, mã hóa audio (ví dụ định dạng nén MP3), vv…

60 2/11/2017

Phân loại mã hóa thoại

61 Phân loại mã hóa thoại

62 a. Mã hoá sóng

 Mã hoá dạng sóng: người ta chia mã hoá dạng sóng ra

làm hai loại chính

 Trong miền thời gian: mã hoá điều xung mã (PCM), điều

chế xung mã vi sai (DPCM) và điều chế xung mã vi sai thích nghi (ADPCM).

 Trong miền tần số: mã hoá băng con SBC (subband coding) và mã hoá biến đổi thích nghi ATC (Adaptive Transform Coding).

63 Mã hoá sóng

- Tại phía phát: Bộ mã hóa nhận các tín hiệu tiếng nói

tương tự và mã hóa thành tín hiệu số trước khi truyền đi

- Tại phía thu: Làm ngược lại để khôi phục tiếng nói

Ví dụ: PCM,DPCM, ADPCM..vv

64 Mã hoá sóng

 Khôi phục được tín hiệu sóng giống như tín hiệu gốc  Độ phức tạp, giá thành, độ trễ công suất tiêu thụ thấp  Chỉ tạo được tiếng nói chất lượng cao tại các tốc độ lớn

hơn 16kbps

 Không tạo được tiếng nói chất lượng cao tại tốc độ nhỏ

hơn 16kbps

65

1. PCM (PULSE CODE MODULATION)

 Sơ đồ khối hệ thống điều chế PCM

66 PCM (PULSE CODE MODULATION

LẤY MẪU (1)

S(t)

Xung lấy mẫu

 Chuyển đổi tín hiệu tương tự thành dãy xung điều biên độ- PAM (tín hiệu rời rạc về mặt thời gian)

Tín hiệu analog

 Yêu cầu: Chu kì lấy mẫu phải thỏa

mãn định lí Nyquist  Tmax≤1/2fmax

 Định lí Shannon – Nyquist:

 Một tín hiệu có dải tần giới nội là B(Hz) (tín hiệu mà biến đổi Fourier của nó đều bằng 0 với |ω|>2πB hay f>B) được xác định một cách duy nhất bởi các giá trị của nó lấy tại các khoảng cách đều nhau bé hơn 1/2B giây.

 Một tín hiệu có dải tần giới nội là B(Hz) có thể được thiết lập lại từ các mẫu của nó

 TS=1/2B giây: khoảng Nyquist  2B mẫu/s: tốc độ lấy mẫu Nyquist

lấy đều đặn với tốc độ không ít hơn 2B mẫu trên một giây.

68

LƯỢNG TỬ HÓA (1)

 Định nghĩa:

 Làm tròn biên độ xung lấy mẫu tới một mức lượng tử gần nhất

(bằng một số nguyên lần các bước lượng tử)

 Mục đích:

 Rời rạc hóa tín hiệu về mặt biên độ

 Phương pháp:

 Lượng tử hóa đều:

 Chia biên độ tín hiệu thành các khoảng đều nhau (các mức lượng tử hóa

có biên độ cách đều nhau) – bước lượng tử hóa đều

 Lượng tử hóa không đều:

 Chia biên độ tín hiệu thành các khoảng không đều nhau theo một qui luật

nhất định (các mức lượng tử hóa có biên độ cách không đều nhau)

69

LƯỢNG TỬ HÓA (2)

 Lượng tử hóa đều:  Bước lương tử hóa

 Q: số lượng mức lượng tử  a: biên độ xung lấy mẫu

 Méo lượng tử

S(t)

Xung lượng tử

- Bước lượng tử đều

Tín hiệu analog

Mức lượng tử

7 6 5 4 3 2 1 0

70 Lượng tử hóa đều

L levels (L-1)q = 2Vp =

Vpp

For large L Lq ≈ Vpp

LƯỢNG TỬ HÓA (3)

 Lượng tử hóa không đều:

 Qui luật lượng tử:

 Biên độ xung lấy mẫu càng lớn thì độ dài bước lượng tử càng lớn

S(t)

Xung lượng tử

i - Bước lượng tử không đều

Tín hiệu analog

Mức lượng tử

4 3 2 1 0

72 Uniform

Non-Uniform

LƯỢNG TỬ HÓA - Non-Uniform

Companding(Compressing-Expanding)

- Để đạt mã hóa không tuyến tính . Tín hiệu được đưa vào bộ nén ( companding) sau

đó lại dùng bộ mã hóa tuyến tính (linear encoding).

- Tại đầu thu tín hiệu được đưa vào bộ dãn (Expanding) đảo của bộ nén .

- Ví dụ:

Compressing

Expanding

8/21

Y X

Nén - giãn

 Nén – dãn analog:  Đặc tính biên độ:

 Luật A:

 Luật µ:

 Trong đó: x=Vin/Vmax; Vmax: điện áp vào ứng với điểm bão hòa của đặc

tính biên độ bộ nén

 Vin: điện áp vào (biến thiên từ 0÷2048Δ; Δ: mức lượng tử hóa đều)

 Đặc điểm bộ nén:

 Số lượng mức lượng tử giảm từ 2048 xuống còn 128 mức  Lượng tử hóa không đều: Biên độ mức lượng tử tăng khi biên độ tín hiệu

tăng

76

Nén – giãn số

 Dựa trên biểu thức toán học của bộ nén analog theo tiêu chuẩn châu Âu, bộ

nén A=87,6/13

Vra

128



112

VII



96



80



64



III

48



32



16

0 

Vvào

256

512

1024

2048

128

64

32

16

77

Nén – giãn số

 Đặc điểm của đặc tính biên độ:

 Hình vẽ đặc tính biên độ thể hiện cho nhánh dương, nhánh âm đối xứng qua

gốc tọa độ

 Biên độ chia thành 13 đoạn:

 Mỗi nhánh có 8 đoạn, đoạn I và đoạn II có cùng bước lượng tử hóa và có

cùng độ dốc được ghép lại thành một đoạn còn 7 đoạn

 Hai đoạn bắt đầu từ gốc tọa độ có cùng độ dốc và cùng bước lượng tử hóa

 ghép thành 1 đoạn

 Trong mỗi đoạn được lượng tử hóa đều với 16 mức lượng tử hóa  Sử dụng một bit b1 để mã hóa dấu của giá trị biên độ (biên độ mang giá trị

âm và dương)

 Việc mã hóa biên độ tín hiệu chỉ cần quan tâm đến giá trị tuyệt đối

78

 Lượng tử hóa trong đoạn:

 Mỗi đoạn được chia thành 16 mức lượng tử hóa với bước lượng

tử hóa đều nhau, đánh số từ 0 đến 15

 Bước lượng tử hóa của các đoạn khác nhau là khác nhau, bước lượng tử hóa của đoạn sau lớn hơn gấp đôi bước lượng tử hóa của đoạn trước liền kềlượng tử hóa không đều  So sánh bước lượng tử hóa đều Δ và không đều Δn:

Δn = (V2n-V1n)/16

Trong đó: n là chỉ số thứ tự đoạn từ 0 đến 7

V2n,V1n: giá trị điện áp tại đầu đoạn và cuối đoạn thứ n

79

MÃ HÓA

 Mục đích:

 Mã hóa mỗi xung lấy mẫu thành một từ mã có số lượng bit ít

nhất  Mã cơ số L:

 L càng lớn, số lượng bit mã hóa cho một xung lấy mẫu càng nhỏ  Thực hiện quyết định bit phía thu khó

 Mã cơ số 2 (L=2):

 Số lượng bit mã hóa cho một xung là lớn nhất  Thực hiện quyết định bit phía thu dễ dàng, có độ chính xác cao  Được sử dụng chủ yếu

80

 Mã hóa – nén số:

Thứ tự đoạn

Số lượng bước lượng tử đều

0 16Δ

 Xung lấy mẫu VPAM được chuyển thành từ mã 8 bit  Bit b1: chỉ thị dấu của giá trị

I

16Δ

biên độ đoạn

II

32Δ

 Bit b2b3b4: mã hóa đoạn  Bit b5b6b7b8: mã hóa mức

III

64Δ

lượng tử trong đoạn

IV

128Δ

V

256Δ

VI

512Δ

VII

1024Δ

81

 Mã hóa đoạn:

Thứ tự đoạn

Từ mã đoạn b2 b3 b4 0 0 0

0

 Sử dụng ba bit b2b3b4 để đánh số thứ tự các đoạn từ 0 đến 7 trong nhánh dương

I

0 0 1

II

0 1 0

III

0 1 1

IV

1 0 0

V

1 0 1

VI

1 1 0

VII

1 1 1

82

TỪ MÃ CÁC BƯỚC

TT bước

b5 b6 b7 b8

0 0 0 0 0

8 1 0 0 0

1 0 0 0 1

9 1 0 0 1

2 0 0 1 0

10 1 0 1 0

3 0 0 1 1

11 1 0 1 1

4 0 1 0 0

12 1 1 0 0

5 0 1 0 1

13 1 1 0 1

6 0 1 1 0

14 1 1 1 0

7 0 1 1 1

15 1 1 1 1

83

CÁC NGUỒN ĐIỆN ÁP CHUẨN

Thứ tự đoạn

Điện áp mẫu đầu đoạn

Mã đoạn b2 b3 b4 000

0 Điện áp mẫu chọn bước trong đoạn b8 

b7 2

b6 4

b5 8

0

I

001



2

4

8

16

II

010 2

4

8

16

32

III

011 4

8

16

32

64

IV

100 8

16

32

64

128

V

101 16

32

64

128

256

VI

110 32

64

128

256

512

VII

111 64

128

256

512

1024

84

 Quy trình mã hóa:

 So sánh giá trị biên độ xung lượng tử chưa nén với nguồn điện

áp mẫu để xác định giá trị các bit

 Xác định giá trị các bit trong từ mã theo lần lượt: bit b1 trước (bit dấu), đến các bit b2b3b4 (chọn đoạn), cuối cùng là các bit b5b6b7b8 (chọn bước lượng tử hóa)

 Bước 1: Chọn bit dấu b1

 VPAM≥0∆ thì b1=1; VPAM<0∆ thì b1=0

85

 Bước 2: Chọn đoạn (b2b3b4)

 Xác định b2:

 VPAM≥128∆ thì b2=1; VPAM<128∆ thì b2=0

 Xác định b3: 2 trường hợp

 Trường hợp 1: b2=1

 VPAM≥512∆ thì b3=1; VPAM<512∆ thì b3=0

 Trường hợp 2: b2=0

 VPAM≥32∆ thì b3=1; VPAM<32∆ thì b3=0

 Xác định b4: 4 trường hợp

 Trường hợp 1: b2b3=00

 VPAM≥16∆ thì b4=1; VPAM<16∆ thì b4=0

 Trường hợp 2: b2b3=01

 VPAM≥64∆ thì b4=1; VPAM<64∆ thì b4=0

 Trường hợp 3: b2b3=10

 VPAM≥256∆ thì b4=1; VPAM<256∆ thì b4=0

 Trường hợp 4: b2b3=11

 VPAM≥1024∆ thì b4=1; VPAM<1024∆ thì b4=0

86

 Bước 3: Chọn bước trong đoạn (b5b6b7b8)

 Xác định b5:

 VPAM  Vm1 thì b5=1; VPAM  Vm1 thì b5=0,

trong đó Vm1= Vmđđ + Vm(b5)

 Xác định b6:

 VPAM  Vm2 thì b6=1; VPAM  Vm2 thì b6=0, trong đó Vm1= Vmđđ + Vm(b6) + Vm(b5=1)

 Xác định b7:

 VPAM  Vm3 thì b7=1; VPAM  Vm3 thì b7=0,

trong đó Vm1= Vmđđ + Vm(b7) + Vm(b6=1) + Vm(b5=1)

 Xác định b8:

 VPAM  Vm4 thì b8=1; VPAM  Vm4 thì b8=0,

trong đó Vm1=Vmđđ+Vm(b8)+Vm(b7=1)+Vm(b6=1)+Vm(b5=1)

87 Ví dụ: Mã hóa PCM

Ví dụ:

2. Điều chế xung mã vi sai dự đoán DPCM

90 Bộ lọc dự đoán

 Thực chất bộ lọc dự đoán gồm nhiều mạch trễ nối tiếp  Thời gian trễ TS của mỗi mạch bằng chu kỳ lấy mẫu  Nếu bộ lọc dự đoán chỉ dùng 1 mạch trễ thì sự dự đoán là bậc 1  Nếu dùng 3 mạch trễ liên tiếp dự đoán bậc 3  Dự đoán bậc 3 cho sự đánh giá tốt hơn bậc 1, tạo ra khả năng mã

hoá và số bit ít hơn.

91 Bộ lọc dự đoán

92 Điều chế xung mã vi sai dự đoán DPCM

93 3. Điều chế Delta (DM)

94 3. Điều chế Delta (DM)

 Lượng tử hóa sai số dự đoán vào 2 mức: , -.  Mỗi mẫu = 1 bit.

95 Điều chế Delta (DM)

96 Điều chế Delta (DM)

97 4. Mã hóa ADPCM (G.721)

Mã hóa ADPCM (sơ đồ)

99 Mã hóa ADPCM (sơ đồ)

5. Mã hóa băng con SBC (Sub- Band Coding)

 Tín hiệu được lọc vào một số dải tần con dùng giàn lọc,

hay FFT,…

 Tín hiệu trong mỗi dải con sẽ được mã hóa một cách độc

lập.

 Sau đó dữ liệu ở tất cả các băng con sẽ được đóng gói lại.  Dùng trong mã hóa thoại, mã hóa audio (ví dụ định dạng

nén MP3), vv…

101

Mã hóa - SBC Encoder

1 0 2

Giải mã - SBC Decoder

1 0 3

Mã hóa băng con SBC

1 0 4

 Bảng sau đưa ra khoảng tần số cho mỗi băng và số

bít được dùng mã hóa mỗi băng .

SB Number

Frequency (Hz)

# of encoded bits

1 225-450 4

2 450-900 3

3 1000-1500 2

 Tính tốc độ tối thiểu của bộ mã hóa SBC .

4 1800-2700 1

SBC

1 0 5

 For perfect reconstruction of band-pass signals, need to sample at Nyquist rate which is twice the signal bandwidth  Band 1: 2x(450-225) = 450 samples/sec  Band 2: 2x(900-450) = 900 samples/sec  Band 3: 2x(1,500-1,000) = 1,000 samples/sec  Band 4: 2x(2,700-1,800) = 1,800 samples/sec

 Total encoding rate is

 450x4+900x3+1,000x2+1,800x1 = 8,300 bits/s

6. Mã hóa chuyển đổi thích nghi

 Tốc độ bít 9.6kbps đến 20kbps  Xử lý trên từng block dữ liệu bằng cách chia dữ

liệu đầu vào thành các khối (block)

 Mỗi khối sẽ được đại diện bởi các hệ số chuyển đổi, nó sẽ được lượng tử và truyền trên kênh truyền

 Ví dụ các phép chuyển đổi thường xuyên được sử dụng: Chuyển đổi cosin rời rạc DCT, chuyển đổi Wavelet..vv

 Dùng trong mã hóa ảnh :Jpeg, Mpeg..vv

106 Nhận xét

 Mã hóa dạng sóng không thể cho chất lượng tốt khi tốc

độ bit < 16 kbps.

 Để giảm hơn nữa tốc độ bit, mô hình tạo ra tiếng nói cần được khai thác → mã hóa dựa trên mô hình (vocoder).

107 b. Mã hóa tham số -Vocoder

Mã hóa Vocoder

 Nguồn tin được mô hình gồm bộ lọc tuyến tính với kích thích

phù hợp.

 Các tham số của bộ lọc và tín hiệu kích thích được mã hóa để truyền đi thay vì phải truyền các mẫu dữ liệu đã mã hóa như các phương pháp khác.

 Chất lượng mã hóa không cao nhưng điểm đặc biệt là số bit

truyền đi ít tỉ lệ nén rất cao.

 Các bộ mã hóa thoại (vocoder- voice coder) thông dụng: LPC,

CELP,CS-CELPvv…

 Dùng trong mã hóa thoại ở các hệ thống thông tin di động

GSM, CDMA.

2/11/2017

Ưu nhược điểm củaVocoder

 Chất lượng phụ thuộc nhiều vào mô hình thoại

 ChÊt lîng kÐm c¸c vocoder rÊt nh¹y c¶m víi lçi.

 Có thể cung cấp thoại số với tốc độ nhỏ hơn 2kbps

110 Mã hóa dự đoán tuyến tính LPC

{ap(k)}

 Mã hóa:

Lấy mẫu Tín hiệu thoại

Xác định âm hữu thanh hay vô thanh và kích thích

Kích thích

Mã hóa Pitch fs =8000 mẫu/s

• Giải mã:

Kích thích

Pitch Bộ lọc IIR

{ap(k)}

Tín hiệu thoại

Bộ tạo tín hiệu Giải mã H(z)

Lọc thông thấp

111 Ví dụ mã hoá thoại trong mạng di động

TRAU

MSC

64 kbits/s

22.8 kbits/s

BSC

13 kbits/s

BTS

112

Ứng dụng bộ mã hóa thoại tốc độ thấp trong GSM

Chuẩn mã hóa thoại cơ bản

2.5 Quantization Techniques

Lượng hóa – Quantization  Giảm bớt các giá trị đầu ra sai khác  Có 3 phương pháp để lượng hóa: + Uniform: Bao gồm midrise quantizer và midtreat

quantizer

+ Nonuniform: companded quantizer + Vector Quantization

116 Lượng tử hóa đều – Uniform Scalar

Quantization: + Phân chia vùng dữ liệu vào (input) thành các khoảng đều nhau, ngoại trừ hai khoảng hoặc hai biên. + Giá trị của dữ liệu ra (output) được lấy tại điểm giữa của mỗi khoảng + Độ dài của mỗi khoảng được gọi là kích thước bước lượng tử (step size) và được ký hiệu là 

117

+ Midrise quantizer: Có một số lẻ các mức ra (output

levels)

+ Midtreat quantizer: Có một số chẵn các mức ra bao

gồm cả số 0 như là một mức ra

 Trong trường hợp  =1 ta có thể tính được các giá trị

ra như sau:

118

Uniform Scalar Quantizers: (a) Midrise (b) Midtreat

119 Lượng tử hóa không đều – Nonuniform

Quantization  Phân chia vùng dữ liệu vào (input) thành các khoảng không đều nhau. Các khoảng cách có thể được lựa chọn để tối ưu hóa SNR cho một kiểu cụ thể của tín hiệu  Một trong số các phương pháp lượng tử hóa của Nonuniform Quantization là Companded Quantization

120

 Companded Quantization là kết hợp của hai bước: Compressed (bên phía gửi) và Expanded (bên phía nhận)

+ Compressed sẽ làm cho tín hiệu đầu vào có phân phối

đều (uniform distribution) do đó có thể sử dụng uniform quantization

+ Bên nhận khi nhận được tín hiệu (compressed) sẽ tiến

hành giải nén dữ liệu (expanded)

121

Lượng tử hóa vector – Vector Quantization

 Các hệ thống nén dữ liệu sẽ làm việc tốt hơn nếu nó hoạt động trên các vector hoặc các nhóm của các mẫu hơn là làm việc với các ký hiệu hay các mẫu riêng lẻ

 Các vector được thành lập bằng cách đặt các mẫu đầu vào

liên tiếp vào trong một vector.

 Trong Vector Quantization các vector mã (code vector)

với n thành phần được sử dụng, các vector mã này sẽ tạo thành một codebook

122

Thủ tục lượng tử hóa vector cơ bản

123 Bài tập

Lời giải

Hướng dẫn ôn tập 1. Lý thuyết :  Nắm vững kiến thức về Entropy và các phương pháp

mã hóa entropy

 Hiểu khái niệm mã hóa PCM,DPCM,Delta, ATC, SBC  Hiểu khái niệm lượng tử đều, không đều, véctơ, 2. Đạt kết quả kiểm tra bài tập chương 2 3. Sử dụng matlab để mô phỏng quá trình điều chế PCM,

Delta, DPCM

127