Cơ sở lý thuyết truyền tin 2004 - Chương 5: Mã hóa nguồn

Chia sẻ: Nguyen Ngoc Yen | Ngày: | Loại File: PDF | Số trang:68

Thêm vào BST

Báo xấu

150
lượt xem 34
download

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

La phép biến đổi đầu tiên cho nguồn tin nguyên thủy. Đầu vào của phép biến đổi này có thể là: nguồn rời rạc hoặc nguồn tin liên tục.

Chủ đề:

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

Lưu

Nội dung Text: Cơ sở lý thuyết truyền tin 2004 - Chương 5: Mã hóa nguồn

Cơ s Lý thuy t Truy n tin-2004 Hà Qu c Trung1 1 Khoa Công ngh thông tin Đ i h c Bách khoa Hà n i Chương 5: Mã hóa ngu n 0. 1/ 64
Chương 5: Mã hóa ngu n 1 Mã hóa ngu n r i r c không nh 2 Mã hóa cho ngu n d ng r i r c 3 Cơ s lý thuy t mã hóa ngu n liên t c 4 Các k thu t mã hóa ngu n liên t c Chương 5: Mã hóa ngu n 0. 2/ 64
Khái ni m chung Là phép bi n đ i đ u tiên cho ngu n tin nguyên th y Đ u vào c a phép bi n đ i này có th là: ngu n tin r i r c ho c ngu n tin liên t c Trong c hai trư ng h p m c đích chính c a phép mã hóa ngu n là bi u di n thông tin v i tài nguyên t i thi u Các v n đ c n nghiên c u Mã hóa ngu n r i r c Mã hóa ngu n liên t c Nén d li u Chương 5: Mã hóa ngu n 1. M t s khái ni m chung 3/ 64
1.2.Mã hóa ngu n Ngu n thông tin t o ra các đ u ra m t cách ng u nhiên Ngu n r i r c: t o ra m t chu i các ký hi u ng u nhiên Ngu n không nh : các ký hi u xu t hi n m t cách đ c l p v i nhau Ngu n có nh : các ký hi n xu t hi n ph thu c vào các ký hi u đã xu t hi n trư c đo Ngu n d ng các m i liên h th ng kê gi a các th i đi m không ph thu c vào th i gian V i ngu n r i r c, v n đ cơ b n là thay đ i b ng ch cái và phân b xác su t đ gi m b t s lư ng ký hi u c n dùng Ngu n liên t c t o ra m t tín hi u, m t th hi n c a m t quá trình ng u nhiên Ngu n liên t c có th đư c bi n thành m t chu i các bi n ng u nhiên (liên t c) b ng phép l y m u Lư ng t hóa cho phép bi n đ i các bi n ng u nhiên này thành các bi n ng u nhiên r i r c, v i sai s nh t đ nh Các k thu t mã hóa ngu n tương t Chương 5: Mã hóa ngu n 1. M t s khái ni m chung 4/ 64
2. Mã hóa ngu n r i r c không nh 1 Mã hóa ngu n r i r c không nh Mô hình toán h c ngu n thông tin Mã hóa v i t mã có đ dài c đ nh Mã hóa v i t mã có đ dài thay đ i 2 Mã hóa cho ngu n d ng r i r c 3 Cơ s lý thuy t mã hóa ngu n liên t c 4 Các k thu t mã hóa ngu n liên t c Chương 5: Mã hóa ngu n 2. Mã hóa ngu n r i r c không nh 5/ 64
Mô hình toán h c ngu n r i r c V i ngu n r i r c c n quan tâm Entropy c a ngu n tin nguyên th y Entropy c a ngu n sau khi mã hóa Hi u qu c a phép mã hóa Gi i h n c a hi u qu mã hóa Xét m t ngu n r i r c không nh , sau m t th i gian ts t o ra ký hi u xi trong L ký hi u v i các xác su t xu t hi n là P(i) Đ cho đơn gi n, ch xét trư ng h p mã hi u nh phân. Khi đó: lư ng tin=lư ng bít= s ký hi u nh phân V i mã hi u có cơ s l n hơn 2, có th m r ng các k t qu thu đư c. Chương 5: Mã hóa ngu n 2. Mã hóa ngu n r i r c không nh 6/ 64
2.2.Mã hóa v i t mã có đ dài c đ nh Nguyên t c: Mã hóa m t ký hi u ngu n thành m t chu i ký hi u mã có đ dài xác đ nh R Đ đ m b o phép mã hóa là 1-1, m t ký hi u ngu n tương ng v i 1 chu i ký hi u nh phân. S lư ng chu i nh phân ph i l n hơn s ký hi u ngu n 2R ≥ L hay R ≥ log2 L N u L là lũy th a c a 2 thì giá tr nh nh t c a R là log2 L N u L không là lũy th a c a 2, giá tr đó là log2 L + 1 Như v y R ≥ H(X ) H(X ) . Hi u su t c a phép mã hóa R ≤1 T c đ l p tin đ u ra s l n hơn t c đ l p tin đ u vào Chương 5: Mã hóa ngu n 2. Mã hóa ngu n r i r c không nh 7/ 64
Tăng hi u qu mã hóa Hi u qu mã hóa đ t giá tr c c đ i khi L là lũy th a c a 2 Ngu n tin ban đ u đ ng xác su t N u ngu n tin ban đ u đ ng xác su t, nhưng L không là lũy th a c a 2, s lư ng ký hi u nh nh t s là H(X ) + 1. Hi u qu c a ngu n là H(X ) H(X ) ≥ H(X ) + 1 H(X ) + 1 Đ tăng hi u qu , c n tăng lư ng tin cho m i l n mã hóa: mã hóa cùng m t lúc J ký hi u. Hi u qu mã hóa JH(X ) JH(X ) ≥ JH(X ) + 1 JH(X ) + 1 Bi u th c trên ti n t i 1 khi J ti n t i vô cùng K t qu này ch đúng cho ngu n đ ng xác su t. Phép mã hóa không có sai s , m i chu i ký hi u ngu n luôn luôn tương ng v i 1 t mã duy nh t. Chương 5: Mã hóa ngu n 2. Mã hóa ngu n r i r c không nh 8/ 64
Tăng hi u qu b ng mã hóa có sai s Trong trư ng h p ngu n không đ ng xác su t, đ có th ti m c n v i hi u qu t i đa (1), c n ch p nh n m t sai s nào đó Xét LJ chu i ký hi u ngu n có đ dài J, mã hóa b ng chu i các ký hi u nh phân có đ dài R, 2R < LJ Như v y còn LJ − 2R t h p ký hi u ngu n không có t mã tương ng S d ng 2R − 1 t mã mã hóa 2 − 1 chu i ký hi u ngu n Các chu i ký hi u ngu n còn l i (ch n các chu i có xác su t nh nh t), đư c mã hóa b ng 1 t mã chung N u ngu n phát m t chu i các ký hi u trùng v i các chu i ký hi u có xác su t th p, s có sai s . G i xác su t sai s là Pe Liên quan gi a Pe , R, J? Chương 5: Mã hóa ngu n 2. Mã hóa ngu n r i r c không nh 9/ 64
Đ nh lý mã hóa ngu n 01 Theorem Cho U là m t ngu n tin có Entropy h u h n. Mã hóa các kh i J ký hi u c a ngu n thành các t mã N ký hi u nh phân. là m t s dương b t kỳ Xác su t sai s có th nh tùy ý n u N R= ≥ H(U) + J Ngư c l i, n u N R= ≤ H(U) − J thì sai s s ti n t i 1 khi J ti n t i vô h n T c đ l p tin c a đ u ra luôn luôn l n hơn c a đ u vào Chương 5: Mã hóa ngu n 2. Mã hóa ngu n r i r c không nh 10/ 64
Ch ng minh đ nh lý Ch ng minh. Ph n thu n Coi t p h p các chu i ký hi u ngu n mà I(uJ ) | − H(U)| ≥ J là các chu i ký hi u ngu n ánh x vào cùng m t t mã. C n ch ng minh 1 Xác su t xu t hi n c a các t mã nói trên có th bé tùy ý khi L l n tùy ý (hi n nhiên, limJ→∞ I(uJ ) = H(U) ) J 2 Các chu i ký hi u còn l i có th đư c mã hóa chính xác (1-1) v i R = N ≥ H(X ) + J Ph n đ o: Ch ng minh xác su t sai s ti n đ n 1 (?) Chương 5: Mã hóa ngu n 2. Mã hóa ngu n r i r c không nh 11/ 64
Ch ng minh đ nh lý Ch ng minh. Ph n thu n Coi t p h p các chu i ký hi u ngu n mà I(uJ ) | − H(U)| ≥ J là các chu i ký hi u ngu n ánh x vào cùng m t t mã. C n ch ng minh 1 Xác su t xu t hi n c a các t mã nói trên có th bé tùy ý khi L l n tùy ý (hi n nhiên, limJ→∞ I(uJ ) = H(U) ) J 2 Các chu i ký hi u còn l i có th đư c mã hóa chính xác (1-1) v i R = N ≥ H(X ) + J Ph n đ o: Ch ng minh xác su t sai s ti n đ n 1 (?) Chương 5: Mã hóa ngu n 2. Mã hóa ngu n r i r c không nh 11/ 64
Ch ng minh đ nh lý Ch ng minh. Ph n thu n Coi t p h p các chu i ký hi u ngu n mà I(uJ ) | − H(U)| ≥ J là các chu i ký hi u ngu n ánh x vào cùng m t t mã. C n ch ng minh 1 Xác su t xu t hi n c a các t mã nói trên có th bé tùy ý khi L l n tùy ý (hi n nhiên, limJ→∞ I(uJ ) = H(U) ) J 2 Các chu i ký hi u còn l i có th đư c mã hóa chính xác (1-1) v i R = N ≥ H(X ) + J Ph n đ o: Ch ng minh xác su t sai s ti n đ n 1 (?) Chương 5: Mã hóa ngu n 2. Mã hóa ngu n r i r c không nh 11/ 64
Ch ng minh đ nh lý Ch ng minh. Ph n thu n Coi t p h p các chu i ký hi u ngu n mà I(uJ ) | − H(U)| ≥ J là các chu i ký hi u ngu n ánh x vào cùng m t t mã. C n ch ng minh 1 Xác su t xu t hi n c a các t mã nói trên có th bé tùy ý khi L l n tùy ý (hi n nhiên, limJ→∞ I(uJ ) = H(U) ) J 2 Các chu i ký hi u còn l i có th đư c mã hóa chính xác (1-1) v i R = N ≥ H(X ) + J Ph n đ o: Ch ng minh xác su t sai s ti n đ n 1 (?) Chương 5: Mã hóa ngu n 2. Mã hóa ngu n r i r c không nh 11/ 64
Ch ng minh đ nh lý Ch ng minh. Ph n thu n Coi t p h p các chu i ký hi u ngu n mà I(uJ ) | − H(U)| ≥ J là các chu i ký hi u ngu n ánh x vào cùng m t t mã. C n ch ng minh 1 Xác su t xu t hi n c a các t mã nói trên có th bé tùy ý khi L l n tùy ý (hi n nhiên, limJ→∞ I(uJ ) = H(U) ) J 2 Các chu i ký hi u còn l i có th đư c mã hóa chính xác (1-1) v i R = N ≥ H(X ) + J Ph n đ o: Ch ng minh xác su t sai s ti n đ n 1 (?) Chương 5: Mã hóa ngu n 2. Mã hóa ngu n r i r c không nh 11/ 64
Ch ng minh ph n thu n G i t p h p các ký hi u còn l i là T . V i m i uJ ∈ T có I(uJ ) − H(U) ≤ J I(uJ ) H(U) − ≤ ≤ H(U) + J 2−J(H(U)− ) ≥ P(uJ ) ≥ 2−J(H(U)+ ) Chú ý 1 ≥ P(T ) ≥ MT min(P(uJ )) ≥ MT 2−J(H(U)+ ) Có MT ≤ 2J(H(U)+ ) V y n u ch n chu i nh phân có đ dài t i thi u là Nm in = log2 2J(H(U)+ ) = J(H(U) + ) s có ánh x 1-1 gi a T và t p các t mã N ký hi u nh phân Phép ánh x chung s có sai s nh tùy ý Pe = | I(uJ ) − H(U)| ≥ J Chương 5: Mã hóa ngu n 2. Mã hóa ngu n r i r c không nh 12/ 64
Ch ng minh ph n đ o Ch n N ≤ J(H(U) − 2 ). Xét m t phép mã hóa b t kỳ P(T ) + P(T ) + Pe = 1 Trong đó P(T ) là xác su t đ m i m t chu i ký hi u trong T có m t t mã P(T ) là xác su t đ m t chu i ký hi u ngoài T có m t t mã Xác su t l i (t n t i chu i ký hi u không có t mã) T ng c ng có 2N t mã, m i t mã s tương ng v i m t t trong T có xác su t nh hơn 2−J(H(U)− ) , v y xác su t đ m t t trong T có m t t mã là )2−J(H(U)−2 ) P(T ) = 2−J(H(U)− ) 2N ≤ 2−J(H(U)− = 2−J Chú ý P(T ) ti n t i 0 khi j ti n t i vô cùng. V y Pe ti n t i 1 Chương 5: Mã hóa ngu n 2. Mã hóa ngu n r i r c không nh 13/ 64
Ý nghĩa đ nh lý Phép mã hóa v i t mã có đ dài không đ i nói chung b o toàn đ b t đ nh c a ngu n H(U) là s ký hi u nh phân nh nh t có th s d ng đ bi u di n ngu n tin nguyên th y m t cách chính xác Trong trư ng h p t ng quát, s ký hi u nh nh t đó có th đ t đư c khi mã hóa m t kh i có chi u dài vô t n các ký hi u ngu n Đ nh lý có th m r ng cho mã hi u cơ s l n hơn 2. Chương 5: Mã hóa ngu n 2. Mã hóa ngu n r i r c không nh 14/ 64
2.3.Mã hóa v i t mã có đ dài thay đ i M c tiêu: mã hóa ký hi u v i s lư ng ký hi u nh phân t i thi u Xét tru ng h p ngu n có phân b xác su t không đ u Các ký hi u ngu n có xác su t xu t hi n l n c n đư c mã hóa v i các t mã có đ dài nh và ngư c l i. S ký hi u trung bình cho m i ký hi u c a ngu n: L R= nk P(uk ) 1 s có giá tr t i ưu Mã hi u s d ng trong trư ng h p này c n có tính prefix (gi i mã đư c) đư c th hi n b ng b t đ ng th c Kraft (McMillan) Chương 5: Mã hóa ngu n 2. Mã hóa ngu n r i r c không nh 15/ 64
2.3.Mã hóa v i t mã có đ dài thay đ i Theorem Đi u ki n c n và đ đ t n t i m t mã hi u nh phân có tính prefix v i các t mã có đ dài n1 ≤ n2 ≤ . . . ≤ nL là L 2−nk ≤ 1 k=1 Chương 5: Mã hóa ngu n 2. Mã hóa ngu n r i r c không nh 16/ 64