Xem mẫu
TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT HƯNG YÊN
KHOA ĐIỆN-ĐIỆN TỬ
BÀI GIẢNG
LÝ THUYẾT THÔNG TIN
Hưng Yên 2015
(Tài liệu lưu hành nội bộ)
TỔNG QUAN VỀ MÔN HỌC
Chƣơng 1: Khái niệm chung.
Chƣơng này giới thiệu những khái niệm và các vấn đề cơ bản trong lý thuyết truyền
tin nhƣ thông tin, tín hiệu, mô hình của hệ thống truyền tin gồm những thành phần nào và
các tham số cơ bản của hệ thống là gì. Mặt khác chƣơng này cũng nhắc lại phƣơng pháp
rời rạc hóa một nguồn tin liên tục thành nguồn rời rạc. Cuối chƣơng đƣa ra khái niệm về độ
đo thông tin và nhắc lại những cơ sở toán học cần thiết cho việc khảo sát các hệ thống
truyền tin.
Chƣơng 2: Thông tin
Chƣơng này trình bày những vấn đề về định lƣợng thông tin của nguồn tin nhƣ
lƣợng tin riêng, lƣợng tin trung bình, lƣợng tin tƣơng hỗ, lƣợng tin có điều kiện (vì tín hiệu
truyền trên kênh bị nhiễu tác động nên khi thu đƣợc tín hiệu ta phải tìm khả năng đầu phát
đã phát đi tín hiệu nào vì vậy chƣơng này liên quan nhiều đến xác suất. Cụ thể là xác suất
riêng, xác suất đồng thời và xác suất có điều kiện và mối liên hệ chúng). Sau đó tập trung
giải quyết các vấn đề về entropy để đo lƣợng tin không chắc chắn của một sự kiện hay
phân phối ngẫu nhiên cũng nhƣ các tính chất của nó. Khi tín hiệu đƣợc truyền đi trên kênh
nên chƣơng này cũng đƣa ra các loại kênh truyền và các tham số kỹ thuật của kênh đồng
thời xác định độ không chắc chắn khi nhận đƣợc một tin cụ thể đã bị nhiễu phá hủy một
phần trên kênh từ đó tính toán dung lƣợng C của kênh truyền để xác định giới hạn trên của
tốc độ mà ta có thể truyền không lỗi.
Phần cuối của chƣơng sẽ đề cập đến việc giải mã (tức nhận đƣợc một tin ta phải đi
tìm tin nào đã đƣợc truyền đi ở bên phát). Sau đó tính các xác suất truyền sai một từ mã và
xác suất truyền sai trung bình.
Chƣơng 3: Mã hiệu.
Chƣơng này ta tập trung vào các khả năng và các định nghĩa về mã cũng nhƣ các
điều kiện và yêu cầu đối với mã hiệu, tức là đƣa ra các phƣơng pháp để lựa chọn, kiểm tra
một bộ mã là phân tách đƣợc và khi nào thì có thể giải mã (độ chậm giải mã). Phần cuối
của chƣơng nói về việc lập một bộ mã hệ thống.
Chƣơng 4: Mã hóa nguồn.
Chƣơng này nghiên cứu các vấn đề mã hóa nguồn trên cơ sở mô hình toán học của
nguồn và các khả năng về lƣợng tin đã xét. Cụ thể chƣơng này đề cập đến 3 phƣơng pháp
mã hóa để loại bỏ sự dƣ thừa của thông tin. Ba phƣơng pháp đó là:
Phƣơng pháp mã hóa Shannon.
Phƣơng pháp mã hóa Fano.
Phƣơng pháp mã hóa Huffman.
Mỗi phƣơng pháp đều đƣa ra phƣơng pháp chuyển các tin thành các từ mã dựa vào
xác suất xuất hiện của nó (tức là các tin có xác suất xuất hiện bé thì mã hóa bằng từ mã có
chiều dài lớn và các tin có xác suất xuất hiện lớn thì mã hóa bằng từ mã có chiều dài nhỏ)
và sau đó tính hiệu suất lập mã.
§Ò c-¬ng bµi gi¶ng
M«n: Lý thuyÕt th«ng tin
Chƣơng 5. Mã phát hiện lỗi và sửa lỗi
Trong chƣơng 4 ta nghiên cứu các phƣơng pháp để giảm chiều dài trung bình của
một bộ mã dựa vào xác suất xuất hiện của từng lớp tin thì trong chƣơng này ta lại thêm vào
một số bít kiểm tra để phát hiện sai và sửa sai để đảm bảo chất lƣợng. Cụ thể ta nghiên cứu
đến 4 loại mã là:
Mã khối tuyến tính.
Mã Hamming
Mã vòng.
Mã chập.
Mỗi loại mã đều đƣa ra phƣơng pháp lập mã và giải mã. Để học tốt về chƣơng này sinh
viên cần có kiến thức về nhân chia đa thức và các phép biến đổi sơ cấp về ma trận.
Chƣơng 6: Mã mật.
Chƣơng 4 đƣợc nghiên cứu với mục đích đảm bảo tính hữu hiệu của hệ thống
truyền tin thì chƣơng 5 đƣợc nghiên cứu với mục đích đảm bảo chất lƣợng và chƣơng 6 sẽ
đảm bảo tính an toàn. Trong chƣơng này ta sẽ nghiên cứu một số hệ thống mật mã đơn
giản để có cách nhìn sơ lƣợc về mã mật và sau đó tập trung vào trình bày các cách thức tấn
công vào một hệ thống mật mã.
2
§Ò c-¬ng bµi gi¶ng
M«n: Lý thuyÕt th«ng tin
CHƢƠNG 1: KHÁI NIỆM CHUNG
1.1 Khái niệm chung về hệ thống thông tin và truyền tin.
1.1.1. Thông tin.
- Hai ngƣời nói chuyện với nhau. Cái mà họ trao đổi gọi là thông tin.
- Một ngƣời xem tivi/nghe đài/đọc báo, ngƣời đó đang nhận thông tin từ đài
phát/báo.
- Quá trình giảng dạy trong lớp.
Nhận xét:
+ Thông tin là cái đƣợc truyền từ đối tƣợng này sang đố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 nhƣ â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.
+ Một trong các 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.
Định nghĩa: Thông tin là sự cảm hiểu của con ngƣời về thế giới xung quanh
(thông qua sự tiếp xúc với nó).
1.1.2. Tín hiệu.
Thông tin là một hiện tƣợng vật lý, nó thƣờng tồn tại và đƣợc truyền đi dƣới
dạng vật chất nào đó. Những dạng vật chất dùng để mang thông tin đƣợc gọi là tín
hiệu.
Định nghĩa: Tín hiệu là biểu diễn vật lý của thông tin.
Ví dụ: Các tín hiệu nhìn thấy là các song ánh sang mang thông tin tới mắt
của chúng ta. Các tín hiệu nghe thấy là các sự biến đổi của áp suất không khí truyền
thông tin tới tai chúng ta.
Chú ý: Không phải bản thân quá trình vật lý là tín hiệu, mà sự biến đổi các
tham số riêng của quá trình vật lý mới là tín hiệu.
Các đặc trƣng vật lý có thể là dòng điện, điện áp, ánh sáng, âm thanh, trƣờng
điện từ.
1.2 Mô hình của 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.
3
§Ò c-¬ng bµi gi¶ng
M«n: Lý thuyÕt th«ng tin
Hệ thống thông tin (hệ thống truyền tin) là hệ thống thực hiện việc chuyển
tin từ nguồn đến đích. Ta xét một hệ thống thông tin tổng quát nhƣ hình vẽ dƣới
đây.
Nguồn tin
Bộ phát
Kênh truyền
Bộ thu
Ngƣời dùng
Nhiễu
Ba phần tử cơ bản nhất của bất cứ hệ thống thông tin nào cũng phải có đó là
máy phát, máy thu và kênh truyền. Mỗi phần tử có một vai trò nhất định trong việc
truyền dẫn tín hiệu.
Máy phát xử lý tín hiệu đầu vào và tạo ra tín hiệu có những đặc tính thích
hợp với kênh truyền dẫn. Quá trình xử lý tín hiệu để truyền dẫn chủ yếu là điều chế
và mã hóa (modulation and coding).
Kênh truyền là môi trƣờng giữa điểm phát và điểm thu. Kênh truyền có thể là
cáp song hành, cáp đồng trục, cáp quang hay môi trƣờng vô tuyến. Mọi kênh truyền
đều gây ra độ suy hao hay là độ tổn thất truyền dẫn. Vì thế cƣờng độ tín hiệu bị suy
giảm dần theo khoảng cách.
Máy thu lấy tín hiệu đầu ra từ kênh truyền để xử lý và tái tạo ngƣợc lại tín
hiệu ở đầu phát. Các hoạt động của máy thu bao gồm khuếch đại để bù vào tổn hao
truyền dẫn, và giải điều chế và giải mã tín hiệu đã đƣợc điều chế và mã hóa ở máy
phát.
1.3. Các yêu cầu cơ bản của hệ thống truyền tin.
1.3.1. Tính hữu hiệu.
Thể hiện trên các mặt sau:
- Tốc độ truyền tin cao.
- Truyền đƣợc đồng thời nhiều tin khác nhau.
- Chi phí cho một bit thông tin thấp.
1.3.2. Độ tin cậy.
Đảm bảo độ chính xác của việc thu nhận tin cao, xác suất thu sai thấp (BER
– Bit Error Rate).
Hai ch tiêu trên mâu thuẫn nhau. Giải quyết mâu thuẫn trên là nhiệm vụ của
4
nguon tai.lieu . vn
KHOA ĐIỆN-ĐIỆN TỬ
BÀI GIẢNG
LÝ THUYẾT THÔNG TIN
Hưng Yên 2015
(Tài liệu lưu hành nội bộ)
TỔNG QUAN VỀ MÔN HỌC
Chƣơng 1: Khái niệm chung.
Chƣơng này giới thiệu những khái niệm và các vấn đề cơ bản trong lý thuyết truyền
tin nhƣ thông tin, tín hiệu, mô hình của hệ thống truyền tin gồm những thành phần nào và
các tham số cơ bản của hệ thống là gì. Mặt khác chƣơng này cũng nhắc lại phƣơng pháp
rời rạc hóa một nguồn tin liên tục thành nguồn rời rạc. Cuối chƣơng đƣa ra khái niệm về độ
đo thông tin và nhắc lại những cơ sở toán học cần thiết cho việc khảo sát các hệ thống
truyền tin.
Chƣơng 2: Thông tin
Chƣơng này trình bày những vấn đề về định lƣợng thông tin của nguồn tin nhƣ
lƣợng tin riêng, lƣợng tin trung bình, lƣợng tin tƣơng hỗ, lƣợng tin có điều kiện (vì tín hiệu
truyền trên kênh bị nhiễu tác động nên khi thu đƣợc tín hiệu ta phải tìm khả năng đầu phát
đã phát đi tín hiệu nào vì vậy chƣơng này liên quan nhiều đến xác suất. Cụ thể là xác suất
riêng, xác suất đồng thời và xác suất có điều kiện và mối liên hệ chúng). Sau đó tập trung
giải quyết các vấn đề về entropy để đo lƣợng tin không chắc chắn của một sự kiện hay
phân phối ngẫu nhiên cũng nhƣ các tính chất của nó. Khi tín hiệu đƣợc truyền đi trên kênh
nên chƣơng này cũng đƣa ra các loại kênh truyền và các tham số kỹ thuật của kênh đồng
thời xác định độ không chắc chắn khi nhận đƣợc một tin cụ thể đã bị nhiễu phá hủy một
phần trên kênh từ đó tính toán dung lƣợng C của kênh truyền để xác định giới hạn trên của
tốc độ mà ta có thể truyền không lỗi.
Phần cuối của chƣơng sẽ đề cập đến việc giải mã (tức nhận đƣợc một tin ta phải đi
tìm tin nào đã đƣợc truyền đi ở bên phát). Sau đó tính các xác suất truyền sai một từ mã và
xác suất truyền sai trung bình.
Chƣơng 3: Mã hiệu.
Chƣơng này ta tập trung vào các khả năng và các định nghĩa về mã cũng nhƣ các
điều kiện và yêu cầu đối với mã hiệu, tức là đƣa ra các phƣơng pháp để lựa chọn, kiểm tra
một bộ mã là phân tách đƣợc và khi nào thì có thể giải mã (độ chậm giải mã). Phần cuối
của chƣơng nói về việc lập một bộ mã hệ thống.
Chƣơng 4: Mã hóa nguồn.
Chƣơng này nghiên cứu các vấn đề mã hóa nguồn trên cơ sở mô hình toán học của
nguồn và các khả năng về lƣợng tin đã xét. Cụ thể chƣơng này đề cập đến 3 phƣơng pháp
mã hóa để loại bỏ sự dƣ thừa của thông tin. Ba phƣơng pháp đó là:
Phƣơng pháp mã hóa Shannon.
Phƣơng pháp mã hóa Fano.
Phƣơng pháp mã hóa Huffman.
Mỗi phƣơng pháp đều đƣa ra phƣơng pháp chuyển các tin thành các từ mã dựa vào
xác suất xuất hiện của nó (tức là các tin có xác suất xuất hiện bé thì mã hóa bằng từ mã có
chiều dài lớn và các tin có xác suất xuất hiện lớn thì mã hóa bằng từ mã có chiều dài nhỏ)
và sau đó tính hiệu suất lập mã.
§Ò c-¬ng bµi gi¶ng
M«n: Lý thuyÕt th«ng tin
Chƣơng 5. Mã phát hiện lỗi và sửa lỗi
Trong chƣơng 4 ta nghiên cứu các phƣơng pháp để giảm chiều dài trung bình của
một bộ mã dựa vào xác suất xuất hiện của từng lớp tin thì trong chƣơng này ta lại thêm vào
một số bít kiểm tra để phát hiện sai và sửa sai để đảm bảo chất lƣợng. Cụ thể ta nghiên cứu
đến 4 loại mã là:
Mã khối tuyến tính.
Mã Hamming
Mã vòng.
Mã chập.
Mỗi loại mã đều đƣa ra phƣơng pháp lập mã và giải mã. Để học tốt về chƣơng này sinh
viên cần có kiến thức về nhân chia đa thức và các phép biến đổi sơ cấp về ma trận.
Chƣơng 6: Mã mật.
Chƣơng 4 đƣợc nghiên cứu với mục đích đảm bảo tính hữu hiệu của hệ thống
truyền tin thì chƣơng 5 đƣợc nghiên cứu với mục đích đảm bảo chất lƣợng và chƣơng 6 sẽ
đảm bảo tính an toàn. Trong chƣơng này ta sẽ nghiên cứu một số hệ thống mật mã đơn
giản để có cách nhìn sơ lƣợc về mã mật và sau đó tập trung vào trình bày các cách thức tấn
công vào một hệ thống mật mã.
2
§Ò c-¬ng bµi gi¶ng
M«n: Lý thuyÕt th«ng tin
CHƢƠNG 1: KHÁI NIỆM CHUNG
1.1 Khái niệm chung về hệ thống thông tin và truyền tin.
1.1.1. Thông tin.
- Hai ngƣời nói chuyện với nhau. Cái mà họ trao đổi gọi là thông tin.
- Một ngƣời xem tivi/nghe đài/đọc báo, ngƣời đó đang nhận thông tin từ đài
phát/báo.
- Quá trình giảng dạy trong lớp.
Nhận xét:
+ Thông tin là cái đƣợc truyền từ đối tƣợng này sang đố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 nhƣ â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.
+ Một trong các 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.
Định nghĩa: Thông tin là sự cảm hiểu của con ngƣời về thế giới xung quanh
(thông qua sự tiếp xúc với nó).
1.1.2. Tín hiệu.
Thông tin là một hiện tƣợng vật lý, nó thƣờng tồn tại và đƣợc truyền đi dƣới
dạng vật chất nào đó. Những dạng vật chất dùng để mang thông tin đƣợc gọi là tín
hiệu.
Định nghĩa: Tín hiệu là biểu diễn vật lý của thông tin.
Ví dụ: Các tín hiệu nhìn thấy là các song ánh sang mang thông tin tới mắt
của chúng ta. Các tín hiệu nghe thấy là các sự biến đổi của áp suất không khí truyền
thông tin tới tai chúng ta.
Chú ý: Không phải bản thân quá trình vật lý là tín hiệu, mà sự biến đổi các
tham số riêng của quá trình vật lý mới là tín hiệu.
Các đặc trƣng vật lý có thể là dòng điện, điện áp, ánh sáng, âm thanh, trƣờng
điện từ.
1.2 Mô hình của 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.
3
§Ò c-¬ng bµi gi¶ng
M«n: Lý thuyÕt th«ng tin
Hệ thống thông tin (hệ thống truyền tin) là hệ thống thực hiện việc chuyển
tin từ nguồn đến đích. Ta xét một hệ thống thông tin tổng quát nhƣ hình vẽ dƣới
đây.
Nguồn tin
Bộ phát
Kênh truyền
Bộ thu
Ngƣời dùng
Nhiễu
Ba phần tử cơ bản nhất của bất cứ hệ thống thông tin nào cũng phải có đó là
máy phát, máy thu và kênh truyền. Mỗi phần tử có một vai trò nhất định trong việc
truyền dẫn tín hiệu.
Máy phát xử lý tín hiệu đầu vào và tạo ra tín hiệu có những đặc tính thích
hợp với kênh truyền dẫn. Quá trình xử lý tín hiệu để truyền dẫn chủ yếu là điều chế
và mã hóa (modulation and coding).
Kênh truyền là môi trƣờng giữa điểm phát và điểm thu. Kênh truyền có thể là
cáp song hành, cáp đồng trục, cáp quang hay môi trƣờng vô tuyến. Mọi kênh truyền
đều gây ra độ suy hao hay là độ tổn thất truyền dẫn. Vì thế cƣờng độ tín hiệu bị suy
giảm dần theo khoảng cách.
Máy thu lấy tín hiệu đầu ra từ kênh truyền để xử lý và tái tạo ngƣợc lại tín
hiệu ở đầu phát. Các hoạt động của máy thu bao gồm khuếch đại để bù vào tổn hao
truyền dẫn, và giải điều chế và giải mã tín hiệu đã đƣợc điều chế và mã hóa ở máy
phát.
1.3. Các yêu cầu cơ bản của hệ thống truyền tin.
1.3.1. Tính hữu hiệu.
Thể hiện trên các mặt sau:
- Tốc độ truyền tin cao.
- Truyền đƣợc đồng thời nhiều tin khác nhau.
- Chi phí cho một bit thông tin thấp.
1.3.2. Độ tin cậy.
Đảm bảo độ chính xác của việc thu nhận tin cao, xác suất thu sai thấp (BER
– Bit Error Rate).
Hai ch tiêu trên mâu thuẫn nhau. Giải quyết mâu thuẫn trên là nhiệm vụ của
4