Trƣờng Đại Học Công Nghệ Thông Tin
KHOA MẠNG & TRUYỀN THÔNG
LÝ THUYẾT THÔNG TIN
Bùi Văn Thành
[email protected]
1
Tháng 7 năm 2013
THÔNG TIN CHUNG VỀ MÔN HỌC
Tên môn học: LÝ THUYẾT THÔNG TIN
(Fundamental of information theory)
Số đvht: 4 đvht
Loại môn học: bắt buộc
Các môn học tiên quyết: Lý thuyết xác suất, Kỹ thuật
số, Kỹ thuật truyền số liệu, Hệ điều hành, Mạng máy
tính.
bổ giờ: Lý thuyết + bài tập :
45 tiết (Hệ Chính quy)
24 tiết (Hệ TXQM)
Phân
2
MỤC TIÊU CỦA MÔN HỌC
Hiểu
các khái niệm về về thông tin, Entropy, Entropy có điều
kiện, Độ đo lƣợng tin. Vận dụng giải quyết các bài toán về xác
định lƣợng tin.
Biết
khái niệm về mã tách được, mã không tách được, mã hóa tối
ưu Huffman. Hiểu định lý mã hóa Shannon (1948). Vận dụng lý
thuyết mã hóa để hiểu thiết bị mã hóa và giải mã.
Từ
đây, các sinh viên có thể tự nghiên cứu các mã khác để vận
dụng cho việc mã hóa và bảo mật thông tin một cách hiệu quả.
Lý thuyết thông tin cũng là một trong các môn học khó vì nó đòi
hỏi người học phải có kiến thức cơ bản về toán và xác suất thống
kê. Do đó, đòi hỏi người học phải tham gia lớp học đầy đủ và3
làm các bài tập theo yêu cầu của môn học thì mới tiếp thu kiến
thức môn học một cách hiệu quả.
NỘI DUNG MÔN HỌC
Chƣơng
1: Những khái niệm cơ bản
Chƣơng
2: Tín hiệu
Chƣơng
3: Lƣợng tin, Entropi nguồn rời rạc
Chƣơng
4: Lý thuyết mã – Mã hóa nguồn
Chƣơng
5: Mã hóa kênh truyền
Chƣơng
6: Mã vòng
4
TÀI LIỆU THAM KHẢO
[1] Adamek,
J.Foundations of Coding: Theory and
Application of Error–Correcting Codes with an
Introduction to Cryptography and Information
Theory, John Wiley and Sons, New York 1991.
[2]
Nguyễn Bình, Lý thuyết thông tin, NXB Bƣu
điện , năm 2007.
[3]
Nguyễn Thúy Vân, Lý thuyết mã, NXB KHKT,
năm 2006.
5
TÀI LIỆU THAM KHẢO
[4] Vũ Ngọc Phàn, Lý thuyết thông tin và mã hóa,
NXB Bƣu điện, năm 2006.
[5]
Đặng Văn Chuyết, Cơ sở lý thuyết tryền tin,
NXB Giáo dục, năm 2001.
[6]
Trần Trung Dũng, Lý thyết truyền tin, NXB KH
& KT, năm 2007.
6
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
(Information theory)
Thông tin?
◦ Hai ngƣời nói chuyện với nhau. Cái mà trao đổi giữa
họ gọi là thông tin.
◦ Một ngƣời đang xem tivi/nghe đài/đọc báo, ngƣời đó
đang nhận thông tin từ đài phát/báo.
◦ Các máy tính nối mạng và trao đổi dữ liệu với nhau.
◦ Máy tính nạp chƣơng trình, dữ liệu từ đĩa cứng vào
7
RAM để thực thi.
THÔNG TIN
Nhận xét
◦
◦
◦
◦
◦
Thông tin là cái đƣợc truyền từ đối tƣợng này đến đối tƣợng
khác để báo một “điều” gì đó.
Thông tin chỉ có ý nghĩa khi “điều” đó bên nhận chƣa biết.
Thông tin xuất hiện dƣới nhiều dạng âm thanh, hình ảnh,
…
Ngữ nghĩa của thông tin chỉ có thể hiểu đƣợc khi bên nhận
hiểu đƣợc cách biểu diễn ngữ nghĩa của bên phát.
Có hai trạng thái của thông tin: truyền và lưu trữ. Môi
trƣờng truyền/lƣu trữ đƣợc gọi chung là môi trường chứa tin
hay kênh tin.
8
CÁC LOẠI THÔNG TIN
Thông tin có thể thuộc nhiều loại nhƣ:
1.
2.
3.
4.
Một dãy kí tự nhƣ trong điện tín (telegraph) của các hệ
thống gởi điện tín (teletype system);
Một hàm theo chỉ một biến thời gian f(t) nhƣ trong radio
và điện thoại;
Một hàm của thời gian và các biến khác nhƣ trong tivi
trắng đen – ở đây thông tin có thể đƣợc nghĩ nhƣ là một
hàm f(x, y, t) của toạ độ hai chiều và thời gian biểu diễn
cƣờng độ ánh sáng tại điểm (x, y) trên màn hình và thời
gian t;
Một vài hàm của một vài biến nhƣ trong trƣờng hợp tivi
màu – ở đây thông tin bao gồm ba hàm f(x, y, t), g(x, y, t),
h(x, y, t) biểu diễn cƣờng độ ánh sáng của các ba thành
phần màu cơ bản (xanh lá cây, đỏ, xanh dƣơng).
9
LỊCH SỬ HÌNH THÀNH
Cuộc
cách mạng lớn nhất về cách nhìn thế giới khoa học là
chuyển hƣớng từ thuyết quyết định Laplacian đến bức tranh
xác suất của tự nhiên.
Thế giới chúng ta đang sống trong đó chủ yếu là xác suất.
Kiến thức của chúng ta cũng là một dạng xác suất.
LTTT nổi lên sau khi cơ học thống kê và lƣợng tử đã phát
triển, và nó chia xẻ với vật lý thống kê các khái niệm cơ bản
về entropy.
Theo lịch sử, các khái niệm cơ bản của LTTT nhƣ entropy,
thông tin tƣơng hỗ đƣợc hình thành từ việc nghiên cứu các hệ
thống mật mã hơn là từ việc nghiên cứu các kênh truyền
thông.
Về mặt toán học, LTTT là một nhánh của lý thuyết xác suất và
các quá trình ngẫu nhiên (stochastical process).
LỊCH SỬ HÌNH THÀNH (TT)
Quan trọng và có ý nghĩa nhất là quan hệ liên kết
giữa LTTT và vật lý thống kê.
Trong một thời gian dài trƣớc khi LTTT đƣợc hình
thành, L. Boltzman và sau đó là L.Szilard đã đánh
đồng ý nghĩa của thông tin với khái niệm nhiệt
động học của entropy. Một mặt khác, D. Gabor chỉ
ra rằng “lý thuyết truyền thông phải được xem như
một nhánh của vật lý”.
C. E. Shannon là cha đẻ của LTTT.
VAI TRÒ CỦA LÝ THUYẾT THÔNG TIN
Thông
tin là một nhu cầu cơ bản, một điều kiện
cần cho sự tồn tại và phát triển.
Trong khoa học kỹ thuật, LTTT nghiên cứu nhằm tạo
ra một “cơ sở hạ tầng” tốt cho việc truyền thông tin
chính xác, nhanh chóng và an toàn; lƣu trữ thông tin
một cách hiệu quả.
Ở các góc độ nghiên cứu khác, LTTT nghiên cứu các
vấn đề về cách tổ chức, biểu diễn, truyền đạt thông
tin, và tổng quát là các vấn đề về xử lý thông tin.
12
ỨNG DỤNG CỦA LÝ THUYẾT THÔNG TIN
LTTT ứng dụng trong truyền thông và xử lý thông tin:
truyền thông, nén, bảo mật, lưu trữ, ...
LTTT đã đƣợc áp dụng trong nhiều lĩnh vực khác: vật
lý, ngôn ngữ học, Kinh tế, khoa học máy tính, tâm lý
học, hóa học,…
Mối quan hệ giữa LTTT và thống kê đã đƣợc tìm thấy,
các phƣơng pháp mới về phân tích thống kê dựa trên
LTTT đã đƣợc đề nghị.
Ứng dụng vào quản lý kinh tế. Ví dụ, lý thuyết đầu tƣ
tối ƣu xuất hiện đồng thời với lý thuyết mã hóa nguồn
tối ƣu.
13
Ứng dụng vào ngôn ngữ học.
CÁC LĨNH VỰC NGHIÊN CỨU CƠ BẢN
Ba
lĩnh vực nghiên cứu cơ bản của môn học:
Mã hoá chống nhiễu.
Mã hoá tối ƣu (hay nén dữ liệu).
Mật mã hoá.
14
CÁC VẤN ĐỀ NGHIÊN CỨU CỦA LTTT
1.
2.
3.
4.
5.
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.
Các vấn đề liên quan đến tính chất bảo mật, tối
ưu hóa quá trình.
Các vấn đề đó thường được gọi là các lý thuyết
thông tin, lý thuyết năng lượng.
15
CÁC VẤN ĐỀ NGHIÊN CỨU CỦA LTTT
Lý
thuyết về năng lượng:
Giải quyết vấn đề xây dựng mạch, tín hiệu.
Tuy nhiên chƣa giải quyết đƣợc vấn đề: 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… .
=> Lý thuyết thông tin nhằm giải quyết vấn đề:
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...
16
CÁC ĐỊNH NGHĨA
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: điện, điện từ, sóng âm,
sóng ánh sáng….
Vật mang có chứa thông tin gọi là tín hiệu.
Tin là dạng vật chất cụ thể biểu diễn hoặc thể
hiện thông tin: bản nhạc, bảng số liệu, bài nói…
Thông tin:
17
1.2 HỆ THỐNG TRUYỀN TIN
1.2.1
Phân loại hệ thống truyền tin
Theo
quan điểm năng lượng :
Năng lƣợng một chiều (điện tín)
Vô tuyến điện (sóng điện từ)
Quang năng (cáp quang)
Sóng siêu âm (la-de)
18
1.2.1 PHÂN LOẠI HỆ THỐNG TRUYỀN TIN
Theo
biểu hiện bên ngoài:
Hệ thống truyền số liệu
Hệ thống truyền hình phát thanh
Hệ thống thông tin thoại
Theo dạng tín hiệu:
Hệ thống truyền tin rời rạc
Hệ thống truyền tin liên tục
19
TRUYỀN TIN (TRANSMISSION)
Định
nghĩa: Là quá trình dịch chuyển thông tin từ
điểm này sang điểm khác trong một môi trƣờng xác
định.
Hai điểm này sẽ đƣợc gọi là điểm nguồn tin (information
source) và điểm nhận tin (information destination).
Môi trƣờng truyền tin còn đƣợc gọi là kênh tin (chanel).
20