Теория информации
Теорема Слепяна-Вольфа
Цели урока
- Сформулировать задачу SW и три ограничения области скоростей
- Объяснить доказательство через случайный хэш (random binning)
- Описать практическую реализацию через синдромное кодирование (DISCUS)
- Обобщить теорему на K источников и связать с MAC-каналом
Предварительные знания
Два независимых кодера не общаются. Декодер может объединить их выходы. Как это позволяет достичь границы H(X,Y) - столько же, сколько при совместном кодировании?
- ZigBee сенсорная сеть: SW-кодирование экономит 40-75% энергии батарей узлов
- DISCOVER видеокодек: кодирование без опорных кадров через синдромы SW/WZ
- LoRaWAN IoT: 500 датчиков с корреляцией 0.9 - потенциальная экономия 5x
- Federated learning: передача градиентов через SW-принцип, 10-50x сжатие
1973: парадоксальная теорема
Дэвид Слепян и Джек Вольф в 1973 году публикуют 'Noiseless Coding of Correlated Information Sources' в IEEE Transactions on Information Theory. Результат поначалу казался парадоксальным: как независимые кодеры могут достичь того же, что совместный кодер? Ответ - в совместном декодировании: декодер использует корреляцию между X и Y, даже если кодеры не знали об этом. Теорема оставалась теоретической 30 лет. Практические коды - DISCUS (Pradhan & Ramchandran, 2003) через LDPC и турбо-коды. DISCOVER (2006) - первый видеокодек на основе SW/WZ. Сейчас SW используется в сенсорных сетях, видеокодировании и federated learning.
Задача Слепяна-Вольфа: зачем кодировать вместе?
2006 год. Сенсорная сеть ZigBee из 100 узлов собирает температуру в промышленном помещении. Каждый узел хочет передать данные независимо - нет смысла прокладывать шину для координации. Но данные коррелированы: соседние датчики показывают похожие значения. Можно ли кодировать независимо и при этом сжать так же хорошо, как при совместном кодировании? Дэвид Слепян и Джек Вольф доказали в 1973 году: да.
ZigBee сенсорная сеть: практический SW
Сеть из N датчиков температуры в промышленном помещении. Каждый датчик i имеет температуру T_i = T_avg + delta_i, где delta_i ~ N(0, sigma^2). Соседние датчики коррелированы: corr(delta_i, delta_j) = exp(-d_ij/L), где d_ij - расстояние, L - корреляционная длина (~10м). При N=100, sigma=2°C, L=10м: H(T1,...,T100) << sum H(T_i). Теорема SW: каждый датчик передаёт H(T_i | T_остальные) ~ 0.5 бит/символ вместо H(T_i) ~ 2 бит/символ. Экономия 75% энергии батареи.
Теорема SW - часть более широкой сетевой теории информации: несколько кодеров, один декодер. Отличие от MAC-канала: там задача кодирования по каналу, здесь - кодирование источника. Дуальность: MAC-канал <-> SW-кодирование. Область SW симметрична области MAC при замене I на H.
Что гарантирует теорема SW при независимом кодировании X и Y?
SW: независимые кодеры, совместный декодер. Суммарно достаточно H(X,Y) бит. Сравни: независимое сжатие до H(X)+H(Y) бит. Выигрыш I(X;Y) = H(X)+H(Y)-H(X,Y). При высокой корреляции (I(X;Y) большое) экономия значительна.
Доказательство и случайный хэш
Доказательство теоремы SW элегантно и поучительно. Ключевая идея: случайный хэш (random binning) заменяет явную конструкцию кода. Кодер X не знает Y, но с высокой вероятностью в его бине оказывается ровно одна последовательность X^n, типичная относительно полученного Y^n.
Практическая реализация теоремы SW - через линейные коды над конечными полями. LDPC + SW: каждый источник применяет синдром LDPC-кода как хэш. Декодирование: двухсторонняя BP на объединённом факторном графе. Это DISCUS (Distributed Source Coding Using Syndromes) - предложен Pradhan & Ramchandran (2003).
Почему P(ошибка типа 2) убывает при R_X > H(X|Y)?
В каждом бине для кодера X ожидается 2^{nH(X|Y)} / 2^{nR_X} = 2^{n(H(X|Y)-R_X)} последовательностей, совместно типичных с Y^n. При R_X > H(X|Y) это < 1 - ложного типичного элемента нет с высокой вероятностью. Декодер находит единственный совместно типичный (x^n, y^n).
Применения: сенсорные сети и распределённые системы
Теорема SW - теоретический идеал для распределённого сжатия. Практические реализации работают через синдромное кодирование: вместо явного кода SW используется проверочная матрица (как в LDPC). Это DISCUS, turbo-SW, LDPC-SW - всё одна идея: синдром = хэш бина.
Видеокодирование Wyner-Ziv / SW: DISCOVER
DISCOVER (2006) - видеокодек на основе SW/WZ: кодируется каждый k-й кадр (keyframe), остальные кодируются через синдром без опорных кадров. Декодер имеет опорный кадр и синдром текущего - это точно задача SW/WZ. При равной скорости DISCOVER: PSNR на 1-2 дБ ниже H.264. Но: кодирование в 10x раз проще - применение для IP-камер с ограниченными вычислениями и видеонаблюдения.
Federated learning через SW-линзу: каждый клиент имеет локальный градиент - коррелированный с глобальным градиентом. Если клиент знает глобальное направление (боковая информация у декодера = сервера), нужно передавать только H(grad_local | grad_global) бит. Это и есть задача WZ/SW для федеративного обучения. PowerGossip (2021) использует случайные проекции градиентов - фактически CS+SW - для экономии пропускной способности в 10-50 раз.
Почему синдромное кодирование (DISCUS) является практической реализацией теоремы SW?
В SW: хэш = бин. В DISCUS: синдром = бин-индекс. Число синдромных бит: nH(X|Y) = нижняя граница SW. Декодер с Y^n делает BP-декодирование: ищет x^n в ядре синдрома, близкий к прогнозу из Y^n. Это точная реализация случайного бинирования через линейный код.
Обобщения: K источников и непрерывные алфавиты
Теорема SW для двух источников обобщается на K источников. Область SW: для каждого подмножества S суммарная скорость >= H(X_S | X_{S^c}). Это 2^K - 1 ограничений - структура аналогична MAC-каналу. Для непрерывных источников: то же с дифференциальной энтропией h(X|Y).
IoT-стандарт LoRaWAN для сельскохозяйственных датчиков: 500 датчиков влажности почвы с корреляцией 0.9 между соседними. Без SW: 500 * H(X_i) = 500 * 4 бит = 2000 бит/секунду. С K-SW: H(X_1,...,X_500) ~ 100 * 4 бит = 400 бит/секунду (эффективная размерность ~ 100 из 500). Выигрыш 5x - принципиально для батарейных устройств со временем жизни 10 лет.
Какова минимальная суммарная скорость для K коррелированных источников по теореме SW?
Сумма скоростей >= H(X_1,...,X_K). Это достижимо: декодировать последовательно по схеме 'onion peeling'. Сравни с независимым кодированием: сумма >= sum H(X_i) = H(X_1,...,X_K) + I(X_1;...;X_K). Выигрыш = взаимная информация всех K источников.
Связь с другими темами
Теорема SW использует: AEP и типичные последовательности (доказательство), условную энтропию H(X|Y) (нижняя граница скорости), случайное кодирование (ключевой приём). Дуальность с MAC-каналом: область SW аналогична области MAC при замене I(X_S;Y|X_{S^c}) на H(X_S|X_{S^c}). Обобщения: WZ (потери), многопользовательский SW (K источников), distributed video coding. Связь с ML: SW-принцип в federated learning - распределённое обучение без передачи всех данных.
- Related Topics — Связанная тема
Итоги
- SW: два независимых кодера достигают суммарной скорости H(X,Y) через совместное декодирование
- Область: R_X >= H(X|Y), R_Y >= H(Y|X), R_X+R_Y >= H(X,Y)
- Доказательство: случайный хэш + типичные множества; ошибка ~ 2^{-n(R_X - H(X|Y))}
- DISCUS: синдром LDPC = хэш бина; практическая реализация SW через BP
Вопросы для размышления
- Почему совместное декодирование позволяет кодерам работать независимо без потери эффективности?
- В чём аналогия между теоремой SW для источников и MAC-каналом для каналов?
- Как синдромное кодирование реализует 'случайный хэш' из доказательства SW?