Открыть сервис
Главная → Блог → Теорема о кодировании канала

Теорема о кодировании канала

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

История

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

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

Формулировка

Для дискретного канала без памяти (ДКБП) теорема формулируется следующим образом:

Пусть канал характеризуется пропускной способностью \( C \) (бит/символ или бит/с). Тогда:

  1. Прямая теорема: Для любой скорости передачи \( R < C \) существует последовательность кодов длины \( n \) со скоростью \( R \), для которых вероятность ошибки декодирования стремится к нулю при \( n \to \infty \).
  2. Обратная теорема: Для любой скорости \( R > C \) вероятность ошибки любого кода длины \( n \) со скоростью \( R \) стремится к 1 при \( n \to \infty \), то есть надёжная передача невозможна.

Пропускная способность канала определяется как максимум взаимной информации между входом и выходом канала по всем возможным распределениям входных символов: \[ C = \max_{p(x)} I(X;Y) \]

Для непрерывного канала с аддитивным белым гауссовским шумом (АБГШ) пропускная способность выражается формулой Шеннона-Хартли: \[ C = B \log_2\left(1 + \frac{S}{N}\right) \] где \( B \) — полоса пропускания канала, \( S/N \) — отношение сигнал/шум.

Доказательство

Прямая теорема (существование хороших кодов)

Доказательство Шеннона использует метод случайного кодирования:

  1. Рассматривается ансамбль всех возможных кодов с заданными параметрами (длина блока \( n \), число кодовых слов \( M = 2^{nR} \)).
  2. Для каждого кодового слова декодер использует типичное декодирование: выбирается слово, совместно типичное с принятой последовательностью.
  3. Показывается, что средняя по ансамблю вероятность ошибки стремится к нулю при \( n \to \infty \), если \( R < C \).
  4. Поскольку среднее значение неотрицательной величины стремится к нулю, существует хотя бы один код с вероятностью ошибки не выше средней.

Обратная теорема (невозможность при превышении скорости)

Доказательство основано на неравенстве Фано и свойствах взаимной информации:

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

Следствия и интерпретация

Предел Шеннона

Теорема устанавливает фундаментальный предел скорости передачи, который не может быть превышен ни при каком кодировании. Этот предел называют «пределом Шеннона» или «шэнноновским пределом». Для канала с АБГШ предел выражается как \( C = B \log_2(1 + SNR) \).

Компромисс между скоростью и надёжностью

Теорема показывает, что для любой скорости ниже пропускной способности можно достичь сколь угодно малой вероятности ошибки, но для этого требуется увеличивать длину кодового блока. Практические системы всегда работают с конечной задержкой и вычислительной сложностью, поэтому реальная вероятность ошибки всегда положительна.

Кодирование и декодирование

Теорема не указывает, как строить конкретные коды, а лишь доказывает их существование. На практике разработаны различные помехоустойчивые коды, приближающиеся к пределу Шеннона: свёрточные коды, турбокоды, коды с низкой плотностью проверок на чётность (LDPC), полярные коды.

Обобщения

Непрерывные каналы

Для каналов с непрерывным временем и АБГШ теорема обобщается с использованием формулы Шеннона-Хартли. Пропускная способность зависит от полосы и отношения сигнал/шум.

Каналы с памятью

Для каналов с памятью (например, каналов с замираниями) теорема обобщается с учётом корреляции между символами. В таких случаях пропускная способность может быть ниже, чем для канала без памяти с теми же маргинальными характеристиками.

Многопользовательские каналы

Для каналов с несколькими передатчиками и/или приёмниками (множественный доступ, вещательный канал, канал с ретрансляцией) существуют свои теоремы кодирования, определяющие области достижимых скоростей.

Квантовые каналы

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

Практическое значение

Теорема о кодировании канала является теоретической основой для проектирования систем связи:

Современные системы связи, такие как 4G/5G, Wi-Fi, DVB-T2, используют коды, работающие в пределах 0.5–1 дБ от предела Шеннона.

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

Теорема предполагает:

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

См. также

Источники

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →

Похожие материалы