Bài giảng Lý thuyết thông tin - Chương 3: Kênh rời rạc không phụ thuộc thời gian (Phần 2)

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 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 y với một ký tự input x *. Khi 9/30/2010 2 Huỳnh Văn Kha j j 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 Ví dụ Xác suất X 1/2 x 9/30/2010Huỳnh Văn Kha 3 Y y Z x11 1/4 x2 1/4 x3 1 y2 y3 1 x2 x3 1 1/2 1/2 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ó: 9/30/2010Huỳnh Văn Kha 4 • 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 Trường hợp input ñồng xác suất • Nếu input là đồng xác suất thì 9/30/2010Huỳnh Văn Kha 5 • 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 Ví dụ • Xét ma trận kênh 9/30/2010Huỳnh Văn Kha 6 1/2 1/3 1/6 y1 y2 y3 x • 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 1/6 1/2 1/3 1/3 1/6 1/2 1 x2 x3 ðị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 9/30/2010Huỳnh Văn Kha 7 • 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 ðị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 9/30/2010Huỳnh Văn Kha 8 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 ðị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ã 9/30/2010Huỳnh Văn Kha 9 • 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ế ðị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 9/30/2010Huỳnh Văn Kha 10 • Ta gán cho mỗi mimột dãy nhị phân độ dài ≤ 5 m1 00000 m2 01101 m3 11010 m4 10111 m1 00 m2 01 m3 10 m4 11 ðị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 9/30/2010Huỳnh Văn Kha 11 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 ðị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 9/30/2010Huỳnh Văn Kha 12 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) ðịnh lý căn bản của LTTT • Mỗi n-chuỗi input là một trạng thái của vector ngẫu nhiên X = (X1, X2, , Xn) • Mỗi n-chuỗi output là một trạng thái của vector 9/30/2010Huỳnh Văn Kha 13 ngẫu nhiên Y = (Y1, Y2, , Yn) • Giả sử x(i) được truyền qua kênh, xác suất sai là ðịnh lý căn bản của LTTT • Xác suất sai của bộmã là 9/30/2010Huỳnh Văn Kha 14 • 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ố ≤ ε ðị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: 9/30/2010Huỳnh Văn Kha 15 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
∞