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

Коды расширителей
двудольный расширительный граф
Классификация
Тип	Линейный блочный код
Длина блока	${\displaystyle n}$
Длина сообщения	${\displaystyle n-m}$
Ставка	${\displaystyle 1-m/n}$
Расстояние	${\displaystyle 2(1-\epsilon )\gamma \cdot n}$
Размер алфавита	${\displaystyle 2}$
Обозначение	${\displaystyle [n,n-m,2(1-\epsilon )\gamma \cdot n]_{2}}$-код

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

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

В теория кодирования, код расширителя - это ${\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 G(L,R,E)\,}$, куда ${\displaystyle L\,}$ и ${\displaystyle R\,}$ - множества вершин и ${\displaystyle E\,}$ множество ребер, соединяющих вершины в ${\displaystyle L\,}$ в вершины ${\displaystyle R\,}$. Предположим, что каждая вершина в ${\displaystyle L\,}$ имеет степень ${\displaystyle d\,}$ (график ${\displaystyle d\,}$-оставили-обычный ), ${\displaystyle |L|=n\,}$, и ${\displaystyle |R|=m\,}$, ${\displaystyle m<n\,}$. потом ${\displaystyle G\,}$ это ${\displaystyle (n,m,d,\gamma ,\alpha )\,}$ график расширения, если каждое достаточно маленькое подмножество ${\displaystyle S\subset L\,}$, ${\displaystyle |S|\leq \gamma n\,}$ имеет свойство, что ${\displaystyle S\,}$ имеет по крайней мере ${\displaystyle d\alpha |S|\,}$ отдельные соседи в ${\displaystyle R\,}$. Заметим, что это тривиально выполняется для ${\displaystyle \gamma \leq {\tfrac {1}{n}}\,}$. Когда ${\displaystyle {\tfrac {1}{n}}<\gamma \leq 1\,}$ и ${\displaystyle \alpha =1-\varepsilon \,}$ для постоянного ${\displaystyle \varepsilon \,}$мы говорим, что ${\displaystyle G\,}$ расширитель без потерь.

С ${\displaystyle G\,}$ является двудольным графом, мы можем рассматривать его ${\displaystyle n\times m\,}$ матрица смежности. Тогда линейный код ${\displaystyle C\,}$ генерируемый просмотром транспонирования этой матрицы, поскольку матрица проверки на четность является кодом расширителя.

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

Ставка

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

Расстояние

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

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

Обратите внимание, что мы можем рассматривать каждое кодовое слово ${\displaystyle c\,}$ в ${\displaystyle C\,}$ как подмножество вершин ${\displaystyle S\subset L\,}$, говоря, что вершина ${\displaystyle v_{i}\in S\,}$ если и только если ${\displaystyle i\,}$-й индекс кодового слова равен 1. Тогда ${\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 доказывает случай ${\displaystyle |T|\leq \gamma n\,}$, так что предположим ${\displaystyle 2(1-\varepsilon )\gamma n>|T|>\gamma n\,}$. Позволять ${\displaystyle S\subset T\,}$ такой, что ${\displaystyle |S|=\gamma n\,}$. По лемме 1 мы знаем, что ${\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\,}$, поэтому по первой части леммы 1 мы знаем ${\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)\,}$ не пусто.

Следствие

Обратите внимание, что если ${\displaystyle T\subset L\,}$ имеет как минимум 1 уникального соседа, т.е. ${\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\,}$.

Кодирование

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

Расшифровка

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

Позволять ${\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, пока есть v в R рядом с нечетным числом вершин в V (y'), если существует i такое, что o (i)> e (i) перевернуть запись i в y 'иначе не получится

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

---

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

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

Правильность

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

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

Когда мы переворачиваем вершину ${\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\,}$ ошибок, то по лемме 1 было бы не менее ${\displaystyle d\gamma (1-2\varepsilon )n\,}$ уникальных соседей, а значит, будет не менее ${\displaystyle d\gamma (1-2\varepsilon )n\,}$ неудовлетворенные вершины, противоречие.

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

Примечания

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

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

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