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

Эта статья может потребовать очистки, чтобы соответствовать стандартам качества Википедии . Конкретная проблема заключается в следующем: отсутствуют определения, а грамматика требует серьезного редактирования текста. Слепое указание на ссылки не должно быть целью статьи. Отсутствует научная экспозиция. Пожалуйста, помогите улучшить эту статью, если можете. ( Июль 2012 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

Коды расширителей [ править ]

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

Определение [ править ]

Рассмотрим двудольный граф , где и - множества вершин, а - множество ребер, соединяющих вершины в с вершинами . Предположим , что каждая вершина имеет степень (граф -left- регулярный ), и , . Тогда это экспандер , если каждое достаточно небольшого подмножества , обладает тем свойством , что имеет , по меньшей мере , отдельные сосед . Обратите внимание, что это тривиально выполняется для . Когда и для константы , мы говорим, что это расширитель без потерь.${\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\,}$

Доказательство [ править ]

Обратите внимание, что мы можем рассматривать каждое кодовое слово в как подмножество вершин , говоря, что вершина тогда и только тогда, когда индекс -й индекс кодового слова равен 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)\,}$

Следствие [ править ]

Обратите внимание , что если имеет , по меньшей мере , 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\,}$

Кодировка [ править ]

Время кодирования для кода расширителя ограничено сверху временем кодирования общего линейного кода - умножением матриц. Результат Спилмана показывает, что кодирование возможно во времени. ^[2]${\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'\,}$

Доказательство [ править ]

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

Правильность [ править ]

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

Заметки [ править ]

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

Ссылки [ править ]