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

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

История

В 1973 году Дэвид Слепиан и Джек Кейл Вольф предложили теоретическое сжатие информации без потерь, основанное на распределенном сжатии двух коррелированных источников iid X и Y. После этого эта граница была распространена на случаи с более чем двумя источниками Томасом М. Ковером в 1975 году: в то время как теоретические результаты в случае сжатия с потерями представлены Аароном Д. Винером и Джейкобом Зивом в 1976 году.

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

Технология синдромного декодирования была впервые использована в распределенном кодировании исходного кода системой DISCUS С.С. Прадхана и К. Рамачандрана (Кодирование с распределенным исходным кодом с использованием синдромов). Они сжимают данные двоичного блока из одного источника в синдромы и передают данные из другого источника в несжатом виде в качестве дополнительной информации . Этот тип схемы DSC обеспечивает асимметричную степень сжатия на источник и приводит к асимметричному DSC. Эту асимметричную схему DSC можно легко расширить на случай более чем двух коррелированных источников информации. Существуют также некоторые схемы DSC, в которых используются биты четности вместо битов синдрома .

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

Начиная с DISCUS , DSC привлек значительную исследовательскую деятельность, и более сложные методы кодирования каналов были внедрены в структуры DSC, такие как Turbo Code , LDPC Code и так далее.

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

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

На основе детерминистических и вероятностных обсуждений корреляционной модели двух коррелированных источников информации были разработаны схемы DSC с более общими сжатыми показателями. В этих неасимметричных схемах оба двух коррелированных источника сжаты.

При определенном детерминированном предположении о корреляции между источниками информации X. Цао и М. Куйпер продемонстрировали структуру DSC, в которой любое количество источников информации может быть сжато распределенным образом. Этот метод выполняет неасимметричное сжатие с гибкими скоростями для каждого источника, достигая той же общей скорости сжатия, что и многократное применение асимметричного DSC для более чем двух источников. Затем, исследуя уникальную связь между синдромами и дополнительными кодовыми словами линейных кодов, они перевели основные этапы совместного декодирования DSC в синдромное декодирование с последующим канальным кодированием через линейный блочный код, а также через его дополнительный код. где теоретически проиллюстрирован метод сборки совместного декодера DSC из кодеров и декодеров линейного кода.

Теоретические границы

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

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

Слепян-Вольф

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

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

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

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

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

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

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

Вскоре после того, как была опубликована теорема Слепиана-Вольфа о распределенном сжатии без потерь, расширение сжатия с потерями с использованием дополнительной информации декодера было предложено как теорема Винера-Зива. Как и в случае без потерь, два статистически зависимых источника iid $X$ и $Y$ даны, где $Y$ доступен на стороне декодера, но недоступен на стороне кодера. Вместо сжатия без потерь в теореме Слепиана-Вольфа теорема Винера-Зива рассматривала случай сжатия с потерями.

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

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

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

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

Асимметричный DSC против симметричного DSC

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

$R_{X}+R_{Y}\geq 10$

$R_{X}\geq 5$

$R_{Y}\geq 5$

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

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

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

В 1974 году стало понятно, что кодирование Слепяна-Вольфа тесно связано с канальным кодированием. и примерно через 30 лет на практике DSC начал реализовываться с использованием различных кодов каналов. Мотивация использования канальных кодов связана со случаем двух источников: корреляция между источниками входных данных может быть смоделирована как виртуальный канал, который имеет входные данные в качестве источника. $X$ и вывести как источник $Y$. Система DISCUS, предложенная С. С. Прадханом и К. Рамчандраном в 1999 году, реализовала DSC с синдромным декодированием , которое работало для асимметричного случая и в дальнейшем было расширено до симметричного случая.

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

Группа кодов может использоваться для создания разделов смежных классов, такие как решетчатые коды и решетчатые коды. Прадхан и Рамчандран разработали правила построения субкодов для каждого источника и представили результат построения смежных классов на основе решетчатого кода в DSC, который основан на сверточном коде и правилах разделения множеств, как в решетчатой ​​модуляции , а также DSC на основе решетчатого кода. . После этого для асимметричного кодирования был предложен встроенный решетчатый код как улучшение их результатов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$\mathbf {y_{1}} =\mathbf {x_{1}} +\mathbf {e_{1}}$, где $w(\mathbf {e_{1}} )\leq 1$

$\mathbf {y_{2}} =\mathbf {x_{2}} +\mathbf {e_{2}}$, где $w(\mathbf {e_{2}} )\leq 1$

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

$\mathbf {y_{1}} +\mathbf {y_{2}} =\mathbf {x_{1}} +\mathbf {x_{2}} +\mathbf {e_{3}} \in \mathbf {C_{2}}$

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

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

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

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

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

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

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

${\mathcal {B}}=2^{\{1,...,NR\}}$

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

${\mathcal {S}}:\{1,...,N\}\rightarrow {\mathcal {B}}$

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

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

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

$J=D+\lambda C$

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

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

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

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

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

$\mathbf {Q} _{1}={\begin{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\;1\end{pmatrix}},$$\mathbf {Q} _{2}={\begin{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\;0\end{pmatrix}},$$\mathbf {Q} _{3}={\begin{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\;1\end{pmatrix}},$$\mathbf {G} =[\mathbf {0} |\mathbf {I} _{9}]$,и $\mathbf {G} ={\begin{pmatrix}\mathbf {G} _{1}\\\mathbf {G} _{2}\\\mathbf {G} _{3}\end{pmatrix}}$такой, что $\mathbf {G} _{1},\mathbf {G} _{2},\mathbf {G} _{3}$ являются ли какие-либо разделы $\mathbf {G}$.

$\mathbf {H} _{1}={\begin{pmatrix}\mathbf {G} _{1}\\\mathbf {Q} _{1}\end{pmatrix}},\mathbf {H} _{2}={\begin{pmatrix}\mathbf {G} _{2}\\\mathbf {Q} _{2}\end{pmatrix}},\mathbf {H} _{3}={\begin{pmatrix}\mathbf {G} _{3}\\\mathbf {Q} _{3}\end{pmatrix}}$ может сжимать источник Хэмминга (т. е. источники, которые отличаются не более чем на один бит, будут иметь разные синдромы). Например, для симметричного случая возможный набор матриц кодирования: $\mathbf {H} _{1}={\begin{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\;1\end{pmatrix}},$$\mathbf {H} _{2}={\begin{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\;0\end{pmatrix}},$$\mathbf {H} _{3}={\begin{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\;1\end{pmatrix}}.$

См. также

• Линейный код
• Расшифровка синдрома
• Код проверки четности низкой плотности
• Турбо-код