Bài giảng Lý thuyết thông tin - Chương 1: Các khái niệm căn bản (Phần 1)

Chương 1: Các khái niệm căn bản 1.1 Độ không chắc chắn 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. 9/30/2010 2 Huỳnh Văn Kha Nguồn Mã Kênh Giải mã Đích Nhiễu 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 9/30/2010 3 Huỳnh Văn Kha • 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 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 9/30/2010 4 Huỳnh Văn Kha 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 ý. Ý 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. 9/30/2010 5 Huỳnh Văn Kha • 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. Nguồn 0 1 0 1 ¾ ¼ ¾ ¼ Ý 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 9/30/2010 6 Huỳnh Văn Kha 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à: Ý 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 9/30/2010 7 Huỳnh Văn Kha • 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ì: Ý 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 9/30/2010 8 Huỳnh Văn Kha • Đ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ã 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: 9/30/2010Huỳnh Văn Kha 9 • 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 Hàm ño ñộ không chắc chắn • Ví dụ 1: biến ngẫu nhiên X có 9/30/2010Huỳnh Văn Kha 10 • Ví dụ 2: biến ngẫu nhiên X có 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 9/30/2010Huỳnh Văn Kha 11 • 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 Bổ ñề 1.1 9/30/2010Huỳnh Văn Kha 12 Cho và là các số dương tùy ý thỏa . Thì: Dấu bằng xảy ra khi và chỉ khi Chứng minh bổ ñề 1.1 9/30/2010Huỳnh Văn Kha 13 Á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. ðịnh lý 1.2 9/30/2010Huỳnh Văn Kha 14 , 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ả 9/30/2010 15 Huỳnh Văn Kha 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à: 9/30/2010Huỳnh Văn Kha 16 ðịnh lý 1.3 Dấu bằng xảy ra khi và chỉ khi ñộc lập Chứng minh: 9/30/2010Huỳnh Văn Kha 17 ðặt: , Thì: Áp dụng Bổ ñề 1.1, ta ñược: