Cơ sở lý thuyết truyền tin - Chương 4: Mã hiệu

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

Thêm vào BST

Báo xấu

84
lượt xem 9
download

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

Mã hiệu là mã sử dụng tập ký hiệu số (các chữ số) đề mã hóa thông tin. Mã hóa: một song ánh giữa hai nguồn tin (một phép biển đổi 1-1 giữa các tin của hai nguồn tin)

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 - Chương 4: Mã hiệu

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 4: Mã hi u Chương 4: Mã hi u 0. 2/1
Gi i thi u X lí thông tin: Có m t ngu n tin nguyên th y Bi n đ i ngu n tin nguyên th y cho phù h p v i các quá trình x lí thành các ngu n tin trung gian khác Bi n đ i ngư c t các ngu n tin thành ngu n tin có d ng ban đ u Bi u di n c a các ngu n tin trung gian b ng mã hi u Mã hi u: Các khái ni m liên quan Đi u ki n đ s d ng đư c mã hi u Cách bi u di n mã hi u Chương 4: Mã hi u 0. 3/1
1. Mã hi u, tham s , đ c tính Chương 4: Mã hi u 1. Mã hi u, tham s , đ c tính 4/1
1.1.Khái ni m mã hi u Mã hi u là mã s d ng t p ký hi u s (các ch s ) đ mã hóa thông tin Mã hóa m t song ánh gi a hai ngu n tin (m t phép bi n đ i 1-1 gi a các tin c a hai ngu n tin) K t qu thu đư c là m t ngu n tin có các thông s th ng kê phù h p: Entropy Đ chính xác Chi u dài các tin K t qu thu đư c này là mã hi u V y mã hi u là m t ngu n tin v i mô hình th ng kê xác đ nh trư c, th a mãn yêu c u nào đó, s d ng các ký hi u s Chương 4: Mã hi u 1. Mã hi u, tham s , đ c tính 5/1
Các khái ni m liên quan c a mã hi u Mã hi u g m m t t p h u h n các ký hi u có phân b xác su t nào đó, g i là d u mã hay ký hi u mã T p h p m t s nào đó các d u mã g i là t h p mã Trong t p h p t t c các t h p mã, m t t p h p các t h p mã đư c xây d ng theo m t lu t nào đó, g i là t h p mã có th (h p l ) Trong quá trình mã hóa, m t tin c a ngu n nguyên th y đư c ánh x vào m t t h p mã. M t t h p mã như v y g i là t mã. Nh ng t h p có th khác g i là t h p c m (t h p không s d ng) M t dãy t mã b t kỳ t o thành m t t thông tin Chương 4: Mã hi u 1. Mã hi u, tham s , đ c tính 6/1
Ví d : mã BCD Binary Coded Decimal đóng gói Ngu n tin nguyên th y g m các tin là các ký hi u t 0 − 9 Mã hóa thành các ký hi u nh phân 0 − 1 Các d u (ký hi u mã): 0, 1 Các t h p mã có th : 0000 đ n 1111, g m 16 t h p mã Các t h p mã đư c s d ng (t mã): 0 1 2 ......... 9 0000 0001 0010 ........ 1001 Các t h p mã b c m: 1010,1011,1100,1101,1110,1111 M t t thông tin: 2005 → 0010000000000101 001000000000010100 Chương 4: Mã hi u 1. Mã hi u, tham s , đ c tính 7/1
Các khái ni m liên quan c a mã hi u Quá trình bi n đ i ngu n tin ban đ u s d ng mã hi u g i là quá trình mã hóa. Ngu n tin r i r c g m nhi u tin t o thành b n tin. Các ngu n tin trong th c t có s lư ng các tin r t l n. Ngư c l i các mã hi u thư ng có s lư ng các ký hi u tương đ i nh . Do đó m t tin c a ngu n ban đ u thư ng đư c mã hóa thành m t chu i các ký hi u mã:(t mã) Quá trình bi n đ i ngư c l i t m t t mã thành m t tin ban đ u g i là quá trình gi i mã Ngo i l : mã hóa m t chu i các tin c a ngu n tin nguyên th y thành m t ho c nhi u t mã: mã kh i (mã theo t ) Chương 4: Mã hi u 1. Mã hi u, tham s , đ c tính 8/1
1.2.Các thông s cơ b n c a mã hi u Mã hi u là m t t p h p các t mã, thành l p t m t b ng ký hi u S lư ng ký hi u trong b ng ký hi u g i là cơ s Đ dài c a t mã: s lư ng các ký hi u c a t mã Đ dài trung bình c a t mã: L R= p(xi )ni i=1 L là t ng s t mã: s tin đư c mã hóa, s t mã, s t h p mã có th đư c s d ng Mã đ y: L = M, M là t ng s các t mã có th Mã vơi: L < mn = M R = M − L: s các t h p b c m (không s d ng) Đ đo c a t mã Chương 4: Mã hi u 1. Mã hi u, tham s , đ c tính 9/1
1.2.Các thông s cơ b n c a mã hi u (Ti p) Đ thu n ti n cho vi c s d ng mã hi u, m i t mã đư c gán cho m t đ đo: tr ng s Đ đo đơn gi n nh t cho m t t c a m t b ng ch cái: h đ m theo v trí S lư ng ký hi u g i là cơ s c a mã hi u M i ký hi u đư c gán cho m t giá tr g i là giá tr riêng hay tr c a ký hi u. Ví d m ký hi u có th đư c gán các tr tương ng là 0, 1, 2 . . . m − 1 Ch s v trí: s th t c a m i ký hi u trong t mã. Ví d : đánh s t 0, t ph i qua trái Tr ng s v trí wk : h s nhân c a t ng v trí ký hi u k. Ví d : trong h đ m cơ s 10, tr ng s c a v trí đ u tiên là 1, th 2 là 10,.... Tr ng s (giá tr ) c a t mã: n−1 b= ak wk k=0 n−1 Trong h đ m cơ s m b = k=0 ak mk Chương 4: Mã hi u 1. Mã hi u, tham s , đ c tính 10/1
1.2.Các thông s cơ b n c a mã hi u (Ti p) Kho ng cách gi a hai t mã có th đo b ng Hi u gi a hai tr ng s M t đ đo đ nh nghĩa riêng Hàm c u trúc c a mã hi u Cho bi t phân b c a các t mã theo đ dài Hàm c u trúc c a mã đ ng đ u? Chương 4: Mã hi u 1. Mã hi u, tham s , đ c tính 11/1
1.3.Đ c tính c a mã hi u Tính đ ng đ u: t t c các t mã có cùng m t đ dài Tính đ y: T t c các t mã có th đ u đư c s d ng Ví d n u chi u dài l n nh t c a t mã là nmax , s lư ng t mã là mnmax +1 − 1 Tính phân tách đư c: cho m t t thông tin, li u có th phân tách đư c m t cách duy nh t t thông tin đó ra m t ho c nhi u t mã hay không? tin nguyên th y mã hi u 1 mã hi u 2 a1 00 0 Ví d a2 01 00 a3 10 10 a4 11 11 T thông tin 00010 v i mã hi u 2 có th phân tách thành 0-0-0-10 ho c 0-00-10. V y mã hi u 2 không có tính phân tách đư c Chương 4: Mã hi u 1. Mã hi u, tham s , đ c tính 12/1
1.3.Đ c tính c a mã hi u (Ti p) Tính phân tách đư c quy t đ nh vi c gi i mã Các đi u ki n khác T i ưu v đ dài T i ưu v kh năng s a sai T i ưu v th i gian gi i mã Chương 4: Mã hi u 1. Mã hi u, tham s , đ c tính 13/1
2. Đi u ki n đ mã phân tách đư c Chương 4: Mã hi u 2. Đi u ki n đ mã phân tách đư c 14/1
2.1.Kh năng gi i mã và đ ch m gi i mã Bài toán gi i mã Nh n l n lư t t ng d u ký hi u mã Ki m tra và tách chu i ký hi u mã thu đư c thành các t mã ??? Chuy n đ i các t mã thành các ký hi u c a ngu n tin ban đ u Đi u ki n gi i mã Chuy n đ i gi a các tin ban đ u thành các t mã là 1-1 Có th phân tách chu i ký hi u mã nh n đư c thành các t mã S lư ng ký hi u t i thi u đ có th nh n d ng đư c m t t mã g i là đ ch m gi i mã (đ tr mã) Chương 4: Mã hi u 2. Đi u ki n đ mã phân tách đư c 15/1
Thu t toán gi i mã 1 Nh n m t ký hi u vào b đ m: B = B + ai 2 Ki m tra n i dung b đ m (phân tách) xem có th tách m t cách duy nh t thành t h p các t mã hay không. N u không quay tr l i 1 3 Gi i mã các t mã. Xóa b đ m: B = ∅ Ví d Chương 4: Mã hi u 2. Đi u ki n đ mã phân tách đư c 16/1
Các tiêu chu n (phương pháp phân tách) Căn c vào tính prefix c a mã (?) ti n t Nhanh Đ dài các t mã khác nhau Ch ng nhi u kém Căn c vào d u phân tách Ch ng nhi u t t Hi u su t th p Căn c vào chi u dài t mã Đơn gi n Ch ng nhi u kém Chú ý: 2 và 3 th c ch t là trư ng h p riêng c a 1 Chương 4: Mã hi u 2. Đi u ki n đ mã phân tách đư c 17/1
2.2.Đi u ki n đ mã phân tách đư c Đi u ki n: b t c m t dãy các t mã nào không đư c trùng v i m t dãy các t mã khác V y đ xác đ nh mã phân tách đư c hay không c n xác đ nh : T n t i hay không m t dãy t mã trùng v i m t dãy t mã khác B ng th mã Li t kê các t mã c t 1 theo th t chi u dài tăng d n Ki m tra theo th t chi u dài tăng d n xem các t mã có là ph n đ u c a m t t mã dài hơn hay không. N u có, ghi ph n còn l i c a t mã dài vào c t th 2 V i các t mã thu đư c trong c t th hai, so sánh v i các t mã trong c t 1, n u là ph n đ u c a m t t mã, ghi ph n còn l i vào c t th 3 ti p t c cho đ n khi nào thu đư c c t tr ng Đi u ki n c n và đ đ mã phân tách đư c: không có m t t h p mã nào trong các c t t th 2 tr đi là m t t mã trong c t 1 Chương 4: Mã hi u 2. Đi u ki n đ mã phân tách đư c 18/1
Ví d 1 1 2 3 00 01 100 1010 1011 Trong trư ng h p này, khi nh n h t các ký hi u c a m t t mã, có th nh n d ng ngay t mã. V y đ ch m gi i mã b ng chi u dài t mã Chương 4: Mã hi u 2. Đi u ki n đ mã phân tách đư c 19/1
Ví d 2 1 2 3 4 5 6 10 0 1 0 1 ... 100 1 11 00 11 ... 01 0 1 0 ... 011 00 11 00 ... B ng th th a mãn yêu c u đ nh lý, nên mã này là mã phân tách đư c Đ ch m gi i mã là vô h n: ch khinào nh n h t b n tin, m i có th phân tách đư c b n tin thành các t mã Ví d dãy vô h n 10010101010.... n u không bi t ký hi u cu i cùng s không phân tách đư c các t mã N u ch xét dãy h u h n 10010101010, ch t n t i m t cách phân tách duy nh t 100-10-10-10-10 Có th đánh giá đ ch m gi i mã j −1 j −1 [ ]nmin ≤ Tch ≤ [ ]nmax 2 2 Chương 4: Mã hi u 2. Đi u ki n đ mã phân tách đư c 20/1