Кодирование Слепяна–Вольфа

В теории информации и связи кодирование Слепяна –Вольфа , также известное как граница Слепяна–Вольфа , является результатом распределенного кодирования источников, открытого Дэвидом Слепяном и Джеком Вольфом в 1973 году. Это метод теоретического кодирования двух сжатых без потерь коррелированных источников . ^[1]

Проблема настройки

Распределенное кодирование — это кодирование двух, в данном случае, или более зависимых источников с отдельными кодерами и совместным декодером . При наличии двух статистически зависимых независимых и одинаково распределенных конечных алфавитных случайных последовательностей и теорема Слепяна–Вольфа дает теоретическую границу для скорости кодирования без потерь для распределенного кодирования двух источников. ${\displaystyle X^{n}}$ ${\displaystyle Y^{n}}$

Теорема

Граница для скорости кодирования без потерь показана ниже: ^[1]

${\displaystyle R_{X}\geq H(X|Y),\,}$

${\displaystyle R_{Y}\geq H(Y|X),\,}$

${\displaystyle R_{X}+R_{Y}\geq H(X,Y).\,}$

Если и кодер, и декодер двух источников независимы, то наименьшая скорость, которую он может достичь для сжатия без потерь, равна и для и соответственно, где и являются энтропиями и . Однако при совместном декодировании, если принимается исчезающая вероятность ошибки для длинных последовательностей, теорема Слепяна–Вольфа показывает, что можно достичь гораздо лучшей скорости сжатия. Пока общая скорость и больше их совместной энтропии и ни один из источников не кодируется со скоростью, меньшей его энтропии , распределенное кодирование может достичь произвольно малой вероятности ошибки для длинных последовательностей. ^[1] ${\displaystyle H(X)}$ ${\displaystyle H(Y)}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle H(X)}$ ${\displaystyle H(Y)}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle H(X,Y)}$

Частным случаем распределенного кодирования является сжатие с информацией на стороне декодера, где источник доступен на стороне декодера, но недоступен на стороне кодера. Это можно рассматривать как условие, которое уже использовалось для кодирования , в то время как мы намерены использовать для кодирования . Другими словами, два изолированных источника могут сжимать данные так же эффективно, как если бы они взаимодействовали друг с другом. Вся система работает асимметрично (степень сжатия для двух источников асимметрична). ^[1] ${\displaystyle Y}$ ${\displaystyle R_{Y}=H(Y)}$ ${\displaystyle Y}$ ${\displaystyle H(X|Y)}$ ${\displaystyle X}$

Эта граница была распространена на случай более двух коррелированных источников Томасом М. Кавером в 1975 году ^[2] , и аналогичные результаты были получены в 1976 году Аароном Д. Уайнером и Джейкобом Зивом в отношении кодирования с потерями совместных гауссовых источников. ^[3]

Смотрите также

• Сжатие данных
• Синхронизация данных
  • Синхронизация (информатика)
• ДИСКУС
• Хронология теории информации

Ссылки

1. Slepian & Wolf 1973, стр. 471–480.
2. Обложка 1975, стр. 226–228.
3. Уайнер и Зив 1976, стр. 1–10.

Источники

• Cover, Thomas M. (март 1975 г.). «Доказательство теоремы о сжатии данных Слепиана и Вольфа для эргодических источников» Т.». Труды IEEE по теории информации . 21 (2): 226–228. doi :10.1109/TIT.1975.1055356. ISSN  0018-9448.
• Слепян, Дэвид С.; Вольф , Джек К. (июль 1973 г.). «Бесшумное кодирование коррелированных источников информации». Труды IEEE по теории информации . 19 (4): 471–480. doi :10.1109/TIT.1973.1055037. ISSN  0018-9448.
• Wyner, Aaron D. ; Ziv, Jacob (январь 1976). "Функция скорости-искажения для кодирования источника с побочной информацией в декодере". IEEE Transactions on Information Theory . 22 (1): 1–10. CiteSeerX  10.1.1.137.494 . doi :10.1109/TIT.1976.1055508. ISSN  0018-9448.

Внешние ссылки

• Алгоритм кодирования видео Винера-Зива для сжатия видео, который работает близко к пределу Слепяна-Вульфа (со ссылками на исходный код).