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

Chia sẻ: Nguyen Uyen | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

46
lượt xem 4
download

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

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ả

Chủ đề:

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

Lưu

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

7/2/2010 Chương 3: Kênh r i r c không ph thu c th i gian 3.2 Phương án gi i mã t i ưu. Đ nh lý căn b n c a LTTT 2 7/2/2010 Huỳnh Văn Kha Gi 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 Kha Ví 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 Kha Bà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 Kha Trư 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 Kha Ví 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á ph i tr là ta c n ph i ch n giây trư c khi mã hóa ngu n tin, cũng có th ph i t n thêm th i gian ch do vi c mã hóa và gi i mã • Thêm vào đó, phương án mã hóa và gi i mã trong đ nh lý này r t ph c t p và khó th c hi n trong th c t 10 7/2/2010 Huỳnh Văn Kha ð nh lý căn b n c a LTTT • Ví d , xét R = 2/5 và n = 5. Trong 5 giây, s m u tin có th có do ngu n sinh ra là 2nR = 4. G i chúng là m1, m2, m3, m4 • Ta gán cho m i mi m t dãy nh phân đ dài ≤ 5 m1 00000 m1 00 m2 01101 m2 01 m3 11010 m3 10 m4 10111 m4 11 5
7/2/2010 11 7/2/2010 Huỳnh Văn Kha ð nh lý căn b n c a LTTT • V i cách mã hóa th hai, ch c n m t ký t b truy n sai cũng không th nào phát hi n đư c • V i cách mã hóa th hai, m i vi c truy n sai m t ký t đ u có th phát hi n và t đ ng s a l i đư c • N u nh n đư c chu i v, ta ch c n ch n t mã w sao cho s v trí khác nhau c a w và v là ít nh t • Chú ý r ng hai t mã khác nhau s khác nhau ít nh t 3 v trí. Do đó m i vi c truy n sai m t ký t s phát hi n và s a l i đư c 12 7/2/2010 Huỳnh Văn Kha ð nh lý căn b n c a LTTT • M t n-chu i là m t dãy n ký t input ho c output • M t b mã (s,n) là m t t p g m s các n-chu i input x(1), …, x(s) cùng v i m t phương án gi i mã, nghĩa là m t hàm cho tương ng m i n-chu i output v i m t trong các x(i). Các x(i) g i là các t mã • M t phương án gi i mã là m t phân ho ch t p các n-output thành các t p con r i nhau B1, …, Bs, mà m i Bi g i là m t t p gi i mã. Khi nh n đư c output trong Bi ta s gi i mã thành x(i) 6
7/2/2010 13 7/2/2010 Huỳnh Văn Kha ð nh lý căn b n c a LTTT i n-chu i input là m t tr ng thái c a vector •M u nhiên X = (X1, X2, …, Xn) ng i n-chu i output là m t tr ng thái c a vector •M u nhiên Y = (Y1, Y2, …, Yn) ng s x(i) đư c truy n qua kênh, xác su t sai là • Gi 14 7/2/2010 Huỳnh Văn Kha ð nh lý căn b n c a LTTT • Xác su t sai c a b mã là • Xác su t sai c c đ i đư c đ nh nghĩa là • Do đó n u pm(e) ≤ ε thì t mã nào cũng đư c truy n v i sai s ≤ ε 7
7/2/2010 15 7/2/2010 Huỳnh Văn Kha ð nh lý căn b n c a LTTT • M t b mã (s,n,λ) là m t b mã (s,n) sao cho xác su t sai c c đ i là ≤ λ Đ nh lý căn b n c a LTTT: Cho trư c m t kênh r i r c không ph thu c th i gian v i dung lư ng kênh C > 0 và m t s dương R < C. Khi đó t n t i m t dãy các b mã a1, a2, …, An, … sao cho an là m t b mã ([2nR],n,λn) và λn 0 khi n ∞ 8