Giáo trình Lý thuyết thông tin - Trường Đại học Thái Nguyên

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 
4 
người ñã sử dụng và khai thác có rất nhiều dạng, khi phân loại chúng người ta 
có thể dựa trên nhiều cơ sở khác nhau. 
1.2.1 Các quan ñiểm ñể phân loại các hệ thống truyền tin 
• Theo 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) 
• 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 
Xuất phát từ các quan ñiểm ñó, trong thực tế trong nhiều lĩnh vực ñặc 
biệt là lĩnh vực truyền thông tồn tại các khái niệm như: Hệ phát thanh truyền 
hình, hệ truyền tín hiệu số, ... 
1.2.2 Sơ ñồ truyền tin và một số khái niệm trong hệ thống truyền tin 
ðịnh nghĩa: Truyền tin(transmission): 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). 
Sơ ñồ khối chức năng của một hệ thống truyền tin tổng quát gồm có 3 
thành phần chính: Nguồn tin, kênh tin và nhận tin. 
Trong ñó: 
NGUỒN TIN KÊNH TIN NHẬN TIN 
5 
• Nguồn tin: là nơi sản sinh ra hay chứa các tin cần truyền ñi, hay nguồn 
tin là tập hợp các tin mà hệ thống truyền tin dùng ñể tạo các bản tin khác nhau 
ñể truyền tin. 
• Kênh tin: là môi trường lan truyền thông tin. 
ðể có thể lan truyền ñược thông tin trong một môi trường vật lý xác 
ñịnh, thông tin phải ñược chuyển thành tín hiệu thích hợp với môi trường 
truyền lan. Như vậy ta có thể ñịnh nghĩa kênh tin: 
Kênh tin là nơi hình thành và truyền tín hiệu mang tin ñồng thời ở ñấy 
sinh ra các tạp nhiễu phá huỷ thông tin. 
Trong lý thuyết truyền tin, kênh là một khái niệm trìu tượng ñại diện cho 
sự hỗn hợp giữa tín hiệu và tạp nhiễu. Từ khái niệm này, sự phân loại kênh sẽ 
dễ dàng hơn, mặc dù trong thực tế các kênh tin có rất nhiều dạng khác nhau. 
 Ví dụ: 
- Truyền tin theo dây song hành, cáp ñồng trục. 
- Tín hiệu truyền lan qua các tầng ñiện ly. 
- Tín hiệu truyền lan qua các tầng ñối lưu. 
- Tín hiệu truyền lan trên mặt ñất, trong ñất. 
- Tín hiệu truyền lan trong nước.. 
• Nhận tin: Là cơ cấu khôi phục thông tin ban ñầu từ tín hiệu thu ñược 
từ ñầu ra của kênh 
ðể tìm hiểu chi tiết hơn ta ñi sâu vào các khối chức năng của sơ ñồ 
truyền tin và xét ñến nhiệm vụ của từng khối. 
1.3 Nguồn tin nguyên thuỷ 
1.3.1 Khái niệm chung 
ðịnh nghĩa: Nguồn tin nguyên thuỷ là tập hợp những tin ban ñầu mà hệ thống 
thu nhận ñược chưa qua một phép biến ñối nhân tạo nào. 
Về mặt toán học, các tin nguyên thuỷ là những hàm liên tục theo thời 
gian )(tf hoặc là những hàm biến ñổi theo thời gian và một số thông số khác 
như hình ảnh ñen trắng ),,( tyxh trong ñó yx, là các toạ ñộ không gian, hoặc 
như các thông tin khí tượng ),( tg iλ trong ñó iλ là các thông số khí tượng như 
nhiệt ñộ, ñộ ẩm, tốc ñộ gió,.. 
6 
Thông tin nguyên thuỷ cũng có thể là các hệ hàm theo thời gian và các 
thông số như trường hợp thông tin hình ảnh màu: 
( , , )
( , , ) ( , , ) .
( , , )
f x y z
K x y z g x y z
h x y z


= 


Các tin nguyên thuỷ phần lớn là hàm liên tục của thời gian trong một 
ngưỡng 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 quãng thời gian T và lấy các giá trị bất kỳ trong phạm vi 
( maxmin , SS ) trong ñó min max,S S là ngưỡng nhỏ nhất và lớn nhất mà hệ thống 
có thể thu nhận ñược. 
 Smax 
 Smin 
Tin nguyên thuỷ có thể trực tiếp ñưa vào hệ thống truyền tin nhưng cần 
phải qua các phép biến ñổi sao cho phù hợp với hệ thống tương ứng. Như vậy 
xét về quan ñiểm truyền tin thì có hai loại tin và hai loại hệ thống tương ứng: 
• Tin rời rạc ứng với 
- Nguồn rời rạc 
- Kênh rời rạc 
• Tin liên tục ứng với 
- Nguồn liên tục 
- Kênh liên tục 
Sự phân biệt về bản chất của nguồn rời rạc với nguồn liên tục ñược hiểu 
là số lượng các tin trong nguồn rời rạc là hữu hạn và số lượng các tin trong 
nguồn liên tục là không ñếm ñược. 
7 
Nói chung các tin rời rạc, hoặc nguyên thuỷ rời rạc, hoặc nguyên thuỷ 
liên tục ñã ñược rời rạc hoá trước khi ñưa vào kênh thông thường ñều qua thiết 
bị mã hoá. Thiết bị mã hoá biến ñổi tập tin nguyên thuỷ thành tập hợp những 
tin thích hợp với ñặc ñiểm cơ bản của kênh như khả năng cho qua (thông 
lượng), tính chất tín hiệu và tập nhiễu. 
1.3.2 Bản chất của thông tin theo quan ñiểm truyền tin 
Chỉ có quá trình ngẫu nhiên mới tạo ra thông tin. Một hàm gọi là ngẫu 
nhiên nếu với một giá trị bất kì của ñối số, giá trị của hàm là một ñại lượng 
ngẫu nhiên (các ñại lượng vật lí trong thiên nhiên như nhiệt ñộ môi trường, áp 
suất không khí là hàm ngẫu nhiên của thời gian). 
Một quá trình ngẫu nhiên ñược quan sát bằng một tập các giá trị ngẫu 
nhiên. Quá trình ngẫu nhiên ñược coi là biết rõ khi thu nhận và xử lí ñược một 
tập ñủ nhiều các giá trị ñặc trưng của nó. 
Giả sử quá trình ngẫu nhiên X(t) có một tập các giá trị mẫu (hay còn 
ñược gọi là các biến) ( )x t , khi ñó ta biểu diễn quá trình ngẫu nhiên bởi: 
{ }( ) ( )
x X
X t x t
∈
= 
Ví dụ: Quan sát thời gian vào mạng của các sinh viên trong 1 ngày, 
người ta tiến hành phỏng vấn 10 sinh viên, gọi X là thời gian vào mạng, kx 
là thời gian vào mạng của sinh viên thứ , ( 1,2,...,10)k k = ta thu ñược mẫu 
như sau: 
{ }10, 50, 20,150,180, 30, 30, 5, 60, 0X = ñơn vị tính (phút) 
Việc ñoán trước một giá trị ngẫu nhiên là khó khăn. Ta chỉ có thể tìm 
ñược quy luật phân bố của các biến thông qua việc áp dụng các qui luật của 
toán thống kê ñể xử lý các giá trị của các biến ngẫu nhiên mà ta thu ñược từ 
các tín hiệu. 
Quá trình ngẫu nhiên có thể là các hàm trong không gian 1 chiều, khi ñó 
ta có quy luật phân phối xác suất 1 chiều và hàm mật ñộ phân phối xác suất 
ñược xác ñịnh bởi các công thức 
( )( ) ( ); ( ) dF xF x p X x w x
dx
= < = 
8 
Trong ñó: 
• x là biến ngẫu nhiên 
• p(x) xác suất xuất hiện X x= trong quá trình ngẫu nhiên, thường 
ñược viết là ( ) ( )p x p X x= = . 
Nếu quá trình ngẫu nhiên là các hàm trong không gian 2 chiều khi ñó 
quy luật ngẫu nhiên ñược biểu hiện bởi các công thức 
2
( , ) ( ; ); ( , ) .xy
FF x y p X x Y y w x y
x y
∂
= < < =
∂ ∂
Tương tự, ta cũng có các quy luật phân phối xác suất trong không gian 
nhiều chiều. 
Các ñặc trưng quan trọng của biến ngẫu nhiên 
1. Trị trung bình (kì vọng toán học) của một quá trình ngẫu nhiên ( )X t 
( ) ( ) ( ) ( )E X X t x t w x dx
+∞
−∞
= = ∫ 
 2. Trị trung bình bình phương 
2 2 2( ) ( ) ( ) ( )E X X t x t w x dx
+∞
−∞
= = ∫ 
3. Phương sai 
( ) ( )2 2( ) ( ) ( ) ( )D X X X x t E x w x dx+∞
−∞
= − = −∫ 
4. Hàm tương quan 
Mô tả mối quan hệ thống kê giữa các giá trị của 1 quá trình ngẫu nhiên 
ở các thời ñiểm t1, t2 
( )1 2 1 2 1 2 1 2 1 2( , ) ( ), ( ) ( ( ), ( ))xB t t E X t X t x x w x t x t dx dx
+∞ +∞
−∞ −∞
= = ∫ ∫ 
Nếu hai quá trình ,X Y khác nhau ở hai thời ñiểm khác nhau, khi ñó 
( )1 2 1 2 1 2( , ) ( ), ( ) ( ( ), ( ))xyB t t E X t Y t xyw x t y t dxdy
+∞ +∞
−∞ −∞
= = ∫ ∫ 
9 
ðể giải quyết bài toán một cách thực tế, người ta không thể xác ñịnh tức 
thời mà thường lấy trị trung bình của quá trình ngẫu nhiên. Có hai loại trị 
trung bình theo tập hợp và trị trung bình theo thời gian. Ta cần nghiên cứu trị 
trung bình theo tập hợp, tuy vậy sẽ gặp nhiều khó khăn khi tiếp nhận và xử lý 
tức thời các biến ngẫu nhiên vì các biến ngẫu nhiên luôn biến ñổi theo thời 
gian. ðể tính trị trung bình theo thời gian, ta chọn thời gian ñủ lớn ñể quan sát 
các biến ngẫu nhiên dễ ràng hơn vì có ñiều kiện quan sát và sử dụng các công 
thức thống kê, khi ñó việc tính các giá trị trung bình theo thời gian ñược xác 
ñịnh bởi các công thức: 
0
1( ) ( )
T
T
X t Lim x t dt
T→+∞
= ∫ 
Trị trung bình bình phương: 
2 2
0
1( ) ( )
T
T
X t Lim x t dt
T→+∞
= ∫ 
Khi thời gian quan sát T dần ñến vô cùng thì trị trung bình tập hợp bằng 
trị trung bình thời gian. Trong thực tế ta thường chọn thời gian quan sát ñủ lớn 
chứ không phải vô cùng như vậy vẫn thoả mãn các ñiều kiện cần nhưng ñơn 
giản hơn, khi ñó ta có trị trung bình theo tập hợp bằng trị trung bình theo thời 
gian. Ta có: 
0
1( ) ( ) ( ) ( )
T
T
X t x t w x dx Lim x t dt
T
+∞
→+∞
−∞
= =∫ ∫ 
Tương tự: 
2 2 2
0
1( ) ( ) ( ) ( )
T
T
X t x t w x dx Lim x t dt
T
+∞
→+∞
−∞
= =∫ ∫ 
Trường hợp này gọi chung là quá trình ngẫu nhiên dừng theo hai nghĩa: 
• Theo nghĩa hẹp: Trị trung bình chỉ phụ thuộc khoảng thời gian quan sát 
2 1t tτ = − mà không phụ thuộc gốc thời gian quan sát. 
10 
• Theo nghĩa rộng: Gọi là quá trình ngẫu nhiên dừng khi trị trung bình là 
một hằng số và hàm tương quan chỉ phụ thuộc vào hiệu hai thời gian quan sát 
2 1t tτ = − . Khi ñó ta có mối tương quan 
1 2 2 1
1 2 1 2 1 2
( , ) ( ) ( ) ( ). ( )
1( , ) ( ) ( )
x
T
T
B t t B t t B X t X t
x x w x x dx dx Lim x t x t dt
T
τ τ τ
τ
+∞ +∞
→+∞
−∞ −∞ −∞
= = − = = +
= = +∫ ∫ ∫
Tóm lại: ðể nghiên cứu ñịnh lượng nguồn tin, hệ thống truyền tin mô hình 
hoá nguồn tin bằng 4 quá trình sau: 
1. Quá trình ngẫu nhiên liên tục: Nguồn tiếng nói, âm nhạc, hình ảnh là tiêu 
biểu cho quá trình này. 
 2. Quá trình ngẫu nhiên rời rạc: là quá trình ngẫu nhiên liên tục sau khi 
ñược rời rạc hóa theo mức trở thành quá trình ngẫu nhiên rời rạc. 
3. Dãy ngẫu nhiên liên tục: ðây là trường hợp một nguồn liên tục ñã ñược 
gián ñoạn hóa theo thời gian, như thường gặp trong các hệ thống tin xung như: 
ñiều biên xung, ñiều tần xung ... không bị lượng tử hóa. 
4. Dãy ngẫu nhiên rời rạc: Nguồn liên tục ñược gián ñoạn theo thời gian 
hoặc trong hệ thống thông tin có xung lượng tử hoá. 
1.4 Hệ thống kênh tin 
1.4.1 Khái niệm 
Như chúng ta ñã biết: vật chất chỉ có thể dịch chuyển từ ñiểm này ñến 
một ñiểm khác trong một môi trường thích hợp và dưới tác ñộng của một lực 
thích hợp. Trong quá trình dịch chuyển của một dòng vật chất, những thông tin 
về nó hay chứa trong nó sẽ ñược dịch chuyển theo. ðây chính là bản chất của 
sự lan truyền thông tin. 
Vậy có thể nói rằng việc truyền tin chính là sự dịch chuyển của dòng các 
hạt vật chất mang tin (tín hiệu) trong môi trường. Trong quá trình truyền tin, 
hệ thống truyền tin phải gắn ñược thông tin lên các dòng vật chất tạo thành tín 
hiệu và lan truyền ñi. 
Việc tín hiệu lan truyền trong một môi trường xác ñịnh chính là dòng các 
hạt vật chất chịu tác ñộng của lực, lan truyền trong một cấu trúc xác ñịnh của 
11 
môi trường. Dòng vật chất mang tin này ngoài tác ñộng ñể dịch chuyển, còn 
chịu tác ñộng của các lực không mong muốn trong cũng như ngoài môi 
trường. ðây cũng chính là nguyên nhân làm biến ñổi dòng vật chất không 
mong muốn hay là nguyên nhân gây ra nhiễu trong quá trình truyền tin. 
Như vậy: Kênh tin là môi trường hình thành và truyền lan tín hiệu mang tin 
ñồng thời ở ñó sinh ra các tạp nhiễu phá hủy thông tin. 
1.4.2 P ... số nguyên tố p=2357 và phần tử sinh α =2∈ Z*2357. A chọn 
khoá riêng a = 1751 và tính aα mod p = 21751 mod 2357 = 1185. Khoá công 
khai của A là (p = 2357, α = 2, aα = 1185). 
Mã hoá: ðể mã hoá một văn bản m=2035, B chọn ngẫu nhiên một số nguyên 
k = 1520 và tính γ =21520 mod 2357 = 1430, 
δ = 2035×11851520 mod 2357 = 697. B gửi γ =1430 và δ =697 cho A. 
Giải mã: ðể giải mã, A thực hiện tính: m = 872*697 mod 2357 = 2035. 
Chú ý: Một bất lợi của mã hoá Elgamal là sự mở rộng của văn bản, bản mã có 
thể dài gấp 2 lần so với bản rõ. Mã hoá Elgamal là một trong những lược ñồ 
mã hoá sử dụng sự ngẫu nhiên trong tiến trình mã hoá. Những nguyên tắc cơ 
bản ñằng sau kỹ thuật mã hoá ngẫu nhiên là sử dụng tính ngẫu nhiên ñể tăng 
thêm sự bảo mật bằng mật mã của tiến trình mã hoá theo một trong các 
phương thức sau: 
1. Tăng dần khoảng trống trong bản rõ một cách phù hợp. 
2. Ngăn ngừa hoặc làm suy giảm sự có hiệu lực của sự tấn công bản 
rõ chọn trước thông qua ánh xạ một - nhiều từ bản rõ ñến bản mã. 
Tính bảo mật của mã hoá Elgamal 
Vấn ñề bẻ khoá lược ñồ mã hoá Elgamal, khôi phục m từ p, α , aα , γ , 
và δ tương ñương với giải quyết vấn ñề Diff-Hellman. Trên thực tế, lược ñồ 
mã hoá Elgamal ñược xem như sự thay ñổi khoá Diff-Hellman ñể quyết ñịnh 
khoá akα , và việc mã hoá văn bản bằng tính nhân với khoá ñó. Vì lý do này, 
130 
tính bảo mật của lược ñồ mã hoá Elgamal ñược gọi là cơ sở trong vấn ñề 
logarithm rời rạc trong Z*P . 
5.4.5 Hệ mã MHK (Merkle -Hellman Knapsack) 
Sơ ñồ mã khoá công khai ba lô dựa trên cơ sở của bài toán tập con, quan 
ñiểm cơ bản là chọn một trường hợp của bài toán tổng con mà dễ dàng tìm lời 
giải, sau ñó che giấu nó như một trường hợp của bài toán tổng con tổng quát 
khó có hy vọng giải ñược. Khoá ñược thiết lập ban ñầu có thể dùng như khoá 
riêng, còn khoá ñược thiết lập sau khi biến ñổi là khoá công khai. Sơ ñồ mã 
hoá MHK che giấu lời giải bằng phép nhân theo modulo và phép hoán vị. 
 ðịnh nghĩa một dãy siêu tăng là một dãy các số nguyên dương (b1,b2, ..., 
bn) thoả mãn tính chất 
1
1
i
i j
j
b b
−
=
>∑ với mỗi i, 2 ≤ i ≤ n. 
Thuật toán 
Tạo khoá: Mỗi thực thể tạo một khoá công khai và một khoá riêng tương ứng. 
Một số nguyên n ñược cố ñịnh như một tham số hệ thống phổ biến. 
1. Chọn một dãy siêu tăng (b1,b2, ..., bn) và modulo M sao cho 
 M > b1 + b2 + ... + bn. 
2. Chọn số nguyên ngẫu nhiên W 1 ≤ W ≤ M-1 sao cho UCLN(W, M) = 1. 
3. Chọn một phép hoán vị ngẫu nhiên pi của n số nguyên {1,2,...,n}. 
4. Tính ai = Wbpi (i) mod M với i = 1, 2, ..., n. 
5. Khoá công khai là (a1, a2, ..., an), khoá riêng là (pi , M, W, (b1,b2, ..., 
bn)). 
Mã hoá: B mã hoá văn bản m gửi cho A. 
1. Thu ñược khoá công khai (a1, a2, ..., an) của A. 
2. Biểu diễn văn bản m như một chuỗi nhị phân có ñộ dài n, m=m1m2...mn. 
3. Tính số nguyên c = m1a1 + m2a2 + ... + mnan. 
131 
4. Gửi bản mã c cho A. 
Giải mã: ðể khôi phục bản rõ m từ c, cần thực hiện các công việc sau: 
1. Tính d = W-1c mod M. 
2. Sử dụng thuật toán tìm lời giải bài toán tổng dãy siêu tăng ñể tìm các 
số nguyên r1,r2,...,rn,ri∈{0,1}, sao cho d=r1b1+r2b2+ ... +rnbn. 
3. Các bit văn bản m là mi = rpi (i), i = 1, 2, ..., n. 
Ví dụ 
Tạo khoá: Lấy n=6, chọn dãy siêu tăng (12, 17, 33, 74, 157, 316), M=737, 
W=635 và phép hoán vị pi của (1, 2, 3, 4, 5, 6) ñược ñịnh nghĩa bởi pi (1)=3, 
pi (2)=6, pi (3)=1, pi (4)=2, pi (5)=5, pi (6)=4. 
Khoá công khai là (319, 196, 250, 477, 200, 559), Khoá riêng là (pi , 
M, W, (12, 17, 33, 74, 157, 316)). 
Mã hoá: Văn bản m = 101101, tính: c = 319 + 250 + 477 + 559 = 1605 
Giải mã: Tính d = W-1c mod M = 136, và tìm lời giải cho bài toán tổng dãy 
siêu tăng: 136 = 12r1 + 17r2 + 33r3 +74r4 + 157r5 + 316r6, nhận ñược 136 = 12 
+ 17 + 33 + 74. Từ ñó r1 = 1, r2 = 1, r3 = 1, r4 = 1, r5 = 0, r6 = 0. Sử dụng phép 
hoán vị pi ñược các bit văn bản m: m1 = r3 = 1, m2 = r6 = 0, m3 = r1 = 1, m4 = 
r2 = 1, m5 = r5 = 0, m6 = r4 = 1. 
Tính bảo mật của mã hoá MHK 
Lược ñồ mã hoá MHK có thể bị bẻ khoá bởi thuật toán thời gian ña thức. 
Trong cách thiết lập khoá công khai, thuật toán này tìm một cặp số nguyên U’, 
M’ sao cho U’/M’ là tỉ lệ với U/M (W và M là một phần khoá riêng, và U=W-1 
mod M) và sao cho các số nguyên b’i = U’ai mod M, 1 ≤ i ≤ n từ dãy siêu 
tăng. Dãy này có thể ñược một ñối thủ sử dụng thay thế vào dãy (b1,b2, ..., bn) 
ñể giải mã văn bản. 
132 
TÀI LIỆU THAM KHẢO 
[1] ðặng Văn Chuyết, Nguyễn Tuấn Anh, “Cơ sở lý thuyết truyền tin” – Tập 1 
và 2, Nhà xuất bản Giáo dục, 1998. 
[2] Robert B.Ash, “Information theory “, Nhà xuất bản Dover, inc, 1990. 
[3] Masud Mansuripur, “Introduction to information theory “, Nhà xuất bản 
Prentice-Hall, Inc, 1987. 
[4] I. Cziszar and J. Korner. Information theory, “Coding Theorems for 
Discrete Memoryless Systems”. Academic Press, New York. 1997. 2nd 
edition. 
[5] D. Hammer, A. Romashenko, A. Shen, N. Vereshchagin, “Inequalities for 
Shannon entropies and Kolmogorov complexities”, Proceedings of CCC'97 
Conference, Ulm. Final version: Inequalities for Shannon entropy and Kol-
mogorov Complexity, Journal of Computer and System Sciences, v. 60, p. 
442{464 (2000). 
[6] A. Shen, “Algorithmic Information Theory and Kolmogorov Complexity”, 
Lecture notes of an introductory course. Uppsala University Technical Report 
2000-034. Available online at 
[7] Bar-Yam, Yaneer, “Dynamics of Complex Systems (Studies in 
Nonlinearity)”, Westview Press, Boulder, 1997. 
[8] Campbell, Jeremy, Grammatical Man, “Information, Entropy, Language, 
and Life, Simon and Schuster”, New York, 1982. 
[9] Cover, T. M., and Thomas J. A., “Elements of Information Theory”, John 
Wiley and Sons, New York, 1991. 
[10] Gatlin, L. L., “Information Theory and the Living System”, Columbia 
University Press, New York, 1972. 
133 
[11] Hamming, R. W., “Coding and information theory”, 2nd ed, Prentice-
Hall, Englewood Cliffs, 1986. 
[12] Landauer, R., “The physical nature of information”, Phys. Lett. A, 217 
188, 1996. 
134 
MỤC LỤC 
LỜI MỞ ðẦU 1 
CHƯƠNG 1. NHỮNG KHÁI NIỆM CƠ BẢN 3 
1.1 Giới thiệu về lý thuyết thông tin ..............................................................3 
1.2 Hệ thống truyền tin ..................................................................................3 
1.2.1 Các quan ñiểm ñể phân loại các hệ thống truyền tin ........................4 
1.2.2 Sơ ñồ truyền tin và một số khái niệm trong hệ thống truyền tin......4 
1.3 Nguồn tin nguyên thuỷ.............................................................................5 
1.3.1 Khái niệm chung..............................................................................5 
1.3.2 Bản chất của thông tin theo quan ñiểm truyền tin ............................7 
1.4 Hệ thống kênh tin...................................................................................10 
1.4.1 Khái niệm........................................................................................10 
1.4.2 Phân loại môi trường truyền tin ......................................................11 
1.4.3 Mô tả sự truyền tin qua kênh: .........................................................11 
 1.5 Hệ thống nhận tin ..................................................................................13 
 1.6 Một số vấn ñề cơ bản của hệ thống nhận tin..........................................13 
 1.6.1 Hiệu suất...........................................................................................13 
 1.6.2 ðộ chính xác.....................................................................................13 
 1.7 Rời rạc hóa một nguồn tin liên tục.........................................................13 
 1.7.1 Quá trình lấy mẫu.............................................................................14 
 1.7.2 Quá trình lượng tử hóa.....................................................................16 
1.8 ðiều chế và giải ñiều chế .......................................................................17 
1.8.2 Giải ñiều chế ...................................................................................18 
CHƯƠNG 2. TÍN HIỆU 19 
2.1 Một số khái niệm cơ bản........................................................................19 
2.1.1 Tín hiệu duy trì: ..............................................................................19 
2.1.2 Tín hiệu xung ..................................................................................19 
2.2 Phân tích phổ cho tín hiệu......................................................................20 
2.2.2 Tích phân Fourier và phổ liên tục ...................................................27 
2.2.3 Phổ các tín hiệu ñiều chế ................................................................28 
2.3 Nhiễu trắng.............................................................................................33 
CHƯƠNG 3. LƯỢNG TIN, ENTROPI NGUỒN RỜI RẠC 35 
3.1 ðộ ño thông tin ......................................................................................35 
3.1.2 ðộ ño thông tin. ..............................................................................35 
3.2 Lượng tin của nguồn rời rạc...................................................................37 
135 
3.2.1 Mối liên hệ của lượng tin và lý thuyết xác suất ..............................37 
3.2.3 Tính chất của lượng tin ...................................................................45 
3.2.4 Lượng tin trung bình .......................................................................46 
3.3 Entropi của nguồn rời rạc......................................................................47 
3.3.1 Khái niệm entropi ...........................................................................47 
3.3.2 Tính chất của entropi .....................................................................47 
3.3.3 Entropi ñồng thời và Entropi có ñiều kiện.....................................48 
3.3.4 Entropi nguồn Markov....................................................................49 
3.4 Mối quan hệ giữa lượng tin tương hỗ trung bình và Entropi .................50 
3.5 Tốc ñộ lập tin nguồn rời rạc và thông lượng kênh rời rạc .....................52 
3.5.1 Tốc ñộ lập tin ......................................................................................52 
3.5.2 Thông lượng kênh...........................................................................54 
CHƯƠNG 4. LÝ THUYẾT MÃ 56 
4.1 Khái niệm mã và ñiều kiện thiết lập mã ................................................56 
4.1.1 Mã hiệu và các thông số cơ bản......................................................56 
4.1.2 ðiều kiện thiết lập bộ mã................................................................58 
4.2 Các phương pháp biểu diễn mã..............................................................60 
4.2.1 Biểu diễn bằng bảng liệt kê (Bảng ñối chiếu mã)...........................60 
4.2.2 Biểu diễn bằng toạ ñộ mã................................................................60 
4.2.3 ðồ hình mã......................................................................................61 
4.2.4 Phương pháp hàm cấu trúc mã.......................................................62 
4.3 Mã có tính phân tách ñược, mã có tính prefix .......................................62 
4.3.1 ðiều kiện ñể mã phân tách ñược....................................................63 
4.3.2 Mã có tính prefix.............................................................................65 
4.3.3 Bất ñẳng thức Kraft.........................................................................66 
4.4 Mã thống kê tối ưu................................................................................67 
4.4.1 Giới hạn ñộ dài trung bình của từ mã ............................................67 
4.4.2 Tiêu chuẩn mã thống kê tối ưu .......................................................68 
4.4.3 Mã thống kê Fano –Shanon ............................................................69 
 4.5 Thuật toán mã hoá Lempel-Ziv..............................................................83 
4.6 Mã chống nhiễu.....................................................................................85 
4.6.1 Khái niệm về mã phát hiện sai và sửa sai .......................................86 
4.6.2 Cơ chế phát hiện sai ........................................................................87 
4.6.3 Xây dựng bộ mã sửa sai bằng bảng chọn........................................89 
4.6.4 Xây dựng bộ mã sửa sai bằng trọng số Hamming và khoảng cách 
Hamming..................................................................................................90 
4.5.5 Một số biện pháp xây dựng bộ mã phát hiện sai và sửa sai...........92 
4.7 Mã tuyến tính .........................................................................................94 
4.7.2 Nguyên lý giải mã...........................................................................96 
136 
4.7.3 Một số giới hạn của mã tuyến tính..................................................98 
4.8 Mã vòng ................................................................................................99 
4.8.1 Khái niệm:.......................................................................................99 
4.8.2 Nguyên lý lập mã..........................................................................100 
4.8.3 Nguyên lý giải mã.........................................................................102 
CHƯƠNG 5. GIỚI THIỆU VỀ HỆ MẬT MÃ 105 
5.1 Khái niệm hệ mật mã ...........................................................................105 
5.2 Phân loại các hệ thống mật mã ............................................................105 
5.3 Hệ mã cổ ñiển (Symmetric-key encryption)........................................106 
5.3.1 Khái niệm......................................................................................106 
5.3.2 Một số hệ mã cổ ñiển ....................................................................106 
5.3.3 Hệ mã DES ...................................................................................117 
5.4 Một số hệ mã hoá công khai ................................................................121 
5.4.1 Khái niệm chung...........................................................................121 
 5.4.2 Hệ mã RSA....................................................................................123 
 5.4.3 Hệ mã Rabin..................................................................................126 
 5.4.4 Hệ mã Elgamal..............................................................................129 
 5.4.5 Hệ mã MHK..................................................................................130 
TÀI LIỆU THAM KHẢO............................................................................. 131 
MỤC LỤC......................................................................................................133