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

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.
Nội dung trích xuất từ tài liệu:
Bài giảng Lý thuyết thông tin: Chương 3.2 - ThS. Huỳnh Văn KhaChương 3:Kênh rời rạc không phụthuộc thời gian3.2 Phương án giải mã tối ưu. Địnhlý căn bản của LTTT 2 Huỳnh Văn Kha 9/30/2010Giả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/2010Ví 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/2010Bà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/2010Trườ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/2010Ví 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ã ...