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

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

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

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

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

Определение

Рассмотрим двудольный граф ${ Displaystyle G (L, R, E) ,}$ , куда ${ Displaystyle L ,}$ и ${ Displaystyle R ,}$ - множества вершин и ${ displaystyle E ,}$ множество ребер, соединяющих вершины в ${ Displaystyle L ,}$ в вершины ${ Displaystyle R ,}$ . Предположим, что каждая вершина в ${ Displaystyle L ,}$ имеет степень ${ displaystyle d ,}$ (график ${ displaystyle d ,}$ -оставили-обычный ), ${ Displaystyle | L | = п ,}$ , и ${ Displaystyle | R | = м ,}$ , ${ Displaystyle м <п ,}$ . потом ${ Displaystyle G ,}$ это ${ Displaystyle (п, м, d, гамма, альфа) ,}$ график расширения, если каждое достаточно маленькое подмножество ${ Displaystyle S подмножество L ,}$ , ${ Displaystyle | S | Leq гамма п ,}$ имеет свойство, что ${ Displaystyle S ,}$ имеет по крайней мере ${ Displaystyle д альфа | S | ,}$ отдельные соседи в ${ Displaystyle R ,}$ . Заметим, что это тривиально выполняется для ${ Displaystyle гамма leq { tfrac {1} {п}} ,}$ . Когда ${ Displaystyle { tfrac {1} {п}} < гамма Leq 1 ,}$ и ${ Displaystyle альфа = 1- varepsilon ,}$ для постоянного ${ Displaystyle varepsilon ,}$ мы говорим, что ${ Displaystyle G ,}$ расширитель без потерь.

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

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

Ставка

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

Расстояние

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

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

Обратите внимание, что мы можем рассматривать каждое кодовое слово ${ displaystyle c ,}$ в ${ Displaystyle C ,}$ как подмножество вершин ${ Displaystyle S подмножество L ,}$ , говоря, что вершина ${ displaystyle v_ {i} in S ,}$ если и только если ${ Displaystyle я ,}$ -й индекс кодового слова равен 1. Тогда ${ displaystyle c ,}$ является кодовым словом тогда и только тогда, когда каждая вершина ${ displaystyle v in R ,}$ смежна с четным числом вершин в ${ Displaystyle S ,}$ . (Чтобы быть кодовым словом, ${ displaystyle cP = 0 ,}$ , куда ${ Displaystyle P ,}$ матрица проверки на четность. Тогда каждая вершина в ${ Displaystyle R ,}$ соответствует каждому столбцу ${ Displaystyle P ,}$ . Умножение матриц завершено ${ Displaystyle { текст {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 подмножество L ,}$ размера ${ Displaystyle | S | Leq гамма п ,}$ , ${ Displaystyle d | S | geq | N (S) | geq | U (S) | geq d (1-2 varepsilon) | S | ,}$ .

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

Тривиально, ${ Displaystyle | N (S) | GEQ | U (S) | ,}$ , поскольку ${ Displaystyle v в U (S) ,}$ подразумевает ${ Displaystyle v в N (S) ,}$ . ${ Displaystyle | N (S) | Leq d | S | ,}$ следует, поскольку степень каждой вершины в ${ Displaystyle S ,}$ является ${ displaystyle d ,}$ . По свойству расширения графа должен быть набор ${ Displaystyle d (1- varepsilon) | S | ,}$ ребра, идущие в разные вершины. Остальные ${ Displaystyle д varepsilon | S | ,}$ края составляют не более ${ Displaystyle д 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 Т подмножество L ,}$ с ${ Displaystyle | Т | <2 (1- varepsilon) гамма п ,}$ есть уникальный сосед.

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

Лемма 1 доказывает случай ${ Displaystyle | Т | Leq гамма п ,}$ , так что предположим ${ Displaystyle 2 (1- varepsilon) gamma n> | T |> gamma n ,}$ . Позволять ${ Displaystyle S подмножество T ,}$ такой, что ${ Displaystyle | S | = гамма п ,}$ . По лемме 1 мы знаем, что ${ Displaystyle | U (S) | geq d (1-2 varepsilon) | S | ,}$ . Тогда вершина ${ Displaystyle v в 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) гамма п ,}$ . С ${ 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 Т подмножество L ,}$ имеет как минимум 1 уникального соседа, т.е. ${ Displaystyle | U (T) |> 0 ,}$ , то соответствующее слово ${ displaystyle c ,}$ соответствующий ${ Displaystyle T ,}$ не может быть кодовым словом, так как оно не будет умножаться на вектор всех нулей на матрицу проверки на четность. Согласно предыдущему аргументу, ${ displaystyle c in C подразумевает wt (c) geq 2 (1- varepsilon) gamma n ,}$ . С ${ Displaystyle C ,}$ линейно, заключаем, что ${ Displaystyle C ,}$ имеет расстояние не менее ${ Displaystyle 2 (1- varepsilon) гамма п ,}$ .

Кодирование

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

Расшифровка

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

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

Вход: получил слово ${ Displaystyle у ,}$ .

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

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

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

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

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

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

Лемма 3.

Если ${ Displaystyle 0$ ~~, то есть ${ displaystyle v_ {i} ,}$ с ${ Displaystyle о (я)> е (я) ,}$ .~~

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

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

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

Лемма 4.

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

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

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

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

Сложность

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

Предварительная обработка: требуется ${ Displaystyle О (г-н) ,}$ время вычислить, каждая ли вершина в ${ Displaystyle R ,}$ имеет нечетное или четное количество соседей.
Предварительная обработка 2: Берем ${ Displaystyle О (дн) = О (дмр) ,}$ время вычислить список вершин ${ displaystyle v_ {i} ,}$ в ${ Displaystyle L ,}$ который имеет ${ Displaystyle о (я)> е (я) ,}$ .
Каждая итерация: мы просто удаляем первый элемент списка. Чтобы обновить список нечетных / четных вершин в ${ Displaystyle R ,}$ , нам нужно только обновить ${ Displaystyle О (д) ,}$ записи, добавляя / удаляя при необходимости. Затем мы обновляем ${ Displaystyle О (др) ,}$ записи в списке вершин в ${ Displaystyle L ,}$ с более нечетными соседями, чем четные, при необходимости добавляя / удаляя. Таким образом, каждая итерация занимает ${ Displaystyle О (др) ,}$ время.
~~Как указывалось выше, общее количество итераций не превышает ${ Displaystyle м ,}$ .~~

Это дает общее время работы ${ Displaystyle О (МДР) = О (п) ,}$ время, где ${ displaystyle d ,}$ и ${ Displaystyle г ,}$ являются константами.

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

График расширителя
Код проверки на четность с низкой плотностью
Линейное временное кодирование и декодирование кодов с исправлением ошибок
Коды ABNNR и AEL
Примечания

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

^ Capalbo, M .; Reingold, O .; Vadhan, S .; Вигдерсон, А. (2002). "Проводники случайности и расширители без потерь постоянной степени". STOC '02 Труды тридцать четвертого ежегодного симпозиума ACM по теории вычислений. ACM. С. 659–668. Дои:10.1145/509907.510003. ISBN 978-1-58113-495-7.
^ Спилман, Д. (1996). «Линейно-временные кодирующие и декодируемые коды с исправлением ошибок». IEEE Transactions по теории информации. 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.

[lossless-1] Capalbo, M .; Reingold, O .; Vadhan, S .; Вигдерсон, А. (2002). "Проводники случайности и расширители без потерь постоянной степени". STOC '02 Труды тридцать четвертого ежегодного симпозиума ACM по теории вычислений. ACM. С. 659–668. Дои:10.1145/509907.510003. ISBN 978-1-58113-495-7.

[spielman-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.

[1]

[2]

[3]