Математическая теория связи¶

Математическая теория связи (также известная как теория информации) — раздел прикладной математики и теории связи, изучающий количественные законы передачи, хранения и обработки информации. Основы теории были заложены американским инженером и математиком Клодом Шенноном в 1948 году в статье «Математическая теория связи» (A Mathematical Theory of Communication). Теория определяет фундаментальные пределы сжатия данных, надёжной передачи по каналам с шумом и оценки количества информации, содержащейся в сообщении.

¶История

Предпосылки к созданию теории информации возникли в конце XIX — начале XX века в связи с развитием телеграфии и телефонии. В 1924 году американский инженер Гарри Найквист вывел формулу, связывающую скорость передачи данных с шириной полосы частот. В 1928 году Ральф Хартли предложил логарифмическую меру количества информации, основанную на числе возможных символов.

Ключевой вклад внёс Клод Шеннон, работавший в Bell Laboratories. В 1948 году он опубликовал статью «Математическая теория связи», в которой ввёл понятие энтропии как меры неопределённости сообщения, определил пропускную способность канала и доказал две фундаментальные теоремы: теорему о кодировании источника (теорема Шеннона — Фано) и теорему о кодировании канала с шумом. Эти результаты стали основой цифровой связи и теории кодирования.

Параллельно с Шенноном схожие идеи развивал советский математик Андрей Колмогоров, который в 1950-х годах дал собственное определение количества информации, основанное на теории алгоритмов (алгоритмическая сложность). В 1956 году вышла книга «Математическая теория связи» под редакцией Шеннона и Уивера, которая систематизировала основные положения.

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

¶Информация и энтропия

В математической теории связи информация рассматривается не как смысл сообщения, а как мера уменьшения неопределённости. Основной количественной характеристикой является энтропия \( H \), измеряемая в битах. Для дискретного источника с алфавитом из \( n \) символов, каждый из которых имеет вероятность \( p_i \), энтропия определяется по формуле:

\[ H = -\sum_{i=1}^{n} p_i \log_2 p_i \]

Энтропия достигает максимума, когда все символы равновероятны, и равна нулю, если один символ встречается с вероятностью 1. Например, для подбрасывания монеты (два равновероятных исхода) энтропия составляет 1 бит.

¶Избыточность

Избыточность — разность между максимально возможной энтропией источника и его фактической энтропией. В естественных языках, например в русском, избыточность высока (около 50 %), что позволяет восстанавливать текст при частичной потере символов.

¶Взаимная информация

Взаимная информация \( I(X;Y) \) — мера зависимости между двумя случайными величинами \( X \) и \( Y \). Она показывает, сколько информации о \( X \) содержится в \( Y \). Взаимная информация симметрична и равна нулю, если величины независимы.

¶Теоремы Шеннона

¶Теорема о кодировании источника

Теорема утверждает, что для источника с энтропией \( H \) существует такой код, что средняя длина кодового слова может быть сколь угодно близка к \( H \), но не меньше \( H \). Это означает, что сжатие данных без потерь возможно до величины, равной энтропии источника. На практике используются коды Хаффмана, арифметическое кодирование и алгоритмы LZ.

¶Теорема о кодировании канала с шумом

Теорема устанавливает, что для канала с шумом существует максимальная скорость передачи информации, называемая пропускной способностью \( C \), при которой можно достичь сколь угодно малой вероятности ошибки. Если скорость передачи \( R \) меньше \( C \), то можно найти код, обеспечивающий надёжную передачу. Если \( R > C \), то ошибки неизбежны. Пропускная способность для дискретного канала без памяти вычисляется по формуле:

\[ C = \max_{p(x)} I(X;Y) \]

где \( p(x) \) — распределение вероятностей входных символов.

¶Классификация каналов связи

В теории информации каналы делятся по нескольким признакам:

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

Примеры: двоичный симметричный канал (BSC) — каждый бит с вероятностью \( p \) инвертируется; двоичный стирающий канал (BEC) — символ с вероятностью \( p \) теряется.

¶Применение

¶Сжатие данных

Теория информации лежит в основе алгоритмов сжатия без потерь (ZIP, PNG, FLAC) и с потерями (JPEG, MP3, MPEG). Для сжатия с потерями используется понятие искажения — минимальная скорость передачи при заданном уровне искажений (теория скорость-искажение).

¶Кодирование с исправлением ошибок

Коды Хэмминга, БЧХ, Рида — Соломона, свёрточные и турбо-коды, а также LDPC-коды применяются в системах связи (Wi-Fi, 4G/5G, спутниковая связь), хранении данных (CD, DVD, RAID) и цифровом телевидении.

¶Криптография

Понятие энтропии используется для оценки стойкости паролей и ключей. Взаимная информация служит мерой утечки данных.

¶Машинное обучение

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

¶Нейробиология и лингвистика

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

¶Критика и ограничения

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

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

¶Интересные факты

• Термин «бит» (binary digit) впервые предложил Клод Шеннон в 1948 году.
• Энтропия по Шеннону совпадает по форме с энтропией в термодинамике, что привело к дискуссиям о связи информации и физики (парадокс Максвелла, демон Максвелла).
• В 1950-х годах советские учёные (А. Н. Колмогоров, В. А. Котельников) развивали теорию информации независимо от западной школы.
• Теорема Шеннона о кодировании канала долгое время считалась чисто теоретической, но с появлением турбо-кодов в 1993 году и LDPC-кодов стало возможным приблизиться к пропускной способности на практике.

¶Источники

• Shannon C. E. A Mathematical Theory of Communication // Bell System Technical Journal. — 1948. — Vol. 27.
• Колмогоров А. Н. Три подхода к определению понятия «количество информации» // Проблемы передачи информации. — 1965. — Т. 1, вып. 1.
• Cover T. M., Thomas J. A. Elements of Information Theory. — 2nd ed. — Wiley, 2006.
• Мак-Элис Р. Теория информации и кодирование. — М.: Мир, 1976.