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

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

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

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

Определение

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

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

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

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

Ставка

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

Расстояние

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

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

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

Лемма 1

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

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

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

Следствие

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

Лемма 2

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

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

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

Следствие

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

Кодирование

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

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

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

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

---

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

инициализировать y' как yв то время как в R есть av, смежный с нечетным числом вершин в V(y') если существует i такое, что o(i) > e(i) перевернуть запись я в y' еще неудача

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

---

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

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

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

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

Лемма 3

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

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

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

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

Лемма 4

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

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

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

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

Сложность

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

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

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

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

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

Примечания

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

Рекомендации

1. Сипсер, М.; Спилман, Д.А. (1996). «Расширительные коды». Транзакции IEEE по теории информации . 42 (6): 1710–1722. дои : 10.1109/18.556667.
2. Капальбо, М.; Рейнгольд, О.; Вадхан, С.; Вигдерсон, А. (2002). «Проводники случайности и расширители без потерь постоянной степени». STOC '02 Материалы тридцать четвертого ежегодного симпозиума ACM по теории вычислений . АКМ. стр. 659–668. дои : 10.1145/509907.510003. ISBN 978-1-58113-495-7. S2CID  1918841.
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.