›
›

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

Download
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 ging  
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 ging  
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 ging  
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  
Nhiễu  
Bộ thu  
Ngƣời dùng  
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. Độ tincậ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
§Ò c ¬ng bµi ging  
M«n: Lý thuyÕt th«ng tin  
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 đó.  
5
§Ò c ¬ng bµi ging  
M«n: Lý thuyÕt th«ng tin  
Đị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
1
I(x) log  
  log p(a )  
i
p(x)  
i1  
Đơ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êntụ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 fs =  
1
t  
Ví dụ: xa (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  
1
Ts   
2B  
FsTần số lấy mẫu.  
T Chu kỳ lấy mẫu.  
s
BBề 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.  
6
§Ò c ¬ng bµi ging  
M«n: Lý thuyÕt th«ng tin  
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.  
7
§Ò c ¬ng bµi ging  
M«n: Lý thuyÕt th«ng tin  
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 tinrờ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  
1
I(xi ) logn  
logn p(xi )  
đƣợc xác định theo công thức:  
p(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  
8
§Ò c ¬ng bµi ging  
M«n: Lý thuyÕt th«ng tin  
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ó:  
n
p(x / y ) 1  
i
j
j1  
m
p(y / x ) 1  
j
i
i1  
Để 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.  
I(xi, yj) I(xi ) I(xi | yj )  
I(xi, yj) log P(xi ) log P(xi | yj )  
P(xi | yj )  
I(xi, yj) log  
P(xi )  
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  
I(xi | yj )  log p(xi | yj )  
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  
9
§Ò c ¬ng bµi ging  
M«n: Lý thuyÕt th«ng tin  
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 -  
Uncertainty Measure (độ bất ngờ) hay là lƣợng tin không chắc chắn  
Entropy riêng của của lớp tin  i: H(xi) = -logn p(xi)  
Độ bất ngờ trung bình của nguồn tin XN đƣợc gọi là entropy riêng trung bình  
hay là entropy riêng của nguồn tin XN, đây chính là một thông số thống kê cơ bản  
của nguồn:  
N
H(X) =  
(bít/ký hiệu)  
(bít/ký hiệu)  
p(x )H(x )  
i
i
i1  
N
H
X
  p log  
pn  
n
n1  
Ví dụ:  
Cho X = {0, 1}, P(0) = p, còn P(1) = 1–p.  
Tính H(X)?  
H(X) = –{plog(p) + (1– p) log(1– p)}  
2.2.2 Tính chất của Entropy  
Entropy là đại lƣợng luôn dƣơng hoặc bằng 0: H(X) 0  
Entropy bằng 0 khi nguồn có một ký hiệu bất kỳ có xác suất xuất hiện bằng 1  
và tất cả các ký hiệu còn lại có xác suất xuất hiện bằng 0. Khi đó giá trị tin  
tức của nguồn không còn ý nghĩa  
H(X) = 0 (xi /p(xi) =1) (xj/p(xj) = 0 j i)  
Entropi cực đại khi xác suất xuất hiện các ký hiệu của nguồn bằng nhau, lúc  
đó độ bất định của một tin bất kỳ trong nguồn là lớn nhất:  
H(X) ≤ H(X)max ≤ logn(N). Dấu bằng xảy ra khi p1=p2=……=pn=1/N  
2.3 Kênh rời rạc.  
2.3.1 Định nghĩa.  
Nguồn tin và nhận tin liên hệ với nhau qua kênh thông tin, và kênh thông tin  
thực hiện một phép biến đổi từ không gian các ký hiệu ở đầu vào tới không gian các  
ký hiệu ở đầu ra của kênh.  
Kênh đƣợc gọi là rời rạc nếu không gian ký hiệu vào và không gian ký hiệu  
ra là rời rạc. Kênh đƣợc gọi là liên tục nếu các hai không gian ký hiệu vào ra là liên  
tục.  
10  
§Ò c ¬ng bµi ging  
M«n: Lý thuyÕt th«ng tin  
Nếu sự truyền tin trong kênh là liên tục theo thời gian thì kênh đƣợc gọi là  
liên tục thời gian và nếu sự truyền tin ch  thực hiện ở những thời điểm rời rạc theo  
thời gian thì kênh đƣợc gọi là rời rạc theo thời gian.  
2.3.2 Entropy đồng thời.  
Giả thiết X là tập các ký hiệu đầu vào [X]=[x1, x2, …. xn] với xác suất xuất  
hiện là [P(x)]=[p(x1), p(x2), ….., p(xN)] . [P(x)] Phản ánh tính chất của nguồn tin.  
[Y ]=[y1, y2, …, yM]: Tập các ký hiệu ở đầu ra với các xác suất xuất hiện tƣơng ứng  
[P(y)]=[p(y1), p(y2), ….., p(yM)]  
Do nhiễu trên kênh thông tin nên không gian Y có thể khác không gian X,  
cũng nhƣ các xác suất P(Y) cũng có thể khác các xác suất ở đầu vào P(X). Với  
không gian các ký hiệu ở đầu vào kênh và ở đầu ra kênh, ta có thể định nghĩa một  
trƣờng tích:  
x y x1 y2 ... x1 y  
m   
1
1
x2 y1 x2 y2 ... x2 ym  
X ,Y  
...  
... ... ...  
xn y1 xn y2 ... xn ym  
Trong đó tích xiyj là sự xuất hiện đồng thời hai sự kiện xi và yj. Chú ý rằng ở  
đây ta không giả thiết gì về sự độc lập hay phụ thuộc giữa xi và yj. Ma trận trên  
tƣơng ứng với ma trận xác suất sau:  
p
x1 y1  
x2 y1  
...  
p
x1 y2  
...  
p
x1 ym  
p
x2 y2  
... p  
...  
x2 ym  
...  
X ,Y  
P
...  
p
xn y1  
p
xn y2  
... p  
xn ym  
Từ ma trận xác suất ta có:  
m
p(xi) =  
p(x , y )  
i
j
j1  
n
p(yj) = p(x , y )  
i
j
i1  
Nhƣ vậy ta có thể định nghĩa ba trƣờng sự kiện:  
N
H
X
   
p
xi  
.log p  
xi  
- Trƣờng ở đầu vào kênh với entropy H(X):  
- Trƣờng ở đầu ra kênh với entropy H(Y):  
i1  
M
H
Y
   
p
yi  
.log p  
yi  
j1  
- Trƣờng ở giữa đầu vào và đầu ra kênh với entropy H(X,Y).  
11  
§Ò c ¬ng bµi ging  
M«n: Lý thuyÕt th«ng tin  
Entropi đồng thời là độ bất định trung bình của một cặp (x,y) bất kỳ trong  
tập tích XY  
N
M
H
X,Y  
Các công thức liên quan:  
xi  
   
p
xi yj  
.log p  
xi yj  
  
i1 j1  
N
M
;
   
p y   
p x y  
p
p
xi yj  
j
i
j
j1  
i1  
Ví dụ: Cho hai biến X, Y độc lập nhau và có phân phối:  
X
0
1
P
0.5  
0.5  
Y
0
1
2
P
0.25  
0.5  
0.25  
Tính H(X,Y)?  
H(X,Y)= 0.125*log0.125 + 0.25*log0.25 + 0.125*log0.125 + 0.125*log0.125 +  
0.25*log0.25 + 0.125*log0.125=2.5 (bit/ký hiệu)  
Tính chất của Entropy đồng thời:  
H(X,Y) H(X) + H(Y)  
Dấu bằng xảy ra khi X, Y độc lập tuyến tính.  
(SV tự chứng minh tính chất này)  
2.3.3 Entropi có điều kiện.  
Khi đầu ra của kênh đã biết, do nhiễu tác động vẫn còn sự bất định về đầu  
vào của kênh. Giá trị trung bình của độ bất định này đƣợc gọi là entropi của trƣờng  
X khi trƣờng Y đã biết  
H(X|Y): Là entropy có điều kiện đặc trƣng cho độ bất định về nguồn tin XN  
còn lại khi đã nhận đƣợc các lớp tin YM. Độ không xác định này do nhiễu trên  
kênh thông tin gây ra.  
H(Y|X): Entropy có điều kiện cho biết độ bất định của nguồn tin nơi nhận  
YM khi biết nguồn tin XN. Độ không xác định này cũng do nhiễu trên kênh thông  
tin gây ra, H(Y|X) còn đƣợc gọi là entropy gây nhiễu hay còn gọi là sai số trung  
bình bởi vì nó cho biết độ bất định (sai số) của đầu ra khi đầu vào đã biết.  
12  
§Ò c ¬ng bµi ging  
M«n: Lý thuyÕt th«ng tin  
N
H
H
H
H
Y X  
p
xi  
H
Y | X xi  
i1  
M
Y X xi  
p(y | x )log p(y | x )  
j
i
2
j
i
j1  
N
M
Y X  
p(x ) p(y | x )logp(y | x )  
  
i
j
i
j
i
i1 j1  
N
M
Y X  
p(x , y )log p(y | x )  
  
i
j
j
i
i1 j1  
Nếu trên kênh không có nhiễu thì p(xi|yj) = 1 và p(yj|xi) = 1 do đó:  
H(X|Y) = H(Y|X) = 0  
Nếu nhiễu trên kênh đủ lớn để đầu vào và đầu ra kênh độc lập với nhau tức là  
p(xi|yj) = p(xi) và p(yj|xi) = p(yj) thì:  
H(X|Y) = H(X)  
H(Y|X) = H(Y)  
Cuối cùng, để xác định các entropy có điều kiện, cần phải biết các xác suất  
có điều kiện dựa vào công thức xác suất hậu nghiệm (Bayes)  
p
x1 | y1  
x2 | y1  
...  
p
x1 | y2  
x2 | y2  
...  
...  
...  
...  
p
x1 | yM  
x2 | yM  
...  
p
p
p
P  
X |Y  
  
p
xN | y1  
p
xN | y2  
... p  
xN | yM  
p
y1 | x1  
p
y2 | x1  
y2 | x2  
...  
...  
p
ym | x1  
ym | x2  
...  
p
y1 | x2  
...  
p
... p  
...  
P  
Y | X  
  
p
y1 | xn  
p
y2 | xn  
... p  
ym | xn  
Ma trận P(Y|X) gọi là ma trận kênh truyền  
Gọi A = [P(Y|X)] là ma trận truyền tin hay mô hình truyền tin của kênh truyền  
rời rạc không nhớ. Và pij = p(Y=yj/X=xi) = p(yj/xi) là xác suất nhận đƣợc lớp tin yj  
khi đã truyền giá trị xi.  
Phân phối đầu nhận  
M
M
   
   
   
p Y y p y p x .p y | x p x .p  
j
j
i
j
i
i
ij  
i1  
i1  
p
yj  
[p(x )].A  
Hay  
,
i
Ví dụ: Cho ma trận truyền tin nhƣ sau.  
13  
§Ò c ¬ng bµi ging  
M«n: Lý thuyÕt th«ng tin  
0.5 0.2 0.3  
, p(x1)=0.5; p(x2)=p(x3)=0.25  
A 0.3 0.5 0.2  
0.2 0.3 0.5  
Khi đó ta tính đƣợc P(Y) nhƣ sau:  
[p(x ) p(x2) p(x3)].  
0.5 0.2 0.3  
0.3 0.5 0.2  
0.2 0.3 0.5  
= [ 0.375 0.3 0.325]  
p
yj  
 
1
Hay p(y1) = 0.375, p(y2) = 0.3, p(y3) = 0.325  
Tính chất của Entropy có điều kiện:  
1. H(X,Y) = H(X) + H(Y|X) = H(Y) + H(X|Y)  
2. Nếu không có nhiễu trên kênh, giữa đầu vào và đầu ra có quan hệ một – một,  
sai số trung bình bằng không khi đó  
H(X,Y) = H(X) = H(Y)  
3. H(X) ≥ H(X|Y); H(Y) ≥ H(Y|X). Dấu bằng xảy ra khi X, Y độc lập thống kê  
với nhau.  
Điều này có nghĩa là độ bất định trung bình của một tin bất kỳ bao giờ cũng  
lớn hơn độ bất định trung bình của tin đó khi đã biết một tin bất kỳ khác có liên  
hệ thống kê với nhau.  
2.3.4 Quan hệ giữa lƣợng tin tƣơng hỗ trung bình và entropy.  
Ở chƣơng 1 ta đã tính đƣợc I(xi,yj). Thông thƣờng ở bên phát phát đi một tập  
tin X = {xi}, Y = {yj}. Do đó ta không quan tâm tới một tin cụ thể xi mà ch  quan  
tâm tới lƣợng thông tin trung bình về mỗi tin của tập X do mỗi tin của tập Y mang  
lại.  
p(xi / yj )  
p(x , y )log  
I(X,Y) =  
  
i
j
p(xi )  
N
M
Lƣợng tin tƣơng hỗ trung bình bằng tổng độ bất định trung bình về tin  
phát và tin thu trừ độ bất định trung bình về sự xuất hiện đồng thời của chúng (SV  
tự chứng minh)  
I(X,Y) = H(X) – H(X|Y) = H(Y) – H(Y|X)  
I(X,Y) = H(X) + H(Y) – H(X,Y)  
Tính chất của I(X,Y)  
I(X,Y) ≥ 0  
Ta đã chứng minh H(X) ≥ H(X|Y)  
14  
§Ò c ¬ng bµi ging  
M«n: Lý thuyÕt th«ng tin  
Mà I(X,Y) = H(X) – H(X|Y) ĐPCM và đẳng thức xảy ra khi H(X) =  
H(X|Y) tức kênh bị đứt.  
I(X,Y) H(X) và đẳng thức xảy ra khi kênh không có nhiễu  
I(X,X) = H(X)  
I(X,Y)=I(Y,X)  
Giản đồ Venn mô tả quan hệ I và H  
2.3.5 Các dạng kênh truyền  
2.3.5.1 Kênh truyền không mất thông tin (Lossless Channel)  
Đầu ra xác định duy nhất một đầu vào  
Đặc trƣng: H(X|Y)=0; Lƣợng tin chƣa biết về X khi nhận Y là bằng 0, tức là  
khi nhận đƣợc Y thì hoàn toàn nhận đƣợc X  
Dung lƣợng: C = maxI(X,Y) = max(H(X)) = log2 N  
2.3.5.2 Kênh đơn định (Deterministic channel)  
Đầu vào xác định duy nhất đầu ra  
Đặc trƣng: H(Y|X)=0; Lƣợng tin chƣa biết về Y khi truyền X bằng 0 hay  
truyền X thì sẽ nhận đƣợc Y  
Dung lƣợng: C = max I(X,Y) =max H(Y) = log2 M  
2.3.5.3 Kênh truyền không nhiễu  
Kết hợp của kênh truyền xác định và kênh truyền không mất thông tin  
Truyền ký tự nào thì nhận đƣợc ký tự đấy  
H(Y|X) = H(X|Y) = 0, C = log2 M  
2.3.5.4 Kênh vô dụng (Useless Channel)  
Mô hình: Khi truyền giá trị nào thì mất giá trị đó hoặc xác suất nhiễu thông  
tin trên kênh truyền lớn hơn xác suất nhận đƣợc  
Đặc điểm:  
o Kênh truyền vô dụng nếu và ch  nếu X và Y độc lập với mọi sự phân bố  
của nguồn phát  
o H(Y|X) và H(X|Y) đạt cực đại và C = 0  
15  
§Ò c ¬ng bµi ging  
M«n: Lý thuyÕt th«ng tin  
2.3.5.5 Kênh truyền đối xứng  
Đặc điểm: Ma trận kênh truyền có tính chất đối xứng. Tức các tham số ở hai  
bên đƣờng chéo của ma trận bằng nhau  
1 2 1 3 1 6  
VD:  
A 1 3 1 6 1 2  
1 6 1 2 1 3  
Khi ma trận kênh truyền là đối xứng thì H(Y/X) là không đổi là bằng entropy  
của một hàng của ma trận kênh truyền  
2.3.6Lƣợc đồ giải mã tối ƣu  
Khi truyền xi nhận đƣợc yj. Đầu thu cần phải giải mã yj về xi tƣơng ứng  
Yêu cầu: Tìm giải pháp tạo mã sao cho sai số giải mã nhỏ hơn ε bất kỳ đồng thời  
phải duy trì R <= C  
Các dạng sai số:  
P
e | xi  
p
Y yj B | X xi  
- Xác suất truyền sai từ mã xi:  
i
M
- Xác suất truyền sai trung bình:  
P
e
P
X xi  
p
e | xi  
i1  
- Xác suất truyền sai lớn nhất:  
Giải thuật:  
P
m  
e
max P  
e| xi  
i1,M  
Bƣớc 0: Khởi tạo các B = φ (∀i)  
i
Bƣớc lặp: xét với mọi yj Y  
+ Tính:  
p(w ).p(y /w )  
1
j
1
p(w ).p(y /w )  
2
j
2
…
p(w ).p(y /w )  
M
j
M
+ So sánh các giá trị tính trên và chọn giá trị w* sao cho p(w* ).p(y /w* )=  
i
i
j
i
Max  
+ B = B + {y } và g(y ) = w* .  
i
i
j
j
i
16  
§Ò c ¬ng bµi ging  
M«n: Lý thuyÕt th«ng tin  
1 2 1 3 1 6  
Ví dụ: Cho ma trận truyền tin  
, P(x1)=1/2; P(x2)=P(x3)=1/4  
A 1 3 1 6 1 2  
1 6 1 2 1 3  
Yêu cầu: Xây dựng lƣợc đồ giải mã tối ƣu, tính các xác xuất truyền sai?  
Khởi tạo B1={}, B2={}, B3={}  
* Khi nhận đƣợc y1.  
p(x1).p(y1|x1)=1/4 max Liệt kê y1 vào B1  
tƣơng ứng với x1  
p(x2).p(y1|x2)=1/12  
p(x3).p(y1|x3)=1/24  
Quá trình tƣơng tự khi nhận đƣợc y2, y3.  
Kết quả ta có lƣợc đồ giải mã sau;  
* Tính các xác suất truyền sai:  
- Xác suất truyền sai từ mã x1:  
p
e | x1  
p
Y yj B | X x1  
p  
y3 | x1 1/6  
1
- Xác suất truyền sai từ mã x :  
p
p
e | x2  
1 2  
1  
2
- Xác suất truyền sai từ mã x :  
e | x2  
3
Xác suất truyền sai trung bình: p(e)=11/24  
Xác suất truyền sai lớn nhất: pm(e) = 1  
2.4 Entropy của nguồn liêntục.  
Ta biết rằng nguồn liên tục cũng đƣợc coi nhƣ một tập các thể hiện của một  
quá trình ngẫu nhiên. Nguồn tin X là nguồn tin liên tục với các thể hiện x(t) có quy  
luật phân bố xác suất (mật độ phân bố xác suất pdf) đƣợc biểu diễn theo hàm fx(x),  
entropy riêng của nguồn tin X đƣợc xác định bằng:  
  
p(x)log p(x)dx  
H(X) = -  
  
2.5 Vấn đề phối hợp nguồn kênh.  
Shannon đã phát biểu hai định lý cơ bản của lý thuyết tin tức liên quan tới sự  
phối hợp giữa nguồn tin và kênh thông tin. Shannon khẳng định sự tồn tại của các  
loại mã tối ƣu làm giảm độ dƣ của nguồn và sửa sai chống lại các tác động của  
nhiễu.  
17  
§Ò c ¬ng bµi ging  
M«n: Lý thuyÕt th«ng tin  
Định lý Shannon 1: Giả sử nguồn tin có entropi H (bít/ký hiệu), và kênh có  
thông lƣợng C (bít/s), có thể mã hóa tin tức ở đầu ra của nguồn làm cho sự  
truyền tin trong kênh không nhiễu theo một tốc độ trung bình C/H – ε (ký  
hiệu/s) với ε bé tùy ý, và không thể truyền nhanh hơn C/H.  
Định lý Shannon 2: Kênh có thông lƣợng C (bít/s), tốc độ lập tin của nguồn  
là R (bít/s)  
o Nếu R<C: Có thể tìm đƣợc một phƣơng pháp mã hóa để cho sự truyền  
tin tỏng kênh có nhiễu với sai bé tùy ý.  
o Nếu R>C: Có thể mã hóa nguồn để cho lƣợng sai bé hơn R – C + ε,  
với ε bé tùy ý, không tồn tại mã hiệu đảm bảo độ sai cảu sự truyền tin  
nhỏ hơn R – C.  
18  
§Ò c ¬ng bµi ging  
M«n: Lý thuyÕt th«ng tin  
CHƢƠNG 3: M  HIỆU  
3.1 Khái niệm và định nghĩa.  
Trong các hệ thống truyền tin rời rạc hoặc truyền các tín hiệu liên tục nhƣng  
đã đƣợc rời rạc hóa, bản tin thƣờng phải thông qua một số phép biến đổi: biến đổi  
tƣơng tự sang số, mã hóa… ở phía phát, còn ở đầu thu phải thông qua quá trình biến  
đổi ngƣợc lại là giải mã.  
Sự mã hóa thông tin cho phép chúng ta ký hiệu hóa thông tin hay sử dụng  
các ký hiệu quy ƣớc để biểu diễn bản tin. Chính nhờ mã hóa, chúng ta có thể hiển  
thị đƣợc thông tin có bản chất là các khái niệm.  
Vai trò của mã hóa:  
Tăng tính hữu hiệu: Tăng tốc độ truyền tin Mã thống kê tối ƣu  
Tăng độ tin cậy của hệ thống: Tăng khả năng chống nhiễu Mã phát  
hiện và sửa sai.  
3.1.1 Các khái niệm:  
Mã hiệu (Code): Tập hữu hạn các dấu hiệu riêng (symbol) và các phép ánh  
xạ các tin hoặc bản tin của nguồn tin thành các ký hiệu tƣơng ứng. Tập các  
ký hiệu này phải thỏa mãn một số yêu cầu của hệ thống truyền tin đặt ra (Tốc  
độ truyền hay độ chính xác) Mã hiệu là tập hữu hạn các ký tự (Symbol)  
hay bảng chữ riêng (dấu mã – ký hiệu mã). Số các ký hiệu gọi là cơ số mã m  
(Ví dụ m = 2 mã nhị phân).  
Mã hóa (Encoding): Quá trình dùng các ký hiệu mã để biểu diễn các tin của  
nguồn, biến nguồn tin thành mã hiệu hay biến đổi nguồn tin theo đặc tính  
thống kê theo yêu cầu. Ngƣợc với quá trình mã hóa là quá trình giải mã  
(decoding).  
Từ mã (Code Word): Chuỗi các ký hiệu mã biểu diễn cho tin của nguồn.  
Tập tất cả các từ mã tƣơng ứng với các tin của nguồn đƣợc gọi là bộ mã.  
Nguồn tin tƣơng ứng với bộ mã. Ký hiệu của từ mã là u,v hoặc w  
3.1.2 Các thông số cơ bản của một bộ mã:  
Chiều dài từ mã: Số ký hiệu có trong từ mã. Ký hiệu: l (hoặc n)  
Chiều dài trung bình của bộ mã:  
N
l P(x ).l  
i
i
i1  
19  
Tải về để xem bản đầy đủ
pdf 58 trang Mãnh Khiết 12/01/2024 18020 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "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", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfbai_giang_ly_thuyet_thong_tin_truong_dai_hoc_su_pham_ky_thua.pdf