WikiDer > Распределенное исходное кодирование

Distributed source coding

Распределенное исходное кодирование (DSC) является важной проблемой в теория информации и коммуникация. Проблемы DSC касаются сжатия нескольких коррелированных источников информации, которые не взаимодействуют друг с другом.^[1] Путем моделирования корреляции между несколькими источниками на стороне декодера вместе с коды каналов, DSC может переносить вычислительную сложность со стороны кодера на сторону декодера, поэтому предоставляет соответствующие структуры для приложений с отправителем с ограниченной сложностью, например сенсорные сети и сжатие видео / мультимедиа (см. распределенное кодирование видео^[2]). Одним из основных свойств кодирования с распределенным источником является то, что вычислительная нагрузка в кодерах перекладывается на совместный декодер.

История

В 1973 г. Давид Слепян и Джек Кейл Вольф предложил теоретический предел сжатия информации без потерь при распределенном сжатии двух коррелированных i.i.d. источники X и Y.^[3] После этого эта оценка была расширена на случаи с более чем двумя источниками Томас М. Обложка в 1975 г.^[4] в то время как теоретические результаты в случае сжатия с потерями представлены Аарон Д. Уайнер и Джейкоб Зив в 1976 г.^[5]

Хотя теоремы о DSC были предложены в 1970-х годах, примерно через 30 лет были начаты попытки практических методов, основанных на идее, что DSC тесно связан с кодированием каналов, предложенным в 1974 году. Аарон Д. Уайнер.^[6] Проблема асимметричного DSC была рассмотрена С. С. Прадханом и К. Рамчандраном в 1999 г., которые сосредоточились на статистически зависимых бинарных и гауссовых источниках и использовали скалярные и решетчатые диаграммы. смежный конструкции для решения проблемы.^[7] Они далее расширили работу на симметричный случай DSC.^[8]

Расшифровка синдрома технология была впервые использована в распределенном исходном коде ОБСУЖДЕНИЕ система С.С. Прадхана и К. Рамачандрана (Распределенное исходное кодирование с использованием синдромов).^[7] Они сжимают данные двоичного блока из одного источника в синдромы и передают данные из другого источника без сжатия как дополнительная информация. Такая схема DSC обеспечивает асимметричную степень сжатия для каждого источника и приводит к асимметричный DSC. Эта асимметричная схема DSC может быть легко расширена на случай более чем двух коррелированных источников информации. Есть также некоторые схемы DSC, которые используют биты четности а не синдромные биты.

Корреляция между двумя источниками в DSC была смоделирована как виртуальный канал который обычно называют двоичный симметричный канал.^[9]^[10]

Начиная с ОБСУЖДЕНИЕ, DSC привлекла значительную исследовательскую деятельность, и более сложные методы кодирования каналов были приняты в структуры DSC, такие как Турбо-код, LDPC Код и так далее.

Подобно предыдущей структуре кодирования без потерь, основанной на теореме Слепяна – Вольфа, были предприняты усилия для случаев с потерями, основанных на теореме Винера – Зива. Теоретические результаты по конструкции квантователей были предоставлены Р. Замиром и С. Шамаи,^[11] в то время как различные структуры были предложены на основе этого результата, в том числе вложенный решетчатый квантователь и решетчатый квантователь.

Более того, DSC использовался при сжатии видео для приложений, требующих кодирования видео низкой сложности, таких как сенсорные сети, многовидовые видеокамеры и т. Д.^[12]

На основе детерминированного и вероятностного обсуждения модели корреляции двух коррелированных источников информации были разработаны схемы DSC с более общими сжатыми скоростями.^[13]^[14]^[15] В этих неасимметричный схем, оба из двух коррелированных источников сжимаются.

При определенном детерминированном предположении о корреляции между источниками информации X. Cao и M. Kuijper продемонстрировали структуру DSC, в которой любое количество источников информации может быть сжато распределенным образом.^[16] Этот метод выполняет неасимметричное сжатие с гибкой скоростью для каждого источника, достигая той же общей скорости сжатия, что и при многократном применении асимметричного DSC для более чем двух источников. Затем, исследуя уникальную связь между синдромами и дополнительными кодовыми словами линейных кодов, они преобразовали основные этапы совместного декодирования DSC в декодирование синдрома с последующим канальным кодированием с помощью линейного блочного кода, а также с помощью его дополнительного кода,^[17] который теоретически проиллюстрировал способ сборки объединенного декодера DSC из кодеров и декодеров линейного кода.

Теоретические оценки

Ограничение теоретического сжатия информации без потерь на DSC ( Слепиан – Волк) был впервые задуман Давид Слепян и Джек Кейл Вольф по энтропии коррелированных источников информации в 1973 г.^[3] Они также показали, что два изолированных источника могут сжимать данные так же эффективно, как если бы они общались друг с другом. Эта оценка была расширена на случай более чем двух коррелированных источников Томас М. Обложка в 1975 г.^[4]

Аналогичные результаты были получены в 1976 г. Аарон Д. Уайнер и Джейкоб Зив в отношении кодирования с потерями совместных гауссовских источников.^[5]

Слепиан – Волк

Распределенное кодирование - это кодирование двух или более зависимых источников с помощью отдельных кодеров и совместного декодера. Учитывая два статистически зависимых i.i.d. Случайные последовательности X и Y с конечным алфавитом, теорема Слепяна – Вольфа включает теоретическую границу скорости кодирования без потерь для распределенного кодирования двух источников, как показано ниже:^[3]

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

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

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

Если и кодер, и декодер двух источников независимы, наименьшая скорость, которую мы можем достичь для сжатия без потерь, будет ${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)}$ и ни один из источников не кодируется со скоростью, превышающей его энтропию, распределенное кодирование может обеспечить сколь угодно малую вероятность ошибки для длинных последовательностей.

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

Граница Винера – Зива

Вскоре после того, как была опубликована теорема Слепяна – Вольфа о распределенном сжатии без потерь, было предложено расширение сжатия с потерями с дополнительной информацией декодера в виде теоремы Винера – Зива.^[5] Как и в случае без потерь, два статистически зависимых i.i.d. источники ${displaystyle X}$ и ${displaystyle Y}$ даны, где ${displaystyle Y}$ доступен на стороне декодера, но недоступен на стороне кодера. Вместо сжатия без потерь в теореме Слепяна – Вольфа в теореме Виннера – Зива рассматривается случай сжатия с потерями.

Теорема Винера – Зива представляет собой достижимую нижнюю границу скорости передачи данных ${displaystyle X}$ при данном искажении ${displaystyle D}$ . Было обнаружено, что для гауссовых источников без памяти и искажения среднеквадратической ошибки нижняя граница скорости передачи ${displaystyle X}$ остаются неизменными независимо от того, доступна ли дополнительная информация в кодировщике или нет.

Виртуальный канал

Детерминированный модель

Вероятностный модель

Асимметричный ДСК против симметричного ДСК

Асимметричный DSC означает, что при кодировании входных источников используются разные битрейты, а в симметричном DSC используется один и тот же битрейт. Возьмем, к примеру, схему DSC с двумя источниками. ${displaystyle X}$ и ${displaystyle Y}$ два дискретных, равномерно распределенных источника без памяти, которые генерируют набор переменных ${displaystyle mathbf {x}}$ и ${displaystyle mathbf {y}}$ длиной 7 бит и расстояние Хэмминга между ${displaystyle mathbf {x}}$ и ${displaystyle mathbf {y}}$ самое большее. Путь Слепяна – Волка для них:

{displaystyle R_ {X} + R_ {Y} geq 10}

{displaystyle R_ {X} geq 5}

{displaystyle R_ {Y} geq 5}

Это означает, что теоретическая оценка ${displaystyle R_ {X} + R_ {Y} = 10}$ а симметричный DSC означает 5 бит для каждого источника. Другие пары с ${displaystyle R_ {X} + R_ {Y} = 10}$ являются асимметричными случаями с различным распределением битовой скорости между ${displaystyle X}$ и ${displaystyle Y}$ , куда ${displaystyle R_ {X} = 3}$ , ${displaystyle R_ {Y} = 7}$ и ${displaystyle R_ {Y} = 3}$ , ${displaystyle R_ {X} = 7}$ представляют два крайних случая, называемых декодированием с дополнительной информацией.

Практическое кодирование с распределенным исходным кодом

Кодирование Слепяна – Вольфа - распределенное кодирование без потерь

Было понятно, что Кодирование Слепяна – Вольфа тесно связан с кодированием каналов в 1974 г.,^[6] и примерно через 30 лет практический ЦИВ начал реализовываться с использованием различных канальных кодов. Мотивация использования кодов каналов исходит из случая двух источников, корреляция между входными источниками может быть смоделирована как виртуальный канал, который имеет вход в качестве источника. ${displaystyle X}$ и вывод как источник ${displaystyle Y}$ . В ОБСУЖДЕНИЕ Система, предложенная С.С. Прадханом и К. Рамчандраном в 1999 г., реализовала DSC с расшифровка синдрома, который работал для асимметричного случая и был расширен на симметричный случай.^[7]^[8]

Базовая структура DSC на основе синдромов состоит в том, что для каждого источника его входное пространство делится на несколько смежных классов в соответствии с конкретным используемым методом кодирования канала. Каждый вход каждого источника получает выходные данные, указывающие, к какому классу смежности принадлежит вход, и объединенный декодер может декодировать все входы по полученным индексам смежного класса и зависимости между источниками. При разработке кодов каналов следует учитывать корреляцию между входными источниками.

Группа кодов может использоваться для создания разделов смежных классов,^[18] такие как решетчатые коды и решеточные коды. Прадхан и Рамчандран разработали правила для построения субкодов для каждого источника и представили результат построения смежных классов на основе решеток в DSC, который основан на код свертки и установить правила разделения, как в Модуляция решетки, а также ЦИВ на основе решеточного кода.^[7]^[8] После этого для асимметричного кодирования был предложен встроенный решетчатый код в качестве улучшения их результатов.^[19]

После того, как система DISCUS была предложена, более сложные коды каналов были адаптированы к системе DSC, например Турбо-код, LDPC Код и итеративный код канала. Кодеры этих кодов обычно просты и легки в реализации, в то время как декодеры имеют гораздо более высокую вычислительную сложность и могут получить хорошую производительность за счет использования статистики источника. Со сложными канальными кодами, производительность которых приближается к пропускной способности корреляционного канала, соответствующая система DSC может приблизиться к границе Слепяна – Вольфа.

Хотя большинство исследований было сосредоточено на DSC с двумя зависимыми источниками, кодирование Слепяна – Вольфа было распространено на более чем два случая входных источников, а методы генерации субкодов из одного канального кода были предложены В. Станковичем, А.Д. Ливерисом и др. С учетом конкретных особенностей. корреляционные модели.^[20]

Общая теорема кодирования Слепяна – Вольфа с синдромами для двух источников

Теорема: Любая пара коррелированных равномерно распределенных источников, ${displaystyle X, Инь влево {0,1ight} ^ {n}}$ , с ${displaystyle mathbf {d_ {H}} (X, Y) leq t}$ , можно сжимать отдельно с парой скоростей ${displaystyle (R_ {1}, R_ {2})}$ такой, что ${displaystyle R_ {1}, R_ {2} geq n-k, R_ {1} + R_ {2} geq 2n-k}$ , куда ${displaystyle R_ {1}}$ и ${displaystyle R_ {2}}$ целые числа, и ${displaystyle kleq n-log (sum _ {i = 0} ^ {t} {n choose i})}$ . Этого можно добиться с помощью ${displaystyle (n, k, 2t + 1)}$ двоичный линейный код.

Доказательство: Граница Хэмминга для ${displaystyle (n, k, 2t + 1)}$ двоичный линейный код ${displaystyle kleq n-log (sum _ {i = 0} ^ {t} {n choose i})}$ , и у нас есть код Хэмминга, достигающий этой границы, поэтому у нас есть такой двоичный линейный код ${displaystyle mathbf {C}}$ с ${displaystyle k imes n}$ матрица генератора ${displaystyle mathbf {G}}$ . Далее мы покажем, как построить синдромное кодирование на основе этого линейного кода.

Позволять ${displaystyle R_ {1} + R_ {2} = 2n-k}$ и ${displaystyle mathbf {G_ {1}}}$ формироваться путем принятия первых ${displaystyle (n-R_ {1})}$ ряды из ${displaystyle mathbf {G}}$ , пока ${displaystyle mathbf {G_ {2}}}$ формируется из оставшихся ${displaystyle (n-R_ {2})}$ ряды ${displaystyle mathbf {G}}$ . ${displaystyle mathbf {C_ {1}}}$ и ${displaystyle mathbf {C_ {2}}}$ - подкоды кода Хэмминга, порожденные ${displaystyle mathbf {G_ {1}}}$ и ${displaystyle mathbf {G_ {2}}}$ соответственно, с ${displaystyle mathbf {H_ {1}}}$ и ${displaystyle mathbf {H_ {2}}}$ в качестве их проверочных матриц.

Для пары ввода ${displaystyle mathbf {(x, y)}}$ , кодировщик задается ${displaystyle mathbf {s_ {1}} = mathbf {H_ {1}} mathbf {x}}$ и ${displaystyle mathbf {s_ {2}} = mathbf {H_ {2}} mathbf {y}}$ . Это означает, что мы можем представить ${displaystyle mathbf {x}}$ и ${displaystyle mathbf {y}}$ в качестве ${displaystyle mathbf {x = u_ {1} G_ {1} + c_ {s1}}}$ , ${displaystyle mathbf {y = u_ {2} G_ {2} + c_ {s2}}}$ , куда ${displaystyle mathbf {c_ {s1}, c_ {s2}}}$ являются представителями смежных классов ${displaystyle mathbf {s1, s2}}$ в отношении к ${displaystyle mathbf {C_ {1}, C_ {2}}}$ соответственно. Поскольку у нас есть ${displaystyle mathbf {y = x + e}}$ с ${displaystyle w (mathbf {e}) leq t}$ . Мы можем получить ${displaystyle mathbf {x + y = uG + c_ {s} = e}}$ , куда ${displaystyle mathbf {u = left [u_ {1}, u_ {2} ight]}}$ , ${displaystyle mathbf {c_ {s} = c_ {s1} + c_ {s2}}}$ .

Предположим, есть две разные входные пары с одинаковыми синдромами, это означает, что есть две разные строки ${displaystyle mathbf {u ^ {1}, u ^ {2}} слева {0,1ight} ^ {k}}$ , так что ${displaystyle mathbf {u ^ {1} G + c_ {s} = e}}$ и ${displaystyle mathbf {u ^ {2} G + c_ {s} = e}}$ . Таким образом, у нас будет ${displaystyle mathbf {(u ^ {1} -u ^ {2}) G = 0}}$ . Поскольку минимальный вес Хэмминга кода ${displaystyle mathbf {C}}$ является ${displaystyle 2t + 1}$ , расстояние между ${displaystyle mathbf {u_ {1} G}}$ и ${displaystyle mathbf {u_ {2} G}}$ является ${displaystyle geq 2t + 1}$ . С другой стороны, согласно ${displaystyle w (mathbf {e}) leq t}$ вместе с ${displaystyle mathbf {u ^ {1} G + c_ {s} = e}}$ и ${displaystyle mathbf {u ^ {2} G + c_ {s} = e}}$ , у нас будет ${displaystyle d_ {H} (mathbf {u ^ {1} G, c_ {s}}) leq t}$ и ${displaystyle d_ {H} (mathbf {u ^ {2} G, c_ {s}}) leq t}$ , что противоречит ${displaystyle d_ {H} (mathbf {u ^ {1} G, u ^ {2} G}) geq 2t + 1}$ . Следовательно, у нас не может быть более одной входной пары с одинаковыми синдромами.

Следовательно, мы можем успешно сжать два зависимых источника с помощью построенных субкодов из ${displaystyle (n, k, 2t + 1)}$ двоичный линейный код с парой скоростей ${displaystyle (R_ {1}, R_ {2})}$ такой, что ${displaystyle R_ {1}, R_ {2} geq n-k, R_ {1} + R_ {2} geq 2n-k}$ , куда ${displaystyle R_ {1}}$ и ${displaystyle R_ {2}}$ целые числа, и ${displaystyle kleq n-log (sum _ {i = 0} ^ {t} {n choose i})}$ . Бревно указывает Бревно₂.

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

Возьмите тот же пример, что и в предыдущем Асимметричный DSC против симметричного DSC В этой части представлены соответствующие схемы DSC с кодами смежных классов и синдромами, включая асимметричный случай и симметричный случай. Граница Слепяна – Вольфа для расчета DSC показана в предыдущей части.

Асимметричный корпус

В случае, когда ${displaystyle R_ {X} = 3}$ и ${displaystyle R_ {Y} = 7}$ , длина входной переменной ${displaystyle mathbf {y}}$ из источника ${displaystyle Y}$ составляет 7 бит, поэтому его можно отправлять без потерь с 7 битами, независимо от любых других бит. Основываясь на знании того, что ${displaystyle mathbf {x}}$ и ${displaystyle mathbf {y}}$ иметь расстояние Хэмминга не больше единицы, для ввода ${displaystyle mathbf {x}}$ из источника ${displaystyle X}$ , поскольку у получателя уже есть ${displaystyle mathbf {y}}$ , единственно возможное ${displaystyle mathbf {x}}$ находятся на расстоянии не более 1 от ${displaystyle mathbf {y}}$ . Если мы смоделируем корреляцию между двумя источниками как виртуальный канал, который имеет вход ${displaystyle mathbf {x}}$ и вывод ${displaystyle mathbf {y}}$ , пока мы получаем ${displaystyle mathbf {y}}$ , все, что нам нужно для успешного «декодирования» ${displaystyle mathbf {x}}$ это «биты четности» с определенной способностью исправления ошибок, принимая разницу между ${displaystyle mathbf {x}}$ и ${displaystyle mathbf {y}}$ как ошибка канала. Мы также можем смоделировать проблему с разбиением смежных классов. То есть мы хотим найти код канала, который может разделить пространство ввода ${displaystyle X}$ на несколько смежных классов, где каждый смежный класс имеет связанный с ним уникальный синдром. С заданным классом смежности и ${displaystyle mathbf {y}}$ , здесь только один ${displaystyle mathbf {x}}$ это может быть входом, учитывая корреляцию между двумя источниками.

В этом примере мы можем использовать ${displaystyle (7,4,3)}$ двоичный Код Хэмминга ${displaystyle mathbf {C}}$ , с матрицей проверки на четность ${displaystyle mathbf {H}}$ . Для входа ${displaystyle mathbf {x}}$ из источника ${displaystyle X}$ , только синдром, заданный ${displaystyle mathbf {s} = mathbf {H} mathbf {x}}$ передается, что составляет 3 бита. С полученным ${displaystyle mathbf {y}}$ и ${displaystyle mathbf {s}}$ , предположим, есть два входа ${displaystyle mathbf {x_ {1}}}$ и ${displaystyle mathbf {x_ {2}}}$ с таким же синдромом ${displaystyle mathbf {s}}$ . Это означает ${displaystyle mathbf {H} mathbf {x_ {1}} = mathbf {H} mathbf {x_ {2}}}$ , который ${displaystyle mathbf {H} (mathbf {x_ {1}} -mathbf {x_ {2}}) = 0}$ . Поскольку минимальный вес Хэмминга ${displaystyle (7,4,3)}$ Код Хэмминга равен 3, ${displaystyle d_ {H} (mathbf {x_ {1}}, mathbf {x_ {2}}) geq 3}$ . Следовательно, вход ${displaystyle mathbf {x}}$ можно восстановить, так как ${displaystyle d_ {H} (mathbf {x}, mathbf {y}) leq 1}$ .

Аналогично распределение битов с ${displaystyle R_ {X} = 7}$ , ${displaystyle R_ {Y} = 3}$ можно добиться, поменяв роли ${displaystyle X}$ и ${displaystyle Y}$ .

Симметричный случай

В симметричном случае нам нужен равный битрейт для двух источников: по 5 бит каждый с отдельным кодером и совместным декодером. Мы по-прежнему используем линейные коды для этой системы, как мы использовали для несимметричного случая. Основная идея аналогична, но в этом случае нам нужно выполнить разделение смежных классов для обоих источников, в то время как для пары полученных синдромов (соответствует одному смежному классу) возможна только одна пара входных переменных с учетом корреляции между двумя источниками.

Предположим, у нас есть пара линейный код ${displaystyle mathbf {C_ {1}}}$ и ${displaystyle mathbf {C_ {2}}}$ и пара кодер-декодер, основанная на линейных кодах, которые могут обеспечивать симметричное кодирование. Выход энкодера определяется следующим образом: ${displaystyle mathbf {s_ {1}} = mathbf {H_ {1}} mathbf {x}}$ и ${displaystyle mathbf {s_ {2}} = mathbf {H_ {2}} mathbf {y}}$ . Если существует две пары допустимых входов ${displaystyle mathbf {x_ {1}}, mathbf {y_ {1}}}$ и ${displaystyle mathbf {x_ {2}}, mathbf {y_ {2}}}$ генерируя одни и те же синдромы, т.е. ${displaystyle mathbf {H_ {1}} mathbf {x_ {1}} = mathbf {H_ {1}} mathbf {x_ {2}}}$ и ${displaystyle mathbf {H_ {1}} mathbf {y_ {1}} = mathbf {H_ {1}} mathbf {y_ {2}}}$ , мы можем получить следующие ( ${displaystyle w ()}$ представляет собой вес Хэмминга):

${displaystyle mathbf {y_ {1}} = mathbf {x_ {1}} + mathbf {e_ {1}}}$ , куда ${displaystyle w (mathbf {e_ {1}}) leq 1}$

${displaystyle mathbf {y_ {2}} = mathbf {x_ {2}} + mathbf {e_ {2}}}$ , куда ${displaystyle w (mathbf {e_ {2}}) leq 1}$

Таким образом: ${displaystyle mathbf {x_ {1}} + mathbf {x_ {2}} в mathbf {C_ {1}}}$

${displaystyle mathbf {y_ {1}} + mathbf {y_ {2}} = mathbf {x_ {1}} + mathbf {x_ {2}} + mathbf {e_ {3}} в mathbf {C_ {2}}}$

куда ${displaystyle mathbf {e_ {3}} = mathbf {e_ {2}} + mathbf {e_ {1}}}$ и ${displaystyle w (mathbf {e_ {3}}) leq 2}$ . Это означает, что если минимальное расстояние между двумя кодами больше, чем ${displaystyle 3}$ , мы можем добиться безошибочного декодирования.

Два кода ${displaystyle mathbf {C_ {1}}}$ и ${displaystyle mathbf {C_ {2}}}$ могут быть построены как подкоды ${displaystyle (7,4,3)}$ Код Хэмминга и, следовательно, имеет минимальное расстояние ${displaystyle 3}$ . Учитывая матрица генератора ${displaystyle mathbf {G}}$ исходного кода Хэмминга порождающая матрица ${displaystyle mathbf {G_ {1}}}$ за ${displaystyle mathbf {C_ {1}}}$ строится путем взятия любых двух строк из ${displaystyle mathbf {G}}$ , и ${displaystyle mathbf {G_ {2}}}$ строится оставшимися двумя рядами ${displaystyle mathbf {G}}$ . Соответствующие ${displaystyle (5 раз 7)}$ матрица проверки на четность для каждого субкода может быть сгенерирован согласно матрице генератора и использован для генерации битов синдрома.

Кодирование Винера – Зива - распределенное кодирование с потерями

В общем, схема кодирования Виннера – Зива получается путем добавления квантователя и деквантизатора к схеме кодирования Слепяна – Вольфа. Следовательно, при разработке кодера Винера-Зива можно было бы сосредоточить внимание на квантователе и соответствующем методе реконструкции. Было предложено несколько конструкций квантователей, таких как квантователь с вложенной решеткой,^[21] квантователь решетчатого кода^[22] и метод квантования Ллойда.^[23]

Распределенное квантование в большом масштабе

К сожалению, вышеупомянутые подходы не масштабируются (по требованиям к конструкции или сложности эксплуатации) для сенсорных сетей больших размеров, сценарий, в котором распределенное сжатие является наиболее полезным. Если есть N источников, передающих по R бит каждый (с некоторой схемой распределенного кодирования), количество возможных реконструкций масштабируется ${displaystyle 2 ^ {NR}}$ . Даже для умеренных значений N и R (например, N = 10, R = 2) предыдущие схемы проектирования становятся непрактичными. В последнее время подход,^[24] с использованием идей, заимствованных из Fusion Coding of Correlated Sources, было предложено, где конструктивная и операционная сложность противопоставляется производительности декодера. Это позволило разработать распределенный квантователь для сетей размером до 60 источников со значительным преимуществом по сравнению с традиционными подходами.

Основная идея заключается в наличии селектора подмножества битов, который поддерживает определенное подмножество принятых (биты NR в приведенном выше примере) бит для каждого источника. Позволять ${displaystyle {mathcal {B}}}$ быть набором всех подмножеств битов NR, т.е.

{displaystyle {mathcal {B}} = 2 ^ {{1, ..., NR}}}

Затем мы определяем отображение селектора подмножества битов как

{displaystyle {mathcal {S}}: {1, ..., N} ightarrow {mathcal {B}}}

Обратите внимание, что каждый выбор селектора подмножества битов налагает требование хранения (C), которое экспоненциально зависит от мощности набора выбранных битов.

{displaystyle C = sum _ {n = 1} ^ {N} 2 ^ {| {mathcal {S}} (n) |}}

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

{displaystyle J = D + lambda C}

Проектирование системы выполняется путем итеративной (и постепенной) оптимизации кодеров, декодера и селектора битовых подмножеств до сходимости.

Неасимметричный ДСК

Неасимметричный DSC для более чем двух источников

Синдромный подход все еще можно использовать более чем для двух источников. Учитывать ${displaystyle a}$ бинарные источники длины- ${displaystyle n}$ ${displaystyle mathbf {x} _ {1}, mathbf {x} _ {2}, cdots, mathbf {x} _ {a} in {0,1} ^ {n}}$ . Позволять ${displaystyle mathbf {H} _ {1}, mathbf {H} _ {2}, cdots, mathbf {H} _ {s}}$ - соответствующие матрицы кодирования размеров ${displaystyle m_ {1} imes n, m_ {2} imes n, cdots, m_ {a} imes n}$ . Затем входные двоичные источники сжимаются в ${displaystyle mathbf {s} _ {1} = mathbf {H} _ {1} mathbf {x} _ {1}, mathbf {s} _ {2} = mathbf {H} _ {2} mathbf {x} _ {2}, cdots, mathbf {s} _ {a} = mathbf {H} _ {a} mathbf {x} _ {a}}$ всего ${displaystyle m = m_ {1} + m_ {2} + cdots m_ {a}}$ биты. По-видимому, два исходных кортежа не могут быть восстановлены одновременно, если они имеют один и тот же синдром. Другими словами, если все интересующие исходные кортежи имеют разные синдромы, то их можно восстановить без потерь.

Общетеоретического результата, похоже, не существует. Однако для ограниченного типа источника так называемого источника Хэмминга ^[25] который имеет не более одного источника, отличного от остальных, и не более одного местоположения бита, не все идентичные, практическое использование DSC без потерь, как показано, существует в некоторых случаях. Для случая, когда имеется более двух источников, количество исходных кортежей в источнике Хэмминга равно ${displaystyle 2 ^ {n} (an + 1)}$ . Следовательно, упаковка ограничивает, что ${displaystyle 2 ^ {m} geq 2 ^ {n} (an + 1)}$ очевидно должен удовлетворять. Когда граница упаковки удовлетворяется равенству, мы можем назвать такой код идеальным (аналог совершенного кода в коде с исправлением ошибок).^[25]

Самый простой набор ${displaystyle a, n, m}$ для выполнения оценки упаковки с равенством ${displaystyle a = 3, n = 5, m = 9}$ . Однако оказывается, что такого кода синдрома не существует.^[26] Самый простой (идеальный) код синдрома с более чем двумя источниками имеет ${displaystyle n = 21}$ и ${displaystyle m = 27}$ . Позволять

${displaystyle mathbf {Q} _ {1} = {egin {pmatrix} 1; 0; 0; 0; 0; 0; 1; 0; 0; 0; 0; 1; 1; 1; 0; 1; 1; 0; 0; 0; 0 0; 1; 0; 0; 0; 0; 1; 1; 0; 0; 0; 0; 1; 0; 0; 0; 0; 0; 1; 1; 1 0; 0; 1; 0; 0; 0; 0; 1; 1; 0; 0; 0; 0; 1; 1; 1; 0; 1; 0; 1; 1 0; 0; 0; 1; 0; 0; 0; 0; 1; 1; 0; 0; 0; 1; 0; 0; 1; 1; 1; 1; 0 0; 0; 0; 0; 1; 0; 0; 0; 0; 1; 1; 0; 1; 0; 1; 1; 0; 1; 1; 1; 1 0; 0; 0; 0; 0; 1; 0; 0; 0; 0; 1; 1; 0; 0; 1; 0; 0; 1; 1; 0; 1end {pmatrix}},}$ ${displaystyle mathbf {Q} _ {2} = {egin {pmatrix} 0; 0; 0; 1; 0; 1; 1; 0; 1; 1; 1; 1; 0; 1; 0; 0; 0; 1; 1; 1; 1 1; 0; 0; 0; 1; 0; 1; 1; 0; 1; 1; 1; 1; 0; 1; 1; 1; 1; 0; 0; 0 0; 1; 0; 0; 0; 1; 1; 1; 1; 0; 1; 1; 1; 0; 0; 0; 0; 0; 1; 0; 1 1; 0; 1; 0; 0; 0; 1; 1; 1; 1; 0; 1; 0; 1; 1; 1; 0; 0; 1; 1; 1 0; 1; 0; 1; 0; 0; 1; 1; 1; 1; 1; 0; 0; 0; 1; 0; 1; 1; 0; 1; 1 0; 0; 1; 0; 1; 0; 0; 1; 1; 1; 1; 1; 1; 1; 0; 1; 0; 1; 1; 1; 0end {pmatrix}},}$ ${displaystyle mathbf {Q} _ {3} = {egin {pmatrix} 1; 0; 0; 1; 0; 1; 0; 0; 1; 1; 1; 0; 1; 0; 0; 1; 1; 1; 1; 1; 1 1; 1; 0; 0; 1; 0; 0; 0; 0; 1; 1; 1; 0; 0; 1; 1; 1; 1; 1; 1; 1 0; 1; 1; 0; 0; 1; 1; 0; 0; 0; 1; 1; 1; 1; 1; 1; 0; 1; 1; 1; 0 1; 0; 1; 1; 0; 0; 1; 1; 0; 0; 0; 1; 0; 0; 1; 1; 1; 1; 0; 0; 1 0; 1; 0; 1; 1; 0; 1; 1; 1; 0; 0; 0; 1; 0; 0; 1; 1; 0; 1; 0; 0 0; 0; 1; 0; 1; 1; 0; 1; 1; 1; 0; 0; 1; 1; 1; 1; 0; 0; 0; 1; 1end {pmatrix}},}$ ${displaystyle mathbf {G} = [mathbf {0} | mathbf {I} _ {9}]}$ ,и ${displaystyle mathbf {G} = {egin {pmatrix} mathbf {G} _ {1} mathbf {G} _ {2} mathbf {G} _ {3} end {pmatrix}}}$ такой, что ${displaystyle mathbf {G} _ {1}, mathbf {G} _ {2}, mathbf {G} _ {3}}$ любой раздел ${displaystyle mathbf {G}}$ .

${displaystyle mathbf {H} _ {1} = {egin {pmatrix} mathbf {G} _ {1} mathbf {Q} _ {1} end {pmatrix}}, mathbf {H} _ {2} = {начало {pmatrix} mathbf {G} _ {2} mathbf {Q} _ {2} end {pmatrix}}, mathbf {H} _ {3} = {egin {pmatrix} mathbf {G} _ {3} mathbf {Q} _ {3} конец {pmatrix}}}$ может сжимать источник Хэмминга (то есть источники, которые отличаются не более чем на один бит, будут иметь разные синдромы).^[25] Например, для симметричного случая возможный набор матриц кодирования: ${displaystyle mathbf {H} _ {1} = {egin {pmatrix} 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 1; 0; 0 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 1; 0 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 1 1; 0; 0; 0; 0; 0; 1; 0; 0; 0; 0; 1; 1; 1; 0; 1; 1; 0; 0; 0; 0 0; 1; 0; 0; 0; 0; 1; 1; 0; 0; 0; 0; 1; 0; 0; 0; 0; 0; 1; 1; 1 0; 0; 1; 0; 0; 0; 0; 1; 1; 0; 0; 0; 0; 1; 1; 1; 0; 1; 0; 1; 1 0; 0; 0; 1; 0; 0; 0; 0; 1; 1; 0; 0; 0; 1; 0; 0; 1; 1; 1; 1; 0 0; 0; 0; 0; 1; 0; 0; 0; 0; 1; 1; 0; 1; 0; 1; 1; 0; 1; 1; 1; 1 0; 0; 0; 0; 0; 1; 0; 0; 0; 0; 1; 1; 0; 0; 1; 0; 0; 1; 1; 0; 1end {pmatrix}},}$ ${displaystyle mathbf {H} _ {2} = {egin {pmatrix} 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 1; 0; 0; 0; 0; 0 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 1; 0; 0; 0; 0 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 1; 0; 0; 0 0; 0; 0; 1; 0; 1; 1; 0; 1; 1; 1; 1; 0; 1; 0; 0; 0; 1; 1; 1; 1 1; 0; 0; 0; 1; 0; 1; 1; 0; 1; 1; 1; 1; 0; 1; 1; 1; 1; 0; 0; 0 0; 1; 0; 0; 0; 1; 1; 1; 1; 0; 1; 1; 1; 0; 0; 0; 0; 0; 1; 0; 1 1; 0; 1; 0; 0; 0; 1; 1; 1; 1; 0; 1; 0; 1; 1; 1; 0; 0; 1; 1; 1 0; 1; 0; 1; 0; 0; 1; 1; 1; 1; 1; 0; 0; 0; 1; 0; 1; 1; 0; 1; 1 0; 0; 1; 0; 1; 0; 0; 1; 1; 1; 1; 1; 1; 1; 0; 1; 0; 1; 1; 1; 0end {pmatrix}},}$ ${displaystyle mathbf {H} _ {3} = {egin {pmatrix} 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 1; 0; 0; 0; 0; 0; 0; 0; 0 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 1; 0; 0; 0; 0; 0; 0; 0 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 1; 0; 0; 0; 0; 0; 0 1; 0; 0; 1; 0; 1; 0; 0; 1; 1; 1; 0; 1; 0; 0; 1; 1; 1; 1; 1; 1 1; 1; 0; 0; 1; 0; 0; 0; 0; 1; 1; 1; 0; 0; 1; 1; 1; 1; 1; 1; 1 0; 1; 1; 0; 0; 1; 1; 0; 0; 0; 1; 1; 1; 1; 1; 1; 0; 1; 1; 1; 0 1; 0; 1; 1; 0; 0; 1; 1; 0; 0; 0; 1; 0; 0; 1; 1; 1; 1; 0; 0; 1 0; 1; 0; 1; 1; 0; 1; 1; 1; 0; 0; 0; 1; 0; 0; 1; 1; 0; 1; 0; 0 0; 0; 1; 0; 1; 1; 0; 1; 1; 1; 0; 0; 1; 1; 1; 1; 0; 0; 0; 1; 1end {pmatrix}}.}$

Navigation