Slide Bài Giảng Môn Môn Học Lý Thuyết Thông Tin - 123doc
Có thể bạn quan tâm
Slide bài giảng môn môn học lý thuyết thông tin
Trang 1BÀI GIẢNG MÔN HỌC
LÝ THUYẾT THÔNG TIN Trường Đại học Công Nghệ Thông Tin
Trang 2NỘI DUNG MÔN HỌC
Bài 1 Giới thiệu
Bài 2 Một số khái niệm cơ bản
Trang 3NỘI DUNG MÔN HỌC (tt)
Bài 10 Mã hóa chống nhiễu, đ ịnh lý kênh
Bài 11 Mã khối tuyến tính
Trang 4TÀI LIỆU THAM KHẢO
1 Information Theory - Robert B.Ash, Nhà xuất bản Dover, Inc,
1990
2 Introduction to Information Theory - Masud Mansuripur, Nhà
xuất bản Prentice–Hall, Inc, 1987
3 A Mathematical Theory of Communication - C E Shannon,
Tạp chí Bell System Technical, số 27, trang 379–423 và 623–
656, tháng 7 và tháng 10, 1948
4 Cơ sở Lý thuyết truyền tin (tập một và hai) - Đặng Văn
Chuyết, Nguyễn Tuấn Anh, Nhà xuất bản Giáo dục, 1998
Trang 5HÌNH THỨC ĐÁNH GIÁ
Sẽ có thông báo cụ thể cho từng khóa học Tuy nhiên, thường là có hình thức như bên dưới.
Giữa kỳ: thi viết (30%)
Cuối kỳ: thi trắc nghiệm 50 câu / 90 phút (50%)
Làm bài tập lớn (20%)
Nộp bài tập lớn và báo cáo vào cuối học kỳ
Trang 6CÁC MÔN LIÊN QUAN
Lý thuyết xác suất
Kỹ thuật truyền số liệu
Xử lý tín hiệu số
Trang 7Bài 1 Giới thiệu
1.1 Thông tin là gì?
1.2 Vai trò của thông tin
1.3 Lý thuyết thông tin nghiên cứu những gì?
1.4 Những ứng dụng của lý thuyết thông tin
1.5 Lý thuyết thông tin – Lịch sử hình thành và quan điểm khoa học hiện đại
Trang 8 Quá trình giảng dạy trong lớp.
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 RAM đểthực thi
Trang 9Thông tin là gì? (tt)
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,
Những dạng này chỉ là “vỏ bọc” vật chất chứa thông tin “Vỏbọc” là phần “xác”, thông tin là phần “hồn”
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
Một trong những phương tiện để diễn đạt thông tin là ngôn ngữ
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
Trang 10Vai trò của thông tin
Các đối tượng sống luôn luôn có nhu cầu hiểu về thế giới xung quanh, để thích nghi và tồn tại Đây là một quá trình quan sát, tiếp nhận, trao đổi và xử lý thông tin từ môi trường xung quanh
Thông tin trở thành một nhu cầu cơ bản, một điều kiện cần cho
Trang 11LTTT nghiên cứu những vấn đề gì?
Ở góc độ 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 và truyền đạt thông tin, và tổng quát làcác vấn đề về xử lý thông tin
Ba lĩnh vực nghiên cứu cơ bản của môn học
Trang 12Những ứng dụng của LT thông tin
Cuộc cách mạng thông tin đang xảy ra, sự phát triển mạnh mẽcủa các phương tiện mới về truyền thông, lưu trữ thông tin làm thay đổi ngày càng sâu sắc xã hội chúng ta
LTTT đóng một vai trò quyết định trong sự phát triển này bằng cách cung cấp cơ sở lý thuyết và một cái nhìn triết học sâu sắc đối với những bài toán mới và thách thức mà chúng ta chạm trán – hôm nay và mai sau
Những ứng dụng phổ biến của LTTT là truyền thông và xử lý
thông tin bao gồm: truyền thông, nén, bảo mật, lưu trữ,
Các ý tưởng của LTTT đã được áp dụng trong nhiều lĩnh vực như vật lý, ngôn ngữ học, sinh vật học, khoa học máy tính, tâm
lý học, hóa học
Trang 13Những ứng dụng của LT thông tin (tt)
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
Ứng dụng vào ngôn ngữ học
Ứng dụng đến tâm lý thực nghiệm và đặc biệt là lĩnh vực dạy vàhọc
Trang 14Lị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)
Trang 15 C E Shannon là cha đẻ của LTTT.
Trang 16Bài 2 Một số khái niệm cơ bản
2.1 Thông tin (Information)
2.2 Mô hình của các quá trình truyền tin
2.3 Các loại hệ thống truyền tin – Liên tục và rời rạc 2.4 Rời rạc hoá
Trang 17 Định nghĩa đầu chưa nói lên được bản chất của thông tin Định nghĩa thứ hai nói rõ hơn về bản chất của thông tin và được dùng
để định lượng thông tin trong kỹ thuật
Trang 18 Thông tin là một quá trình ngẫu nhiên.
Tín hiệu mang tin tức cũng là tín hiệu ngẫu nhiên và mô hình toán học của nó là các quá trình ngẫu nhiên thực hay phức
Và LTTT là lý thuyết ngẫu nhiên của tin tức, có nghĩa là nó xét đến tính bất ngờ của tin tức đối với nơi nhận tin
Trang 19Mô hình của các quá trình truyền tin
Khái niệm thông tin thường đi kèm với một hệ thống truyền tin
Sự truyền tin (transmission)
Là sự dịch chuyển thông tin từ điểm này đến điểm khác trong một môi trường xác định
Nguồn tin (information source)
Là một tập hợp các tin mà hệ thống truyền tin dùng để lập các bảng tin hay thông báo (message) để truyền tin
Bảng tin chính là dãy tin được bên phát truyền đi
Thông tin có thể thuộc nhiều loại như
(1) 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);
Nguồn phát Kênh truyền Nguồn nhận
Nhiễu
Trang 20Mô hình của các quá trình truyền tin (tt)
(2) một hàm theo chỉ một biến thời gian f(t) như trong radio và điện thoại;
(3) 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;
(4) 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)
Thông tin trước khi được truyền đi, tuỳ theo yêu cầu có thể
được mã hoá để nén, chống nhiễu, bảo mật,
Kênh tin (channel)
Là nơi hình thành và truyền (hoặc lưu trữ) tín hiệu mang tin
đồng thời ở đấy xảy ra các tạp nhiễu (noise) phá hủy tin tức
Trong LTTT kênh là một khái niệm trừu tượng đại biểu cho
hỗn hợp tín hiệu và tạp nhiễu
Trang 21Một số khái niệm (tt)
Môi trường truyền tin thường rất đa dạng
môi trường không khí, tin được truyền dưới dạng âm thanh và tiếng nói, ngoài ra cũng có thể bằng lửa hay bằng ánh sáng;
môi trường tầng điện ly trong khí quyển nơi mà thường xuyên xảy ra sự truyền tin giữa các vệ tinh nhân tạo với các trạm rada ở dưới mặt đất;
đường truyền điện thoại nơi xảy ra sự truyền tín hiệu mang tin là dòng điện hay đường truyền cáp quang qua biển trong đó tín hiệu mang tin là sóng ánh sáng v.v…
Nhiễu (noise)
Cho dù môi trường nào cũng có nhiễu Nhiễu rất phong phú và
đa dạng và thường đi kèm với môi trường truyền tin tương ứng
Chẳng hạn nếu truyền dưới dạng sóng điện từ mà có đi qua các vùng của trái đất có từ trường mạnh thì tín hiệu mang tin thường bị ảnh hưởng ít nhiều bởi từ trường này Nên có thể coi từ trường này là một loại nhiễu.
Nếu truyền dưới dạng âm thanh trong không khí thì tiếng ồn xung quanh
có thể coi là một loại nhiễu.
Trang 22Một số khái niệm (tt)
Nhiễu có nhiều loại chẳng hạn nhiễu cộng, nhiễu nhân
Nhiễu cộng là loại nhiễu mà tín hiệu mang tin bị tín hiệu nhiễu
“cộng” thêm vào
Nhiễu nhân là loại nhiễu mà tín hiệu mang tin bị tín hiệu nhiễu
“nhân” lên
Nơi nhận tin (sink)
Là nơi tiếp nhận thông tin từ kênh truyền và cố gắng khôi phục lại thành thông tin ban đầu như bên phát đã phát đi
Tin đến được nơi nhận thường không giống như tin ban đầu vì
có sự tác động của nhiễu Vì vậy nơi nhận phải thực hiện việc
phát hiện sai và sửa sai
Nơi nhận còn có thể phải thực hiện việc giải nén hay giải mã thông tin đã được mã hoá bảo mật nếu như bên phát đã thực hiện việc nén hay bảo mật thông tin trước khi truyền
Trang 23Các loại hệ thống truyền tin
Các nguồn tin thường thấy trong tự nhiên được gọi là các nguồn tin nguyên thuỷ Đây là các nguồn tin chưa qua bất kỳ một phép biến đổi nhân tạo nào
Các tín hiệu âm thanh, hình ảnh được phát ra từ các nguồn tin nguyên thuỷ này thường là các hàm liên tục theo thời gian và theo mức, nghĩa là có thể biểu diễn một thông tin nào đó dưới
dạng một hàm s(t) tồn tại trong một quãng thời gian T và lấy
các trị bất kỳ trong một phạm vi (smin, smax) nào đó.
s(t)
t
s max
s min
Trang 24Các loại hệ thống truyền tin (tt)
Các nguồn như vậy được gọi là các nguồn liên tục (continuous source), các tin được gọi là tin liên tục (continuous information)
và kênh tin được gọi là kênh liên tục (continuous channel)
Tuy nhiên vẫn có những nguồn nguyên thuỷ là rời rạc
Bảng chữ cái của một ngôn ngữ.
Các tin trong hệ thống điện tín, các lệnh điều khiển trong một hệ thống điều khiển,
Trong trường hợp này các nguồn được gọi là nguồn rời rạc
(discrete source), các tin được gọi là tin rời rạc (discrete
information) và kênh tin được gọi là kênh rời rạc (discrete
Trang 25Rời rạc hóa
Các hệ thống liên tục có nhiều nhược điểm của như cồng kềnh, không hiệu quả, và chi phí cao
Các hệ thống truyền tin rời rạc có nhiều ưu điểm hơn, khắc
phục được những nhược điểm trên của các hệ thống liên tục và đặc biệt đang ngày càng được phát triển và hoàn thiện dần
những sức mạnh và ưu điểm của nó
Rời rạc hoá thường bao gồm hai loại: Rời rạc hoá theo trục thời gian, còn được gọi là lấy mẫu (sampling) và rời rạc hoá theo
biên độ, còn được gọi là lượng tử hoá (quantize)
Lấy mẫu một hàm là trích ra từ hàm ban đầu các mẫu được lấy tại những thời điểm xác định
Vấn đề là làm thế nào để sự thay thế hàm ban đầu bằng các mẫu này là một sự thay thế tương đương, điều này đã được giải
quyết bằng định lý lấy mẫu nổi tiếng của Shannon
Trang 27Rời rạc hóa (tt)
Lượng tử hoá (Quantize)
Biên độ của các tín hiệu thường là một miền liên tục (s min , s max) Lượng tử hoá là phân chia miền này thành một số mức nhất
định, chẳng hạn là s min = s0, s1, , s n = s max và qui các giá trị
biên độ không trùng với các mức này về mức gần với nó nhất
Việc lượng tử hoá sẽ biến đổi hàm s(t) ban đầu thành một hàm s’(t) có dạng hình bậc thang Sự khác nhau giữa s(t) và s’(t)
được gọi là sai số lượng tử Sai số lượng tử càng nhỏ thì s’(t) biểu diễn càng chính xác s(t).
s(t)
t
s max
s min
Trang 28 Một nguồn rời rạc là một bảng chữ cái A gồm m kí hiệu, A =
{a1, a2, , a m }, với những xác suất xuất hiện p(a i ), i = 1, , m.
Định nghĩa không diễn tả mối quan hệ giữa tin trước và sau
trong một bản tin, nên đây được gọi là một nguồn rời rạc không nhớ (discrete memoryless source)
Bảng tin của một nguồn tin rời rạc không nhớ
Là một dãy (có thể vô hạn) các kí hiệu liên tiếp từ bảng chữ cái của nguồn tin, x = ( a–2a–1a0a1a2 )
Trong thực tế bảng tin có bắt đầu và kết thúc cho nên bảng tin
là một dãy hữu hạn các kí hiệu, x* = (a1a2 …a n)
Trang 29Bài 3 Chuẩn bị toán học
3.1 Xác suất (Probability)
3.2 Bất đẳng thức Chebyshev và luật yếu của số lớn 3.3 Tập lồi (Convex sets) và hàm lồi (convex
functions), bất đẳng thức Jensen
Trang 30Xác suất
Là tập (hay không gian) tất cả các kết quả có thể có của một thínghiệm Thường được kí hiệu là E hay S Nếu không gian mẫu
là rời rạc thì E có thể được biểu diễn bằng E = {e1, e2, , e n}
Sự kiện (Event), sự kiện cơ bản (elementary event)
Mỗi tập con của E (không gian mẫu) được gọi là một sự kiện, đặc biệt mỗi phần tử của E được gọi là một sự kiện cơ bản.
Trang 31Xác suất (tt)
Lấy một văn bản tiếng Anh điển hình và nhặt một kí tự bất kỳ
thì E = {a, b, c, , x, y, z} và xác suất của các kí tự được phân
bố như sau P(a) = 0,0642 , , P(e) = 0,103 , , P(z) = 0,0005.
Biến ngẫu nhiên rời rạc (Discrete random variable)
Một biến ngẫu nhiên rời rạc x được định nghĩa bằng cách gán một số thực x i tới mỗi sự kiện cơ bản e i của không gian mẫu rời
rạc E Xác suất của x i được định nghĩa là xác suất của sự kiện
cơ bản tương ứng và được kí hiệu là p(x i)
Trị trung bình (kỳ vọng) (average, expected value),
phương sai (variance)
Trị trung bình và phương sai của biến ngẫu nhiên rời rạc x lần
lượt được kí hiệu và định nghĩa như sau
Trang 32Xác suất (tt)
Var(x) =
=
trong đó E(x2) là trị kỳ vọng của x2
Tổng quát, trị kỳ vọng của một hàm của x, chẳng hạn f(x), được
định nghĩa bằng
Xác suất đồng thời (joint probability), xác suất có điều
kiện (conditional probability)
Một cặp biến ngẫu nhiên (x, y) liên kết với một thí nghiệm tạo thành một biến ngẫu nhiên nối (joint random variable) Nếu x, y
là rời rạc, sự phân bố xác suất nối hay xác suất đồng thời được định nghĩa là
f
Trang 33i j
x p
y x
p x
p ,
Trang 34Xúc xắc
Đồng xu
Trang 35Xác suất (tt)
Sự độc lập (Independence)
Hai biến ngẫu nhiên x và y được gọi là độc lập nếu
p(x i , y j ) = p(x i )p(y j) ∀ i, j
Chúng ta thấy nếu hai biến x và y độc lập thì
có nghĩa là xác suất y j trong điều kiện có x i xảy ra hay không xảy ra đều như nhau, không thay đổi, và ngược lại
Cũng từ sự độc lập chúng ta suy ra một kết quả mà hay được sửdụng sau này
E(xy) = E(x) E(y) =
i
j i
i
j i i
x p
y p x
p x
p
y x
p x
y
yx
Trang 36Xác suất (tt)
Sự tương quan (correlation)
Sự tương quan C giữa hai biến x và y được định nghĩa là trị kỳ
vọng của (x – )(y – ):
C(x, y) = E((x – )(y – )) =
= E(xy) –
Trong trường hợp x và y là độc lập chúng ta suy ra C(x, y) = 0
Tuy nhiên điều ngược lại thì không đúng
y x
Trang 37Bất đẳng thức Chebyshev
và luật yếu của số lớn
Cho một biến ngẫu nhiên x có trị trung bình là và phương sai
là , bất đẳng thức Chebyshev đối với một số dương tuỳ ý δ là
δ
2 x
0
x x
1 x
x
Q1
Trang 38Slide 37
Q1 Bất đẳng thức Chebyshev chỉ ra cận trên của xác suất để một đại lượng ngẫu nhiên lệch khỏi kỳ vọng toán học của nó: giả sử X là đại
lượng ngẫu nhiên có kỳ vọng toán học là EX=a và phương sai DX=d2 Bất đẳng thức Chebyshev chỉ rõ rằng với e>0 cho trước, xác suất của biến cố |X-a|>=e không vượt quá d2/e2 Bất đẳng thức này được dùng để chứng minh luật số lớn.
Quang, 3/12/2008
Trang 392 x
x
2 x
x x
x
δ
δ δ
δ
Trang 40Luật yếu của số lớn (tt)
Xét một thí nghiệm nhị phân trong đó các kết quả của thí
nghiệm là 0 và 1 với các xác suất tương ứng là p0 và 1– p0
Thí nghiệm này được lặp lại N lần một cách độc lập, và kết quả
trung bình được định nghĩa là yN; tức là, yN bằng tổng số các số
1 trong N lần thí nghiệm chia cho N.
Rõ ràng, yN là một biến ngẫu nhiên có không gian mẫu là {0,
N 1 x
1 y
Trang 41Luật yếu của số lớn (tt)
( )
1 y
n N
N
E N
n
n N
N
N
E E
1
N N
N
n
x 2
1
2 2
1x
x
=
Trang 42Luật yếu của số lớn (tt)
Đối với một số nguyên dương tuỳ ý ε, theo bất đẳng thức
Chebyshev chúng ta có
từ đây chúng ta dẫn ra được luật yếu của số lớn
Chú ý rằng vế phải tiến tới 0 khi N tiến ra vô cùng.
Luật yếu của số lớn vì vậy khẳng đinh rằng trị trung bình mẫu
của x tiếp cận trị trung bình thống kê với xác suất cao khi N →
∞
y
| y y
x x
1
ε
δ ε
N N
Từ khóa » Slide Môn Lý Thuyết Thông Tin
-
Bài Giảng Môn Học Lý Thuyết Thông Tin - Hồ Văn Quân - TaiLieu.VN
-
[PDF]Lý Thuyết Thông Tin - Giáo Trình, Bài Giảng, Bài Tập Lớn, đề Thi
-
[PDF]Lý Thuyết Thông Tin - Hv Công Nghệ Bcvt - Nguyễn Bình
-
Slide Môn: Lý Thuyết Thông Tin
-
Tài Liệu Môn Lý Thuyết Thông Tin
-
Slide Bài Giảng Môn Môn Học Lý Thuyết Thông Tin - Một Số Khái Niệm ...
-
Lý Thuyết Thông Tin - Kho Tài Liệu Số - UIT
-
Hệ Thống Thông Tin - SlideShare
-
LÝ THUYẾT THÔNG TIN PDF - Download Thư Viện Tài Liệu Miên Phí
-
(PDF) Giáo Trình: Lý Thuyết Thông Tin | Thientai Nguyen
-
Tài Liệu Slide Lý Thuyết Thông Tin - MegaCode
-
Giáo Trình Lý Thuyết Thông Tin
-
[PDF] Giáo Trình Lý Thuyết Thông Tin - Đào Tạo Từ Xa PTIT