Распределенное исходное кодирование ( DSC ) - важная проблема в теории информации и коммуникации . Проблемы DSC касаются сжатия нескольких коррелированных источников информации, которые не взаимодействуют друг с другом. [1] Моделируя корреляцию между несколькими источниками на стороне декодера вместе с канальными кодами , DSC может переносить вычислительную сложность со стороны кодера на сторону декодера, таким образом обеспечивая соответствующие структуры для приложений с отправителем с ограниченной сложностью, таких как сенсорные сети. и сжатие видео / мультимедиа (см. распределенное кодирование видео [2]). Одним из основных свойств кодирования с распределенным источником является то, что вычислительная нагрузка в кодерах перекладывается на объединенный декодер.
История
В 1973 году Дэвид Слепян и Джек Кейл Вольф предложили теоретический предел сжатия информации без потерь для распределенного сжатия двух коррелированных источников ИИД X и Y. [3] После этого Томас М. Ковер расширил это ограничение на случаи с более чем двумя источниками. в 1975 г. [4], а теоретические результаты в случае сжатия с потерями представлены Аароном Д. Винером и Якобом Зивом в 1976 г. [5]
Хотя теоремы о DSC были предложены в 1970-х годах, примерно через 30 лет были начаты попытки практических методов, основанных на идее, что DSC тесно связан с кодированием каналов, предложенным в 1974 году Аароном Д. Винером . [6] Проблема асимметричного DSC была рассмотрена С.С. Прадханом и К. Рамчандраном в 1999 г., которые сосредоточились на статистически зависимых двоичных и гауссовских источниках и использовали скалярные и решетчатые конструкции смежных классов для решения проблемы. [7] Они продолжили работу над симметричным случаем DSC. [8]
Технология декодирования синдромов была впервые использована в кодировании распределенного источника системой DISCUS С.С. Прадхана и К. Рамачандрана (Распределенное кодирование источника с использованием синдромов). [7] Они сжимают данные двоичного блока из одного источника в синдромы и передают данные из другого источника в несжатом виде в качестве дополнительной информации . Этот вид схемы DSC обеспечивает асимметричную степень сжатия для каждого источника и приводит к асимметричному DSC. Эта асимметричная схема DSC может быть легко расширена на случай более чем двух коррелированных источников информации. Существуют также некоторые схемы DSC, в которых используются биты четности, а не биты синдрома.
Корреляция между двумя источниками в DSC была смоделирована как виртуальный канал, который обычно называют двоичным симметричным каналом . [9] [10]
Начиная с DISCUS , DSC привлекла значительную исследовательскую деятельность, и более сложные методы кодирования каналов были приняты в структуры DSC, такие как Turbo Code , LDPC Code и т. Д.
Подобно предыдущей структуре кодирования без потерь, основанной на теореме Слепяна – Вольфа, были предприняты усилия для случаев с потерями, основанных на теореме Винера – Зива. Теоретические результаты по схемам квантователя были предоставлены Р. Замиром и С. Шамаи [11], в то время как различные структуры были предложены на основе этого результата, включая вложенный решетчатый квантователь и квантователь с решетчатым кодом.
Более того, DSC использовался при сжатии видео для приложений, требующих кодирования видео низкой сложности, таких как сенсорные сети, многовидовые видеокамеры и т. Д. [12]
На основе детерминированного и вероятностного обсуждения корреляционной модели двух коррелированных источников информации были разработаны схемы DSC с более общими сжатыми скоростями. [13] [14] [15] В этих неасимметричных схемах оба из двух коррелированных источников сжимаются.
При определенном детерминированном предположении о корреляции между источниками информации X. Cao и M. Kuijper продемонстрировали структуру DSC, в которой любое количество источников информации может быть сжато распределенным образом. [16] Этот метод выполняет неасимметричное сжатие с гибкой скоростью для каждого источника, достигая той же общей скорости сжатия, что и при многократном применении асимметричного DSC для более чем двух источников. Затем, исследуя уникальную связь между синдромами и дополнительными кодовыми словами линейных кодов, они преобразовали основные этапы совместного декодирования DSC в декодирование синдрома с последующим канальным кодированием с помощью линейного блочного кода, а также с помощью его дополнительного кода [17], который теоретически проиллюстрировал способ сборки объединенного декодера DSC из кодеров и декодеров линейного кода.
Теоретические оценки
Теоретический предел сжатия информации без потерь на DSC (граница Слепяна – Вольфа ) был впервые предложен Дэвидом Слепяном и Джеком Кейлом Вольфом в терминах энтропий коррелированных источников информации в 1973 году. [3] Они также показали, что два изолированных источника могут сжимать данные как эффективно, как если бы они общались друг с другом. Эта оценка была распространена на случай более чем двух коррелированных источников Томасом М. Ковером в 1975 г. [4]
Аналогичные результаты были получены в 1976 году Аароном Д. Винером и Якобом Зивом в отношении кодирования с потерями совместных гауссовских источников. [5]
Слепиан – Волк
Распределенное кодирование - это кодирование двух или более зависимых источников с помощью отдельных кодеров и совместного декодера. Учитывая две статистически зависимые случайные последовательности iid X и Y с конечным алфавитом, теорема Слепяна – Вольфа включает теоретическую оценку скорости кодирования без потерь для распределенного кодирования двух источников, как показано ниже: [3]
Если и кодер, и декодер двух источников независимы, самая низкая скорость, которую мы можем достичь для сжатия без потерь, будет а также для а также соответственно, где а также энтропии а также . Однако при совместном декодировании, если для длинных последовательностей принимается исчезающая вероятность ошибки, теорема Слепяна – Вольфа показывает, что может быть достигнута гораздо лучшая степень сжатия. Пока общая ставка а также больше их совместной энтропии и ни один из источников не кодируется со скоростью, превышающей его энтропию, распределенное кодирование может обеспечить сколь угодно малую вероятность ошибки для длинных последовательностей.
Особым случаем распределенного кодирования является сжатие с дополнительной информацией декодера, где источник доступен на стороне декодера, но недоступен на стороне кодера. Это можно рассматривать как условие, при котором уже использовался для кодирования , а мы намерены использовать кодировать . Вся система работает асимметрично (степень сжатия для двух источников асимметрична).
Граница Винера – Зива
Вскоре после того, как была опубликована теорема Слепяна – Вольфа о распределенном сжатии без потерь, было предложено расширение сжатия с потерями с дополнительной информацией декодера в виде теоремы Винера – Зива. [5] Как и в случае без потерь, два статистически зависимых источника идентификаторов а также даны, где доступен на стороне декодера, но недоступен на стороне кодера. Вместо сжатия без потерь в теореме Слепяна – Вольфа в теореме Виннера – Зива рассматривается случай сжатия с потерями.
Теорема Винера – Зива представляет собой достижимую нижнюю границу для скорости передачи данных при данном искажении . Было обнаружено, что для гауссовых источников без памяти и искажения среднеквадратичной ошибки нижняя граница скорости передачи данных остаются неизменными независимо от того, доступна ли дополнительная информация в кодировщике или нет.
Виртуальный канал
Детерминированная модель
Вероятностная модель
Асимметричный DSC против симметричного DSC
Асимметричный DSC означает, что разные битрейты используются при кодировании входных источников, в то время как один и тот же битрейт используется в симметричном DSC. Возьмем, к примеру, схему DSC с двумя источниками. а также два дискретных, равномерно распределенных источника без памяти, которые генерируют набор переменных а также длиной 7 бит и расстояние Хэмминга между а также самое большее. Маршрут Слепяна – Волка для них:
Это означает, что теоретическая оценка а симметричный DSC означает 5 бит для каждого источника. Другие пары с являются асимметричными случаями с различным распределением скорости передачи данных между а также , где , а также , представляют два крайних случая, называемых декодированием с дополнительной информацией.
Практическое кодирование с распределенным исходным кодом
Кодирование Слепяна – Вольфа - распределенное кодирование без потерь
Было понятно, что кодирование Слепяна – Вольфа тесно связано с канальным кодированием в 1974 г. [6], и примерно через 30 лет практическое ЦИВ стало реализовываться с использованием других канальных кодов. Мотивация использования кодов каналов исходит из случая двух источников, корреляция между входными источниками может быть смоделирована как виртуальный канал, который имеет вход в качестве источника. и вывод как источник . В системе DISCUS , предложенной С.С. Прадханом и К. Рамчандраном в 1999 г., реализована DSC с синдромным декодированием , которая работала для асимметричного случая и была расширена до симметричного случая. [7] [8]
Базовая структура DSC на основе синдромов состоит в том, что для каждого источника его входное пространство делится на несколько смежных классов в соответствии с конкретным используемым методом кодирования канала. Каждый вход каждого источника получает выходные данные, указывающие, к какому классу смежности принадлежит вход, и объединенный декодер может декодировать все входы по полученным индексам смежности и зависимости между источниками. При разработке кодов каналов следует учитывать корреляцию между входными источниками.
Группа кодов может использоваться для создания разделов смежных классов [18], таких как решетчатые коды и решеточные коды. Прадхан и Рамчандран разработали правила для построения субкодов для каждого источника и представили результат построений смежных классов на основе решетчатой диаграммы в DSC, который основан на коде свертки и правилах разделения множеств, как в модуляции решетчатой диаграммы , а также в DSC на основе решеточного кода . [7] [8] После этого для асимметричного кодирования был предложен встроенный решетчатый код в качестве улучшения по сравнению с их результатами. [19]
После того, как была предложена система DISCUS, к системе DSC были адаптированы более сложные канальные коды, такие как турбо-код , LDPC- код и итеративный канальный код. Кодеры этих кодов обычно просты и легки в реализации, в то время как декодеры имеют гораздо более высокую вычислительную сложность и могут получить хорошую производительность за счет использования исходной статистики. Со сложными канальными кодами, производительность которых приближается к пропускной способности корреляционного канала, соответствующая система DSC может приблизиться к границе Слепяна – Вольфа.
Хотя большинство исследований было сосредоточено на DSC с двумя зависимыми источниками, кодирование Слепяна – Вольфа было распространено на более чем два случая входных источников, а методы генерации субкодов из одного канального кода были предложены В. Станковичем, А.Д. Ливерисом и т. Д. С учетом конкретных обстоятельств. корреляционные модели. [20]
Общая теорема кодирования Слепяна – Вольфа с синдромами для двух источников
Теорема : любая пара коррелированных равномерно распределенных источников,, с участием , можно сжимать отдельно с парой скоростей такой, что , где а также целые числа, и . Этого можно добиться с помощью двоичный линейный код.
Доказательство : оценка Хэмминга для двоичный линейный код , и у нас есть код Хэмминга, достигающий этой границы, поэтому у нас есть такой двоичный линейный код с участием матрица генератора . Далее мы покажем, как построить синдромное кодирование на основе этого линейного кода.
Позволять а также быть сформированным путем принятия первых ряды из , пока формируется из оставшихся ряды . а также - подкоды кода Хэмминга, порожденные а также соответственно, с а также в качестве их проверочных матриц.
Для пары ввода , кодировщик задается а также . Это означает, что мы можем представить а также в виде , , где являются представителями смежных классов в отношении к соответственно. Поскольку у нас есть с участием . Мы можем получить, где , .
Предположим, есть две разные входные пары с одинаковыми синдромами, это означает, что есть две разные строки. , такое что а также . Таким образом, у нас будет. Поскольку минимальный вес Хэмминга кода является , расстояние между а также является . С другой стороны, согласно вместе с а также , Мы будем иметь а также , что противоречит . Следовательно, у нас не может быть более одной входной пары с одинаковыми синдромами.
Следовательно, мы можем успешно сжать два зависимых источника с помощью построенных субкодов из двоичный линейный код с парой скоростей такой, что , где а также целые числа, и . Журнал указывает Журнал 2 .
Пример кодирования Слепяна – Вольфа
Возьмите тот же пример, что и в предыдущей части Асимметричный DSC и Симметричный DSC , в этой части представлены соответствующие схемы DSC с кодами смежного класса и синдромами, включая асимметричный случай и симметричный случай. Граница Слепяна – Вольфа для расчета DSC показана в предыдущей части.
Асимметричный корпус
В случае, когда а также , длина входной переменной из источника составляет 7 бит, поэтому он может быть отправлен без потерь с 7 битами, независимо от любых других бит. Основываясь на знании того, что а также иметь расстояние Хэмминга не более одного, для ввода из источника , поскольку у получателя уже есть , единственно возможное находятся на расстоянии не более 1 от . Если мы смоделируем корреляцию между двумя источниками как виртуальный канал, который имеет вход и вывод , пока мы получаем , все, что нам нужно для успешного «декодирования» это «биты четности» с определенной способностью исправления ошибок, принимая разницу между а также как ошибка канала. Мы также можем смоделировать проблему с разбиением смежных классов. То есть мы хотим найти код канала, который может разделить пространство ввода.на несколько смежных классов, где каждый смежный класс имеет связанный с ним уникальный синдром. С заданным классом смежности и, здесь только один это может быть входом, учитывая корреляцию между двумя источниками.
В этом примере мы можем использовать двоичный код Хэмминга , с матрицей проверки на четность . Для входа из источника , только синдром, заданный передается, что составляет 3 бита. С полученным а также , предположим, есть два входа а также с таким же синдромом . Это означает, который . Поскольку минимальный вес Хэмминга Код Хэмминга равен 3, . Следовательно, вход можно восстановить, так как .
Аналогично распределение битов с , может быть достигнуто путем изменения ролей а также .
Симметричный случай
В симметричном случае нам нужен равный битрейт для двух источников: по 5 бит каждый с отдельным кодером и совместным декодером. Мы по-прежнему используем линейные коды для этой системы, как мы использовали для несимметричного случая. Основная идея аналогична, но в этом случае нам нужно выполнить разделение смежных классов для обоих источников, в то время как для пары полученных синдромов (соответствует одному смежному классу) возможна только одна пара входных переменных с учетом корреляции между двумя источниками.
Предположим, у нас есть пара линейных кодов а также и пара кодер-декодер на основе линейных кодов, которые могут обеспечивать симметричное кодирование. Выходной сигнал энкодера определяется следующим образом: а также . Если существует две пары допустимых входов а также генерируя те же синдромы, т. е. а также , мы можем получить следующее ( представляет собой вес Хэмминга):
, где
, где
Таким образом:
где а также . Это означает, что если минимальное расстояние между двумя кодами больше, чем, мы можем добиться безошибочного декодирования.
Два кода а также могут быть построены как подкоды Код Хэмминга и, следовательно, имеет минимальное расстояние . Учитывая порождающую матрицу исходного кода Хэмминга порождающая матрица для строится путем взятия любых двух строк из , а также строится оставшимися двумя рядами . Соответствующие Матрица проверки на четность для каждого субкода может быть сгенерирована в соответствии с образующей матрицей и использована для генерации битов синдрома.
Кодирование Винера – Зива - распределенное кодирование с потерями
В общем, схема кодирования Виннера – Зива получается путем добавления квантователя и деквантизатора к схеме кодирования Слепяна – Вольфа. Следовательно, дизайн кодера Винера – Зива может быть сосредоточен на квантователе и соответствующем методе реконструкции. Было предложено несколько схем квантования, таких как квантователь с вложенной решеткой, [21] квантователь решетчатого кода [22] и метод квантования Ллойда. [23]
Распределенное квантование в большом масштабе
К сожалению, вышеупомянутые подходы не масштабируются (по требованиям к конструкции или сложности эксплуатации) для сенсорных сетей большого размера, сценарий, в котором распределенное сжатие является наиболее полезным. Если есть N источников, передающих по R бит каждый (с некоторой схемой распределенного кодирования), количество возможных реконструкций масштабируется. Даже для умеренных значений N и R (скажем, N = 10, R = 2) предыдущие схемы проектирования становятся непрактичными. Недавно был предложен подход [24], использующий идеи, заимствованные из Fusion Coding of Correlated Sources, где конструктивная и операционная сложность противопоставляется производительности декодера. Это позволило разработать распределенный квантователь для сетей размером до 60 источников с существенным преимуществом по сравнению с традиционными подходами.
Основная идея заключается в наличии селектора подмножества битов, который поддерживает определенное подмножество полученных (биты NR в приведенном выше примере) бит для каждого источника. Позволять быть набором всех подмножеств битов NR, т.е.
Затем мы определяем отображение селектора подмножества битов как
Обратите внимание, что каждый выбор селектора подмножества битов налагает требование хранения (C), которое экспоненциально зависит от мощности набора выбранных битов.
Это позволяет разумно выбирать биты, которые минимизируют искажение, учитывая ограничения на хранение декодера. По-прежнему необходимы дополнительные ограничения на набор допустимых подмножеств. Функция эффективных затрат, которую необходимо минимизировать, представляет собой взвешенную сумму искажений и памяти декодера.
Проектирование системы выполняется путем итеративной (и постепенной) оптимизации кодеров, декодера и селектора битовых подмножеств до сходимости.
Неасимметричный ДСК
Неасимметричный DSC для более чем двух источников
Синдромный подход можно использовать более чем для двух источников. Рассмотреть возможность бинарные источники длины- . Позволять - соответствующие матрицы кодирования размеров . Затем входные двоичные источники сжимаются в всего биты. Очевидно, два исходных кортежа не могут быть восстановлены одновременно, если они имеют один и тот же синдром. Другими словами, если все интересующие исходные кортежи имеют разные синдромы, то их можно восстановить без потерь.
Общетеоретического результата, похоже, не существует. Однако для ограниченного типа источника, так называемого источника Хэмминга [25], который имеет не более одного источника, отличного от остальных, и не более одного местоположения бита, не все идентичные, в некоторых случаях показано практическое использование ЦИВ без потерь. Для случая, когда имеется более двух источников, количество исходных кортежей в источнике Хэмминга равно. Следовательно, упаковка ограничивала, чтоочевидно, должен удовлетворять. Когда граница упаковки удовлетворяется равенству, мы можем назвать такой код идеальным (аналог совершенного кода в коде с исправлением ошибок). [25]
Самый простой набор для выполнения оценки упаковки с равенством . Однако оказывается, что такого кода синдрома не существует. [26] Самый простой (идеальный) код синдрома с более чем двумя источниками имеет а также . Позволять
, а также такой, что любой раздел .
может сжимать источник Хэмминга (т. е. источники, которые отличаются не более чем на один бит, будут иметь разные синдромы). [25] Например, для симметричного случая возможный набор матриц кодирования:
Смотрите также
- Линейный код
- Расшифровка синдрома
- Код проверки на четность с низкой плотностью
- Турбо-код
Рекомендации
- ^ "Распределенное исходное кодирование для сенсорных сетей" З. Сюн, А. Д. Ливерис и С. Ченг
- ^ "Распределенное кодирование видео в беспроводных сенсорных сетях" Пури, Р. Маджумдар, А. Ишвар, П. Рамчандран, К.
- ^ a b c "Бесшумное кодирование коррелированных источников информации" Д. Слепяна и Дж. Вольфа
- ^ a b «Доказательство теоремы сжатия данных Слепяна и Вольфа для эргодических источников» Т. Ковер
- ^ a b c "Функция" скорость-искажение для кодирования источника с дополнительной информацией в декодере "А. Винера и Дж. Зива.
- ^ a b "Последние результаты в теории Шеннона" А.Д. Виннер
- ^ a b c d "Распределенное исходное кодирование с использованием синдромов (DISCUS): проектирование и создание" С. С. Прадхана и К. Рамчандрана.
- ^ a b c "Распределенное кодирование источника: симметричные скорости и приложения к сенсорным сетям" С.С. Прадхан и К. Рамчандран
- ^ "Распределенные конструкции кода для всей области скорости Слепяна – Вольфа для произвольно коррелированных источников" Шенберг, Д. Рамчандран, К. Прадхан, SS
- ^ "Обобщенные коды смежности для распределенного биннинга" Прадханом, С.С. Рамчандраном, К.
- ^ "Вложенные линейные / решетчатые коды для кодирования Виннера-Зива" Р. Замир и С. Шамай
- ^ "Распределенное кодирование видео" Б. Жирода и др.
- ^ «О дизайне кода для проблемы Слепяна – Вольфа и многотерминальных сетей без потерь» Станкович, В. Ливерис, А.Д. Зиксианг Сюн Георгиадес, CN
- ^ "Общая и оптимальная структура для достижения всего диапазона скоростей для кодирования Слепяна – Вольфа" П. Тан и Дж. Ли
- ^ "Распределенное исходное кодирование с использованием коротких и умеренных кодов LDPC, совместимых со скоростью: весь диапазон скорости Слепяна – Вольфа" Сартипи, М. Фекри, Ф.
- ^ «Структура кодирования с распределенным исходным кодом для нескольких источников» Сяомин Цао и Куиджпер, М.
- ^ [1] «Распределенное исходное кодирование с помощью линейных блочных кодов: общая структура для нескольких источников» Сяомин Цао и Куиджпер, М.
- ^ "Коды смежности. I. Введение и геометрическая классификация" Г.Д. Форни
- ^ "Дизайн решетчатых кодов для исходного кодирования с дополнительной информацией в декодере" X. Ванга и М. Орчарда
- ^ "Дизайн кодов Слепяна – Вольфа путем разделения кодов каналов" В. Станкович, А.Д. Ливерис, З. Сюн и К.Н. Георгиадес
- ^ «Вложенное квантование и кодирование Слепяна – Вольфа: парадигма кодирования Виннера – Зива для источников идентификаторов» З. Сюн, А. Д. Ливерис, С. Ченг и З. Лю
- ^ "Кодирование Виннера-Зива на основе кодов TCQ и LDPC" Янг, С. Ченг, З. Сюн и В. Чжао
- ^ "Дизайн оптимальных квантователей для распределенного кодирования источника" Д. Реболло-Монедеро, Р. Чжан и Б. Гирод
- ^ "К крупномасштабному распределенному кодированию источника" С. Рамасвами, К. Вишванатха, А. Саксена и К. Роуз
- ^ a b c "Коды Хэмминга для множественных источников" Р. Ма и С. Ченг
- ^ "Отсутствие кодов Слепяна-Волка длины 5 из трех источников" С. Ченга и Р. Ма. Архивировано 25 апреля 2012 года в Wayback Machine.