Bài giảng Lý thuyết thông tin: Chương 3.2 - ThS. Huỳnh Văn Kha

Chia sẻ: Ngocnga Ngocnga | Ngày: | Loại File: PDF | Số trang:15

Thêm vào BST

Báo xấu

80
lượt xem 7
download

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

Tiếp tục với kênh rời rạc không phụ thuộc thời gian, trong chương này chúng ta sẽ tập trung tìm hiểu các phương án giải mã tối ưu và định lý căn bản của lý thuyết thông tin. Mời các bạn cùng tham khảo để nắm bắt các nội dung chi tiết.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Lý thuyết thông tin: Chương 3.2 - ThS. Huỳnh Văn Kha

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 Huỳnh Văn Kha 9/30/2010 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
3 Huỳnh Văn Kha 9/30/2010 Ví dụ Xác X Y Z suất 1/2 x1 1 y1 x1 1 1/4 x2 y2 x2 1/2 1/4 x3 y3 x3 1/2
4 Huỳnh Văn Kha 9/30/2010 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
5 Huỳnh Văn Kha 9/30/2010 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 Huỳnh Văn Kha 9/30/2010 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
7 Huỳnh Văn Kha 9/30/2010 ðị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 Huỳnh Văn Kha 9/30/2010 ðị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
9 Huỳnh Văn Kha 9/30/2010 ðị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 Huỳnh Văn Kha 9/30/2010 ðị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
11 Huỳnh Văn Kha 9/30/2010 ðị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 Huỳnh Văn Kha 9/30/2010 ðị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)
13 Huỳnh Văn Kha 9/30/2010 ðị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 ngẫu nhiên Y = (Y1, Y2, …, Yn) • Giả sử x(i) được truyền qua kênh, xác suất sai là
14 Huỳnh Văn Kha 9/30/2010 ðị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ố ≤ ε
15 Huỳnh Văn Kha 9/30/2010 ðị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 ∞