Lý thuyết thông tin

Lý thuyết thông tin là một nhánh của toán học ứng dụng và kĩ thuật điện nghiên cứu về đo đạc lượng thông tin. Lý thuyết thông tin được xây dựng bởi Claude E. Shannon để xác định giới hạn cơ bản trong các hoạt động xử lý tín hiệu chẳng hạn như nén dữ liệu hay lưu trữ và truyền dẫn dữ liệu. Ngay từ những ngày đầu, nó đã mở rộng phạm vi ứng dụng ra nhiều lĩnh vực khác, bao gồm suy luận thống kê, xử lý ngôn ngữ tự nhiên, mật mã học, các mạng lưới bên cạnh mạng lưới viễn thông - chẳng hạn như trong thần kinh^[1], sự tiến hóa^[2] và chức năng^[3] của các mã phân tử, lựa chọn mô hình^[4] trong sinh thái học, vật lý nhiệt, máy tính lượng tử^[5], phát hiện sao chép^[6] và các hình thức phân tích dữ liệu khác.^[7]

Một độ đo cơ bản của thông tin là entropy, thường được diễn đạt dưới dạng số lượng bit cần thiết trung bình để lưu trữ hoặc dẫn truyền. Entropy lượng hóa sự không chắc chắn trong việc dự đoán giá trị của một biến ngẫu nhiên. Ví dụ như, xác định kết quả của một lần tung đồng xu công bằng (hai kết quả có khả năng như nhau) cho ít thông tin hơn (entropy nhỏ hơn) là xác định kết quả của một lần tung xúc sắc (sáu kết quả có khả năng như nhau).

Các ứng dụng cơ bản của lý thuyết thông tin bao gồm nén không mất dữ liệu (chẳng hạn như ZIP), nén mất dữ liệu (chẳng hạn MP3, JPG), mã hóa kênh (chẳng hạn như trong DSL). Lý thuyết thông tin nằm ở phần giao nhau giữa toán học, thống kê, khoa học máy tính, vật lý, thần kinh, và kĩ thuật điện. Các ngành hẹp quan trọng của lý thuyết thông tin bao gồm mã hóa nguồn, mã hóa kênh, lý thuyết thông tin thuật toán, bảo mật theo lý thuyết thông tin.

Tổng quan

Khái niệm cơ bản của lý thuyết thông tin có thể được nắm bắt thông qua việc xem xét hình thức liên lạc phổ biến nhất của con người: ngôn ngữ. Hai yếu tố quan trọng của một ngôn ngữ ngắn gọn là: các từ thông dụng (như "một", "cái", "tôi") nên ngắn gọn hơn các từ kém thông dụng hơn (như "thông tin", "thợ thủ công") để các câu không bị quá dài. Sự cân bằng độ dài các từ như vậy cũng tương tự như trong nén dữ liệu và là một thành phần cơ bản của mã hóa nguồn. Ngoài ra, nếu một phần của câu không nghe được hoặc bị nghe nhầm do tiếng ồn, chẳng hạn như do có ô tô chạy qua, thì người nghe vẫn có thể đoán ra ý nghĩa của câu. Sự vững chắc đó là một thành phần thiết yếu cho hệ thống liên lạc điện tử cũng như cho ngôn ngữ. Tính chất đó trong truyền thông được đảm bảo bởi mã hóa kênh. Mã hóa nguồn và mã hóa kênh là những mối quan tâm chính của lý thuyết thông tin.

Lý thuyết thông tin thường được xem là xuất phát từ bài báo quan trọng của Shannon (1948) mang tên "A Mathematical Theory of Communication". Mô hình trung tâm của lý thuyết thông tin cổ điển là vấn đề kĩ thuật của việc truyền dẫn thông tin trên một kênh nhiễu. Kết quả cơ bản trong lý thuyết này là định lý mã hóa nguồn của Shannon, khẳng định rằng tính trung bình, số bit cần dùng để mô tả kết quả của một sự kiện ngẫu nhiên chính là entropy của nó, và định lý mã hóa trên kênh nhiễu cũng của Shannon, khẳng định rằng việc liên lạc không lỗi trên một kênh nhiễu là có thể miễn là tốc độ truyền dữ liệu là nhỏ hơn một giới hạn nhất định, gọi là dung lượng kênh. Có thể đạt đến gần dung lượng kênh trong thực tế bằng cách sử dụng các hệ thống mã hóa và giải mã thích hợp.

Bối cảnh lịch sử

Sự kiện nổi bật đánh dấu sự khởi đầu của lý thuyết thông tin là bài báo của Claude E. Shannon "A Mathematical Theory of Communication" ở Bell System Technical Journal vào tháng 7 và tháng 10 năm 1948.

Trước bài báo này, một số ý tưởng về lý thuyết thông tin đã được phát triển tại Bell Labs, trong trường hợp đặc biệt khi tất cả các sự kiện đều có cùng xác suất. Bài báo năm 1924 của Harry Nyquist, "Certain Factors Affecting Telegraph Speed", chứa một phần lý thuyết định lượng "tri thức" (intelligence) và "tốc độ đường truyền" (line speed), đưa ra mối liên hệ W = Klogm, trong đó W là tốc độ dẫn truyền tri thức, m là số cấp điện áp có thể sử dụng tại mỗi bước và K là một hằng số. Bài báo năm 1928 của Ralph Hartley, "Transmission of Information", sử dụng thuật ngữ "thông tin" (information) như một đại lượng đo được, thể hiện khả năng phân biệt giữa các dãy ký hiệu của người nhận, do đó lượng hóa thông tin bởi H = logSⁿ = nlogS, trong đó S là số ký hiệu có thể sử dụng, và n là số ký hiệu được truyền đi. Đơn vị tự nhiên của thông tin do đó là một chữ số thập phân, sau này được đổi tên là hartley để ghi danh đóng góp của ông, là một đơn vị đo thông tin. Năm 1940, Alan Turing đã sử dụng những ý tưởng tương tự cho phân tích thống kê để phá bộ mã Enigma của Đức trong chiến tranh thế giới thứ hai.

Phần lớn lý thuyết toán học đằng sau lý thuyết thông tin với các sự kiện có xác suất khác nhau được xây dựng trong ngành nhiệt động học bởi Ludwig Boltzmann và J. Willard Gibbs. Mối liên hệ giữa entropy thông tin và entropy nhiệt động học, bao gồm đóng góp quan trọng của Rolf Landauer trong thập kỉ 1960, được mô tả trong trang Entropy trong nhiệt động học và lý thuyết thông tin.

Đo lường thông tin

Lý thuyết thông tin được xây dựng dựa trên lý thuyết xác suất và thống kê. Thông số quan trọng nhất của thông tin là entropy, lượng thông tin trong một biến ngẫu nhiên, và thông tin tương hỗ, lượng thông tin chung giữa hai biến ngẫu nhiên.

Entropy

Nếu $\mathbb {X}$ là tập hợp tất cả các thông điệp $\{x_{1},...,x_{n}\}$ mà $X$ có thể nhận giá trị, và $p(x)$ là xác suất $X$ nhận giá trị $x\in \mathbb {X}$ , thì entropy của $X$ được định nghĩa như sau:^[8]

H(X)=\mathbb {E} _{X}[I(x)]=-\sum _{x\in \mathbb {X} }p(x)\log p(x).

Trường hợp đặc biệt của entropy thông tin cho biến ngẫu nhiên với đúng hai khả năng gọi là hàm entropy nhị phân, thường được tính theo lôgarit cơ số 2:

H_{\mbox{b}}(p)=-p\log _{2}p-(1-p)\log _{2}(1-p).\,

Entropy hợp

Entropy hợp của hai biến ngẫu nhiên rời rạc X và Y là entropy của cặp (X, Y). Có nghĩa là nếu X và Y là độc lập thì entropy hợp là tổng của entropy của mỗi biến.

H(X,Y)=\mathbb {E} _{X,Y}[-\log p(x,y)]=-\sum _{x,y}p(x,y)\log p(x,y)\,

Entropy có điều kiện

Entropy có điều kiện của X cho trước Y là giá trị kì vọng của entropy của X theo phân bố của Y.

H(X|Y)=\mathbb {E} _{Y}[H(X|y)]=-\sum _{y\in Y}p(y)\sum _{x\in X}p(x|y)\log p(x|y)=-\sum _{x,y}p(x,y)\log {\frac {p(x,y)}{p(y)}}.

Một tính chất cơ bản của entropy có điều kiện là

H(X|Y)=H(X,Y)-H(Y).\,

Thông tin tương hỗ

Thông tin tương hỗ đo lượng thông tin thu được về một biến ngẫu nhiên thông qua giá trị của một biến ngẫu nhiên khác.

I(X;Y)=\mathbb {E} _{X,Y}[SI(x,y)]=\sum _{x,y}p(x,y)\log {\frac {p(x,y)}{p(x)\,p(y)}}

Một tính chất cơ bản của thông tin tương hỗ là

I(X;Y)=H(X)-H(X|Y).\,

Thông tin tương hỗ có tính chất đối xứng:

I(X;Y)=I(Y;X)=H(X)+H(Y)-H(X,Y).\,

Thông tin tương hỗ có thể được biểu diễn dưới dạng khoảng cách Kullback-Leibler của phân bố hậu nghiệm của X nếu biết giá trị của Y và phân bố tiền nghiệm của X:

I(X;Y)=\mathbb {E} _{p(y)}[D_{\mathrm {KL} }(p(X|Y=y)\|p(X))].

Nói cách khác, độ đo này xác định, về mặt trung bình, sự thay đổi của phân bố của X nếu biết giá trị của Y. Giá trị này còn có thể tính bằng khoảng cách giữa tích của các phân bố biên với phân bố hợp:

I(X;Y)=D_{\mathrm {KL} }(p(X,Y)\|p(X)p(Y)).

Khoảng cách Kullback-Leibler

Khoảng cách Kullback-Leibler (hoặc entropy tương đối) là một cách so sánh hai phân bố: phân bố "thật" p(x) và một phân bố bất kì q(x). Nó được định nghĩa như sau:

D_{\mathrm {KL} }(p(X)\|q(X))=\sum _{x\in X}-p(x)\log {q(x)}\,-\,\left(-p(x)\log {p(x)}\right)=\sum _{x\in X}p(x)\log {\frac {p(x)}{q(x)}}.

Mặc dù đôi khi nó được sử dụng như một "khoảng cách metric", khoảng cách Kullback-Leibler không phải là một metric do nó không đối xứng và không thỏa mãn bất đẳng thức tam giác.

Các thông số khác

Một vài thông số khác trong lý thuyết thông tin bao gồm entropy Rényi, entropy vi phân, thông tin tương hỗ có điều kiện.

Lý thuyết mã hóa

Một bức ảnh các vết xước trên bề mặt của một đĩa CD-R. Nhạc và dữ liệu lưu trên CD được mã hóa bằng mã tự sửa lỗi và do đó vẫn có thể đọc được ngay cả khi có những vết xước nhỏ, bằng cách sử dụng kĩ thuật phát hiện và sửa lỗi.

Lý thuyết mã hóa là một trong những ứng dụng quan trọng và trực tiếp nhất của lý thuyết thông tin. Nó có thể được chia làm lý thuyết mã hóa nguồn và lý thuyết mã hóa kênh. Sử dụng kết quả thống kê cho dữ liệu, lý thuyết thông tin định lượng số bit cần thiết để lưu trữ dữ liệu (chính là entropy thông tin của dữ liệu).

Nén dữ liệu (mã hóa nguồn): Có hai hình thức nén dữ liệu:

Nén không mất dữ liệu: dữ liệu phải được khôi phục chính xác
Nén mất dữ liệu: phân bổ đủ số bit cần thiết để khôi phục dữ liệu, trong một độ chính xác định trước, đo bởi một hàm biến dạng.

Mã sửa lỗi (mã hóa kênh): Khi nén dữ liệu đã loại bỏ hoàn toàn phần dữ liệu thừa, một mã sửa lỗi thêm vào một số thông tin dự phòng để có thể truyền dữ liệu một cách hiệu quả và trung thực qua một kênh nhiễu.

Cách phân chia lý thuyết mã hóa thành nén và truyền được giải thích bởi các định lý truyền thông tin, hoặc các định lý phân chia nguồn-kênh, trong đó lý giải việc sử dụng bit làm đơn vị chung cho thông tin trong nhiều bối cảnh khác nhau. Tuy nhiên các định lý này chỉ đúng trong trường hợp một người gửi muốn truyền thông tin cho đúng một người nhận. Trong trường hợp có nhiều người gửi (kênh đa truy cập), hoặc nhiều người nhận (kênh phát sóng), hoặc có người trung gian giúp đỡ (kênh tiếp sức), hoặc tổng quát hơn, trong mạng máy tính, việc nén rồi truyền có thể không còn tối ưu. Lý thuyết thông tin trên mạng nghiên cứu về những mô hình truyền thông nhiều đối tượng.

Ghi chú

^ F. Rieke, D. Warland, R Ruyter van Steveninck, W Bialek, Spikes: Exploring the Neural Code. The MIT press (1997).
^ cf. Huelsenbeck, J. P., F. Ronquist, R. Nielsen and J. P. Bollback (2001) Bayesian inference of phylogeny and its impact on evolutionary biology, Science 294:2310-2314
^ Rando Allikmets, Wyeth W. Wasserman, Amy Hutchinson, Philip Smallwood, Jeremy Nathans, Peter K. Rogan, Thomas D. Schneider Lưu trữ 2012-02-04 tại Wayback Machine, Michael Dean (1998) Organization of the ABCR gene: analysis of promoter and splice junction sequences, Gene 215:1, 111-122
^ Burnham, K. P. and Anderson D. R. (2002) Model Selection and Multimodel Inference: A Practical Information-Theoretic Approach, Second Edition (Springer Science, New York) ISBN 978-0-387-95364-9.
^ Jaynes, E. T. (1957) Information Theory and Statistical Mechanics, Phys. Rev. 106:620
^ Charles H. Bennett, Ming Li, and Bin Ma (2003) Chain Letters and Evolutionary Histories Lưu trữ 2007-10-07 tại Wayback Machine
^ David R. Anderson (ngày 1 tháng 11 năm 2003). “Some background on why people in the empirical sciences may want to better understand the information-theoretic methods” (PDF). Bản gốc (pdf) lưu trữ ngày 23 tháng 7 năm 2011. Truy cập ngày 23 tháng 6 năm 2010.
^ Fazlollah M. Reza (7 tháng 11 năm 1994). An Introduction to Information Theory. Dover Publications, Inc., New York. ISBN 0-486-68210-2.

Các công trình cổ điển

Shannon, Claude E. (1948). “[[A Mathematical Theory of Communication]]” (PDF). Bell System Technical Journal. 27: 379–423 & 623–656. PDF Bản gốc Kiểm tra giá trị |url= (trợ giúp) lưu trữ ngày 15 tháng 12 năm 2017. Truy cập ngày 28 tháng 8 năm 2011. Tựa đề URL chứa liên kết wiki (trợ giúp)
R.V.L. Hartley (1928). “Transmission of Information” (PDF). Bell System Technical Journal. Bản gốc (PDF) lưu trữ ngày 4 tháng 10 năm 2011. Truy cập ngày 28 tháng 8 năm 2011.
Andrey Kolmogorov (1968). “Three approaches to the quantitative definition of information”. International Journal of Computer Mathematics.

[1] F. Rieke, D. Warland, R Ruyter van Steveninck, W Bialek, Spikes: Exploring the Neural Code. The MIT press (1997).

[2] . Huelsenbeck, J. P., F. Ronquist, R. Nielsen and J. P. Bollback (2001) Bayesian inference of phylogeny and its impact on evolutionary biology, Science 294:2310-2314

[3] Rando Allikmets, Wyeth W. Wasserman, Amy Hutchinson, Philip Smallwood, Jeremy Nathans, Peter K. Rogan, Thomas D. Schneider Lưu trữ 2012-02-04 tại Wayback Machine, Michael Dean (1998) Organization of the ABCR gene: analysis of promoter and splice junction sequences, Gene 215:1, 111-122

[4] Burnham, K. P. and Anderson D. R. (2002) Model Selection and Multimodel Inference: A Practical Information-Theoretic Approach, Second Edition (Springer Science, New York) ISBN 978-0-387-95364-9.

[5] Jaynes, E. T. (1957) Information Theory and Statistical Mechanics, Phys. Rev. 106:620

[6] Charles H. Bennett, Ming Li, and Bin Ma (2003) Chain Letters and Evolutionary Histories Lưu trữ 2007-10-07 tại Wayback Machine

[7] David R. Anderson (ngày 1 tháng 11 năm 2003). “Some background on why people in the empirical sciences may want to better understand the information-theoretic methods” (PDF). Bản gốc (pdf) lưu trữ ngày 23 tháng 7 năm 2011. Truy cập ngày 23 tháng 6 năm 2010.

[Reza-8] Fazlollah M. Reza (7 tháng 11 năm 1994). An Introduction to Information Theory. Dover Publications, Inc., New York. ISBN 0-486-68210-2.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

x t s Toán học
Lịch sử Dòng thời gian Tương lai Đại cương Danh sách Ký hiệu
Nền tảng	Logic toán Lý thuyết hình thái Lý thuyết phạm trù Lý thuyết tập hợp Lý thuyết thông tin Triết học toán học
Đại số	Đa tuyến tính Đồng điều Giao hoán Lý thuyết nhóm Phổ dụng Sơ cấp Trừu tượng Tuyến tính
Giải tích	Giải tích điều hòa Giải tích hàm Giải tích phức Giải tích thực Lý thuyết độ đo Phương trình vi phân Vi tích phân
Rời rạc	Lý thuyết đồ thị Lý thuyết thứ tự Tổ hợp
Hình học	Đại số Euclid Giải tích Hữu hạn Rời rạc Số học Vi phân
Lý thuyết số	Số học Đại số Giải tích Hình học Diophantos
Tô pô	Đại số Hình học Đại cương Vi phân Lý thuyết đồng luân
Ứng dụng	Hóa học Kinh tế Lý thuyết điều khiển tự động Lý thuyết trò chơi Sinh học Tài chính Tâm lý Thống kê toán học Xác suất Thống kê Vật lý
Tính toán	Khoa học máy tính Lý thuyết tính toán Lý thuyết độ phức tạp tính toán Đại số máy tính Giải tích số Tối ưu hóa
Liên quan	Toán học giải trí Toán học và nghệ thuật Giáo dục toán học
Thể loại · Chủ đề · Commons · Dự án

x t s Những lĩnh vực chính của khoa học máy tính
Các nền tảng toán học	Logic toán · Lý thuyết tập hợp · Lý thuyết số · Lý thuyết đồ thị · Lý thuyết kiểu · Lý thuyết thể loại · Giải tích số · Lý thuyết thông tin · Đại số · Nhận dạng mẫu · Nhận dạng tiếng nói · Toán học tổ hợp · Đại số Boole · Toán rời rạc
Lý thuyết phép tính	Độ phức tạp Kolmogorov · Lý thuyết Automat · Lý thuyết tính được · Lý thuyết độ phức tạp tính toán · Lý thuyết điện toán lượng tử
Các cấu trúc dữ liệu và các giải thuật	Phân tích giải thuật · Thiết kế giải thuật · Hình học tính toán · Tối ưu hóa tổ hợp
Các ngôn ngữ lập trình và Các trình biên dịch	Các bộ phân tích cú pháp · Các trình thông dịch · Lập trình cấu trúc · Lập trình thủ tục · Lập trình hướng đối tượng · Lập trình hướng khía cạnh · Lập trình hàm · Lập trình logic · Lập trình máy tính · Lập trình mệnh lệnh · Lập trình song song · Lập trình tương tranh · Các mô hình lập trình · Prolog · Tối ưu hóa trình biên dịch
Tính song hành, Song song, và các hệ thống phân tán	Đa xử lý · Điện toán lưới · Kiểm soát song hành · Hiệu năng hệ thống · Tính toán phân tán
Công nghệ phần mềm	Phân tích yêu cầu · Thiết kế phần mềm · Các phương pháp hình thức · Kiểm thử phần mềm · Quy trình phát triển phần mềm · Các phép đo phần mềm · Đặc tả chương trình · LISP · Mẫu thiết kế · Tối ưu hóa phần mềm
Kiến trúc hệ thống	Kiến trúc máy tính · Tổ chức máy tính · Các hệ điều hành · Các cấu trúc điều khiển · Cấu trúc bộ nhớ lưu trữ · Vi mạch · Thiết kế ASIC · Vi lập trình · Vào/ra dữ liệu · VLSI design · Xử lý tín hiệu số
Viễn thông và Mạng máy tính	Audio máy tính · Chọn tuyến · Cấu trúc liên kết mạng · Mật mã học
Các cơ sở dữ liệu và Các hệ thống thông tin	Hệ quản trị cơ sở dữ liệu · Cơ sở dữ liệu quan hệ · SQL · Các giao dịch · Các chỉ số cơ sở dữ liệu · Khai phá dữ liệu · Biểu diễn và giao diện thông tin · Các hệ thống thông tin · Khôi phục dữ liệu · Lưu trữ thông tin · Lý thuyết thông tin · Mã hóa dữ liệu · Nén dữ liệu · Thu thập thông tin
Trí tuệ nhân tạo	Lập luận tự động · Ngôn ngữ học tính toán · Thị giác máy tính · Tính toán tiến hóa · Các hệ chuyên gia · Học máy · Xử lý ngôn ngữ tự nhiên · Robot học · Biểu diễn tri thức và suy luận
Đồ họa máy tính	Trực quan hóa · Hoạt họa máy tính · Xử lý ảnh
Giao diện người-máy tính	Khả năng truy cập máy tính · Giao diện người dùng · Điện toán mang được · Điện toán khắp mọi nơi · Thực tế ảo
Khoa học tính toán	Cuộc sống nhân tạo · Tin sinh học · Khoa học nhận thức · Hóa học tính toán · Khoa học thần kinh tính toán · Vật Lý học tính toán · Các giải thuật số · Toán học kí hiệu
Chú ý: khoa học máy tính còn có thể được chia thành nhiều chủ đề hay nhiều lĩnh vực khác dựa theo Hệ thống xếp loại điện toán ACM.