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

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.
Nội dung trích xuất từ tài liệu:
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 iChươ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 cChươ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 uChươ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 tChươ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 cChươ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àoChươ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 ...