Код расширителя

Коды расширителя
Коды расширителя
	двудольный расширительный граф
Классификация
Тип	Линейный блочный код
Длина блока
Длина сообщения
Ставка
Расстояние
Размер алфавита
Обозначения	-код
	v ; т ; и ;

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

Коды расширителя

В теории кодирования расширительный код — это $[n,n-m]_{2}\,$ линейный блочный код , матрица проверки четности которого является матрицей смежности двудольного графа-расширителя . Эти коды имеют хорошее относительное расстояние $2(1-\varepsilon )\gamma \,$ , где $\varepsilon \,$ и $\gamma \,$ являются свойствами графа расширения, как определено позже, скорость $\left(1-{\tfrac {m}{n}}\right)\,$ и декодируемость (алгоритмы времени выполнения $O(n)\,$ существовать).

Определение

Позволять $B$ быть $(c,d)$ - бирегулярный граф между множеством $n$ узлы $\{v_{1},\cdots ,v_{n}\}$ , называемые переменными , и набор $cn/d$ узлы $\{C_{1},\cdots ,C_{cn/d}\}$ , называемые ограничениями .

Позволять $b(i,j)$ быть функцией, спроектированной так, что для каждого ограничения $C_{i}$ , переменные, соседние $C_{i}$ являются $v_{b(i,1)},\cdots ,v_{b(i,d)}$ .

Позволять ${\mathcal {S}}$ быть кодом, исправляющим ошибки, длиной блока $d$ . Код расширителя ${\mathcal {C}}(B,{\mathcal {S}})$ это код длины блока $n$ чьи кодовые слова являются словами $(x_{1},\cdots ,x_{n})$ такой, что для $1\leq i\leq cn/d$ , $(x_{b(i,1)},\cdots ,x_{b(i,d)})$ является кодовым словом ${\mathcal {S}}$ . ^[1]

Было показано, что существуют нетривиальные графы-расширители без потерь. Более того, мы можем их явно сконструировать. ^[2]

Ставка

Скорость $C\,$ — это его размерность, деленная на длину блока. В этом случае матрица проверки четности имеет размер $m\times n\,$ , и, следовательно, $C\,$ имеет ставку как минимум $(n-m)/n=1-m/n\,$ .

Расстояние

Предполагать $\varepsilon <{\tfrac {1}{2}}\,$ . Тогда расстояние а $(n,m,d,\gamma ,1-\varepsilon )\,$ код расширения $C\,$ по крайней мере $2(1-\varepsilon )\gamma n\,$ .

Доказательство

Обратите внимание, что мы можем рассмотреть каждое кодовое слово $c\,$ в $C\,$ как подмножество вершин $S\subset L\,$ , говоря, что вершина $v_{i}\in S\,$ тогда и только тогда, когда $i\,$ индекс кодового слова равен 1. Тогда $c\,$ является кодовым словом тогда и только тогда, когда каждая вершина $v\in R\,$ смежно с четным числом вершин в $S\,$ . (Чтобы быть кодовым словом, $cP=0\,$ , где $P\,$ — матрица проверки четности. Тогда каждая вершина в $R\,$ соответствует каждому столбцу $P\,$ . Умножение матрицы ${\text{GF}}(2)=\{0,1\}\,$ то дает желаемый результат.) Итак, если вершина $v\in R\,$ смежна с одной вершиной в $S\,$ , мы сразу знаем, что $c\,$ не является кодовым словом. Позволять $N(S)\,$ обозначаем соседей по $R\,$ из $S\,$ , и $U(S)\,$ обозначим тех соседей $S\,$ которые уникальны, т. е. смежны с одной вершиной $S\,$ .

Лемма 1

Для каждого $S\subset L\,$ размера $|S|\leq \gamma n\,$ , $d|S|\geq |N(S)|\geq |U(S)|\geq d(1-2\varepsilon )|S|\,$ .

Доказательство

Тривиально, $|N(S)|\geq |U(S)|\,$ , с $v\in U(S)\,$ подразумевает $v\in N(S)\,$ . $|N(S)|\leq d|S|\,$ следует, поскольку степень каждой вершины в $S\,$ является $d\,$ . По свойству расширения графа должно существовать множество $d(1-\varepsilon )|S|\,$ ребра, ведущие в различные вершины. Остальные $d\varepsilon |S|\,$ края составляют максимум $d\varepsilon |S|\,$ соседи не уникальные, поэтому $U(S)\geq d(1-\varepsilon )|S|-d\varepsilon |S|=d(1-2\varepsilon )|S|\,$ .

Следствие

Каждый достаточно малый $S\,$ имеет единственного соседа. Это следует из того, что $\varepsilon <{\tfrac {1}{2}}\,$ .

Лемма 2

Каждое подмножество $T\subset L\,$ с $|T|<2(1-\varepsilon )\gamma n\,$ имеет единственного соседа.

Доказательство

Лемма 1 доказывает справедливость $|T|\leq \gamma n\,$ , так что предположим $2(1-\varepsilon )\gamma n>|T|>\gamma n\,$ . Позволять $S\subset T\,$ такой, что $|S|=\gamma n\,$ . По лемме 1 мы знаем, что $|U(S)|\geq d(1-2\varepsilon )|S|\,$ . Тогда вершина $v\in U(S)\,$ находится в $U(T)\,$ если только $v\notin N(T\setminus S)\,$ , и мы это знаем $|T\setminus S|\leq 2(1-\varepsilon )\gamma n-\gamma n=(1-2\varepsilon )\gamma n\,$ , поэтому по первой части леммы 1 мы знаем $|N(T\setminus S)|\leq d(1-2\varepsilon )\gamma n\,$ . С $\varepsilon <{\tfrac {1}{2}}\,$ , $|U(T)|\geq |U(S)\setminus N(T\setminus S)|\geq |U(S)|-|N(T\setminus S)|>0\,$ , и, следовательно, $U(T)\,$ не пуст.

Следствие

Обратите внимание, что если $T\subset L\,$ имеет хотя бы 1 уникального соседа, т.е. $|U(T)|>0\,$ , то соответствующее слово $c\,$ соответствующий $T\,$ не может быть кодовым словом, поскольку оно не будет умножать вектор всех нулей на матрицу проверки четности. Согласно предыдущему аргументу, $c\in C\implies wt(c)\geq 2(1-\varepsilon )\gamma n\,$ . С $C\,$ линейно, заключаем, что $C\,$ имеет расстояние как минимум $2(1-\varepsilon )\gamma n\,$ .

Кодирование

Время кодирования расширительного кода ограничено сверху временем кодирования общего линейного кода - $O(n^{2})\,$ путем матричного умножения. Результат Спилмана показывает, что кодирование возможно в $O(n)\,$ время. ^[3]

Декодирование

Расшифровка кодов расширителей возможна в $O(n)\,$ время, когда $\varepsilon <{\tfrac {1}{4}}\,$ используя следующий алгоритм.

Позволять $v_{i}\,$ быть вершиной $L\,$ что соответствует $i\,$ индекс в кодовых словах $C\,$ . Позволять $y\in \{0,1\}^{n}\,$ быть принятым словом, и $V(y)=\{v_{i}\mid {\text{the }}i^{\text{th}}{\text{ position of }}y{\text{ is a }}1\}\,$ . Позволять $e(i)\,$ быть $|\{v\in R\mid v_{i}\in N(v){\text{ and }}N(v)\cap V(y){\text{ is even}}\}|\,$ , и $o(i)\,$ быть $|\{v\in R\mid v_{i}\in N(v){\text{ and }}N(v)\cap V(y){\text{ is odd}}\}|\,$ . Затем рассмотрим жадный алгоритм:

Ввод: полученное слово $y\,$ .

initialize y' to y
while there is a v in R adjacent to an odd number of vertices in V(y')
    if there is an i such that o(i) > e(i)
        flip entry i in y'
    else
        fail

Вывод: ошибка или измененное кодовое слово. $y'\,$ .

Доказательство

Сначала мы покажем корректность алгоритма, а затем проверим время его работы.

Корректность

Мы должны показать, что алгоритм завершается с использованием правильного кодового слова, когда полученное кодовое слово находится на расстоянии половины кода от исходного кодового слова. Пусть набор поврежденных переменных будет $S\,$ , $s=|S|\,$ , и множество неудовлетворенных (соседних с нечётным числом вершин) вершин в $R\,$ быть $c\,$ . Следующая лемма окажется полезной.

Лемма 3

Если $0<s<\gamma n\,$ , то есть $v_{i}\,$ с $o(i)>e(i)\,$ .

Доказательство

По лемме 1 мы знаем, что $U(S)\geq d(1-2\varepsilon )s\,$ . Таким образом, средняя вершина имеет по крайней мере $d(1-2\varepsilon )>d/2\,$ уникальные соседи (напомним, что уникальные соседи неудовлетворены и, следовательно, способствуют $o(i)\,$ ), с $\varepsilon <{\tfrac {1}{4}}\,$ , и, следовательно, существует вершина $v_{i}\,$ с $o(i)>e(i)\,$ .

Итак, если мы еще не достигли кодового слова, то всегда будет какая-то вершина, которую можно перевернуть. Далее мы покажем, что количество ошибок никогда не может превысить $\gamma n\,$ .

Лемма 4

Если мы начнем с $s<\gamma (1-2\varepsilon )n\,$ , то мы никогда не достигнем $s=\gamma n\,$ в любой точке алгоритма.

Доказательство

Когда мы переворачиваем вершину $v_{i}\,$ , $o(i)\,$ и $e(i)\,$ меняются местами, и поскольку у нас было $o(i)>e(i)\,$ , это означает, что количество неудовлетворенных вершин справа уменьшается как минимум на одну после каждого переворота. С $s<\gamma (1-2\varepsilon )n\,$ , начальное число неудовлетворенных вершин не более $d\gamma (1-2\varepsilon )n\,$ , по графику $d\,$ -регулярность. Если бы мы достигли строки с $\gamma n\,$ ошибок, то по лемме 1 будет как минимум $d\gamma (1-2\varepsilon )n\,$ уникальные соседи, а это значит, что будет как минимум $d\gamma (1-2\varepsilon )n\,$ неудовлетворенные вершины — противоречие.

Леммы 3 и 4 показывают нам, что если мы начнем с $s<\gamma (1-2\varepsilon )n\,$ (половина расстояния $C\,$ ), то мы всегда найдем вершину $v_{i}\,$ перевернуть. Каждый переворот уменьшает количество неудовлетворенных вершин в $R\,$ не менее чем на 1, и, следовательно, алгоритм завершается не более чем через $m\,$ шагов и завершается на некотором кодовом слове по лемме 3. (Если бы не кодовое слово, была бы какая-то вершина, которую можно было бы перевернуть). Лемма 4 показывает нам, что мы никогда не сможем оказаться дальше, чем $\gamma n\,$ от правильного кодового слова. Поскольку код имеет расстояние $2(1-\varepsilon )\gamma n>\gamma n\,$ (с $\varepsilon <{\tfrac {1}{2}}\,$ ), кодовое слово, на котором оно заканчивается, должно быть правильным кодовым словом, поскольку количество переворотов битов меньше половины расстояния (поэтому мы не могли пройти достаточно далеко, чтобы добраться до любого другого кодового слова).

Сложность

Теперь мы покажем, что алгоритм может обеспечить декодирование с линейным временем. Позволять ${\tfrac {n}{m}}\,$ быть постоянным, и $r\,$ быть максимальной степенью любой вершины в $R\,$ . Обратите внимание, что $r\,$ также постоянна для известных конструкций.

Предварительная обработка: требуется $O(mr)\,$ время вычислить, каждая ли вершина в $R\,$ имеет нечетное или четное число соседей.
Предварительная обработка 2: Берем $O(dn)=O(dmr)\,$ время вычислить список вершин $v_{i}\,$ в $L\,$ которые имеют $o(i)>e(i)\,$ .
Каждая итерация: мы просто удаляем первый элемент списка. Чтобы обновить список нечетных/четных вершин в $R\,$ , нам нужно только обновить $O(d)\,$ записи, вставка/удаление по мере необходимости. Затем мы обновляем $O(dr)\,$ записи в списке вершин в $L\,$ с более нечетными, чем четными соседями, вставка/удаление по мере необходимости. Таким образом, каждая итерация занимает $O(dr)\,$ время.
Как утверждалось выше, общее число итераций не превышает $m\,$ .

Это дает общее время работы $O(mdr)=O(n)\,$ время, где $d\,$ и $r\,$ являются константами.

См. также

Расширяемый график
Код проверки четности низкой плотности
Линейное время кодирования и декодирования кодов, исправляющих ошибки.
Коды ABNNR и AEL

Примечания

Эта статья основана на конспектах курса доктора Венкатесана Гурусвами. ^[4]

Ссылки

^ Сипсер, М.; Спилман, Д.А. (1996). «Расширительные коды». Транзакции IEEE по теории информации . 42 (6): 1710–1722. дои : 10.1109/18.556667 .
^ Капальбо, М.; Рейнгольд, О.; Вадхан, С.; Вигдерсон, А. (2002). «Проводники случайности и расширители без потерь постоянной степени» . STOC '02 Материалы тридцать четвертого ежегодного симпозиума ACM по теории вычислений . АКМ. стр. 659–668. дои : 10.1145/509907.510003 . ISBN 978-1-58113-495-7 . S2CID 1918841 .
^ Спилман, Д. (1996). «Кодируемые с линейным временем и декодируемые коды с исправлением ошибок». Транзакции IEEE по теории информации . 42 (6): 1723–31. CiteSeerX 10.1.1.47.2736 . дои : 10.1109/18.556668 .
^ Гурусвами, В. (15 ноября 2006 г.). «Лекция 13: Коды расширителя» (PDF) . CSE 533: Исправление ошибок . Университет Вашингтона.
Гурусвами, В. (март 2010 г.). «Примечания 8: Коды расширителя и их декодирование» (PDF) . Введение в теорию кодирования . Университет Карнеги-Меллон.
Гурусвами, В. (сентябрь 2004 г.). «Гостевая колонка: коды, исправляющие ошибки, и графы-расширители» . Новости ACM SIGACT . 35 (3): 25–41. дои : 10.1145/1027914.1027924 . S2CID 17550280 .

[definition-1] Сипсер, М.; Спилман, Д.А. (1996). «Расширительные коды». Транзакции IEEE по теории информации . 42 (6): 1710–1722. дои : 10.1109/18.556667 .

[lossless-2] Капальбо, М.; Рейнгольд, О.; Вадхан, С.; Вигдерсон, А. (2002). «Проводники случайности и расширители без потерь постоянной степени» . STOC '02 Материалы тридцать четвертого ежегодного симпозиума ACM по теории вычислений . АКМ. стр. 659–668. дои : 10.1145/509907.510003 . ISBN 978-1-58113-495-7 . S2CID 1918841 .

[spielman-3] Спилман, Д. (1996). «Кодируемые с линейным временем и декодируемые коды с исправлением ошибок». Транзакции IEEE по теории информации . 42 (6): 1723–31. CiteSeerX 10.1.1.47.2736 . дои : 10.1109/18.556668 .

[4] Гурусвами, В. (15 ноября 2006 г.). «Лекция 13: Коды расширителя» (PDF) . CSE 533: Исправление ошибок . Университет Вашингтона.
Гурусвами, В. (март 2010 г.). «Примечания 8: Коды расширителя и их декодирование» (PDF) . Введение в теорию кодирования . Университет Карнеги-Меллон.
Гурусвами, В. (сентябрь 2004 г.). «Гостевая колонка: коды, исправляющие ошибки, и графы-расширители» . Новости ACM SIGACT . 35 (3): 25–41. дои : 10.1145/1027914.1027924 . S2CID 17550280 .

[1]

[2]

[3]

[4]