Bài giảng Lý thuyết thông tin

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 
 2 
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ã. 
§Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 
 3 
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. 
§Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 
 4 
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. 
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 
Nguồn tin 
Bộ phát 
Kênh truyền 
Bộ thu 
Ngƣời dùng 
Nhiễu 
§Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 
 5 
lý thuyết thông tin. 
1.3.3. An toàn. 
- Bí mật: 
+ Không thể khai thác thông tin trái phép. 
+ Ch có ngƣời nhận hợp lệ mới hiểu đƣợc thông tin. 
- Xác thực: Gắn trách nhiệm của bên gửi – bên nhận với bản tin (chữ ký số). 
- Toàn vẹn: 
+ Thông tin không bị bóp méo (cắt xén, xuyên tạc, sửa đổi). 
+ Thông tin đƣợc nhận phải nguyên vẹn cả về nội dung và hình 
thức. 
- Khả dụng: Mọi tài nguyên và dịch vụ của hệ thống phải đƣợc cung cấp đầy 
đủ cho ngƣời dùng hợp pháp. 
1.4. Độ đo thông tin. 
 Các mục về sau chúng ta sẽ khảo sát lƣợng đo thông tin một cách chi tiết 
hơn, ở đây chúng ta ch nêu một khái niệm ban đầu về lƣợng tin để có thể so sánh 
định lƣợng các thông tin với nhau. Từ đó giúp cho chúng ta dễ nhận thức hơn 
những ch tiêu chất lƣợng đề ra khi xây dựng các phƣơng pháp xử lý thông tin. 
 Một tin tức đối với ngƣời nhận đều mang hai đặc tính: Độ bất ngờ của tin và 
ý nghĩa của tin. Để so sánh giữa các tin với nhau ngƣời ta có thể dùng một trong hai 
đặc tính trên hoặc dùng cả hai đặc tính trên làm thƣớc đo. Tuy nhiên những nội 
dung mang tính ý nghĩa của tin không ảnh hƣởng đến các vấn đề cơ bản của hệ 
thống thông tin (hệ thống thông tin đòi hỏi hai vấn đề cơ bản đó là tốc độ truyền tin 
và độ chính xác). Trong khi đó độ bất ngờ của tin lại liên quan đến những vấn đề 
đó. 
 Một tin có xác suất xuất hiện càng nhỏ thì độ bất ngờ càng lớn (càng bất ngờ) 
thì khi xuất hiện tác động càng mạnh lên giác quan của con ngƣời, và chúng ta cho 
rằng lƣợng tin của chúng càng lớn. 
 Xét một tin x có xác suất xuất hiện là p(x) thì chúng ta có thể xem tin này 
nhƣ là một tin trong một tập có 1/p(x) tin với các tin có xác suất xuất hiện nhƣ 
nhau. 
 Nếu p(x) càng nhỏ thì 1/p(x) càng lớn và vì vậy “lƣợng tin” khi nhận đƣợc 
tin này cũng sẽ càng lớn. 
 Vậy “lƣợng tin” của một tin t lệ thuận với số khả năng của một tin và t lệ 
nghịch với xác suất xuất hiện của tin đó. 
§Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 
 6 
 Định nghĩa lƣợng tin: Lƣợng đo thông tin của một tin đƣợc đo bằng logarit 
độ bất ngờ của tin hay nghịch đảo xác suất xuất hiện của tin đó. 

n
i
iap
xp
xI
1
)(log
)(
1
log)( 
 Đơn vị lƣợng tin: 
 Cơ số 2: đơn vị là Bit. 
 Cơ số e: đơn vị là Nat 
 Cơ số 10: đơn vị là Hartley. 
1.5. Số hóa nguồn tin liên tục. 
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). 
1.5.1 Lấy mẫu (Sampling). 
Lấy mẫu là bƣớc đầu tiên trong quá trình biến đổi tín hiệu tƣơng tự sang số. Mục 
đích của bƣớc lấy mẫu này là từ tín hiệu tƣơng tự tạo nên một dãy xung rời rạc theo 
thời gian (thực chất là việc nhân tín hiệu thoại đầu vào với một chuỗi xung nhịp f s = 
t 
1
Ví dụ: x a (t) là một hàm theo thời gian, t là biến thì lẫy mẫu là rời rạc hóa biến t. 
 Định lý lấy mẫu: 
 Nếu ta muốn khôi phục tín hiệu tƣơng tự thì tín hiệu lấy mẫu một cách trung 
thành thì tần số lấy mẫu lớn hơn hoặc bằng hai lần bề rộng phổ của tín hiệu (bề rộng 
của băng tần cơ bản). 
Fs 2B 
B
Ts
2
1
 Fs Tần số lấy mẫu. 
Ts Chu kỳ lấy mẫu. 
B Bề rộng phổ tín hiệu. 
Nếu Fs = 2B thì tần số lấy mẫu này 
gọi là tần số Nyquist. 
§Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 
 7 
1.5.2 Lƣợng tử hóa (Quantizing) 
Lƣợng tử hóa tức là rời rạc hóa hàm 
a
(t) hay nói cách khác chia dải động tín 
hiệu thành M mức (mức biên độ chuẩn đã đƣợc định nghĩa sẵn trong một dải biên 
độ tín hiệu cho trƣớc. ) sau đó thực hiện làm tròn các xung lấy mẫu về các mức gầ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). 
1.5.3 Mã hóa (Coding) 
 Quá trình mã hóa biến đổi các mức lƣợng tử hóa thành các từ mã, thông 
thƣờng là từ mã nhị phân. Trong tín hiệu nhị phân, “0” và “1” đƣợc thể hiện bằng 
hai mức điện áp khác nhau. 
§Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 
 8 
CHƢƠNG 2: THÔNG TIN 
2.1 Lƣợng tin nguồn rời rạc 
2.1.1 Khái niệm nguồn tin rời rạc 
- Nguồn rời rạc: nguồn tạo ra một chuỗi các biến ngẫu nhiên, rời rạc 
- Ký hiệu: Phần tử nhỏ nhất chứa thông tin. VD các ký tự trong bộ chữ cái 
- Bộ ký hiệu: Tập tất cả các ký hiệu [X]={x1,x2,xn} 
- Từ: Tập hợp hữu hạn các ký hiệu trong bộ ký hiệu 
- Bộ từ: Tập hợp tất cả các từ mà bộ ký tự có thể tạo ra 
- Nguồn rời rạc không nhớ: Xác suất xuất hiện của một ký hiệu không phụ 
thuộc vào các ký hiệu trƣớc đó. 
- Nguồn rời rạc có nhớ: Xác suất xuất hiện một ký tự phụ thuộc vào một hoặc 
nhiều các ký tự xuất hiện trƣớc đó 
2.1.2 Lƣợng tin nguồn rời rạc 
Lƣợng tin riêng: Mỗi lớp tin xi trong nguồn tin X đều có một lƣợng tin riêng 
đƣợc xác định theo công thức: )(log
)(
1
log)( in
i
ni xp
xp
xI 
 Đơn vị lƣợng tin: 
- Cơ số n = 2: Bit (Binary – nhị phân) 
- Cơ số n = e: Nat (đọc là nit – nature) 
- Cơ số n = 10: Harley. 
Trong môn học này tập trung trình bày mã nhị phân nên mặc định n = 2. 
Trong hệ thống thông tin, việc truyền tin từ nguồn tin X đến nơi nhận Y đƣợc 
coi nhƣ một phép biến đổi (ánh xạ) từ một không gian X tới một không gian Y. Do 
tác động của nhiễu nên ánh xạ này không phải là ánh xạ 1-1. Nói cách khác, việc 
nhận đƣợc một lớp tin yj cụ thể ở nơi nhận ch cho chúng ta biết khả năng tin tức 
của nguồn tin X truyền đi lớp tin xi, điều này theo quan điểm thống kê có thể xác 
định đƣợc xác suất có điều kiện về sự xuất hiện các lớp tin xi ở nguồn với điều kiện 
nơi nhận nhận đƣợc lớp tin yj. Xác suất này đƣợc gọi là xác suất có điều kiện, ký 
hiệu là p(xi/yj). 
p(xi/yj): xác suất có điều kiện về sự xuất hiện các lớp tin xi ở nguồn với điều 
kiện nơi nhận nhận đƣợc lớp tin yj 
p(yj/xi):xác suất có điều kiện về sự xuất hiện các lớp tin yj ở nơi nhận tin với 
điều kiện nguồn tin phát đi lớp tin xi 
§Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 
 9 
 Ngoài ra ta còn xác định đƣợc xác suất xuất hiện đồng thời các lớp tin xi ở 
nguồn và yi ở nơi nhận là p(xi,yi) 
Theo quy luật phân bố xác suất có điều kiện ta có: 


m
i
ij
n
j
ji
xyp
yxp
1
1
1)/(
1)/(
Để giải quyết bài toán truyền tin đặt ra khi nhận đƣợc một lớp tin yj của tập 
của tập YM, hãy xác định lớp tin tƣơng ứng của tập XN ở đầu vào. Ở đây ta không 
thể xác định đƣợc chính xác duy nhất một lớp tin xi ở đầu vào mà ch đƣa ra các khả 
năng có thể xảy ra ở nguồn. 
Lƣợng tin tƣơng hỗ: Là lƣợng tin về một tin bất kỳ xi trong nguồn tin XN 
chứa trong một tin bất kỳ yj của nơi nhận tin YM đƣợc gọi là lƣợng tin tƣơng hỗ giữa 
xi và yj bằng lƣợng tin ban đầu của xi trừ đi lƣợng tin còn lại của xi sau khi đã nhận 
đƣợc yj. 
)|()(),( jii yxIxIyjxiI 
)|(log)(log),( jii yxPxPyjxiI 
)(
)|(
log),(
i
ji
xP
yxP
yjxiI 
Lƣợng tin có điều kiện: Lƣợng tin còn lại của xi sau khi đã nhận đƣợc yj 
đƣợc gọi là lƣợng tin có điều kiện của xi với điều kiện nơi nhận nhận đƣợc yj 
)|(log)|( jiji yxpyxI 
Lƣợng tin còn lại này chính là lƣợng tin do nhiễu phá hủy không đến đƣợc nơi 
nhận 
2.2 Entropi nguồn rời rạc 
2.2.1 Định nghĩa 
 Lƣợng tin trung bình đƣợc hiểu là lƣợng tin trung bình trong một tin bất kỳ 
của nguồn tin đã cho. Khi nhận đƣợc một tin, ta sẽ nhận đƣợc một lƣợng tin trung 
bình, đồng thời độ bất ngờ của tin cũng đƣợc giải thoát, do vậy độ bất ngờ của tin 
và lƣợng tin về ý nghĩa vật lý trái ngƣợc nhau nhƣng về số đo lại bằng nhau. Độ bất 
ngờ của lớp tin xi trong nguồn tin XN đƣợc tính bằng entropy riêng của lớp tin xi 
trong nguồn tin XN 
§Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 
 10 
Entropy là một đại lƣợng toán học dùng để đo lƣợng tin không chắc (hay 
lƣợng ngẫu nhiên) của một sự kiện hay của phân phối ngẫu nhiên cho trƣớc - 
Un ... a ta thu đƣợc từ mã 11 10 00 10 11, ta tiến hành so sánh các giá 
trị đầu ra thu đƣợc với các giá trị đầu ra trên lƣới. Tính các khoảng cách Hamming 
giữa hai từ mã. Sau đó tìm đƣờng mã sao cho khoảng cách mã là nhỏ nhất 
t1 t2 t3 t4 t5 t62 1 0 1 2
00
10
01
11
Trạng 
thái n-k 
thanh 
g i cuối
0 1 2 1 0
0 1 0 1
2 1 0
2 1 2 1
1 2 1
1 0 1
0 1 2
11 10 00 10 11Gía trị t u được
Gía trị đầu vào 1 0 1 0 0
§Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 
 51 
Giả sử đầu ra ta thu đƣợc từ mã 11 11 10 01 00, ta tiến hành so sánh các giá 
trị đầu ra thu đƣợc với các giá trị đầu ra trên lƣới. Tính các khoảng cách Hamming 
giữa hai từ mã. Sau đó tìm đƣờng mã sao cho khoảng cách mã là nhỏ nhất 
11 11 10 01 00Gía trị t u được
Gía trị đầu vào 1 1 1 0 1
t1 t2 t3 t4 t5 t62 2 1 1 0
00
10
01
11
Trạng 
thái n-k 
thanh 
g i cuối
0 0 1 1 0
1 0 2 1
1 1 2
1 2 0 1
2
0 1
0 2 1
1 1 0
§Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 
 52 
CHƢƠNG 6: M MẬT 
6.1 Giới thiệu chung về các hệ thống mật mã 
Mong muốn đƣợc trao đổi thông tin một cách bí mật là một trong những đòi 
hỏi của con ngƣời xuất hiên từ rất sớm trong lịch sử. Vì thế lịch sử của việc trao đổi 
thông tin mật rất phong phú và bao gồm những phát minh độc đáo. Ngành học 
nghiên cứu cách thức che dấu thông tin đối với những đối tƣợng không mong muốn 
đƣợc gọi là mật mã học. 
 Phân loại các hệ thống mật mã. 
 Xét cách thức tiến hành mã hóa ta có thể chia quá trình mật mã thành hai 
loại: 
 Mã hóa khối: Dữ liệu trƣớc khi mã hóa sẽ bị chia nhỏ thành từng khối có 
độ dài cố định, sau đó mỗi khối đƣợc mã hóa một cách độc lập. Do đó, 
§Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 
 53 
nếu sử dụng cùng khóa thì việc mã hóa các các khối văn bản gốc giống 
nhau sẽ cho ta các khối văn bản mã hóa giống nhau. 
 Mã hóa chuỗi dữ liệu: Tƣơng tự nhƣ mã chập, độ dài không cố định. 
Mỗi bít của văn bản gốc m đƣợc mã hóa bằng thành phần thứ i của 
chuỗi ký hiệu đƣợc hình thành từ từ khóa. 
 Xét về mối quan hệ giữa mã hóa và giải mã ta có thể chia quá trình mật mã 
thành hai loại: 
 Hệ thống mật mã đối xứng (bí mật): Là hệ thống sử dụng một khóa duy 
nhất cho cả mã hóa và giải mã. 
 Hệ thống mật mã không đối xứng (công khai): Có hai khóa, một khóa 
dùng cho lập mã và có thể công bố rộng rãi, khóa còn lại dùng để giải 
mã đƣợc giữ bí mật 
6.2 Một số hệ thống mật mã. 
 Bảng chữ cái. 
Ví dụ: 
§Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 
 54 
 Ma trận vuông Polybius: 
Bảng chữ cái đƣợc xếp thành một ma trận 5x5 (chữ i và chữ J đƣợc gộp lại nhƣ một 
chữ) 
 1 2 3 4 5 
1 A B C D E 
2 F G H IJ K 
3 L M N O P 
4 Q R S T U 
5 V W X Y Z 
 Mã lũy tiến 
 Đây là một ví dụ của mã hóa bản chữ cái bội 
Hàng 0: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 
Hàng 1: B C D E F G H I J K L M N O P Q R S T U V W X Y Z A 
Hàng 2: C D E F G H I J K L M N O P Q R S T U V W X Y Z A B 
........................................................................................................... 
Hàng 25:Z A B C D E F G H I J K L M N O P Q R S T U V W X Y 
 Phƣơng pháp sử dụng bản chữ cái này là chữ đầu tiên mã hóa ở hàng 1, chữ 
thứ 2 mã hóa ở hàng 2 và cứ nhƣ thế tiếp tục. 
6.3. Những cách thức tấn công vào một hệ thống mật mã. 
Hệ thống tấn công có thể có một trong bốn khả năng tấn công một hệ thống mật mã 
tùy thuộc vào những thông tin có thể thu thập đƣợc. 
 Ch biết bản tin mật mã: Trong trƣờng hợp này hệ thống tấn công ch có 
trong tay các bản tin mật mã. Quá trình phân tích phải dựa trên tính chất 
thống kê, phân bố và các tính chất khác của bản tin mật mã – những điều 
đƣợc truyền công khai trên kênh truyền. 
§Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 
 55 
 Biết đầy đủ hoặc một phần bản tin gốc và bản tin mật mã tƣơng ứng: Trong 
trƣờng hợp này hệ thống phân tích may mắn hoặc tình cờ có đƣợc bản tin 
gốc cùng với bản tin mật mã tƣơng ứng. Chẳng hạn, những thông báo ngoại 
giao hoặc pháp lý th nh thoảng đƣợc công bố và đồng thời hệ thống phân tích 
lại thu đƣợc cả bản tin mật mã trên kênh truyền. Gọi C là bản tin mật mã, P 
là bản tin gốc, E là thuật toán mã hóa. D là thuật toán giải mã thì C = E(P). 
Hệ thống phân tích có đƣợc C, P và cố gắng tìm ra E hoặc D. 
Những cấu trúc cố định của các mẫu văn bản kinh tế, ngoại giao cũng nhƣ 
những cấu trúc của các ngôn ngữ lập trình thƣờng cung cấp những thông tin 
về văn bản gốc để hệ thống tấn công thực hiện dạng tấn công loại này. 
 Biết bản tin mật mã của bất cứ bản tin gốc nào: 
Trong một số trƣờng hợp hệ thống phân tích có thể thâm nhập vào hệ thống 
gửi để có thể mã hóa và gửi đi một bản tin theo ý muốn. Tấn công loại này 
còn đƣợc gọi là tấn công lựa chọn bản tin gốc. Chẳng hạn hệ thống phân tích 
có thể chèn hoặc xóa các bản ghi trong một cơ sở dữ liệu rồi quan sát những 
thay đổi xảy ra đối với bản tin mật mã. 
Cách tấn công này rất hay đƣợc các hệ thống phân tích tận dụng. Mặc dù 
việc tấn công biết trƣớc văn bản gốc không phải lúc nào cũng thực hiện đƣợc 
nhƣng tần suất của nó đủ để cho một hệ thống không thể coi là an toàn trừ 
khi hệ thống đó chống lại đƣợc kiểu tấn công này. 
 Biết bản tin gốc và thuật toán: Hệ thống phân tích cũng có thể có đƣợc thuật 
toán mật mã cùng với các bản tin mật mã thu đƣợc trên kênh truyền. Hệ 
thống phân tích có thể tấn công bằng cách đơn giản là thử mã hóa một số 
lƣợng rất lớn các bản tin gốc có thể cho đến khi nhận đƣợc bản tin mật mã 
thu đƣợc trên kênh. Mục đích của quá trình thử là xác định khóa đang sử 
dụng để có thể sử dụng cho giải mã các bản tin trong tƣơng lai. 
§Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 
 56 
MỤC LỤC 
CHƢƠNG 1: KHÁI NIỆM CHUNG .....................................................................................3 
1.1 Khái niệm chung về hệ thống thông tin và truyền tin. .................................................3 
1.1.1. Thông tin. .............................................................................................................3 
1.1.2. Tín hiệu.................................................................................................................3 
1.2 Mô hình của hệ thống truyền tin. .................................................................................3 
1.3. Các yêu cầu cơ bản của hệ thống truyền tin. ..............................................................4 
1.3.1. Tính hữu hiệu. ......................................................................................................4 
1.3.2. Độ tin cậy. ............................................................................................................4 
1.3.3. An toàn. ................................................................................................................5 
1.4. Độ đo thông tin. ..........................................................................................................5 
1.5. Số hóa nguồn tin liên tục. ...........................................................................................6 
1.5.1 Lấy mẫu (Sampling). .............................................................................................6 
1.5.2 Lƣợng tử hóa (Quantizing) ....................................................................................7 
1.5.3 Mã hóa (Coding)....................................................................................................7 
CHƢƠNG 2: THÔNG TIN ....................................................................................................8 
2.1 Lƣợng tin nguồn rời rạc ................................................................................................8 
2.1.1 Khái niệm nguồn tin rời rạc ...................................................................................8 
2.1.2 Lƣợng tin nguồn rời rạc .........................................................................................8 
2.2 Entropi nguồn rời rạc ....................................................................................................9 
2.2.1 Định nghĩa .............................................................................................................9 
2.2.2 Tính chất của Entropy .........................................................................................10 
2.3 Kênh rời rạc. ..............................................................................................................10 
2.3.1 Định nghĩa. ..........................................................................................................10 
2.3.2 Entropy đồng thời. ...............................................................................................11 
2.3.3 Entropi có điều kiện. ............................................................................................12 
2.3.4 Quan hệ giữa lƣợng tin tƣơng hỗ trung bình và entropy. ....................................14 
2.3.5 Các dạng kênh truyền ........................................................................................156 
2.3.6Lƣợc đồ giải mã tối ƣu .........................................................................................16 
2.4 Entropy của nguồn liên tục. ........................................................................................17 
2.5 Vấn đề phối hợp nguồn kênh. .....................................................................................17 
CHƢƠNG 3: M HIỆU.......................................................................................................19 
3.1 Khái niệm và định nghĩa. ............................................................................................19 
3.1.1 Các khái niệm: .....................................................................................................19 
3.1.2 Các thông số cơ bản của một bộ mã: ...................................................................19 
3.2 Các phƣơng pháp biểu diễn mã ..................................................................................20 
3.2.1 Các bảng mã ........................................................................................................20 
3.2.2 Đồ hình mã ..........................................................................................................21 
3.2.3 Hàm cấu trúc mã..................................................................................................22 
3.3 Điều kiện phân tách của mã hiệu. ...............................................................................22 
3.3.1 Điều kiện chung đối với một bảng mã phân tách đƣợc. ......................................22 
3.3.2 Bảng thử mã.........................................................................................................23 
§Ò c-¬ng bµi gi¶ng M«n: Lý thuyÕt th«ng tin 
 57 
3.3.3 Bất đẳng thức Kraft............................................................................................. 24 
3.3.4 Thủ tục tạo mã phân tách đƣợc dựa vào độ dài đã biết của các từ mã ............... 24 
3.4 Mã hệ thống. .............................................................................................................. 25 
3.4.1 Mã hệ thống tổng quát. ....................................................................................... 25 
3.4.2 Mã hệ thống có tính prefix. ................................................................................. 26 
CHƢƠNG 4: M H A NGU N ....................................................................................... 27 
4.1 Mô hình toán học của nguồn thông tin. ..................................................................... 27 
4.1.1 Định lý giới hạn dƣới về độ dài trung bình của các từ mã. ................................ 27 
4.1.2 Định lý giới hạn trên về độ dài trung bình của các từ mã. .................................. 28 
4.2 Mã hóa nguồn rời rạc. ................................................................................................ 28 
4.2.1 Phƣơng pháp mã hóa Shannon ........................................................................... 28 
4.2.2 Phƣơng pháp mã hóa Fano ................................................................................. 29 
4.2.3 Phƣơng pháp mã hóa Huffman ........................................................................... 30 
CHƢƠNG 5: M H A K NH........................................................................................... 33 
5.1 Mã khối tuyến tính (Block code) ............................................................................... 33 
5.1.1 Các khái niệm: ................................................................................................... 33 
5.1.2 Ma trận sinh. ....................................................................................................... 34 
5.1.3 Mã khối tuyến tính hệ thống. .............................................................................. 36 
5.1.4 Giải mã................................................................................................................ 37 
5.2. Mã Hamming (Hamming Code) ............................................................................... 40 
5.2.1. Khái niệm. .......................................................................................................... 40 
5.2.2 Phƣơng pháp tạo mã. .......................................................................................... 40 
5.2.3 Giải mã................................................................................................................ 41 
5.3 Mã vòng (Xyclic code) .............................................................................................. 42 
5.3.1 Khái niệm............................................................................................................ 42 
5.3.2 Đa thức sinh và ma trận sinh. ............................................................................. 42 
5.3.3. Mã vòng hệ thống .............................................................................................. 44 
5.3.4. Phƣơng pháp giải mã. ........................................................................................ 45 
5.4 Mã chập (Convolution code) ..................................................................................... 46 
5.4.1 Khái niệm............................................................................................................ 46 
5.4.2 Biểu diễn bộ lập mã chập .................................................................................... 46 
5.4.3 Giải mã chập ....................................................................................................... 50 
CHƢƠNG 6: M MẬT....................................................................................................... 52 
6.1 Giới thiệu chung về các hệ thống mật mã ................................................................. 52 
6.2 Một số hệ thống mật mã. ........................................................................................... 53 
6.3. Những cách thức tấn công vào một hệ thống mật mã. ............................................. 54