Алгоритм Земора основан на типе расширяющих графов, называемых графом Таннера . Построение кода было впервые предложено Таннером. [3] Коды основаны на двойной обложке. , обычный эспандер , который является двудольным графом. знак равно, где - множество вершин и - множество ребер и знак равно а также знак равно , где а также обозначает множества вершин. Позволятьбыть число вершин в каждой группе, т.е. ,. Набор кромок иметь размер знак равно и каждый край в имеет одну конечную точку в обоих а также . обозначает множество ребер, содержащих .
Предположим, что заказ на , поэтому порядок будет производиться по всем краям для каждого . Пусть конечное поле , и к слову в , пусть подслово слова будет проиндексировано . Обозначим это слово через. Подмножество вершин а также вызывает каждое слово раздел на неперекрывающиеся подслова , где колеблется над элементами . Для построения кода, рассмотрим линейный подкод , который является код, где , размер алфавита . Для любой вершины, позволять быть некоторым порядком вершины рядом с . В этом коде каждый бит связан с ребром из .
Мы можем определить код быть набором двоичных векторов из такое, что для каждой вершины из , это кодовое слово . В этом случае можно рассмотреть частный случай, когда каждое ребро примыкает точно к вершины . Это означает, что а также составляют, соответственно, множество вершин и множество ребер регулярный график .
Назовем код построенный таким образом как код. Для данного графика и заданный код , есть несколько коды, поскольку существуют разные способы упорядочения ребер, инцидентных данной вершине , т.е. . Фактически наш код состоят из всех кодовых слов, таких что для всех . Код линейный в поскольку он генерируется из субкода , что является линейным. Код определяется как для каждого .
На этом рисунке . Он показывает график и код .
В матрице , позволять равно второй по величине собственного значения из матрицы смежности из. Здесь наибольшее собственное значение. Сделаны два важных утверждения:
Утверждение 1
. Позволять - скорость линейного кода, построенного из двудольного графа, чьи разрядные узлы имеют степень и чьи узлы подкода имеют степень . Если единый линейный код с параметрами и оценить связан с каждым из узлов подкода, то .
Доказательство
Позволять - скорость линейного кода, равная Пусть есть узлы подкода в графе. Если степень субкода равна, то код должен иметь цифр, поскольку каждый цифровой узел связан с принадлежащий ребра в графе. Каждый узел подкода вносит свой вклад уравнения к матрице проверки на четность для всего . Эти уравнения не могут быть линейно независимыми. Следовательно,
, Поскольку значение , т. е. разрядным узлом этого двудольного графа является и здесь , мы можем написать как:
Утверждение 2
Если линейный код скорости , длина кода блока , и минимальное относительное расстояние , и если является графом инцидентности вершин ребер - регулярный граф со вторым по величине собственным значением , то код имеет рейтинг не менее и минимальное относительное расстояние не менее .
Доказательство
Позволять быть выведенным из регулярный график . Итак, количество переменных является а количество ограничений равно . Согласно Алону-Чангу, [4] если является подмножеством вершин размера , то количество ребер, содержащихся в подграфе, индуцируется в самое большее .
В результате любой набор переменные будут иметь не менее ограничения как соседи. Таким образом, среднее количество переменных на ограничение составляет:
Так что если , то слово относительного веса , не может быть кодовым словом . Неравенство удовлетворен для . Следовательно, не может иметь ненулевое кодовое слово относительного веса или менее.
В матрице , можно считать, что ограничен от . Для этих значений в котором нечетное простое число, существуют явные конструкции последовательностей - правильные двудольные графы со сколь угодно большим числом вершин такие, что каждый граф в последовательности - граф Рамануджана . Он называется графом Рамануджана, поскольку удовлетворяет неравенству. Некоторые свойства расширения видны на графике как расстояние между собственными значениями а также . Если график является графом Рамануджана, то это выражение станет в конце концов, как становится большим.
Приведенный ниже алгоритм итеративного декодирования чередует вершины а также в и исправляет кодовое слово в а затем переключается на исправление кодового слова в . Здесь ребра, связанные с вершиной на одной стороне графа, не инцидентны другой вершине на этой стороне. На самом деле, не имеет значения, в каком порядке набор узлов а также обрабатываются. Обработка вершин также может выполняться параллельно.
Декодер расшифровывается как декодер для который восстанавливается правильно с любыми кодовыми словами с меньшим, чем ошибки.
Алгоритм декодера
Получено слово:
For to do // is the number of iterations
{ if ( is odd) // Here the algorithm will alternate between its two vertex sets.
else
Iteration : For every , let // Decoding to its nearest codeword.
}
Выход:
Пояснение к алгоритму
С двудольный, множество вершин индуцирует разбиение множества ребер знак равно . Набор вызывает другое разделение, знак равно .
Позволять - полученный вектор, и напомним, что . Первая итерация алгоритма состоит в применении полного декодирования кода, индуцированного для каждого . Это означает, что для замены на каждые, вектор одним из ближайших кодовых слов . Поскольку подмножества ребер не пересекаются для , расшифровка этих подвекторы можно делать параллельно.
Итерация даст новый вектор . Следующая итерация состоит в применении предыдущей процедуры к но с заменен на . Другими словами, он состоит из декодирования всех подвекторов, индуцированных вершинами. В следующих итерациях эти два шага повторяются, поочередно применяя параллельное декодирование к подвекторам, индуцированным вершинами и подвекторам, индуцированным вершинами .
Примечание: [Если а также полный двудольный граф, то код продукта сам с собой, и описанный выше алгоритм сводится к естественному жесткому итеративному декодированию кодов продуктов].
Здесь количество итераций, является . В общем, описанный выше алгоритм может исправить кодовое слово, вес Хэмминга которого не превышает для ценностей . Здесь алгоритм декодирования реализован в виде схемы размером и глубина который возвращает кодовое слово, если вес вектора ошибки меньше, чем .
Теорема
Если является графом Рамануджана достаточно высокой степени для любого , алгоритм декодирования может исправить ошибки, в раундов (где большая- обозначение скрывает зависимость от ). Это может быть реализовано за линейное время на одном процессоре; на процессоров каждый цикл может быть реализован в постоянное время.
Доказательство
Поскольку алгоритм декодирования нечувствителен к значению ребер и линейности, мы можем предположить, что переданное кодовое слово является вектором всех нулей. Пусть полученное кодовое слово будет. Учитывается набор ребер, имеющий неверное значение при декодировании. Здесь под неверным значением мы подразумеваемв любой из бит. Позволять быть начальным значением кодового слова, быть значениями после первого, второго. . .этапы декодирования. Здесь,, а также . Здесь соответствует тому набору вершин, который не смог успешно декодировать свое кодовое слово в круглый. Из приведенного выше алгоритмаколичество неудачных вершин будет корректироваться на каждой итерации. Мы можем доказать, что- убывающая последовательность. По факту,. Как мы предполагаем,, приведенное выше уравнение находится в геометрической убывающей последовательности . Так когда, больше, чем раунды необходимы. Более того,, и если мы реализуем круглый в time, то общее время последовательной работы будет линейным.