Hàm số trong lý thuyết thông tin và các bài toán liên quan

BỘ GIÁO DỤC VÀ ĐÀO TẠO

ĐẠI HỌC ĐÀ NẴNG

NGÔ THỊ MINH TRANG

HÀM SỐ TRONG LÝ THUYẾT THÔNG TIN VÀ

CÁC BÀI TOÁN LIÊN QUAN

Chuyên ngành : Phương pháp Toán sơ cấp

Mã số: 60.46.40

TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC

Đà Nẵng - Năm 2013

Công trình được hoàn thành tại

ĐẠI HỌC ĐÀ NẴNG

Người hướng dẫn khoa học: GS.TSKH. NGUYỄN VĂN MẬU

Phản biện 1: TS. LÊ HẢI TRUNG

Phản biện 2: TS. HOÀNG QUANG TUYẾN

Luận văn được bảo vệ tại Hội đồng chấm luận văn

tốt nghiệp Thạc sĩ khoa học họp tại Đại học Đà Nẵng vào

ngày 26 tháng 05 năm 2013.

* Có thể tìm hiểu luận văn tại:

- Trung tâm Thông tin - Học liệu, Đại học Đà Nẵng

- Thư viện trường Đại học Sư phạm, Đại học Đà Nẵng

1

MỞ ĐẦU

1. Lý do chọn đề tài

Phương trình hàm là một trong những đề tài lâu đời nhất của toán học.

D’Alembert, Euler, Gauss, Cauchy, Abel, Weierstrass, Darboux và Hilbert là

những nhà toán học lớn quan tâm đến đề tài này và đưa ra hướng giải quyết

chúng. Mặc dù lý thuyết về phương trình hàm đã có từ lâu, nhưng các ứng dụng

của nó vào khoa học kỹ thuật và đời sống thì chỉ mới bắt đầu được các nhà toán

học quan tâm trong những thập kỷ gần đây. Thực tế cho thấy, phương trình hàm

có ở khắp nơi và được áp dụng trong rất nhiều lĩnh vực khác nhau. Có thể kể đến

như: khoa học ứng dụng, khoa học hành vi, xã hội học, sinh học, tổ hợp, khoa

học máy tính, kinh tế, kỹ thuật, thống kê,. . . Trong đó, một ứng dụng rất quan

trọng của phương trình hàm là trong lý thuyết thông tin. Do nhu cầu trao đổi

thông tin của con người ngày càng lớn nên lý thuyết thông tin ngày càng phát

triển. Lý thuyết thông tin cơ bản là một nhánh của toán học nghiên cứu về đo

đạc lượng thông tin. Ứng dụng truyền thông của nó là điều kiện tiên quyết cho

những ứng dụng khác. Với những lí do trên, tôi chọn đề tài: “Hàm số trong lý

thuyết thông tin và các bài toán liên quan” làm đề tài luận văn thạc sĩ.

Tôi hi vọng đây là một tài liệu tham khảo tốt cho những ai quan tâm đến đề tài

này.

2. Mục đích nghiên cứu

Hệ thống và tổng quan một số kiến thức về lý thuyết thông tin.

Bước đầu tìm hiểu, khảo sát một số phương trình hàm liên quan đến lý

thuyết thông tin và bước đầu tiếp cận một số áp dụng của nó.

3. Nhiệm vụ nghiên cứu

Tìm hiểu về lý thuyết thông tin, một số phương trình hàm liên quan đến lý

thuyết thông tin và mối quan hệ của chúng.

4. Đối tượng và phạm vi nghiên cứu

Đối tượng nghiên cứu: độ đo thông tin entropy, các phương trình hàm liên

quan đến lý thuyết thông tin.

Phạm vi nghiên cứu: tài liệu, giáo trình của GS. TSKH Nguyễn Văn Mậu,

các tài liệu từ các website, tạp chí toán học và các diễn đàn toán học,...

5. Phương pháp nghiên cứu

Nghiên cứu từ các tài liệu, giáo trình của GS. TSKH Nguyễn Văn Mậu, các

2

tài liệu tiếng Anh, các trang web,... Từ đó tác giả phân tích, đánh giá, tổng hợp

và trao đổi với thầy hướng dẫn kết quả đang nghiên cứu để hoàn chỉnh luận văn.

6. Ý nghĩa khoa học và thực tiễn của đề tài

Tạo được một đề tài có tính hệ thống, tổng quan tương đối đầy đủ về lý

thuyết thông tin và các phương trình hàm liên quan.

Hi vọng đề tài sẽ là tài liệu tham khảo bổ ích cho sinh viên, học viên cao

học và tất cả các bạn yêu toán.

Đề tài đóng góp thiết thực cho việc nghiên cứu và tìm hiểu toán học hiện

đại nói chung và hàm số trong lý thuyết thông tin nói riêng.

7. Cấu trúc luận văn

Luận văn gồm phần mở đầu, kết luận, tài liệu tham khảo và 3 chương.

Chương 1. Trình bày tổng quan về thông tin, các khái niệm cơ bản của lý

thuyết thông tin, đơn vị đo lường thông tin (entropy) và đưa ra một số kết quả

quan trọng liên quan đến tính chất của entropy.

Chương 2. Trình bày hai dạng phương trình hàm liên quan đến lý thuyết

thông tin và công thức nghiệm của nó.

Chương 3. Trình bày một số độ đo khác của thông tin và các vấn đề liên

quan.

3

CHƯƠNG 1

CÁC KIẾN THỨC BỔ TRỢ TRONG LÝ THUYẾT

THÔNG TIN

1.1. KHÁI NIỆM THÔNG TIN

Thông tin là những tính chất xác định của vật chất mà con người (hoặc hệ

thống kỹ thuật) nhận được từ thế giới vật chất bên ngoài hoặc từ những quá trình

xảy ra trong bản thân nó.

Khái niệm thông tin gắn liền với sự bất định của đối tượng cần xét. Có sự

bất định về một đối tượng nào đó thì những thông báo về đối tượng đó sẽ cho

ta thông tin. Khi không có sự bất định thì sẽ không có thông tin. Như vậy, khái

niệm thông tin chỉ là một cách diễn đạt khác đi của khái niệm sự bất định.

1.2. LÝ THUYẾT THÔNG TIN

Lý thuyết thông tin là một nhánh mới của lý thuyết xác suất với lượng lớn

các ứng dụng trong hệ thống thông tin liên lạc. Nó có nguồn gốc từ thế kỷ 20

nhưng chỉ trong năm thập kỷ qua nó đã phát triển mạnh mẽ và có ứng dụng

rộng rãi. Trước đây, thông tin chỉ được đo về chất lượng cụ thể: rất đáng tin cậy,

đáng tin cậy hoặc không đáng tin cậy. Nhưng lý thuyết xác suất đã giúp ích rất

nhiều trong việc cung cấp độ đo chất lượng thông tin nhận được từ hệ thống. Sự

kiện nổi bật đánh dấu sự ra đời của lý thuyết thông tin là bài báo của Claude

E. Shannon :"A mathematical theory of communication" năm 1948. Điều này đã

dẫn đến việc nghiên cứu và ứng dụng phương trình hàm trong lý thuyết thông

tin.

1.3. ĐỘ ĐO THÔNG TIN

Thông tin là một đại lượng vật lí, do đó ta cần phải xác định một độ đo cho

thông tin. Theo bản chất của thông tin thì thông tin càng có ý nghĩa khi nó càng

ít xuất hiện nên độ đo của nó phải tỉ lệ nghịch với xác suất xuất hiện của tin.

Nói cách khác, hàm độ đo phải là hàm tỉ lệ nghịch với xác suất xuất hiện của

tin. Kí hiệu x là tin với xác suất xuất hiện là p(x). Khi đó hàm độ đo ký hiệu là

I(x) = f



1

p(x)



là hàm tỉ lệ nghịch với xác suất p(x). Một tin x sẽ là không

4

có ý nghĩa nếu chúng ta đã biết về nó hay xác suất xuất hiện p(x) = 1. Trong

trường hợp này độ đo phải bằng không tức là I(x) = 0.

Xét 2 tin x, y là độc lập thống kê với xác suất xuất hiện tương ứng là

p(x), p(y) . Khi đó tin z = xy là tin khi xuất hiện đồng thời 2 tin x, y cùng một

thời điểm. Do đó theo tính chất tuyến tính, chúng ta phải có

I(xy) = I(x) + I(y)

Như vậy để xây dựng hàm độ đo thông tin, ta thấy hàm I(x) phải là hàm

không âm và thỏa mãn đồng thời cả 3 điều kiện đã nêu. Dễ thấy trong tất cả các

hàm toán học đã biết thì nếu chọn

I(x) = loga



1

p(x)



, a > 1

thì tất cả các điều kiện đều được thỏa mãn, bởi vì

1. I(x) = loga



1

p(x)



≥ 0, a > 1, với mọi 0 ≤ p(x) ≤ 1

2. I(x) = loga



1

p(x)



, a > 1 là hàm số nghịch biến với xác suất p(x)

3. I(x) = loga



1

p(x)



= 0 khi p(x) ≡ 1

4. I(xy) = loga



1

p(xy)



= loga



1

p(x)p(y)



= loga



1

p(x)



+ loga



1

p(y)



= I(x) + I(y)

Xuất phát từ những lý do trên, trong lý thuyết thông tin, hàm số

I(x) = loga



1

p(x)



= − loga

(p(x)), a > 1

được chọn làm độ đo thông tin. Trong công thức này, cơ số của hàm logarit có

thể chọn tùy ý thỏa mãn a > 1.

1.4. ENTROPY SHANNON

Khái niệm entropy của một thí nghiệm được giới thiệu bởi Shannon năm

1948 là một khái niệm cơ bản của lý thuyết thông tin.

Định nghĩa 1.1. Đặt

∆n = {(p1, p2, ..., pn) : 0 <

X

n

i=1

pi ≤ 1, pi ≥ 0, i = 1, 2, ..., n} (1.1)

5

là những tập với phân bố xác suất hữu hạn, có thể không đầy đủ. Entropy Shannon

là dãy các hàm Hn : ∆n → R (n = 1, 2, ...,) được định nghĩa bởi

Hn(p1, p2, ..., pn) =

X

n

k=1

L(pk)

X

n

k=1

pk

, (1.2)

trong đó

L(x) = 

−x log2 x với x ∈ (0, 1]

0 với x = 0 .

(1.3)

Nếu ta bỏ qua các biến cố với xác suất bằng 0 thì (1.2) có thể được viết

Hn(p1, p2, ..., pn) =

−

X

n

k=1

pk log(pk)

X

n

k=1

pk

(1.4)

với X

n

k=1

pk ≤ 1, pk > 0, k = 1, 2, ..., n; n = 1, 2, ...

Từ đây về sau, ta sẽ viết L(pk) = −pklogpk và dùng công thức (1.4) đối với

trường hợp có một (hoặc nhiều hơn, nhưng không phải tất cả) các pk = 0 và thừa

nhận

0 log 0 := 0. (1.5)

Với những phân bố xác suất hoàn chỉnh, (1.2) trở thành

Hn(p1, p2, ..., pn) = X

n

k=1

L(pk) (1.6)

với X

n

k=1

pk = 1, pk ≥ 0, k = 1, 2, ..., n; n = 2, 3, ...

Và theo quy ước (1.5), ta có thể viết một cách đơn giản

Hn(p1, p2, ..., pn) = −

X

n

k=1

pk log pk (1.7)

với mọi pk ≥ 0 (k = 1, 2, ..., n) và X

n

k=1

pk = 1 (n = 2, 3, ...).

6

Trong những trường hợp này, ta nhấn mạnh rằng (p1, p2, ..., pn) được chọn

từ tập hợp của tất cả những phân bố xác suất hữu hạn, hoàn chỉnh

Γn = {(p1, p2, ..., pn), pk ≥ 0,

X

n

k=1

pk = 1; k = 1, 2, ..., n; n = 2, 3, ...} (1.8)

thay vì ∆n và Hn : Γn → R là một độ đo của thông tin.

Đặt

Γ

0

n = {(p1, p2, ..., pn), pk > 0,

X

n

k=1

pk = 1; k = 1, 2, ..., n; n = 2, 3, ...} (1.9)

∆

0

n = {(p1, p2, ..., pn), pk > 0,

X

n

k=1

pk ≤ 1; k = 1, 2, ..., n; n = 2, 3, ...} (1.10)

Rõ ràng, Γ

0

n

là phần trong của tập Γn, trong khi đó ∆0

n

cũng chứa một vài

(nhưng không phải tất cả) điểm biên của ∆n. Tuy nhiên vai trò của chúng khá

tương tự nhau, nên ta cũng có những ký hiệu tương tự.

1.5. TÍNH CHẤT CỦA ENTROPY SHANNON

1.5.1. Tính chất đại số

Các entropy Shannon Hn được định nghĩa bởi (1.2), tương ứng (1.6) có các

tính chất sau:

Tính chất 1.1. Tính đối xứng

Hn(p1, p2, ..., pn) = Hn(pα(1), pα(2), ..., pα(n)) (1.11)

với mọi (p1, p2, ..., pn) ∈ Γn, với α là một hoán vị tùy ý trên {1, 2, ..., n}.

Tính chất 1.2. Tính mở rộng

Hn(p1, p2, ..., pn) = Hn+1(0, p1, p2, ..., pn) (1.12)

Điều này có nghĩa là khi thêm vào một kết quả với xác suất bằng 0 thì không

làm thay đổi lượng thông tin mong đợi.

Tính chất 1.3. Tính chuẩn tắc

H2



1

2

,

1

2



= 1. (1.13)

7

Tính chất 1.4. Tính quyết định

H2(1, 0) = H2(0, 1) = 0. (1.14)

Tính chất 1.5. Tính cộng tính mạnh

Hmn(p1q11, p1q12, ..., p1q1n, p2q21, p2q22, ..., p2q2n, ..., ..., pmqm1, pmqm2, ..., pmqmn)

= Hm(p1, p2, ..., pm) +X

m

j=1

pjHn(qj1, qj2, ..., qjn) (1.15)

với mọi (p1, p2, ..., pm) ∈ Γm, (qj1, qj2, ..., qjn) ∈ Γn, j = 1, 2, ..., m.

Tính chất 1.6. Tính cộng tính

Hmn(p1q1, p1q2, ..., p1qm, p2q1, p2q2, ..., p2qn, ..., ..., pmq1, pmq2, ..., pmqn)

= Hm(p1, p2, ..., pm) + Hn(q1, q2, ..., qn) (1.16)

với mọi (p1, p2, ..., pm) ∈ ∆m, với mọi (q1, q2, ..., qn) ∈ ∆n, j = 1, 2, ..., m.

Tính chất 1.7. Tính đệ qui

Hn(p1, p2, p3, ..., pn) = Hn−1(p1 + p2, p3, ..., pn) + (p1 + p2)H2



p1

p1 + p2

,

p2

p1 + p2



(1.17)

với mọi (p1, p2, ..., pn) ∈ Γn, p1 + p2 > 0.

1.5.2. Tính chất giải tích

Định nghĩa 1.2. Hàm thực ψ là một hàm lõm khả vi trên khoảng (a, b) nếu nó

có đạo hàm cấp hai trên (a, b) và

ψ

00(x) ≤ 0 với mọi x ∈ (a, b). (1.21)

Bổ đề 1.1. Nếu ψ là một hàm lõm khả vi trong khoảng (a, b) thì với mọi xk ∈

(a, b) (k = 1, 2, ..., n) và mọi (q1, q2, ..., qn) ∈ Γn (n = 2, 3, ...) ta có bất đẳng thức

sau

ψ

X

n

k=1

qkxk

!

≥

X

n

k=1

qkψ(xk). (1.22)

Đặc biệt

ψ

X

n

k=1

xk

n

!

≥

X

n

k=1

ψ(xk)

n

. (1.23)

8

Bổ đề 1.2. Hàm L được định nghĩa bởi (1.3) là một hàm lõm khả vi trong (0, 1)

và liên tục trên đoạn [0, 1] (đặc biệt liên tục tại 0).

Bổ đề 1.1 và 1.2 được áp dụng để chứng minh một số bất đẳng thức quan

trọng sau

Định lý 1.1. Với mọi (p1, p2, ..., pn) ∈ ∆n (n = 1, 2, ...) ta có

Hn(p1, p2, ..., pn) ≤ Hn

X

n

k=1

pk

n

,

X

n

k=1

pk

n

, ...,X

n

k=1

pk

n

!

= − log X

n

k=1

pk

n

!

. (1.24)

Đặc biệt, với mọi (p1, p2, ..., pn) ∈ Γn (n = 2, 3, ...) ta có

Hn(p1, p2, ..., pn) ≤ Hn



1

n

,

1

n

, ...,

1

n



= log n. (1.25)

Định lí này cho thấy entropy như là một độ đo sự bất định về kết quả của

một thí nghiệm và đạt giá trị lớn nhất khi các kết quả có xác suất như nhau. Do

đó (1.25) được gọi là tính cực đại.

Định lý 1.2. Với (p1, p2, ..., pm) ∈ Γm, (qj1, qj2, ..., qjn ∈ Γn) (j = 1, 2, ..., m),

X

m

j=1

pjHn(qj1, qj2, ..., qjn) ≤ Hn





X

m

j=1

pjqj1,

X

m

j=1

pjqj2, ...,X

m

j=1

pjqjn



 . (1.26)

Định lý 1.3. (Bất đẳng thức Shannon) Với mọi (p1, p2, ..., pn) ∈ Γn và với mọi

(q1, q2, ..., qn) ∈ ∆0

n

,

Hn(p1, p2, ..., pn) = −

X

n

k=1

pk log pk ≤ −X

n

k=1

pk log qk (1.31)

thỏa mãn với quy ước (1.5).

Định lí 1.3 thường được gọi là bổ đề Shannon và bất đẳng thức (1.31) được

gọi là bất đẳng thức Shannon.

1.5.2. Một số tính chất khác

Entropy Shannon như đã tìm hiểu ở trên có các tính chất đại số và giải tích.

Vậy tính chất nào được áp đặt cho dãy các hàm

In : ∆n → R (n = 1, 2, ...) hoặc Γn → R (n = 2, 3, ...)