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

Теория информации изучает вопросы измерения, хранения и передачи информации.

История теории информации

Появление дисциплины теории информации в основном связывают с публикацией в июле и октябре 1948 года в журнале Bell System Technical Journal статьи Клода Шеннона “Математическая теория коммуникации”.

В этой революционной работе впервые представлена качественная и количественная модель связи в виде статистического процесса. Эта модель собственно стала основой теории информации.

Вследствие появления модели связи, появились так же понятия

• информационной энтропии и избыточности источника; Теорема Шеннона о кодировании источника
• взаимной информации и пропускной способности зашумлённого канала; Теоремы Шеннона для канала с шумами
• теоремы Шеннона-Хартли о предельной пропускной способности зашумлённого канала с гауссовским шумом
• количественной меры информации

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

Прямыми предшественниками работ Шеннона были две работы, опубликованные в 1920-х годах Гарри Найквистом и Ральфом Хартли.

Статья Найквиста 1924 года “Определённые факторы, влияющие на скорость телеграфа” в основном посвящена некоторым подробным техническим аспектам телеграфных сигналов. Однако в более теоретическом разделе рассматривается количественная оценка “сведений” и “линейной скорости”, с которой они могут передаваться через коммуникационную систему в виде

\[W=K\log m,\] где \(W\) - скорость передачи данных, \(m\) - количество различных уровней напряжения на выбор на каждом шаге, а \(K\) - постоянная.

В работе Хартли 1928 года, называвшейся просто “Передача информации”, было использовано слово “информация” (в техническом смысле), и было чётко указано, что информация в этом контексте является измеримой величиной, отражающей только способность получателя отличать одну последовательность символов от любой другой - независимо от любого связанного значения или других психологических или семантических аспектов, которые они могут представлять. Это количество информации, которую он определил как

\[H=\log S^{n},\] где S - количество возможных символов, а n - количество символов в передаче. Естественной единицей информации, таким образом, была десятичная цифра.

Аналогичные единицы вероятности были введены Аланом Тьюрингом в 1940 году в рамках статистического криптоанализа немецкой шифровальной машины Enigma.

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

Областью, в которой активно изучалась неравномерность вероятностей, являлась статистическая механика. В частности, Людвиг Больцманн в контексте своей H-теоремы 1872 года впервые представил количественную меру

\[ H=-\sum f_{i}\log f_{i}\] в качестве меры широты распространения состояний, доступных для одной частицы в газе таких же частиц, где f представляет собой относительное распределение частот каждого возможного состояния. Больцманн математически утверждал, что эффект столкновений между частицами неизбежно приведёт к увеличению Н-функции от любой начальной конфигурации до достижения равновесия, и далее идентифицировал её как лежащее в основе микроскопического обоснования макроскопической термодинамической энтропии Клаузиуса.

Определение Больцмана вскоре было переработано Уиллардом Гиббсом в общую формулу статистико-механической энтропии, которая больше не требует идентичных и не взаимодействующих частиц, а основана на вероятностном распределении pi для всего микросостояния i общей системы:

\[S=-k_{\text{B}}\sum p_{i}\ln p_{i}\]

Эта (Гиббсовская) энтропия, как можно показать на основе статистической механики, находится в прямом соответствии с классическим термодинамическим определением Клаузиуса.

Сам Шеннон, по-видимому, не был особенно осведомлен о близком сходстве между его новой мерой информации и предыдущей работой в области термодинамики, но Джон фон Нейман был. Говорят, что когда Шеннон решал, как назвать свою новую меру и боялся, что термин “информация” уже был чрезмерно загружен, фон Нейман твердо сказал ему: “Следует назвать новую меру энтропией, по двум причинам. Во-первых, соответствующая функция неопределённости использовалась в статистической механике под этим названием, поэтому у неё уже есть название. Во-вторых, что ещё более важно, никто не знает, что такое энтропия на самом деле, поэтому в дебатах вы всегда будете иметь преимущество”.

Понятие информации

Информация – это одно из фундаментальных понятий современной науки, наряду с понятиями материи и энергии. По-видимому, не только понятие. В начале прошлого века Эйнштейн показал, что материя и энергия – по сути одно и то же (знаменитая формула \(E=m c^2\)). Современные исследования в физике указывают на то, что подобная связь может быть и между информацией и энергией.

С точки зрения же человека, информация – это некие сведения, которые могут быть понятными, достоверными, актуальными и т.п., или наоборот.

Существуют различные формальные подходы к определению информации. С точки зрения информатики, нас интересуют два определения.

Информация по Шеннону

Информация – это снятая неопределенность.

Это удобное интуитивное определение. Неопределенность в данном случае – характеристика нашего незнания о предмете. Например, в момент броска игрального кубика, мы не знаем, какая из 6 граней выпадет. Когда же кубик останавливается на какой-то грани – мы получаем информацию.

Это определение, однако, не слишком удобно без некоторой количественной меры неопределенности.

Величина неопределенности

количество возможных равновероятных исходов события

Так, например, игральный кубик имеет неопределенность 6.

Такой подход к определению информации называется содержательным. Он интуитивно понятен, однако, не отвечает на вопрос “сколько информации получено”.

Количество информации по Колмогорову

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

Поскольку любой алфавит может быть закодирован в двоичном, очевидно это определение достаточно универсально: оно применимо для любого сообщения, которое может быть записано на каком-либо языке. Этот подход называется алфавитным.

В качестве основной единицы количества информации принято брать бит – от binary digit.

При алфавитном подходе один бит – это количество информации, которое можно закодировать одним двоичным знаком (0 или 1). С точки зрения содержательного подхода, один бит – это количество информации, уменьшающее неопределенность в два раза.

Существуют более крупные единицы информации, которые чаще используются на практике.

В вопросе хранения информации, основным показателем является не количество информации, а информационный объем

Информационный объем сообщения

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

В отличие от количества информации, информационный объем может быть не минимальным. В частности, кодирование текстов в различных кодировках далеко не оптимально.

Задачи, решаемые в рамках теории информации

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

Любая информация для того, чтобы быть переданной, должна быть соответственным образом «закодирована», т. е. переведена на язык специальных символов или сигналов. Сигналами, передающими информацию, могут быть электрические импульсы, световые или звуковые колебания, механические перемещения и т. д.

Одной из задач теории информации является отыскание наиболее экономных методов кодирования, позволяющих передать заданную информацию с помощью минимального количества символов. Эта задача решается как при отсутствии, так и при наличии помех в канале связи.

Другая типичная задача теории информации ставится следующим образом: имеется источник информации (передатчик), непрерывно вырабатывающий информацию, и канал связи, по которому эта информация передаётся в другую точку (на приёмник). Какова должна быть пропускная способность канала связи для того, чтобы канал “справлялся” со своей задачей, т. е. передавал всю поступающую информацию без задержек и искажений?

Ряд задач теории информации относится к определению объёма запоминающих устройств, предназначенных для хранения информации, к способам ввода информации в эти запоминающие устройства и вывода её для непосредственного использования.

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