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

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

Основы теории заложил К. Шеннон в статье «Математическая теория связи» (A Mathematical Theory of Communication), опубликованной в двух частях в Bell System Technical Journal в июле и октябре 1948 года¹. Теория отвечает на два вопроса: насколько можно сжать данные и с какой скоростью их можно надежно передать по каналу с помехами².

Предмет

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

Модель системы связи

Шеннон описал систему связи из пяти частей¹:

Источник информации (information source) — порождает сообщение или последовательность сообщений: текст, речь, изображение.
Передатчик (transmitter) — преобразует сообщение в сигнал, пригодный для передачи: например, кодирует текст в точки и тире телеграфа или дискретизирует, квантует и кодирует речь.
Канал (channel) — среда, по которой сигнал идет от передатчика к приемнику: пара проводов, коаксиальный кабель, полоса радиочастот, луч света. В канале на сигнал действует источник шума (noise source).
Приемник (receiver) — выполняет обратное передатчику преобразование и восстанавливает сообщение из сигнала.
Получатель (destination) — человек или устройство, которому предназначено сообщение.

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

Основные понятия

Количество информации. Если сообщение выбирается из конечного множества равновероятных вариантов, мерой информации служит логарифм их числа. Логарифмическая мера удобна практически (добавление одного реле удваивает число состояний и прибавляет единицу к двоичному логарифму), соответствует интуиции (две перфокарты вмещают вдвое больше, чем одна) и упрощает математику¹.
Бит (bit) — единица информации при логарифме по основанию 2; слово предложил Дж. Тьюки. Устройство с двумя устойчивыми состояниями, например реле или триггер, хранит один бит¹.
Собственная информация (Shannon information content) исхода x — величина log₂ (1/P(x)) бит: чем менее вероятен исход, тем больше информации несет его наступление³.
Энтропия (entropy) — средняя неопределенность случайной величины: H = −Σ pᵢ log pᵢ, где pᵢ — вероятности исходов. Шеннон показал, что это единственная с точностью до множителя функция, удовлетворяющая естественным требованиям к мере неопределенности, и назвал ее энтропией по аналогии со статистической механикой¹.
Условная энтропия H(X|Y) — оставшаяся неопределенность X, когда известно Y; энтропии связаны цепным правилом H(X, Y) = H(X) + H(Y|X)⁴.
Взаимная информация (mutual information) I(X; Y) = H(X) − H(X|Y) — среднее уменьшение неопределенности X после того, как стало известно Y. Она симметрична и неотрицательна⁴.
Относительная энтропия, или расхождение Кульбака — Лейблера (Kullback–Leibler divergence), — мера отличия одного распределения вероятностей от другого. Она неотрицательна и равна нулю только для совпадающих распределений, но несимметрична, поэтому не является расстоянием в строгом смысле³.
Пропускная способность канала (channel capacity) C — максимально возможная скорость передачи информации по каналу. Для канала с шумом скорость передачи равна энтропии на входе за вычетом неопределенности входа, остающейся после наблюдения выхода: R = H(x) − H_y(x)¹.

Основные теоремы

Теорема кодирования источника (для канала без шума). Если источник имеет энтропию H бит на символ, а канал — пропускную способность C бит в секунду, то выход источника можно закодировать так, чтобы передавать в среднем сколь угодно близко к C/H символов в секунду, но не быстрее¹. Энтропия, таким образом, — нижняя граница среднего числа двоичных символов на сообщение при сжатии без потерь⁵.
Теорема кодирования для канала с шумом (noisy-channel coding theorem). Если энтропия источника в секунду H не превышает пропускной способности канала C, существует способ кодирования, при котором сообщения передаются со сколь угодно малой частотой ошибок. Если H > C, ошибки неизбежны, и никакое кодирование не сделает потерю информации меньше H − C¹. Иначе говоря, надежная связь возможна на любой скорости ниже пропускной способности и невозможна выше нее². Доказательство Шеннона не строит такой код, а показывает, что он существует среди некоторого класса кодов¹.
Пропускная способность канала с белым шумом. Для канала с полосой W, мощностью сигнала, ограниченной P, и мощностью белого теплового шума N пропускная способность равна C = W log₂ ((P + N) / N) бит в секунду¹. Формула показывает, как полоса и отношение сигнал/шум ограничивают скорость передачи.

Разделы

Кодирование источника (source coding), или сжимающее кодирование, — представление сообщений возможно меньшим числом символов. Средняя длина оптимального символьного кода лежит в пределах от H до H + 1 бита на символ; такой код строит, например, алгоритм Хаффмана⁵.
Канальное кодирование (channel coding), или помехоустойчивое кодирование, — добавление избыточности, которая позволяет обнаруживать и исправлять ошибки. Простейший пример — код Хэмминга (7, 4): три проверочных бита на каждые четыре информационных позволяют исправить любую одиночную ошибку в блоке из семи бит².
Теория секретных систем. В 1949 году Шеннон опубликовал в том же журнале статью «Теория связи в секретных системах» (Communication Theory of Secrecy Systems), где применил подход теории связи к криптографии⁶.

Применение

Результаты теории используются при проектировании модемов и линий связи, космической радиосвязи, систем хранения данных; ее понятия применимы и к копированию генетической информации при делении клеток, которое тоже можно рассматривать как канал с шумом². Дискретный случай теории, по замечанию Шеннона, применим также к вычислительным машинам и проектированию телефонных станций¹. Относительная энтропия и смежные понятия используются в распознавании образов и нейронных сетях³, а энтропия как мера неупорядоченности системы — в системной инженерии.

История

Шеннон опирался на работы Г. Найквиста (1924, 1928) и Р. Хартли (1928) о скорости телеграфной передачи и передаче информации; на то, что логарифмическая функция — наиболее естественная мера информации, указал еще Хартли. Сам Шеннон расширил теорию на влияние шума в канале и на экономию, которую дает статистическая структура сообщений¹.

Литература

Shannon C. E. A Mathematical Theory of Communication // Bell System Technical Journal. — 1948. — Vol. 27, № 3. — P. 379–423; № 4. — P. 623–656. — DOI: 10.1002/j.1538-7305.1948.tb01338.x, 10.1002/j.1538-7305.1948.tb00917.x.
Shannon C. E. Communication Theory of Secrecy Systems // Bell System Technical Journal. — 1949. — Vol. 28, № 4. — P. 656–715. — DOI: 10.1002/j.1538-7305.1949.tb00928.x.
MacKay D. J. C. Information Theory, Inference, and Learning Algorithms. — Cambridge: Cambridge University Press, 2003. — 640 p.
Cover T. M., Thomas J. A. Elements of Information Theory. — 2nd ed. — Hoboken: Wiley-Interscience, 2006. — ISBN 978-0-471-24195-9.

См. также

Shannon C. E. A Mathematical Theory of Communication. 1948 — введение, разделы о дискретном канале без шума (теоремы 2 и 9), о канале с шумом (теорема 11) и о непрерывном канале (теорема 17). ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸ ↩⁹ ↩¹⁰ ↩¹¹ ↩¹² ↩¹³
MacKay D. J. C. Information Theory, Inference, and Learning Algorithms. 2003. Глава 1 «Introduction to Information Theory». ↩ ↩² ↩³ ↩⁴ ↩⁵
MacKay D. J. C. Information Theory, Inference, and Learning Algorithms. 2003. Разделы 2.4 и 2.6. ↩ ↩² ↩³
MacKay D. J. C. Information Theory, Inference, and Learning Algorithms. 2003. Глава 8 «Dependent Random Variables». ↩ ↩²
MacKay D. J. C. Information Theory, Inference, and Learning Algorithms. 2003. Глава 5 «Symbol Codes». ↩ ↩²
Shannon C. E. Communication Theory of Secrecy Systems // Bell System Technical Journal. 1949. Vol. 28, № 4, p. 656–715. ↩