Kênh rời rạc không phụ thuộc thời gian - Phần 2

Tham khảo tài liệu kênh rời rạc không phụ thuộc thời gian - phần 2, công nghệ thông tin, quản trị mạng phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Kênh rời rạc không phụ thuộc thời gian - Phần 2 7/2/2010Chương 3:Kênh r i r c không phthu c th i gian3.2 Phương án gi i mã t i ưu. Đ nhlý căn b n c a LTTT 2 7/2/2010 Huỳnh Văn KhaGi i mã• G i x1, x2, …, xM và y1, y2, …, yL l n lư t là các ký t input và output.• M t phương án gi i mã là m t phép tương ng m i ký t output yj v i m t ký t input xj*. Khi nh n đư c yj ta s gi i mã thành xj*• Gi i mã là phân ho ch t p ký t output thành các t p B1, …, BM sao cho m i y trong Bi s gi i mã thành xi• M t phương án gi i mã có th xem như m t kênh deterministic v i t p ký t input là y1, y2, …, yL và t p ký t output là x1, x2, …, xM 1 7/2/2010 3 7/2/2010 Huỳnh Văn KhaVí d Xác X Y Z su t 1 x1 y1 x1 1/2 1 x2 y2 x2 1/4 1/2 x3 y3 x3 1/4 1/2 4 7/2/2010 Huỳnh Văn KhaBài toán gi i mã• Cho trư c input, xây d ng phương án gi i mã sao cho xác su t sai là nh nh t• Gi s yj tương ng v i xj*• G i xác su t đúng là p(e’), ta có:• Kênh và input cho trư c nên các p(yj) không đ i• V i m i yj cho trư c ch c n ch n xj* sao cho p(xj*|yj) là l n nh t 2 7/2/2010 5 7/2/2010 Huỳnh Văn KhaTrư ng h p input ñ ng xác su t• N u input là đ ng xác su t thì• V i y c đ nh thì vi c c c đ i p(xi|y) tương đương v i vi c c c đ i p(y|xi)• Như v y v i phân ph i đ u c a input thì phương án gi i mã t i ưu là v i m i y cho trư c ch n xi sao cho p(y|xi) là c c đ i• Ta s xét k hơn v n đ này trong chương 4 6 7/2/2010 Huỳnh Văn KhaVí d• Xét ma tr n kênh y1 y2 y3 x1 1/2 1/3 1/6 x2 1/6 1/2 1/3 x3 1/3 1/6 1/2• G i s p(x1) = ½, p(x2) = p(x3) = ¼• Tìm phương án gi i mã t i ưu và tính xác su t sai 3 7/2/2010 7 7/2/2010 Huỳnh Văn Khað nh lý căn b n c a LTTT• Gi s ngu n sinh ra dãy các ký t nh phân v i đ nh lư ng không đ i R bit/giây, và đ nh lư ng truy n c a ngu n không quá 1 bit/giây• Trong n giây, ngu n sinh nR ký t• T ng s m u tin có th có trong n giây là 2nR• Chú ý 2nR có th không nguyên, trong trư ng h p đó, ta l y [2nR] (ph n nguyên c a 2nR)• Ta cũng không quan tâm trư ng h p s ký t c a ngu n không ph i là 2. Vì n u s ký t mã là D và ngu n sinh S ký t /giây, thì trong n giây, ngu n sinh DnS = 2nSlog D. Và có th xem nó như ngu n nh phân v i đ nh lư ng R = S log D 8 7/2/2010 Huỳnh Văn Khað nh lý căn b n c a LTTT• Thay vì truy n t ng ký t qua kênh, ta s mã hóa m i block n ký t• Do đ nh lư ng truy n không quá 1 bit/giây nên s ký t mã mã hóa m i block không quá n ký t• Đ gi đ nh lư ng sinh c a ngu n là R, ta c n 2nR t mã chi u dài ≤ n• Ý tư ng cơ b n c a đ nh lý là cho trư c ε > 0, n u ch n n đ l n, ta có th tìm đư c 2nR t mã và m t cách gi i mã sao cho sai s đ u < ε, nghĩa là < ε b t ch p t mã nào đư c truy n qua kênh 4 7/2/2010 9 7/2/2010 Huỳnh Văn Khað nh lý căn b n c a LTTT• Cái giá ...