Теория информации

Теория информации — раздел прикладной математики, радиотехники (теория обработки сигналов) и информатики, относящийся к измерению количества информации, её свойств и устанавливающий предельные соотношения для систем передачи данных. Как и любая математическая теория, теория оперирует математическими моделями, а не реальными физическими объектами (источниками и каналами связи). Использует, главным образом, математический аппарат теории вероятностей и математической статистики.

Основные разделы теории информации — кодирование источника (сжимающее кодирование) и канальное (помехоустойчивое) кодирование. Теория информации тесно связана с информационной энтропией, коммуникационными системами, криптографией и другими смежными дисциплинами.

Область находится на пересечении математики, статистики, информатики, физики, нейробиологии, информационной инженерии и электротехники. Теория также нашла применение в других областях, включая статистический вывод, обработку естественного языка, криптографию, нейробиологию^[1], человеческое зрение^[2], эволюцию^[3] и функцию^[4] молекулярных кодов (биоинформатика), выбор статистической модели^[5], теплофизику^[6], квантовые вычисления, лингвистику, выявление плагиата^[7], распознавание образов и выявление аномалий^[8]. Важные подразделы теории информации включают в себя сжатие данных, канальное кодирование, алгоритмическую теорию сложности, алгоритмическую теорию информации, информационно-теоретическую безопасность, реляционный анализ Грея и измерение информации.

Введение

Появление теории информации связано с опубликованием Клодом Шенноном работы «Математическая теория связи» в 1948 году. С точки зрения Шеннона, теория информации — раздел математической теории связи. Теория информации устанавливает основные границы возможностей систем передачи информации, задает исходные принципы их разработки и практического воплощения. Круг задач теории информации представляется с помощью структурной схемы, типичной системы передачи или хранения информации.

Схема системы связи

В схеме источником является любой объект вселенной, порождающий сообщения, которые должны быть перемещены в пространстве и времени. Независимо от изначальной физической природы, все подлежащие передаче сообщения обычно преобразуются в форму электрических сигналов, такие сигналы и рассматриваются как выход источника. Кодер источника представляет информацию в наиболее компактной форме. Кодер канала обрабатывает информацию для защиты сообщений от помех при передаче по каналу связи или возможных искажений при хранении информации. Модулятор преобразовывает сообщения, формируемые кодером канала, в сигналы, согласованные с физической природой канала связи или средой накопителя информации. Среда распространения информации (канал связи) вносит в процесс передачи информации случайный шум, который искажает сообщение и тем самым затрудняет его прочтение. Блоки, расположенные на приёмной стороне, выполняют обратные операции и предоставляют получателю информацию в удобном для восприятия виде.

История

Рождение теории информации зачастую связывают с размещением в июле-октябре 1948 года Клодом Шенноном работы в журнале американской телефонной компании «Bell System» под названием «Математическая теория связи». Но стоит упомянуть, что вклад в формулировку и построение теории информации также был внесён и многими другими выдающимися учёными. Сам Шеннон в начале своей статьи написал «Некоторые основные положения этой теории имеются в важных работах Найквиста и Хартли. В настоящее время теория расширена тем, что включено некоторое число новых факторов, в частности, влияние шума в канале».

В основном Шеннон развивал направление работ Хартли, используя понятие «информации», но сам термин не разъясняет, лишь оговаривает, что сообщения могут иметь какое-то «значение», то есть относиться к системе, имеющей свою физическую или умозрительную сущность (кибернетическая система). Теория Шеннона изначально рассматривалась как точно сформулированная математическая задача и дала возможность определить пропускную способность коммуникационного канала с шумом.

Кодирование данных

Кодирование являет собой процесс перехода сообщения на входе канала связи до кода сообщения на выходе, при этом информационная ценность сообщения должна оставаться неизменной. В теории информации можно выделить следующие разделы:

1. Кодирование дискретных источников (модель кодирования данных «без потерь»).

2. Кодирование данных, обеспечивающее их безошибочную передачу по каналу с шумом.

Код является однозначно декодируемым, если любая последовательность символов из алфавита кода (а, в основном, это 0 и 1) разбивается на отдельные слова. Если ни одно кодовое слово не является началом другого, код называется префиксным и он является однозначно декодируемым. Следовательно, префиксность — достаточное, но не необходимое условие однозначной декодируемости. Требование префиксности ограничивает множество длин кодовых слов и не даёт возможности выбирать кодовые слова слишком короткими. Необходимым и достаточным условием существования префиксного кода объёма $M$ с длинами кодовых слов $l_{1},...,l_{M}$ является выполнение неравенства Крафта:

\sum _{i=1}^{M}{2}^{-l_{i}}\leqslant {1}

Также требуется рассмотреть код Шеннона — Фано — алгоритм префиксного неоднородного кодирования. Этот метод кодирования использует избыточность сообщения, заключённую в неоднородном распределении частот символов его алфавита, то есть заменяет коды более частых символов короткими двоичными последовательностями, а коды более редких символов — более длинными двоичными последовательностями. Рассмотрим источник, выбирающий буквы из множества $X=M$ с вероятностями $p_{M}$ . Считаем, что буквы упорядочены по убыванию вероятностей ( ${p_{1}}\geqslant {p_{2}}\geqslant {p_{M}}$ ). Кодовым словом кода Шеннона для сообщения с номером $M$ является двоичная последовательность, представляющая собой первые $l=-\log {p_{m}}$ разрядов после запятой в двоичной записи числа $q_{M}$ :

{q_{M}}=\sum _{i=1}^{M-1}p_{i}

3. Кодирование данных для систем со многими пользователями описывает оптимальное взаимодействие абонентов, использующих общий ресурс, например, канал связи.

См. также

Примечания

↑ F. Rieke; D. Warland; R Ruyter van Steveninck; W Bialek. Spikes: Exploring the Neural Code (неопр.). — The MIT press, 1997. — ISBN 978-0262681087.
↑ Delgado-Bonal, Alfonso; Martín-Torres, Javier. Human vision is determined based on information theory (англ.) // Scientific Reports^[англ.]. — 2016. — 3 ноября (т. 6, № 1). — ISSN 2045-2322. — doi:10.1038/srep36038. — Bibcode: 2016NatSR...636038D. — PMC 5093619. Архивировано 24 февраля 2021 года.
↑ cf; Huelsenbeck, J. P.; Ronquist, F.; Nielsen, R.; Bollback, J. P. Bayesian inference of phylogeny and its impact on evolutionary biology (англ.) // Science : journal. — 2001. — Vol. 294, no. 5550. — P. 2310—2314. — doi:10.1126/science.1065889. — Bibcode: 2001Sci...294.2310H.
↑ Allikmets, Rando; Wasserman, Wyeth W.; Hutchinson, Amy; Smallwood, Philip; Nathans, Jeremy; Rogan, Peter K. Thomas D. Schneider, Michael Dean (1998) Organization of the ABCR gene: analysis of promoter and splice junction sequences] (англ.) // Gene^[англ.] : journal. — Elsevier, 1998. — Vol. 215, no. 1. — P. 111—122. — doi:10.1016/s0378-1119(98)00269-8. Архивировано 21 августа 2008 года.
↑ 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. Information Theory and Statistical Mechanics (англ.) // Phys. Rev. : journal. — 1957. — Vol. 106, no. 4. — P. 620. — doi:10.1103/physrev.106.620. — Bibcode: 1957PhRv..106..620J. Архивировано 30 августа 2011 года.
↑ Bennett, Charles H.; Li, Ming; Ma, Bin. Chain Letters and Evolutionary Histories (англ.) // Scientific American. — Springer Nature, 2003. — Vol. 288, no. 6. — P. 76—81. — doi:10.1038/scientificamerican0603-76. — Bibcode: 2003SciAm.288f..76B. — PMID 12764940. Архивировано 7 октября 2007 года.
↑ David R. Anderson. Some background on why people in the empirical sciences may want to better understand the information-theoretic methods (неопр.) (pdf) (1 ноября 2003). Дата обращения: 23 июня 2010. Архивировано 23 июля 2011 года.

Литература

Кудряшов Б. Д. Теория информации, СПбГУ НИУ ИТМО
Леонтьев В. К., Гордеев Э. Н. Комбинаторные аспекты теории информации. М.: МФТИ, 2019.
Тростников В.Н. Человек и информация. — М.: Наука, 1970. — 188 с.
Фурсов В. А. Лекции по теории информации ISBN 5-7883-0458-X
Claude E. Shannon, Warren Weaver. The Mathematical Theory of Communication. Univ of Illinois Press, 1963. ISBN 0-252-72548-4
Thomas M. Cover^[англ.], Joy A. Thomas. Elements of information theory New York: Wiley, 1991. ISBN 0-471-06259-6
R. Landauer, Information is Physical Proc. Workshop on Physics and Computation PhysComp’92 (IEEE Comp. Sci.Press, Los Alamitos, 1993) pp. 1-4.
Maxwell’s Demon: Entropy, Information, Computing, H. S. Leff and A. F. Rex, Editors, Princeton University Press, Princeton, NJ (1990). ISBN 0-691-08727-X
Шеннон К. Работы по теории информации и кибернетике. — М.: Изд. иностр. лит., 1963. — 830 с.
Колмогоров А. Н. Три подхода к определению понятия «количество информации», Пробл. передачи информ., 1:1 (1965), 3-11
MacKay, David. Information Theory, Inference, and Learning Algorithms. — Cambridge University Press, 2003. — ISBN 9780521642989.

Ссылки

Теория информации // Энциклопедия «Кругосвет».
Норберт Винер. «Кибернетика или Управление и связь в животном и машине»
К. Шеннон. «Бандвагон»
Традиционные подходы к количественному определению информации
Синергетическая теория информации
Холево А. С. Введение в квантовую теорию информации
Холево А. С. Квантовые системы, каналы, информация (c2) М.: МЦНМО, 2014, 327 с. (На портале изд-ва, pdf, 2M)
compression.ru
Электронный учебник по теории информации
Электронный учебник по теории информации

[Spikes-1] F. Rieke; D. Warland; R Ruyter van Steveninck; W Bialek. Spikes: Exploring the Neural Code (неопр.). — The MIT press, 1997. — ISBN 978-0262681087.

[2] Delgado-Bonal, Alfonso; Martín-Torres, Javier. Human vision is determined based on information theory (англ.) // Scientific Reports^[англ.]. — 2016. — 3 ноября (т. 6, № 1). — ISSN 2045-2322. — doi:10.1038/srep36038. — Bibcode: 2016NatSR...636038D. — PMC 5093619. Архивировано 24 февраля 2021 года.

[3] cf; Huelsenbeck, J. P.; Ronquist, F.; Nielsen, R.; Bollback, J. P. Bayesian inference of phylogeny and its impact on evolutionary biology (англ.) // Science : journal. — 2001. — Vol. 294, no. 5550. — P. 2310—2314. — doi:10.1126/science.1065889. — Bibcode: 2001Sci...294.2310H.

[4] Allikmets, Rando; Wasserman, Wyeth W.; Hutchinson, Amy; Smallwood, Philip; Nathans, Jeremy; Rogan, Peter K. Thomas D. Schneider, Michael Dean (1998) Organization of the ABCR gene: analysis of promoter and splice junction sequences] (англ.) // Gene^[англ.] : journal. — Elsevier, 1998. — Vol. 215, no. 1. — P. 111—122. — doi:10.1016/s0378-1119(98)00269-8. Архивировано 21 августа 2008 года.

[5] 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.

[6] Jaynes, E. T. Information Theory and Statistical Mechanics (англ.) // Phys. Rev. : journal. — 1957. — Vol. 106, no. 4. — P. 620. — doi:10.1103/physrev.106.620. — Bibcode: 1957PhRv..106..620J. Архивировано 30 августа 2011 года.

[7] Bennett, Charles H.; Li, Ming; Ma, Bin. Chain Letters and Evolutionary Histories (англ.) // Scientific American. — Springer Nature, 2003. — Vol. 288, no. 6. — P. 76—81. — doi:10.1038/scientificamerican0603-76. — Bibcode: 2003SciAm.288f..76B. — PMID 12764940. Архивировано 7 октября 2007 года.

[8] David R. Anderson. Some background on why people in the empirical sciences may want to better understand the information-theoretic methods (неопр.) (pdf) (1 ноября 2003). Дата обращения: 23 июня 2010. Архивировано 23 июля 2011 года.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]