Xử lý ảnh số - Nén dữ liệu ảnh part 4

Chia sẻ: Adfgajdshd Asjdaksdak | Ngày: | Loại File: PDF | Số trang:6

Thêm vào BST

Báo xấu

94
lượt xem 13
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Hiệu ứng chuyển động được khống chế bởi tốc độ màn trập của máy ảnh, là thời gian màn trập mở ra để ánh sáng có thể lọt vào cảm biến. Nếu một đối tượng trong bối cảnh chụp chuyển động trong khi màn trập mở, thì nó sẽ mờ nhoe ở hình chụp được. Điều này có nghĩa tốc độ màn trập càng chậm thì càng thấy rõ hiệu ứng chuyển động. Để thay đổi tốc độ màn trập, chúng ta để máy ảnh ở chế độ ưu tiên tốc độ (chữ S hoặc Tv) hoặc ở chế độ chỉnh...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Xử lý ảnh số - Nén dữ liệu ảnh part 4

Entropy H (bits/k´ hiˆu) ye . . .. .. . . ... . . . . . . . . . . 1.0 . ............... ............ . .... . ... . ... . .. ... .. . .. . .. . .. .. . .. .. .. . . .. .. .. . .. . . .. .. .. . .. . . .. .. .. . .. . . .. . .. .. 0.8 . . . . . .. . . . . . . .. .. . . .. . . . . . . . . . . . . .. . . . . . . . .. . . .. . . . .. . . .. . . . .. . . 0.6 .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . .. .. . .. . . .. . . . .. . 0.2 .. . . .. . . .. .. . . . . .. . .. . .. . .. . .. .. .. . .. . .. .. .. . .. . .. . . . .. .. .. . .................................................................................................................................... .. . . . . ... . . . . . . . ... . . . . . . . ... . . . . . . ... . . . . . . . ... . . . . . . ... . . . . . . ..... . . . . . . . . 0.0 . . . 0.0 0.2 0.4 0.6 0.8 1.0 ´ X´c suˆ t pbs a a (a) Thˆng lu.o.ng C (bits/k´ hiˆu) Thˆng tin tu.o.ng hˆ I (bits/k´ hiˆu) ˜ o ye o o ye . . . . . .. . .. .. . ... ... . . . . . . 1 − H (p ) . . . . . . bs e . . . . . . . . . . 1 1.0 . . . . . . .. . ... . . . .. . . . . . ... . .. . .. . . . .. . . . . .. . . .. . .. . .. . . .. . . . .. . . .. .. . . .. . .. . .. .. . .. . . . .. . . . ... . .. . . .. . . . .. . . ... . . . .... .. . . 0.8 . .. . .. . . .. . .. . ..... . ... . . . . . . . . . . . .......... .... . . . . ... . . ... . .. . . .... ..... ..... ..... ..... ..... ................... ..... ..... .... ..... .... .. .. . .. .. . . .. .. .. ..... . . . .... .... . . .... . . . . . . ... ... . . . ... ... . . . . . ... . . . .. . . . ... .. . . . . .. .. . . . .. . . . .. . . .. .. . . . . .. . . . . .. . . . .. . .. . .. . . . . . 0.6 .. . . .. . .. . . . .. . . . . . . . . .. .. . . . .. . . . . . . . . . . . .. .. . . . . .. . . . . .. . . .. . .. . . . . .. . . . . . .. . . . . . .. . . .. . . . . . . .. . . . . . . .. . . . . . . . . .. . . . . . . .. . . . . . 0.4 . .. .. . . . . . . . . . . . . . .. . . .. . .. . . . . . . . . . . . .. . .. . . . . . .. . . . . . . . .. . . . . .. . . . . . . . . . . . . . . . . . . . . . .. . .. . . . . . .. . . . . . . . . . . . . .. . . . . . . . . . . . 0.2 . . . . .. .. . . . . . .. . . . . . . .. .. .. . . .. . .. .. . .. .. . . .. .. . . .. .. . .. . .. .. . . .. . .. .. . .. . . .. .. . . . .. . .. . .. .. .. .. . .. . . .. .. .. .. ... . ... .. .. . .. . .. .. .. . . . . ... . . . . . . ... . . . . . . . ... ...................... . . ... . . . . . . . ... . . . . . . ... . . . . . . . ... . .................................................................................................................................... .. . .. . . ... . .. ................................................................................................................................... . . 0 0.0 .. ... . . . . . . . ... . . . . . . ... . . . . . . . ... . . . . . . ... . . . . . . . ... . . . . . . . ... .... . . . ... . . . . 0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 0.8 1.0 ´ ´ X´c suˆ t pbs a a X´c suˆ t pe a a (b) (c) H` 6.5: Ba h`m thˆng tin nhi phˆn: (a) h`m entropy; (b) thˆng tin tu.o.ng hˆ cua ˜’ o˙ ınh a o .a a o kˆnh d ˆi x´.ng nhi phˆn (BSC); (c) thˆng lu.o.ng cua BSC. ´ ˙ ’ e ¯o u .a o . 159
Ngu.`.i su. dung ` o˙. ’ Nguˆn o . ...... . . ..... .. Kˆnh e .. .... ... ........ ... .. . .... ... ......... . .. ... . . .. .. . . . . . . . . . . . . . . . . . . thˆng tin o thˆng tin o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..... .... ..... .... ..... .... ..... .... ..... ...... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... .... ..... .... ..... .... ..... .... ...... .... ..... .... ..... .... .... .... .... .... .... .... ..... .... ..... .... ..... .... . . .. . . . .. . . . .. . . . ... . . . .. . . . . . . . . . . . . . . . . . . . . . . . . ... . . ... . . .. . . . .. . . . . .. . . . .. . . . .. . ... .. . ... .. . . .. .. . . . .. . . . .. . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .´ . . . . Hˆ thˆng eo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . ` ......... . ........ ......... truyˆn tin e ˙ ’a M˜ ho´ aa .. .... . . .... . . .. ... Giai m˜ ......... .. .. . .. . .´ ` H` 6.6: Mˆ h`nh hˆ thˆng truyˆn tin. ınh oı eo e C´c d .nh l´ m˜ ho´ co. ba n ˙ ’ 6.3.3 a ¯i ya a Trong Phˆn 6.3.2 ch´ng ta d ˜ d` cˆp d e n mˆ h` trong H`nh 6.4 gˆm nguˆn thˆng ` ´ ` ` a u ¯a ¯ˆ a ¯ˆ e. o ınh ı o o o .`.i su. dung. Phˆn n`y ta s˜ thˆm v`o mˆt hˆ thˆng truyˆn tin v` d` ` ..´ ` tin, kˆnh v` ngu o ˙ . ’ e a aa ee a oeo e a ¯ˆ e cˆp d e n ba d .nh l´ vˆ m˜ ho´ v` biˆ’u diˆn thˆng tin. Nhu. H` 6.6 chı ra, hˆ thˆng ˙ ˜ ´ y` a aa e .´ ˙ ’ a ¯ˆ ¯i e e o ınh eo . truyˆn tin d u.o.c ch`n gi˜.a nguˆn thˆng tin v` ngu.`.i su. dung; hˆ thˆng n`y bao gˆm ` ` .´ ` o˙. ’ e ¯. e u o o a eo a o o o a aa o o ˙ a ..’ mˆt bˆ m˜ ho´ v` mˆt bˆ gia m˜. .. -. ˜ Dinh l´ m˜ ho´ khˆng nhiˆu ya a o e Khi kˆnh thˆng tin v` hˆ thˆng truyˆn tin khˆng c´ nhiˆu th` ch´.c nˇng ch´nh cua hˆ ˜ .´ ` ˙e ’. e o ae o e o o e ıua ı thˆng truyˆn tin l` biˆ’u diˆn nguˆn sao cho s´c t´ nhˆ t. V´.i nh˜.ng gia thiˆt n`y, ˙ ˜ ´ ` ` ´ ´ ˙ ’ o e ae e o u ıch a o u ea d. nh l´ m˜ ho´ khˆng nhiˆu hay c`n goi l` d. nh l´ th´. nhˆ t cua Shannon cho biˆt d ˆ ˜ ´’ ´. yua˙ ¯i yaao e o . a ¯i e ¯o d`i trung b`nh cua t`. m˜ nho nhˆ t. ´ ˙ua ’ ˙ ’a a ı Ta goi nguˆn khˆng nh´. l` nguˆn thˆng tin v´.i khˆng gian x´c suˆ t h˜.u han ` ` ´ o o oa o o o o a au . . .i nhau. Nˆu khao s´t t´ hiˆu ra t`. ` ¯ˆ a ´ ´ ˙ a ın e ’ (A, z) v` c´c k´ hiˆu nguˆn d oc lˆp thˆng kˆ v´ aa y e o o eo e u . .. . nguˆn khˆng nh´. l` bˆ gˆm n k´ hiˆu trong bang ch˜. nguˆn th` t´n hiˆu nguˆn l` mˆt ` oao` ` `ao ˙ ’ o o .o ye u o ıı e o . . . . A gˆm J k´ hiˆu, nˆn sˆ phˆn tu. cua An n ˜ ` eo` ´a˙˙ ˙ ’ ’’ vector ngˆu nhiˆn thuˆc A . Do bang ch˜ a e o u o ye . . bˇ ng J n . Gia su. An = {α1 , α2, . . . , αJ n }, trong d ´ mˆi αi l` chuˆi gˆm n k´ hiˆu thuˆc ` ˜ ˜o o` ˙˙ ’’ a ¯o o a ye o . . . A. K´ hiˆu P (α ) l` x´c suˆ t xuˆ t hiˆn vector α = (a , a , . . . , a ). Khi d ´ ´ ´e ˙ ’ bang ch˜ u ye aa a a ¯o . . i i i1 i2 in P (αi ) = P (ai1 )P (ai2 ) · · · P (ain ). -a Dˇt z = (P (αi1 ), P (αi2 ), . . . , P (αJ n ))t . Ta c´ entropy cua nguˆn bˇ ng ` ` ˙ ’ o oa . Jn H (z ) = − P (αi ) log P (αi ). i=1 160
Suy ra H (z ) = nH (z). N´i c´ch kh´c, entropy cua nguˆn thˆng tin khˆng nh´. (tao ra c´c vector ngˆu nhiˆn) ˜ ` ˙ ’ oa a o o o o. a a e gˆ p n lˆn entropy cua nguˆn tao ra t`.ng k´ hiˆu mˆt. M˜ nguˆn nhu. vˆy thu.`.ng goi ´ ` `. ` ˙ ’ a a o u ye o a o a o . . . . . rˆng th´. n cua nguˆn k´ hiˆu d .n. ` y e ¯o a ˙.’ ˙ ’ l` mo o u o . V` thˆng tin riˆng cua t´n hiˆu ra αi l` log[1/P (αi )] nˆn s˜ l` ho.p l´ nˆu ch´ng ´ ˙ı ’ ıo e e a e ea . y e u . . dung t`. m˜ c´ d o d`i nguyˆn l(α ) sao cho ˙ ’ ta m˜ ho´ αi su . aa u a o ¯ˆ a e . i 1 1 log ≤ l(αi ) < log + 1. P (αi ) P ( αi ) Mˆt c´ch tru.c gi´c go.i y rˇ ng t´n hiˆu ra αi d u.o.c biˆ’u diˆn bo.i mˆt t`. m˜ m` d ˆ d`i ˙ a .´` ˜ ˙ ’ oa a ı e ¯. e e o u a a ¯o a . . . . . ˙ a t`. m˜ l` sˆ nguyˆn nho nhˆ t l´.n ho.n thˆng tin riˆng cua αi .4 Nhˆn kˆt qua n`y ´ ´ ´ ’ u aao ˙ ’ ao ˙ ’ ˙a ’ cu e o e ae .i P (α ) v` lˆ y tˆ’ng theo i ta d u.o.c ´˙ v´ o aa o ¯. i Jn Jn Jn 1 1 P (αi ) log ≤ P (αi )l ( αi ) < P (αi ) log + 1; P (αi ) P ( αi ) i=1 i=1 i=1 hay tu.o.ng d u.o.ng ¯ H (z ) ≤ Lavg < H (z ) + 1, trong d ´ Lavg l` d ˆ d`i trung b` cua c´c t`. m˜ biˆ’u diˆn cho c´c t´n hiˆu ra αi . T´.c ˙ ˜ ınh ˙ a u a e ’ ¯o a ¯o a e aı e u . . l` a n J Lavg = P (αi ) l (αi ) . i=1 u´ ` Ch´ y rˇ ng H (z )/n = H (z). Suy ra a Lavg 1 H (z) ≤ < H (z) + . n n Vˆy a . Lavg = H (z). lim n→∞ n Phu.o.ng tr`nh n`y ch´ l` nˆi dung cua d inh l´ th´. nhˆ t cua Shannon d oi v´.i nguˆn ´’ ´ ` ˙ ¯. ’ yua˙ ı a ınh a o ¯ˆ o o . thˆng tin khˆng nh´.. Kˆt qua n`y chı ra rˇ ng c´ thˆ’ lˆ y n d u l´.n dˆ’ n xˆ p xı Lavg ˙´ ˙ ` ´ ´˙ ˙a ’ ˙ ’ ¯ ˙ o ¯e ’ ’ o o o e a o ea a .o.c suy t`. gia thiˆt c´c k´ hiˆu nguˆn d oc lˆp thˆng kˆ, ˙ ’ ´ ` ¯ˆ a ´ u˙ ’ H (z). Mˇc d` khˇng d .nh d . aua ¯i ¯u eaye o o e . . .. nhu.ng ta dˆ d`ng mo. rˆng d ˆi v´.i nh˜.ng nguˆn tˆ’ng qu´t ho.n, chˇng han v´.i nguˆn ˙ ˜a ˙ ’ ´ `o ` ˙ o ¯o o ’. e u o a a .o o . xuˆ t hiˆn cua k´ hiˆu a c´ thˆ’ phu thuˆc v`o m k´ hiˆu ˙ ´ e ˙ y e jo e ’ Markov bˆc m trong d ´ su a a ¯o . oa ye . . . . . . .´.c. C´c nguˆn Markov thu.`.ng d .o.c su. dung d oi v´.i c´c mˆ h`nh c´ mˆi tu.o.ng ` ´ ´ ˙. ’ tru o a o o ¯u . ¯ˆ o a oı oo C´ thˆ’ xˆy du.ng m˜ c´ thˆ’ giai m˜ t´.c th`.i thoa d iˆu kiˆn n`y. 4 ˙ ˙ ’ au ˙ ¯` ao e ˙ ’e o ea o ea . . 161
T`. m˜ -o a Ky hiˆu ´e P ( αi ) I ( αi ) l (αi ) ua Dˆ d`i . . ` αi nguˆn o Mo. rˆng th´. nhˆ t ´ ˙o ’. u a α1 a1 2/3 0.59 1 0 1 α2 a2 1/3 1.58 2 1 1 Mo. rˆng th´. hai ˙o ’. u α1 a1 a1 4/9 1.17 2 0 1 α2 a1 a2 2/9 2.17 3 10 2 α3 a2 a1 2/9 2.17 3 110 3 α4 a2 a2 1/9 3.17 4 111 3 Bang 6.2: V´ du m˜ ho´ nguˆn mo. rˆng. ` ˙ ’ ˙o ’. ı.a a o quan gi˜.a c´c pixel trong anh. V` H (z) l` mˆt cˆn du.´.i cua Lavg nˆn ta c´ thˆ’ d inh ˙ ˙ ’ o˙ ’ ua ı aoa e o e ¯. .. n .o.ng ´’ a˙ ngh˜ hiˆu suˆ t cua qu´ tr`nh m˜ ho´ l` d . i lu . ıa e aı a a a ¯a . H (z) η=n . Lavg V´ du 6.3.3 X´t nguˆn thˆng tin khˆng nh´. c´ bang ch˜. A = {a1, a2} v´.i c´c x´c ` oo˙ ’ ı. e o o o u oaa oa` ´ ` ˙ ’ suˆ t P (a1 ) = 2/3 v` P (a2) = 1/3. Entropy cua nguˆn n`y bˇ ng 0.918 bits/k´ hiˆu. a a a ye . ˙u diˆn c´c k´ hiˆu a1 v` a2 bˇ ng c´c t`. m˜ 0 v` 1 th` Lavg = 1 bit/k´ hiˆu v` ’ ˜aye ` ´ Nˆu biˆ e e e a a aua a ı yea . . ´’ a˙ hiˆu suˆ t cua m˜ l` η = (1)(0.918)/1 = 0.918. e aa . Bang 6.2 tˆ’ng ho.p m˜ nhi phˆn v` m˜ mo. rˆng v´.i n = 2 (phˆn cuˆi cua bang) ˙ ` ´’˙ ˙ ’ a . a a a ˙o ’. o˙ ’ o o a . .i c´c x´c suˆ t tu.o.ng u.ng l` 4/9, 2/9, 2/9 v` 1/9. ` ´ ´ gˆm bˆn vector α1, α2 , α3 v` α4 v´ a a o o a o a ´ a a Trong tru.`.ng ho.p n`y, d o d`i trung b`nh cua c´c t`. m˜ l` 17/9 1.89 bit/k´ hiˆu. ˙ a u aa ’ o a ¯ˆ a ı ye . . . . rˆng gˆ p hai lˆn entropy cua nguˆn ban d` u, t´.c l` bˇ ng 1.83 u a` ` ´ ` ` ˙ ’ ˙. ’ ˙ ’ Entropy cua nguˆn mo o o a a o ¯ˆ a a bit/k´ hiˆu. Do d ´ hiˆu suˆ t cua m˜ ho´ nguˆn mo. rˆng l` η = 1.83/1.89 0.97 l´.n ´’ ` a˙ ˙o ’. ye ¯o e aa o a o . . .n hiˆu suˆ t cua m˜ ho´ nguˆn ban d` u. M˜ ho´ nguˆn mo. rˆng giam sˆ bit trung ´’ ` ` ´ a˙ ˙o ’. ˙’ ho e aa o ¯ˆa aa o o . b`nh trˆn k´ hiˆu t`. 1 bit/k´ hiˆu xuˆng c`n 1.89/2 0.92 bit/k´ hiˆu. ´ ı eyeu ye o o ye . . . -. ˜ Dinh l´ m˜ ho´ c´ nhiˆu ya ao e Nˆu kˆnh trong H` 6.6 bi nhiˆu hoˇc c´ thˆ’ xay ra lˆi trong d .`.ng truyˆn th` vˆ n ˙’ ˜ ˜ ´ ` ´ aoe˙ ee ınh e o ¯u o e ıa . . . biˆ’u diˆn thˆng tin mˆt c´ch s´c t´ch sang viˆc m˜ ho´ sao d` quan tˆm thay d ˆ’i t` e ¯o u ˙ ˙ ˜ ¯ˆ e a e o oa uı e aa . . .o.c d˜. liˆu truyˆn. Mˆt vˆ n d` tu. nhiˆn d at ra l`: l`m sao d e’ ´t cho c´ thˆ’ tin cˆy d . u e ˙ ˙ ` .´e oe a ¯u e o a ¯ˆ . e ¯ˇ aa ¯ˆ ı . . . ˜ ´ ` lˆi nhˆ t khi truyˆn thˆng tin? o a e o 162
V´ du 6.3.4 X´t kˆnh d oi x´.ng nhi phˆn (BSC) c´ x´c suˆ t lˆi pe = 0.01 (t´.c l` 99 ´˜ ´ ı. ee ¯ˆ u .a oa ao ua . nguˆn khi d .o.c truyˆn qua kˆnh l` ch´ x´c). Mˆt c´ch d .n ` ` ` phˆn trˇm c´c k´ tu a a a y. o ¯u . e e a ınh a o a ¯o . gian d e’ tˇng d o tin cˆy khi truyˆn thˆng tin l` lˇp lai mˆi thˆng b´o hay k´ hiˆu nhi ˙ ˜ ` ˙ ¯ˆ a ¯ˆ ’ a e o aa . o o a ye . . . . . . chˇng han, thay v` truyˆn 0 hoˇc 1, ch´ng ta m˜ ho´ th`nh ˙ ’ ` u lˆn. Gia su a ` ` ˙˙ ’’ phˆn nhiˆ a a e ı e a u aaa . . ˜ ` ¯i a ´ ˙’ c´c thˆng b´o 000 v` 111 v` truyˆn d c´c thˆng b´o n`y. X´c suˆ t khˆng xay ra lˆi a o a a a e o aa a a o o 3 3 ` khi truyˆn thˆng b´o bˇ ng c´ch lˇp ba lˆn k´ hiˆu ban d` u l` (1 − pe ) = pe . X´c ` ` e o aa a a aye ¯ˆ a a ¯ a . . 2 2; 3 .˜ ˜ o` ˜a ´’ ´’ a˙ a˙ suˆ t xay ra mˆt lˆi l` 3pe pe ; hai lˆi l` 3pe pe v` x´c suˆ t xay ra ba lˆi bˇ ng pe . V` ooa ¯ oa ¯ aa ı x´c suˆ t khi truyˆn bi mˆt lˆi nho ho.n 50 phˆn trˇm nˆn c´c thˆng b´o nhˆn d .o.c .˜ ´ ` ` ˙ ’ a a e .oo a a ea o a a ¯u . . . dung luˆt sˆ d ong. Do d o x´c suˆ t giai m˜ sai mˆt t`. m˜ (gˆm ba c´ thˆ’ giai m˜ su . ˙ ’ a˙ .´ ´ oua` oe˙ ’ ˙ ’a a o ¯ˆ ¯´ a a o . k´ hiˆu) bˇ ng tˆ’ng x´c suˆ t khi xay ra hai lˆi v´.i x´c suˆ t xay ra ba lˆi, t´.c l` bˇ ng ˙ ` ˜ o u a` ˜ ´ ´’ ˙ ’ a˙ ye a o a a ooa a . p3 + 3pe p2 . Khi khˆng xay ra lˆi hoˇc chı c´ mˆt lˆi th` giai m˜ theo luˆt sˆ d ˆng cho ˜ .˜ .´ ˙ ’ ˙o o o ’ ı˙ ’a ¯e o o a a o ¯o . e l`.i giai dung. V´.i pe = 0.01 th` x´c suˆ t xay ra lˆi khi truyˆn giam xuˆng c`n 0.0003. ˜ ´’ ` ´ ˙ ¯´ ’ a˙ ˙ ’ o o ıa o e o o Bˇ ng c´ch mo. rˆng phu.o.ng ph´p m˜ lˇp trˆn, ch´ng ta c´ thˆ’ l`m cho lˆi to`n ˙ ` ˜ ˙o ’. a a a aa e u o ea oa . bˆ trong qu´ tr` truyˆn thˆng nho theo mong muˆn. Trong tru.`.ng ho.p tˆ’ng qu´t, ˙ ` ´ ˙ ’ o a ınh e o o o .o a . .c hiˆn d ` u n`y bˇ ng c´ch m˜ ho´ mo. rˆng th´. n cua nguˆn su. ch´ng ta c´ thˆ’ thu˙ e ¯iˆ a ` ` a a ˙o ’. ˙ ’ o˙ ’ u oe. e a a u . dung c´c d˜y d ˆ d`i r t`. K k´ hiˆu, trong d o K r ≥ J n . L`.i giai o. d ˆy l` chı chon ϕ ˙ ˙ ¯a a ˙ . ’’ ’ a a ¯o a u ye ¯´ o . . . . m˜ ho.p lˆ v` ra quyˆt d inh sao cho x´c suˆ t giai r ´ ´ ˙a ’ ˙ ’ d˜y trong K kha nˇng l`m c´c t` a . e a a a au e ¯. a a . m˜ dung l` tˆi u.u. Trong v´ du tru.´.c, lˇp mˆi k´ hiˆu ba lˆn l` tu.o.ng d .o.ng v´.i ˜ ´ `a a ¯´ ao ı. oa oye a ¯u o . . . dung hai t`. m˜ ho.p lˆ 000 v` 111 trong sˆ tˆ t ca 23 = 8 ` ´´ ’ o˙ ’ oa ˙ m˜ ho´ k´ hiˆu nguˆn su . a aye ua.e a . . kha nˇng. Nˆu nhˆn d .o.c d˜y ba bit khˆng phai t`. m˜ ho.p lˆ, su. dung luˆt sˆ d ong ´ .´ ˙a ’ ˙ua.e˙. ’ .’ e a ¯u . a o a o ¯ˆ . .o.c truyˆn. Chˇng han, nˆu nhˆn d .o.c 101, th` kˆt luˆn ˙ ’ ` ´ ´a ch´ng ta s˜ x´c d inh bit d . u e a ¯. ¯u e a e a ¯u . ıe . . . ˜i bit d u.o.c truyˆn l` 111 v` k´ hiˆu muˆn gu.i l` 1. `a ´ ˙a ’ chuˆ o ¯. e ay e o . Nguˆn thˆng tin khˆng nh´. sinh ra thˆng tin v´.i tˆc d ˆ (theo c´c d o.n vi thˆng ` ´. o o o o o o o ¯o a¯ .o tin trˆn k´ hiˆu) bˇ ng entropy H (z) cua n´. Nguˆn mo. rˆng th´. n cung cˆ p thˆng ` ` ´ ˙o ’ ˙o ’. eye a o u a o . .i tˆc d ˆ H (z )/n d o.n vi thˆng tin trˆn mˆt k´ hiˆu. Nˆu thˆng tin d .o.c m˜ o´. ´ tin v´ o ¯o ¯ .o e oye e o ¯u . a . . ho´, nhu. trong v´ du tru.´.c, tˆc d ˆ cu.c d ai cua thˆng tin d .o.c m˜ ho´ l` (log ϕ)/r; ´. o ¯o . ¯ . ˙ ’ a ı. o o ¯u . a aa . m˜ d u.o.c su. dung dˆ’ m˜ ho´ nguˆn c´ x´c suˆ t bˇ ng nhau. ˙ ´` a` ` oa ´a dˆ u bˇ ng xay ra khi ϕ t` a ¯ . ˙ . ˙ ’ ’ aa u ¯e a a o Do d ´, bˆ m˜ gˆm ϕ t`. m˜, mˆi t`. m˜ c´ d ˆ d`i r, goi l` c´ tˆc d ˆ ˜ ¯o o a ` ´. o u a o u a o ¯o a . a o o ¯o . . ϕ R = log . r Dinh l´ th´. hai cua Shannon, c`n goi l` d.nh l´ m˜ ho´ c´ nhiˆu, chı ra rˇ ng, v´.i bˆ t -. ˜ ` ´ ˙ ’ ˙ ’ yu o . a ¯i y a ao e a oa k` R < C, trong d ´ C l` thˆng lu.o.ng cua kˆnh khˆng nh´. v´.i ma trˆn Q,5 tˆn tai sˆ ` .o ´ ˙e ’ y ¯o ao o oo a o . . . m˜ d ˆ d`i r n`o d o v´.i tˆc d ˆ R sao cho x´c suˆ t khi ao a` ´. ´ nguyˆn r v` bˆ m˜ gˆm c´c t` a ¯o a e o au a ¯´ o o ¯o a a . . Kˆnh khˆng nh´. l` kˆnh m` phan u.ng cua n´ d ˆi v´.i k´ hiˆu v`o hiˆn th`.i khˆng phu thuˆc v`o 5 ´ ˙´ ’ ˙ o ¯o o y e a ’ e o oae a e o o oa . . . . ˙ n u.ng cua kˆnh d oi v´.i c´c k´ hiˆu v`o tru.´.c d ´. ´ ’´ ˙e ’ pha ¯ˆ o a y e a o ¯o . 163
giai m˜ sai mˆt d˜y r k´ hiˆu nho ho.n hoˇc bˇ ng v´.i moi > 0 cho tru.´.c. Do d ´ .` ˙ ’a ˙’ oa ye aa o o ¯o . . . .i d ` u kiˆn tˆc d ˆ thˆng b´o d .o.c m˜ ho´ nho ho.n thˆng lu.o.ng cua kˆnh th` x´c .´. ˙ ’ ˙e ’ v´ ¯iˆ o e e o ¯o o a ¯u . aa o ıa . suˆ t xay ra lˆi c´ thˆ’ l`m nho tu` y. ˙ ˜ ´’ a˙ ˙ y´ ’ o o ea -. ` Dinh l´ m˜ ho´ nguˆn ya a o C´c d .nh l´ d .o.c mˆ ta trˆn thiˆt lˆp gi´.i han d e’ truyˆn thˆng khˆng xay ra lˆi d oi ˙ ˜´ ´. ` o˙ e’ ˙ ’ a ¯i y ¯u . ea o . ¯ˆ e o o o ¯ˆ v´.i c´c kˆnh tin cˆy c˜ng nhu. c´c kˆnh khˆng tin cˆy. Trong phˆn n`y, ch´ng ta x´t ` oae au ae o a aa u e . . .ng qu´ tr` truyˆn thˆng l`m mˆ t thˆng tin. Trong nh˜.ng tru.`.ng ˜ ` ´ kˆnh khˆng lˆi nhu e o o a ınh e o a a o u o ho.p n`y, ch´.c nˇng ch´ cua hˆ thˆng truyˆn thˆng l` “n´n thˆng tin”. V´.i hˆu hˆt ’.´ ` o` ´ ınh ˙ e o a ua e o ae o ae . c´c tru.`.ng ho.p, lˆi trung b`nh trong qu´ tr` n´n khˆng vu.o.t qu´ m´.c cho ph´p cu.c ˜ a o o ı a ınh e o au e. . . d ai D. Ch´ng ta muˆn x´c d inh tˆc d ˆ nho nhˆ t v´.i d ` u kiˆn cho tru.´.c tiˆu chuˆ’n ˙ ´ ´. ´ ˙ ’ a o ¯iˆ ¯. u o a ¯. o ¯o e e o e a . trung thu.c, nh˜.ng thˆng tin n`o vˆ nguˆn c´ thˆ’ truyˆn d . t dˆn ngu.`.i su. dung. B`i ˙ a` `oe ` ¯a ¯e ´ o˙. ’ u o e o e a . to´n n`y thuˆc l˜nh vu.c cua l´ thuyˆt rate distortion trong l´ thuyˆt thˆng tin. ´ ´ ˙y ’ aa oı e y e o . . Gia su. nguˆn thˆng tin v` bˆ phˆn giai m˜ trong H` 6.6 d .o.c x´c d .nh tu.o.ng ` ˙˙ ’’ ˙a ’ o o ao a ınh ¯u . a ¯i . . u.ng bo.i c´c khˆng gian x´c suˆ t h˜.u han (A, z) v` (B, v). Gia thiˆt kˆnh cua H`nh ´ ´ ˙a ’ ˙ ’ ˙ ’ ´ o a au a ee ı . . z sang v 6.6 khˆng bi nhiˆu. Khi d o ma trˆn biˆn d o’i kˆnh thuˆn Q chuyˆ’n d o’i t` ˙ ˙ ˙ ˜ ´ o e ¯´ a e ¯ˆ e a e ¯ˆ u . . . c´ thˆ’ xem ch´ l` qu´ tr` m˜ ho´-giai m˜. Do qu´ tr` m˜ ho´-giai m˜ l` x´c ˙ ınh a a ınh a a ˙ ’ a ınh a a ˙ ’ oe a aa a . nhˆn tao mˆ h`nh cho t´c d ong cua n´n o˙ o e ’. ˙e ’ d inh, ma trˆn Q mˆ ta mˆt kˆnh khˆng nh´ ¯. a o o a. oı a ¯ˆ . . v` giai n´n thˆng tin. Mˆi khi nguˆn sinh ra k´ hiˆu aj , n´ d .o.c biˆ’u diˆn bo.i mˆt ˙ ˜ ˜ ` a˙e ’ ˙ ’ o o o ye o ¯u . e e o . . . m˜ v` sau d o d u.o.c giai m˜ th`nh k´ hiˆu ra b v´.i x´c suˆ t q (xem Phˆn 6.3.2). ´ ` ˙ ’aa t` a a u ¯´ ¯ . ye ko a a kj a . B`i to´n m˜ ho´ nguˆn sao cho distorsion trung b` nho ho.n D d `i hoi phai c´ ` ˙ ’ ¯o ˙ ’ ˙o ’ aa aa o ınh .ng gi´ tri distortion d ˆi v´.i moi xˆ p xı c´ thˆ’ tai d` u ra cua ˙ ´ ´ ´’ . a ˙ o e . ¯ˆ ˙’ c´c nguyˆn tˇc xˆy du a eaa a. ¯o o a . nguˆn. V´.i tru.`.ng ho.p d .n gian cua nguˆn ban d` u (nguˆn mo. rˆng th´. nhˆ t) ta c´ ` ` ` ´ ˙’ ˙ ’ ˙o ’. o o o . ¯o o ¯ˆa o ua o . dung h`m chi ph´ khˆng ˆm ρ(a , b ), goi l` d ˆ d o distorsion, l` ph´ tˆ’n phai thˆ’ su . ˙’ ˙ e˙ ˙ ’ a ıoa . a ¯o ¯ a ıo . jk tra dˆ’ t´i tao lai t´ hiˆu nguˆn aj khi giai m˜ ra bk . T´ hiˆu ra cua nguˆn l` ngˆu ’˙ ˜ ` `aa ˙ ¯e a . . ın e ˙ ’a ˙ ’ o ın e o . . ˜ ´ ınh, k´ hiˆu d(Q), nhiˆn nˆn distortion c˜ng l` mˆt biˆn ngˆu nhiˆn m` gi´ tri trung b` ee u ao e a e aa. ye . . ` bˇ ng a J K d(Q) = ρ(aj , bk )P (aj , bk ) j =1 k =1 J K = ρ(aj , bk )P (aj )qkj . j =1 k =1 ` ´ ˙ ’ K´ hiˆu d(Q) nhˇ m nhˆ n manh distortion l` mˆt h`m trung b`nh cua qu´ tr`nh m˜ ye a a aoa ı aı a . . . .o.c mˆ h`nh bo.i ma trˆn Q. Thu tuc m˜ ho´-giai m˜ goi l` D−chˆ p ´ a˙ ’ ˙ ’ ˙. ’ aa˙ ’ ho´-giai m˜ d u . a¯ oı a a.a a . 164