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

Chương 1.1 của bài giảng Lý thuyết thông tin giúp người học hiểu được một số khái niệm căn bản. Các nội dung được trình bày trong chương này gồm: Mô hình truyền thông, mục đích của lý thuyết thông tin, ý nghĩa của định lý căn bản, hàm đo độ không chắc chắn,...và các nội dung liên quan khác. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Lý thuyết thông tin: Chương 1.1 - ThS. Huỳnh Văn KhaChương 1:Các khái niệm căn bản1.1 Độ không chắc chắn 2 Huỳnh Văn Kha 9/30/2010Mô hình truyền thông• Lý thuyết thông tin khảo sát về hệ thống truyền thông. Sơ đồ như sau. Nhiễu Nguồn Mã Kênh Giải mã Đích 3 Huỳnh Văn Kha 9/30/2010Mô hình truyền thông• Nguồn: phát ra thông tin• Mã: thủ tục chuyển đổi mẫu tin thành “thực thể” thích hợp để truyền qua kênh• Kênh: truyền đi mẫu tin đã mã hóa, trong quá trình này chịu sự tác động của Nhiễu• Giải mã: thủ tục biến đổi output của kênh thành mẫu tin ban đầu• Đích: nhận thông tin 4 Huỳnh Văn Kha 9/30/2010Mục ñích của LTTT• LTTT nhằm xây dựng mô hình toán học cho mỗi khối trong sơ đồ truyền thông• Không đi sâu vào chi tiết kỹ thuật mà chỉ khảo sát chủ yếu về lý thuyết mã hóa và giải mã• Định lý căn bản của LTTT phát biểu: Có thể truyền thông tin qua một kênh bị nhiễu theo một định lượng truyền bất kỳ nhỏ hơn dung lượng kênh theo một xác suất sai nhỏ tùy ý. 5 Huỳnh Văn Kha 9/30/2010Ý nghĩa của ðịnh lý căn bản• Giả sử nguồn sinh ra một chuỗi bit 0,1 với xác suất như nhau với định lượng sinh 1 bit/giây. Giả sử các bit được sinh ra độc lập nhau.• Chúng được truyền qua một kênh có xác suất truyền sai 1 bit bất kỳ là ¼. Giả sử tốc độ truyền qua kênh là 1 bit/giây. ¾ 0 0 ¼Nguồn ¼ 1 1 ¾ 6 Huỳnh Văn Kha 9/30/2010Ý nghĩa của ðịnh lý căn bản• Do xác suất sai ¼ là quá lớn, ta tìm cách làm giảm xác suất này xuống.• Một cách làm là mỗi bit sinh ra được truyền qua kênh 3 lần và giải mã theo nguyên tắc đa số.• Xác xuất để giải mã sai là: 7 Huỳnh Văn Kha 9/30/2010Ý nghĩa của ðịnh lý căn bản• Như vậy đã giảm được xác suất sai• Nhưng phải trả giá: Giảm định lượng sinh của nguồn xuống còn 1/3 bit/giây• Tổng quát, xác suất sai của kênh là β < ½ , mỗi bit nguồn được truyền 2n+1 lần và giải mã theo đa số.Thì: 8 Huỳnh Văn Kha 9/30/2010Ý nghĩa của ðịnh lý căn bản• p(e)0 khi n ∞• Như vậy có thể giảm xác suất sai xuống bất kỳ nếu giảm định lượng sinh xuống nhỏ gần bằng 0• Điều cốt lõi của định lý căn bản là nó khẳng định: Không cần phải giảm định lượng sinh về 0 mà chỉ cần giảm về một đại lượng gọi là dung lượng kênh.• Để đạt được điều này chúng ta cần tới lý thuyết mã 9 Huỳnh Văn Kha 9/30/2010Hàm ño ñộ không chắc chắn• Biến ngẫu nhiên X có các giá trị và xác suất tương ứng• Ký hiệu:• Hàm đo độ không chắc chắn của biến X được định nghĩa (log được lấy theo cơ số 2):• Thỉnh thoảng ta cũng viết thay cho 10 Huỳnh Văn Kha 9/30/2010Hàm ño ñộ không chắc chắn• Ví dụ 1: biến ngẫu nhiên X có• Ví dụ 2: biến ngẫu nhiên X có 11 Huỳnh Văn Kha 9/30/2010Hàm ño ñộ không chắc chắn• H(X) dùng để đo lượng thông tin cần xác định của một biến ngẫu nhiên• Xét biến ngẫu nhiên W nhận các giá trị: trong đó• Thì H(X) chính là kỳ vọng (trung bình) của W• H(X) là số câu hỏi “yes no” trung bình cực tiểu để xác định kết quả của X 12 Huỳnh Văn Kha 9/30/2010Bổ ñề 1.1Cho và là các sốdương tùy ý thỏa . Thì:Dấu bằng xảy ra khi và chỉ khi 13 Huỳnh Văn Kha 9/30/2010Chứng minh bổ ñề 1.1Áp dụng bất ñẳng thức (dấubằng xảy ra khi và chỉ khi ), với , nhân 2 vế cho rồi lấy tổng theo :Từ ñây ta suy ra ñiều cần chứng minh. ...