Bài giảng Kỹ thuật audio và video

MULTIMEDIA MULTIMEDIA MULTIMEDIA

TTÀÀI LI

I LIỆỆU THAM KH

U THAM KHẢẢOO

365 Course Contents,

Spring

2000,

Website:

• CMPT

http://www.cs.sfu.ca/CourseCentral/365/li/index.html

”, Ken C.PohmanmFourth Edition

• “Principles of Digital Audio

McGraw-Hill.

• “Digital Video processing ”, A. MuratTekalp, University of Rochester,

Prentice Hall PTR.

• “Multimedia processing”, Andrew Calway, COMS72200. • “Fundamentals of Digital Image Processing”., Anil.K.Jan, Prentice Hall,

1996.

Services

and Technologies”,

• MPEG Home Page, http://www.cselt.it/mpeg/ • “Emerging Wireless Multimedia

JohnWileySons, Aug 2005

• “Multimedia Content and the Semantic Web Standards Methods and

Tools”, John Wiley Sons, Jun 2005

• “Introduction To Digital Audio Signal Processing”, DavideRocchesso,

2003

Page 2

I DUNG NNỘỘI DUNG

• TỔNG QUAN • KỸ THUẬT AUDIO • KỸ THUẬT VIDEO

Page 3

NG QUAN TTỔỔNG QUAN

• TỔNG QUAN VỀ MULTIMEDIA • KHÁI NIỆM CHUNG VỀ AUDIO VÀ VIDEO • HỆ THỐNG AUDIO-VIDEO • MỘT SỐ VẤN ðỀ VỀ TÍN HIỆU

Page 5

TTỔỔNG QUAN V

MULTIMEDIA NG QUAN VỀỀ MULTIMEDIA

• Lịch sử phát triển của hệ thống ña môi trường – Báo, tạp chí - môi trường: văn bản, ñồ hoạ và hình ảnh. – Cáp ñồng: môi trường truyền tải tín hiệu ñiện. – 1895, Guglemo Marconi phát minh ra máy radio ở Pontechio – Ý, môi trường chuyển tải tín hiệu audio quảng bá hiện nay.

– Truyền hình, môi trường truyền thông của thế kỷ 20, truyền

hình ảnh và âm thanh ñến mọi nơi.

– Các hệ thống máy tính tích hợp nhiều dạng môi trường số khác nhau, khả năng biểu diễn, tương tác với các dạng thông tin, tiềm năng lớn phục vụ nhu cầu trao ñổi thông tin chất lượng cao.

– Các hệ thống ña môi trường trở nên phong phú, kết hợp các công nghệ khác nhau với khả năng di ñộng, liên lạc từ xa dưới nhiều hình thức.

Page 6

TTỔỔNG QUAN V

MULTIMEDIA NG QUAN VỀỀ MULTIMEDIA

ðồ hoạ

Văn bản thường (tuyến tính)

Âm thanh

Siêu văn bản

Hình 1-1 Hypertext, Hypermedia

Page 7

TTỔỔNG QUAN V

MULTIMEDIA NG QUAN VỀỀ MULTIMEDIA

• Siêu môi trường và ña môi trường (hypermedia –

multimedia) – Hypertext: “Siêu văn bản là một tài liệu không tuyến tính, bằng cách kích vào một ñiểm nóng nào ñó trên văn bản, nó có thể chuyển ñến một tài liệu hay một văn bản khác, rồi có thể quay về, thuận tiện cho người ñọc trong việc duyệt văn bản hoặc muốn tổng quan một văn bản từ phần mục lục”. (Ted Nelson ,1965)

– Hypermedia: Bao gồm nhiều môi trường truyền thông khác nhau như ñồ thị, hình ảnh, âm thanh, hoạt hình và ảnh ñộng. (Ted Nelson).

– Multimedia: thông tin máy tính có thể ñược mô tả bằng audio, video hay hoạt hình ngoài những môi trường truyền thống.

Page 8

Video Siêu môi trường

TTỔỔNG QUAN V

MULTIMEDIA NG QUAN VỀỀ MULTIMEDIA

• Ví dụ một số ứng dụng multimedia:

• Hệ thống xây dựng và soạn thảo video số. • Tạp chí ñiện tử. • Trò chơi. • Thương mại ñiện tử. • Truyền hình tương tác iTV. • Truyền hình hội nghị. • Truyền hình theo yêu cầu. • Thực tế ảo. • ...

Page 9

TTỔỔNG QUAN V

MULTIMEDIA NG QUAN VỀỀ MULTIMEDIA

• Các dạng môi trường và tín hiệu:

dạng môi trường

audio

video

animation

liên tục

rời rạc

images

text

graphic

gốc tín hiệu

thu nhận

tổng hợp

Hình 1-2 Dạng môi trường

Page 10

TTỔỔNG QUAN V

MULTIMEDIA NG QUAN VỀỀ MULTIMEDIA

Hình 1-3 Thu nhận và tổng hợp

Page 11

TTỔỔNG QUAN V

MULTIMEDIA NG QUAN VỀỀ MULTIMEDIA

• Âm thanh (audio) • Âm thanh: Là dao ñộng sóng âm gây ra áp lực làm dịch chuyển các hạt vật chất trong môi trường ñàn hồi làm tai người cảm nhận ñược các dao ñộng này. Tai người có thể nghe ñược trong khoảng tần số từ 20Hz ñến 20kHz.

• Âm thanh tự nhiên: Là sự kết hợp phức giữa các sóng âm có

tần số và dạng sóng khác nhau.

• Dải ñộng của tai: Giới hạn bởi ngường nghe thấy (0dB) ñến

ngưỡng ñau (120dB) của người.

• Ngưỡng nghe tối thiểu: Mức thấp nhất của biên ñộ mà tai người có thể cảm nhận ñược âm thanh tuỳ thuộc vào từng người, mức áp lực và tần số của âm thanh.

Page 12

TTỔỔNG QUAN V

MULTIMEDIA NG QUAN VỀỀ MULTIMEDIA

• Hiệu ứng che khuất âm thanh: Hiện tượng âm thanh mà tại ñó ngưỡng nghe của một âm tăng lên trong khi có mặt của một âm khác (khó nghe hơn). ðược sử dụng trong kỹ thuật nén. • Hướng âm thanh: Tai và não có thể giúp ta xác ñịnh hướng âm thanh, ñiều này có thể ứng dụng ñể tạo các hiệu ứng âm thanh như stereo, surround.

• Vang và trễ: Vang là hiện tượng kép dài âm thanh sau khi nguồn âm ñã tắt. Trễ là thời gian τ âm thanh phản xạ ñến ñích so với âm thanh trực tiếp. Nếu τ>50ms thì trễ ñó gọi là tiếng vọng. Biên ñộ của âm thanh cứ sau 1 lần phản xạ thì bị suy giảm.

• Âm nhạc: Là âm thanh có chu kỳ ở những tần số mà tai người cảm nhận một cách dễ chịu, êm ái, ñược kết hợp một cách phù hợp. Âm nhạc gồm cao ñộ, âm sắc và nhịp ñiệu.

Page 13

TTỔỔNG QUAN V

MULTIMEDIA NG QUAN VỀỀ MULTIMEDIA

• Video

• Tín hiệu video: Là sự tái tạo ảnh tự nhiên với những

khoảng cách về không gian, thời gian hoặc cả hai.

• Ảnh tự nhiên: ñược tạo nên từ các nguồn sáng mặt trời hay ánh sáng nhân tạo phản xạ lên các vật thể mà ta có thể nhìn thấy ñược.

• Ảnh: Là một ma trận các ñiểm ảnh mang thông tin về ñộ

chói và màu sắc.

• Sự lưu ảnh: Khả năng lưu hình của mắt trong một giây. Mắt có thể lưu ñược 24 hình trong một giây. Chọn số hình trong một giây của ảnh ñộng phù hợp

Page 14

TTỔỔNG QUAN V

MULTIMEDIA NG QUAN VỀỀ MULTIMEDIA

• ðộ chói: Là biên ñộ của thành phần trong ảnh (pixel).

• Ví dụ tín hiệu chói Y ñược tổng hợp bởi các tín hiệu RGB theo

công thức:

(1-2)

• EY=0,299ER+0,587EG+0,114EB

• Thông tin màu ñược xác ñịnh:

• EB-EY=0,587EG+0,889EB+0,229ER • ER-EY=0,587EG+0,114EB+0,701ER (1-3) • ðộ tương phản: Tỷ số của ñộ chói thành phần sáng nhất

so với ñộ chói của thành phần tối nhất.

Page 15

TTỔỔNG QUAN V

MULTIMEDIA NG QUAN VỀỀ MULTIMEDIA

• Hệ thống audio tương tự

m â

t ấ u X

ý l ử X

n ồ u g N

i ạ ñ h c ế u h K

i ạ ñ h c ế u h k n ề i T

Lưu trữ

Hình 1-4 Hệ thống audio tương tự

Page 16

HHỆỆ THTHỐỐNG AUDIO

VIDEO NG AUDIO--VIDEO

• Hệ thống video tương tự

Xử lý tín hiệu

Chuyển ñổi ảnh- tín hiệu

Ống kính

Cảnh tự nhiên

Tạo xung ñồng bộ

Ảnh tái tạo

Xử lý tín hiệu

Chuyển ñổi tín hiệu - ảnh

Lưu trữ hoặc truyền dẫn

Tách xung ñồng bộ

Hình 1-5 Hệ thống Video tương tự

Page 17

Mắt người

HHỆỆ THTHỐỐNG AUDIO

VIDEO NG AUDIO--VIDEO

• Hệ thống audio-video số:

Nguồn tín hiệu (Analog)

Chuyển ñổi Analog - Digital

Xử lý, Lưu trữ, Truyền dẫn (Digital)

Chuyển ñổi Digital - Analog

Xuất âm, hiển thị (Analog)

Hình 1-6 Hệ thống audio-video số

Page 18

HHỆỆ THTHỐỐNG AUDIO

VIDEO NG AUDIO--VIDEO

• Các thành phần của hệ thống:

– Bộ phận thu: Micro và Camera thu và chuyển tín hiệu (âm thanh hoặc ảnh) sang tín hiệu ñiện tương tự. ðối với các hệ thống số phải thực hiện việc chuyển ñổi tương tự sang số. – Lưu trữ: Thiết bị lưu trữ là băng từ hoặc ñĩa từ. Có thể là các thiết bị riêng biệt sử dụng với muc ñích thuận tiện và yêu cầu một chất lượng nào ñó.

– Xử lý tín hiệu: ðiều chỉnh ñặc tuyến tần số, màu sắc, tạo

hiệu ứng..

– Truyền dẫn: Truyền tín hiệu từ vị trí này sang vị trí khác với một khoảng cách không gian nào ñó qua một môi trường truyền dẫn nào ñó.

Page 19

HHỆỆ THTHỐỐNG AUDIO

VIDEO NG AUDIO--VIDEO

• Phân loại các hệ thống Audio-Video:

Lớp hệ thống

Giá

Chất lượng

Dễ sử dụng

Linh hoạt

Khả năng mở rộng

Yếu tố quan trọng nhất

A-V gia ñình

Giá, dễ sử dụng

Chất lượng, giá

Bán chuyên nghiệp

Cầu hội thảo

Nén video

Phân phối video

Khả năng lưu trữ

Sản xuất studio

Chất lượng, linh họat

Sản xuất chương trình ngoài trời

Cơ ñộng, dễ sử dụng

Sản xuất hậu kỳ

Chất lượng, linh họat

Máy tính cá nhân

Toàn bộ

Page 20

HHỆỆ THTHỐỐNG AUDIO

VIDEO NG AUDIO--VIDEO

• Hệ thống Audio – Video dân dụng:

– Xây dựng hoặc tạo lại một số chương trình nhất ñịnh – Ghi, lưu trữ những sự kiện cá nhân. – Hầu hết các chương trình ñược thu và tạo ra tại chỗ. – Hệ thống ñáp ứng nhu cầu giá thành thấp, dễ sử dụng ñể

phổ biến rộng rãi.

– Sử dụng phương pháp sản xuất hậu kỳ với chất lượng giới

hạn nhất ñịnh.

– ða hệ và tương thích với mọi tiêu chuẩn. – Mối quan tâm của các nhà sản xuất.

Page 21

HHỆỆ THTHỐỐNG AUDIO

VIDEO NG AUDIO--VIDEO

• Hệ thống Audio-Video dân dụng

VCR, VCD, DVD

Interface card

Camera

PAL, NTSC

Hình 1-7 Hệ thống Audio – Video dân dụng

Page 22

HHỆỆ THTHỐỐNG AUDIO

VIDEO NG AUDIO--VIDEO

• Hệ thống Audio – Video bán chuyên dụng

Interface card

Camera

VCR, VCD, DVD

Băng, ñĩa

PAL, NTSC

Băng, ñĩa Tới khách hàng

Hình 1-8 Hệ thống Audio – Video bán chuyên dụng

Page 23

HHỆỆ THTHỐỐNG AUDIO

VIDEO NG AUDIO--VIDEO

• Hệ thống phân phối:

– Tập hợp chương trình thành một dòng dữ liệu ñể phát

quảng bá, truyền hình cáp hay vệ tinh.

– Khả năng chuyển tải ñến người xem thông qua máy phát,

mạng hay một phương thức nào ñó.

– Máy chủ phải ñáp ứng khả năng lưu trữ ñối với tín hiệu nhằm tạo ñường truyền thông suốt giữa các chương trình.

– Yêu cầu tự ñộng cao, giảm chi phí nhân công. – Truyền hình tương tác yêu cầu khả năng xử lý và chất lượng ñường truyền khá cao, ñồng thời hệ thống phải có khả năng phát các chương trình khác nhau trong cùng thời ñiểm.

Page 24

HHỆỆ THTHỐỐNG AUDIO

VIDEO NG AUDIO--VIDEO

• Hệ thống Audio – Video studio sản xuất chương

trình

Camera1 Camera2 Camera3 Camera4

Cam1 Cam2 Cam3 Cam4 VCR1 VCR2 VCR3 EFF LINE

VCR1

LINE

E F F 2

ðầu ra video

VCR1

VCR2

E F F 1 Bộ tạo kỹ xảo

VCR2

VCR3

Page 25

Hình 1-9 Hệ thống Audio – Video studio sản xuất chương trình

HHỆỆ THTHỐỐNG AUDIO

VIDEO NG AUDIO--VIDEO

• Hệ thống sản xuất chương trình ngoài trời:

– ðược sử dụng ñể thu các bản tin hay một chương trình nào ñó mà không cần nhiều người thực hiện, thường sử dụng các thiết bị cầm tay.

– Các chương trình truyền trực tiếp thì hệ thống có thể là các hệ thống cố ñịnh nhưng với quy mô nhỏ và chất lượng thấp hơn.

– Yêu cầu tính cơ ñộng cao. – Camera ñược nối với máy ghi riêng mà khôg sử dụng ma

trận chuyển mạch.

– Máy ghi âm ña ñường ñược sử dụng ñể thuận tiện trong hậu kỳ âm thanh nhưng phải yêu cầu ñồng bộ với hình.

Page 26

HHỆỆ THTHỐỐNG AUDIO

VIDEO NG AUDIO--VIDEO

• Hệ thống sản xuất hậu kỳ Bộ tạo tiêu ñề Bộ tạo ñồ họa Camera copy

TITL1 GRPH1 Cam1 VCR1 VCR2 VCR3

EFFA

EFFB

E F F B 1

E F F B 2

VCR1

E F F A 1

Kỹ xảo B

VCR2

E F F A 2 Kỹ xảo A

BỘ ðIỀU KHIỂN DỰNG

Page 27

Hình 1-10 Hệ thống Audio – Video sản xuất hậu kỳ

VCR3

HHỆỆ THTHỐỐNG AUDIO

VIDEO NG AUDIO--VIDEO

• Hệ thống cầu hội thảo Monitor

Camera

Bộ xử lý và ñiều khiển số

Micro

Vị trí A

Audio

Vị trí B

Máy chiếu

Monitor

Camera

Micro

Bộ xử lý và ñiều khiển số

Audio

Máy chiếu

Page 28

Hình 1-11 Hệ thống cầu hội thảo

HHỆỆ THTHỐỐNGNG AUDIO

VIDEO AUDIO--VIDEO

• Hệ thống audio video trong PC

– PC dùng ñể trình diễn, lưu trữ, xử lý âm thanh, hình ảnh. – ðiều khiển bằng phần mềm chuyên dụng kết hợp với các

card ñồ họa, xử lý kỷ xảo.

– ða dạng về tiêu chuẩn dẫn ñến khó tương thích. – Có thể yêu cầu nhiều dạng card thích ứng khác nhau và có

thể sử dụng hơn một màn hình ñể hiển thị.

– Dữ liệu có thể yêu cầu nén và giải nén vì phạm vi ứng

dụng khả rộng.

Page 29

MMỘỘT ST SỐỐ VVẤẤN ðN ðỀỀ VVỀỀ TTÍÍN HIN HIỆỆUU

• Tín hiệu và hàm

– Tín hiệu tương tự là hàm theo thời gian. – Biên ñộ âm thanh ñược biểu diễn bằng mức ñộ âm thanh tại

thời ñiểm ñã cho.

– Tín hiệu ñược biểu diễn bằng hàm f(t).

• Tín hiệu có chu kỳ

– Sự lặp lại trong một khoảng thời gian ngắn nhất không ñổi

của tín hiệu gọi là chu kỳ T.

– Tần số là nghịch ñảo của chu kỳ: u=1/T.

Biên ñộ f(t0)

Thời gian t

Page 30

Hình 1-7 Biểu diễn biên ñộ-thời gian

MMỘỘT ST SỐỐ VVẤẤN ðN ðỀỀ VVỀỀ TTÍÍN HIN HIỆỆUU

• Phân tích Fourier

– Trong thực tế, rất ít khi ta có ñược một tín hiệu ñơn tần, mà thông thường là các tín hiệu phức tạp, kết hợp bởi nhiều tần số và các hài của nó.

– Việc phân tích Fourier cho kết quả là tổng của các hàm sin và cosin

của các tần số khác nhau. • Phân tích Fourier một chiều:

∞

F(u)=FR(u)+jFI(u)

−

F u ( )

t e ( )

dtπ 2 ut

= ∫

F u ( )

−∞ ∞

2 F u ( ) R

2 F u ( ) I

t ( )

( ) j F u e

duπ 2 ut

= ∫

)

arctan(

=θ )( u

−∞

)( uF I )( uF R

θ j

u )(

uF )(

u )(

euF )(

uF )( R

jF I

Page 31

MMỘỘT ST SỐỐ VVẤẤN ðN ðỀỀ VVỀỀ TTÍÍN HIN HIỆỆUU

• Phổ tần số

– Sự phân bố của |F(u)| gọi là phổ tần của tín hiệu. – Tín hiệu biến thiên chậm thì phổ tần tập trung ở tần số thấp và ngược lại. Từ ñó hình thành tín hiệu tần số thấp và tần số cao.

Biên ñộ phổ |Fu|

Tần số (u)

Page 32

MMỘỘT ST SỐỐ VVẤẤN ðN ðỀỀ VVỀỀ TTÍÍN HIN HIỆỆUU

• Tín hiệu Audio và Video

– Tín hiệu âm thanh thường là tín hiệu một chiều. – Tín hiệu ảnh là tín hiệu hai chiều. – Tín hiệu Video là tín hiệu 3 chiều. – Với các chiều khác nhau, ta sẽ có số biến khác nhau tương

ứng.

• Chuyển ñổi Fourier 2 chiều

∞

−

π (2

)

),( vuF

,( eyxf )

dxdy

∫ ∫

∞−

π (2

+ ux

) vy

π 2

− e

− ux e

∞

π (2

)

,( yxf

)

),( evuF

− e dudv

∫ ∫

∞−

Page 33

MMỘỘT ST SỐỐ VVẤẤN ðN ðỀỀ VVỀỀ TTÍÍN HIN HIỆỆUU

• Mằu sắc

– Việc kết hợp các màu khác nhau tạo nên một màu mới. Thông thường, chọn các màu cơ bản ñể kết hợp, ví dụ RGB

Red

Magenta

Yellow

White

Blue

Green

Hình 1-8 Lý thuyết 3 màu RGB

Page 34

MMỘỘT ST SỐỐ VVẤẤN ðN ðỀỀ VVỀỀ TTÍÍN HIN HIỆỆUU

• Không gian cảm quan màu

3 chiều: – Con người cảm quan màu sắc ở

các khía cạnh sau:

brightness: ñộ sáng như thế nào. hue: màu nào. saturation: sự tinh khiết

– Sự cảm quan này ñối với mỗi người là mỗi khác biệt, do ñó, không thể so ñược giữa người này với người kia.

Hình 1-9 Cảm quan 3 chiều

Page 35

NNÉÉN DN DỮỮ LILIỆỆUU

• ðại lượng ño thông tin

– Lượng thông tin trong tín hiệu có thể không bằng lượng dữ liệu của nó

mà quan hệ mật thiết với xác suất xuất hiện của nó.

• Tự-thông tin (lượng tin)

– Thông tin ñược mang bởi một biến cố A có xác suất xuất hiện P[A] là:

= −

log

[ P A

]

1 [ P A

]

– Thông tin không (lượng tin =0): • Mặt trời mọc ñằng ñông.

– Lượng tin ít

P[A]

• Máy ñiện thoại di ñộng trong tương lai ñều có khả năng multimedia

– Lượng tin nhiều:

• Trường ðKBK ðN ñược xếp hạng nhất trên thế giới về ðTVT

Page 36

NNÉÉN DN DỮỮ LILIỆỆUU

• Entropy

– Lượng tin trung bình của nguồn tin, một cách gần ñúng, là số bit trung bình của

H S ( )

log

[ P X

]

thông tin yêu cầu ñể biểu diễn các ký hiệu của nguồn tin. – Với nguồn N ký hiệu Xi thì entropy ñược ñịnh nghĩa như sau: = −∑

= 1

• H(S)≥0; ñối với mã hoá nhị phân, H(S) thể hiện mã hoá với số bít/ký hiệu

tối thiểu.

• Ví dụ: Trong một ảnh phân bố ñều ở thang xám (256 mức): pi=1/256, số bit mã hoá

cho mức xám là log2256=8bits. (cid:1)Entropy của ảnh này là H(S)=Σpilog2(1/pi)=8bits/ký hiệu.

Vậy, trong trường hợp phân bố ñều này, mã hoá ñộ dài cố ñịnh sẽ ñạt ñược số

bit tối thiểu. Trong trường hợp tổng quan thì mã hóa ñộ dài cố ñịnh sẽ không hiệu quả.

Page 37

NNÉÉN DN DỮỮ LILIỆỆUU

• Mã hoá ñộ dài cố ñịnh FLC (Fixed-Length Code)

– ðặc ñiểm:

• Sử dụng số bit cố ñịnh ñể biểu diễn mọi ký hiệu của nguồn. • ðơn giản trong quá trình mã hoá/giải mã.

– Ví dụ

• Mã ASCII (American Standard Code for Information Interchange)

sử dụng 8 bits ñể mã hoá các ký tự.

– Truyền chuỗi: DTVT: 68 84 86 84: 01101000 10000100 10000110

10000100

– Nhược ñiểm:

• Không hiệu quả

Page 38

NNÉÉN DN DỮỮ LILIỆỆUU

• Mã hoá ñộ dài thay ñổi VLC (Variable-Length

Code) – ðặc ñiểm

• Sử dụng số bit khác nhau ñể biểu diễn các ký tự khác nhau. • Các ký tự có xác suất xuất hiện cao ñược phân bố bởi từ mã ngắn

và ngược lại.

• Hiệu quả trong việc biểu diễn hơn, nén tốt hơn.

– Ví dụ:

• Mã Morse. • Shannon-Fano. • Huffman. • Mã hoá loạt dài (RLC).

Page 39

NNÉÉN DN DỮỮ LILIỆỆUU

• Thuật toán Shannon-Fano • Ví dụ mô tả thuật toán:

Ký hiệu A B C D E

• Mã hoá theo thuật toán Shannon-Fano: - Sắp xếp các ký tự theo thứ tự giảm dần của tần suất xuất hiện. - Tính xác suất. - ðệ quy làm hai phần, mỗi phần có tổng xác suất gần bằng nhau. Mã hoá

phần trên bằng bit 0 (hoặc bit 1), phần dưới bằng bit 1 (hoặc bit 0).

- Vẽ sơ ñồ cây. - Tính Entropy, số bits mã hoá trung bình và số bit mã hoá thông thường. - Nhận xét.

Page 40

Số lầ xuất hiện 15 7 6 5 6

NNÉÉN DN DỮỮ LILIỆỆUU

Ký hiệu ðếm Mã Tổng bits

A 15 Pi 15/39 Log2(1/pi) 1.38 0 0 30

B 7 7/39 2.48 0 1 14

C 6 6/39 2.7 1 0 12

E 6 6/39 2.7 1 1 0 18

D 5 5/39 2.96 1 1 1 15

H S ( )

log

.1.38

.2.48

2.7

2.96

p i

15 39

6 39

5 39

7 39

= i A 2.19.

( ) H s

•

• Gốc Entropy của nguồn: E 1 ∑ = p i 1 0

(cid:1)

b 2.28 its

Số bits sử dụng trung bình: + 30 14 12 18 15 39 Số bít mã hoá thông thường: log25=3bits • • Nhận xét: Số bits sử dụng trung bình gần

1 1 0 0 1 0 A B C

H(S) thì bộ mã càng hiệu quả.

Page 41

E D

NNÉÉN DN DỮỮ LILIỆỆUU

• Mã hoá Huffman – Nguyên tắc:

Dựa vào mô hình thống kê của dữ liệu gốc, ký tự có xác suất càng cao

thì mã hoá với từ mã càng ngắn.

– Thuật toán:

- Tính tần suất xuất hiện trong dữ liệu gốc, sắp xếp theo thú tự giảm

dần.

- Xét từ dưới lên trên, bắt ñầu từ hai ký tự có xác suất bé nhất, quy ñinh mỗi nhánh là 0 (hoặc 1) hợp lại với nhau thành nút có xác suất bằng tổng hai xác suất hợp thành.

- Lặp lại cho ñến hết.

Page 42

NNÉÉN DN DỮỮ LILIỆỆUU

– Xét ví dụ trên

Ký hiệu Xác suất Mã Tổng bit

A 15/39 1 15 1

– Số bít trung bình: 87/39=2.23 (<2.28) – Hiệu quả hơn Shannon – Fano.

Page 43

0 B 7/39 000 21 0 1 C 6/39 001 18 13/39 0 0 E 6/39 010 18 24/39 1 1 D 5/39 011 15 11/39

NNÉÉN DN DỮỮ LILIỆỆUU

• Mã hoá loạt dài RLC (Run-Length Coding)

– Nguyên lý

• Mã hoá loạt ký hiệu bằng chiều dài và ký hiệu của loạt ñó.

– ðặc ñiểm

• Mã hoá không tổn hao • Mã hoá liên ký tự. • Hiệu quả với một số nguồn tín hiệu, nhất là sau phép chuyển ñổi. Cần 4 bits mã hoá

Cần 2 bits mã hoá

– Ví dụ

• 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 15: (11,13)3 (9,13)15 • mã: (11,3) (9,15)

Bit thô

Run-length Loạt 0 dài

side số bit cần mã hoá

Page 44

NNÉÉN DN DỮỮ LILIỆỆUU

• Mã hoá Lempel-Zip-Welch:

– Nén từ ñiển ñược Jacob Lampel và

0 0

… …

Abraham Ziv ñề xuất năm 1977, phát triển thành họ LZ, LZ77, LZ78.

255 255

– Năm 1984, Terry Welch cải tiến thành

LZW.

256 256 | Clear Code

257 257 | End of Information

258 Chuỗi mới

… …

– Nguyên tắc: Dựa vào việc xây dựng một từ ñiển lưu các chuỗi ký tự có tần suất cao và thay thế bằng một từ mã mới. – LZW tổ chức từ ñiển tốt hơn nên nâng

cao tỷ lệ nén.

– Ví dụ: Xét từ ñiển có ñộ lớn bằng 4096 giá trị từ mã, vậy ñộ dài lớn nhất của từ mã là 12 bits (212=4096).

4095 Chuỗi mới

– Xét chuỗi vào ABCBCABCABCD.

Page 45

256: Mã xoá CC ñể khắc phục tình trạng mẫu lặp lớn hơn 4096, nếu mẫu lặp lớn hơn 4096 thì gởi CC ñể xây dựng từ ñiển cho phần tiếp theo. EoI: Báo hiệu hết một phần nén.

NNÉÉN DN DỮỮ LILIỆỆUU

Output

Index

Symbol

Nil

258

259

260

259

261

BCA

258

262

ABC

• Thuật toán: - w = NIL; - trong khi ñọc ñược ký tự thứ k trong chuối - nếu wk ñã tồn tại trong từ ñiển thì w = wk - còn không thì thêm wk vào trong từ ñiển, mã hoá ngõ ra cho w; w = k; - k=k+1;

263

• Chuỗi ra: 65 66 67 259 258 67

262 68

ABC

262

264

ABCD

• ðầu vào 12ktx8bits=96 bits. • ðầu ra : 5ktx8+3ktx9=67bits. • Tỷ lệ nén: 96/67=1.43

Page 46