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

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

Thêm vào BST

Báo xấu

95
lượt xem 5
download

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

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.

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 1.1 - ThS. Huỳnh Văn Kha

Chương 1: Các khái niệm căn bản 1.1 Độ không chắc chắn
2 Huỳnh Văn Kha 9/30/2010 Mô 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/2010 Mô 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/2010 Mụ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/2010 Hà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/2010 Hà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/2010 Hà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/2010 Bổ ñề 1.1 Cho 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/2010 Chứng minh bổ ñề 1.1 Áp dụng bất ñẳng thức (dấu bằ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.
14 Huỳnh Văn Kha 9/30/2010 ðịnh lý 1.2 , dấu bằng xảy ra khi và chỉ khi với mọi ðây là hệ quả của Bổ ñề phía trên, với tất cả
15 Huỳnh Văn Kha 9/30/2010 Hàm ño ñộ không chắc chắn của ñồng thời hai biến ngẫu nhiên Xét hai biến ngẫu nhiên: • Biến X lấy giá trị với xác suất lần lượt là: • Biến Y lấy giá trị với xác suất lần lượt là: ðặt . ðộ không chắc chắc ñồng thời của X và Y ñược ñịnh nghĩa là:
16 Huỳnh Văn Kha 9/30/2010 ðịnh lý 1.3 Dấu bằng xảy ra khi và chỉ khi ñộc lập Chứng minh:
17 Huỳnh Văn Kha 9/30/2010 ðặt: , Thì: Áp dụng Bổ ñề 1.1, ta ñược: