1 ðẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN Vũ Vinh Quang – Chủ biên Nguyễn ðình Dũng, Nguyễn Hiền Trinh, Dương Thị Mai Thương GIÁO TRÌNH LÝ THUYẾT THÔNG TIN THÁI NGUYÊN – NĂM 2010 2 LỜI MỞ ðẦU Giáo trình lý thuyết thông tin ñược biên soạn dựa trên các bài giảng ñã ñược giảng dạy nhiều năm cho ñối tượng là sinh viên chính quy ngành Công nghệ thông tin tại khoa Công nghệ thông tin ðại học Thái Nguyên cùng với việc tham khảo một số giáo trình của các trường ðại học khác cũng như các tài liệu nước ngoài. ðể ñọc giáo trình này, người ñọc cần phải ñược trang bị ñầy ñủ các kiến thức về toán cao cấp, xác suất thống kê, lý thuyết thuật toán và một ngôn ngữ lập trình cơ bản (C hoặc Pascal). Giáo trình ñược cấu trúc gồm 5 chương Chương 1 trình bày một số khái niệm cơ bản về lý thuyết thông tin như cấu trúc của hệ thống truyền tin, phân loại môi trường truyền tin, vấn ñề rời rạc hóa các nguồn tin liên tục và các khái niệm về ñiều chế và giải ñiều chế. Chương 2 ñưa ra các khái niệm cơ bản về tín hiệu và các cơ chế phân tích phổ cho tín hiệu, khái niệm về nhiễu trong quá trình truyền tin. Chương 3 trình bày các khái niệm cơ bản về ñộ ño thông tin, lượng tin, entropi và mối quan hệ giữa lượng tin và entropi, các công thức xác ñịnh lượng tin và entropi dựa trên cơ sở của lý thuyết xác suất, khái niệm về tốc ñộ lập tin và thông lượng kênh trong quá trình truyền tin. Chương 4 giới thiệu các khái niệm chung về mã hóa, ñiều kiện thiết lập, các phương pháp biểu diễn, các thuật toán mã hóa cơ bản, khái niệm về mã chống nhiễu và mã tuyến tính. Chương 5 của giáo trình giới thiệu về một số hệ mật mã nổi tiếng trên thế giới ñể người ñọc tham khảo. Trong quá trình soạn thảo giáo trình chắc chắn không tránh khỏi những thiếu xót về nội dung cũng như hình thức, nhóm biên soạn trân trọng cảm ơn những ý kiến quý báu của các bạn ñọc ñể giáo trình ñược hoàn thiện hơn. Thái Nguyên, tháng 01 năm 2010 Thay mặt nhóm biên soạn Vũ Vinh Quang 3 CHƯƠNG 1. NHỮNG KHÁI NIỆM CƠ BẢN 1.1 Giới thiệu về lý thuyết thông tin Trong thế giới ngày nay, chúng ta hàng ngày phải tiếp xúc với rất nhiều các hệ thống chuyển tải thông tin khác nhau như: Các hệ thống truyền hình phát thanh, hệ thống ñiện thoại cố ñịnh và di ñộng, hệ thống mạng LAN, Internet, các hệ thống này ñều với mục ñích là chuyển thông tin từ nơi phát ñến nơi thu với những mục ñích khác nhau. ðể nghiên cứu về các hệ thống này, chúng ta cần phải nghiên cứu về bản chất thông tin, bản chất của quá trình truyền tin theo quan ñiểm toán học, cấu trúc vật lý của môi trường truyền tin và các vấn ñề liên quan ñến tính chất bảo mật, tối ưu hóa quá trình. Khái niệm ñầu tiên cần nghiên cứu là thông tin: thông tin ñược hiểu là tập hợp các tri thức mà con người thu ñược qua các con ñường tiếp nhận khác nhau, thông tin ñược mang dưới dạng năng lượng khác nhau gọi là vật mang, vật mang có chứa thông tin gọi là tín hiệu. Lý thuyết về năng lượng giải quyết tốt vấn ñề xây dựng mạch, tín hiệu. Nhưng vấn ñề về tốc ñộ, hiện tượng nhiễu, mối liên hệ giữa các dạng năng lượng khác nhau của thông tin… chưa giải quyết ñược mà phải cần có một lý thuyết khác ñó là lý thuyết thông tin. Lý thuyết thông tin là lý thuyết nhằm giải quyết vấn ñề cơ bản của quá trình truyền tin như vấn ñề về rời rạc hóa nguồn, mô hình phân phối xác suất của nguồn và ñích, các vấn ñề về mã hóa và giải mã, khả năng chống nhiễu của hệ thống... Cần chú ý rằng lý thuyết thông tin không ñi sâu vào việc phân tích các cấu trúc vật lý của hệ thống truyền tin mà chủ yếu nghiên cứu về các mô hình toán học mô tả quá trình truyền tin trên quan ñiểm của lý thuyết xác suất thống kê, ñồng thời nghiên cứu về các nguyên tắc và các thuật toán mã hóa cơ bản, các nguyên tắc mã chống nhiễu... 1.2 Hệ thống truyền tin Trong thực tế, chúng ta gặp rất nhiều các hệ thống ñể truyền thông tin từ ñiểm này tới ñiểm khác, trong thực tế những hệ thống truyền tin cụ thể mà con