Теорема о разделении¶

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

¶История

¶Предпосылки

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

¶Формулировка Шенноном

В 1948 году Клод Шеннон опубликовал работу «Математическая теория связи», в которой ввёл понятия энтропии источника, пропускной способности канала и сформулировал две основные теоремы кодирования:

• Теорема о кодировании источника (source coding theorem), которая утверждает, что средняя длина кода может быть сколь угодно близкой к энтропии источника, но не меньше её.
• Теорема о кодировании канала (channel coding theorem), которая устанавливает, что надёжная передача возможна со скоростью, меньшей пропускной способности канала, и невозможна при превышении этой величины.

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

¶Развитие и уточнения

В 1970-х — 1980-х годах теорема о разделении была строго доказана для различных классов каналов, включая стационарные каналы без памяти и каналы с памятью. Томас Кавер и Мохаммад-Али Мехрдад в 1975 году показали, что для некоторых каналов с обратной связью разделение может не быть оптимальным, однако для большинства практических сценариев теорема остаётся справедливой. В 2000-х годах появились работы, анализирующие границы применимости теоремы для каналов с конечной длиной блока и для многопользовательских систем (например, каналов с множественным доступом).

¶Формальная постановка

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

• Источник дискретных сообщений — случайный процесс, порождающий символы из конечного алфавита с известным распределением вероятностей.
• Энтропия источника H(S) — мера средней неопределённости на символ, выраженная в битах.
• Канал связи — среда, на выходе которой сигнал искажается шумом; характеризуется пропускной способностью C (бит на использование канала).
• Скорость передачи R — среднее количество бит информации, передаваемых за одно использование канала.

¶Утверждение

Пусть источник S имеет энтропию H, а канал — пропускную способность C. Тогда для любого ε > 0 существует схема кодирования, состоящая из двух последовательных блоков:

1. Кодер источника — преобразует последовательность символов источника в двоичный поток (кодовые слова), длина которого стремится к H бит на символ при стремлении длины блока к бесконечности, с вероятностью ошибки восстановления < ε.
2. Кодер канала — преобразует сжатый поток в последовательность входных символов канала таким образом, что при скорости R < C вероятность ошибки декодирования может быть сделана сколь угодно малой.

Обратное утверждение: если R > C, то надёжная передача невозможна с любой схемой кодирования.

¶Доказательство (концепция)

Доказательство теоремы о разделении обычно опирается на метод типичных последовательностей (method of typical sets). Идея состоит в том, что при больших длинах блоков почти все последовательности источника оказываются в «типичном множестве» размера ≈ 2^{nH}, а остальные последовательности имеют ничтожную вероятность. Сжатие источника сводится к индексации только типичных последовательностей, что даёт скорость, близкую к H. Затем эти индексы передаются по каналу с помощью случайного кодирования, где кодовые слова выбираются случайно из всех возможных входных последовательностей. Для скорости R < C с вероятностью, стремящейся к 1, типичное кодовое слово будет единственным, совместно типичным с принятым сигналом, что обеспечивает надёжность декодирования.

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

¶Разделение задач в системах связи

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

• В мобильной связи (LTE, 5G) аудиокодек сжимает речь по стандарту AMR или EVS, после чего канальный кодер добавляет избыточность (турбокоды или коды LDPC) без учёта статистики речи — это допустимо благодаря теореме.
• В цифровом телевидении (DVB) сначала выполняется сжатие видео (MPEG), затем — помехоустойчивое кодирование (код Рида — Соломона, свёрточный код).
• В интернет-протоколах данные сжимаются (gzip, Deflate), а затем передаются по протоколам с контролем ошибок (TCP, ARQ).

¶Ограничения для коротких блоков

Теорема о разделении справедлива в асимптотическом смысле — при стремлении длины блока к бесконечности. Для коротких сообщений (например, 10–100 бит) независимое кодирование источника и канала может быть существенно хуже совместно оптимизированной схемы. В таких случаях применяют так называемые совместное кодирование (joint source-channel coding), особенно в беспроводных сенсорных сетях или в системах с жёсткими ограничениями на задержку.

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

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

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

• Клод Шеннон сформулировал теорему на интуитивном уровне, не давая строгого математического доказательства. Первое строгое доказательство появилось в 1954 году в работах А. Файнштейна и Ч. Шеннона.
• Теорема о разделении положила начало информационному разделению «source-channel separation principle», которое до сих пор используется в учебниках и практических разработках.
• В квантовой теории информации существует аналог — теорема Шеннона для квантовых каналов, которая также устанавливает возможность разделения кодирования источника и канала, но с учётом принципов квантовой механики.
• Несмотря на более чем полувековой возраст, теорема остаётся предметом активных исследований применительно к новым моделям каналов (например, каналы с энергетическим ограничением, каналы с памятью в молекулярной связи).

¶Источники

• Шеннон, К. «Математическая теория связи» (1948).
• Кавер, Т. М., Томас, Дж. А. «Элементы теории информации» (2006).
• Галлагер, Р. «Теория информации и надёжная связь» (1968).
• Арктис, П. «Современное кодирование: совместный источник-канальный подход» (2014).