Алгоритм декодирования Земорса - Википедия - Zemors decoding algorithm

В теория кодирования, Алгоритм Земора, разработан и разработан Жилем Земором,^[1] рекурсивный подход к построению кода с низкой сложностью. Это улучшение алгоритма Sipser и Шпильман.

Земор рассматривал типичный класс конструкции Зипсера – Шпильмана коды расширителей, где базовый граф двудольный граф. Сипсер и Спилман представили конструктивное семейство асимптотически хороших кодов линейных ошибок вместе с простым параллельным алгоритмом, который всегда удаляет постоянную долю ошибок. Статья основана на материалах курса доктора Венкатесана Гурусвами. ^[2]

Построение кода

Алгоритм Земора основан на типе графики расширителей называется Граф Таннера. Построение кода впервые было предложено Таннером.^[3] Коды основаны на двойная крышка ${ displaystyle d}$, обычный эспандер ${ displaystyle G}$, который является двудольным графом. ${ displaystyle G}$ =${ Displaystyle влево (V, E вправо)}$, куда ${ displaystyle V}$ - множество вершин и ${ displaystyle E}$ - множество ребер и ${ displaystyle V}$ = ${ displaystyle A}$ ${ Displaystyle чашка}$ ${ displaystyle B}$ и ${ displaystyle A}$ ${ displaystyle cap}$ ${ displaystyle B}$ = ${ displaystyle emptyset}$, куда ${ displaystyle A}$ и ${ displaystyle B}$ обозначает набор из 2-х вершин. Позволять ${ displaystyle n}$ - количество вершин в каждой группе, т.е., ${ Displaystyle | A | = | B | = п}$. Набор кромок ${ displaystyle E}$ иметь размер ${ displaystyle N}$ =${ displaystyle nd}$ и каждый край в ${ displaystyle E}$ имеет одну конечную точку в обоих ${ displaystyle A}$ и ${ displaystyle B}$. ${ Displaystyle E (v)}$ обозначает множество ребер, содержащих ${ displaystyle v}$.

Предположим, заказ на ${ displaystyle V}$, поэтому порядок будет производиться по всем краям ${ Displaystyle E (v)}$ для каждого ${ displaystyle v in V}$. Позволять конечное поле ${ Displaystyle mathbb {F} = GF (2)}$, и к слову ${ displaystyle x = (x_ {e}), e in E}$ в ${ Displaystyle mathbb {F} ^ {N}}$, пусть подслово слова будет проиндексировано ${ Displaystyle E (v)}$. Обозначим это слово через ${ displaystyle (x) _ {v}}$. Подмножество вершин ${ displaystyle A}$ и ${ displaystyle B}$ вызывает каждое слово ${ Displaystyle х in mathbb {F} ^ {N}}$ раздел на ${ displaystyle n}$ неперекрывающиеся подслова ${ Displaystyle влево (х вправо) _ {v} in mathbb {F} ^ {d}}$, куда ${ displaystyle v}$ колеблется над элементами ${ displaystyle A}$. Для построения кода ${ displaystyle C}$, рассмотрим линейный подкод ${ displaystyle C_ {o}}$, который является ${ displaystyle [d, r_ {o} d, delta]}$ код, где ${ displaystyle q}$, размер алфавита ${ displaystyle 2}$. Для любой вершины ${ displaystyle v in V}$, позволять ${ Displaystyle v (1), v (2), ldots, v (d)}$ быть некоторым порядком ${ displaystyle d}$ вершины ${ displaystyle E}$ рядом с ${ displaystyle v}$. В этом коде каждый бит ${ displaystyle x_ {e}}$ связан с ребром ${ displaystyle e}$ из ${ displaystyle E}$.

Мы можем определить код ${ displaystyle C}$ быть набором двоичных векторов ${ displaystyle x = left (x_ {1}, x_ {2}, ldots, x_ {N} right)}$ из ${ Displaystyle {0,1 } ^ {N}}$ такое, что для каждой вершины ${ displaystyle v}$ из ${ displaystyle V}$, ${ Displaystyle влево (x_ {v (1)}, x_ {v (2)}, ldots, x_ {v (d)} right)}$ это кодовое слово ${ displaystyle C_ {o}}$. В этом случае можно рассмотреть частный случай, когда каждое ребро ${ displaystyle E}$ примыкает точно к ${ displaystyle 2}$ вершины ${ displaystyle V}$. Это означает, что ${ displaystyle V}$ и ${ displaystyle E}$ составляют, соответственно, множество вершин и множество ребер ${ displaystyle d}$ регулярный график ${ displaystyle G}$.

Назовем код ${ displaystyle C}$ построенный таким образом как ${ displaystyle left (G, C_ {o} right)}$ код. Для данного графа ${ displaystyle G}$ и заданный код ${ displaystyle C_ {o}}$, есть несколько ${ displaystyle left (G, C_ {o} right)}$ коды, поскольку существуют разные способы упорядочения ребер, инцидентных данной вершине ${ displaystyle v}$, т.е. ${ Displaystyle v (1), v (2), ldots, v (d)}$. Фактически наш код ${ displaystyle C}$ состоят из всех кодовых слов, таких что ${ displaystyle x_ {v} in C_ {o}}$ для всех ${ displaystyle v in A, B}$. Код ${ displaystyle C}$ линейный ${ displaystyle [N, K, D]}$ в ${ Displaystyle mathbb {F}}$ поскольку он генерируется из субкода ${ displaystyle C_ {o}}$, что является линейным. Код ${ displaystyle C}$ определяется как ${ displaystyle C = {c in mathbb {F} ^ {N} :( c) _ {v} in C_ {o} }}$ для каждого ${ displaystyle v in V}$.

График G и код C

На этом рисунке ${ displaystyle (x) _ {v} = left (x_ {e1}, x_ {e2}, x_ {e3}, x_ {e4} right) in C_ {o}}$. Он показывает график ${ displaystyle G}$ и код ${ displaystyle C}$.

В матрице ${ displaystyle G}$, позволять ${ displaystyle lambda}$ равен второму по величине собственное значение из матрица смежности из ${ displaystyle G}$. Здесь наибольшее собственное значение ${ displaystyle d}$. Сделаны два важных утверждения:

Утверждение 1

${ displaystyle left ({ dfrac {K} {N}} right) geq 2r_ {o} -1}$
. Позволять ${ displaystyle R}$ - скорость линейного кода, построенного из двудольного графа, чьи разрядные узлы имеют степень ${ displaystyle m}$ и чьи узлы подкода имеют степень ${ displaystyle n}$. Если единый линейный код с параметрами ${ Displaystyle влево (п, к вправо)}$ и оценить ${ Displaystyle г = влево ({ dfrac {k} {п}} вправо)}$ связан с каждым из узлов подкода, то ${ Displaystyle к GEQ 1- влево (1-р вправо) м}$.

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

Позволять ${ displaystyle R}$ - скорость линейного кода, равная ${ displaystyle K / N}$Пусть есть ${ displaystyle S}$ узлы подкода в графе. Если степень подкода равна ${ displaystyle n}$, то код должен иметь ${ displaystyle left ({ dfrac {n} {m}} right) S}$ цифр, поскольку каждый цифровой узел подключен к ${ displaystyle m}$ из ${ Displaystyle влево (п вправо) S}$ ребра в графе. Каждый узел подкода вносит свой вклад ${ Displaystyle (п-к)}$ уравнения к матрице проверки на четность для всего ${ Displaystyle влево (п-к вправо) S}$. Эти уравнения не могут быть линейно независимыми. Следовательно, ${ displaystyle left ({ dfrac {K} {N}} right) geq left ({ dfrac {({ dfrac {n} {m}}) S- (nk) S} {({ dfrac {n} {m}}) S}} right)}$
${ Displaystyle GEQ 1-м влево ({ dfrac {п-к} {п}} вправо)}$
${ Displaystyle GEQ 1-м влево (1-р вправо)}$, Поскольку значение ${ displaystyle m}$, т. е. разрядным узлом этого двудольного графа является ${ displaystyle 2}$ и тут ${ displaystyle r = r_ {o}}$, мы можем записать как:
${ displaystyle left ({ dfrac {K} {N}} right) geq 2r_ {o} -1}$

Утверждение 2

${ displaystyle D geq N left ({ dfrac {( delta - ({ dfrac { lambda} {d}}))} {(1 - ({ dfrac { lambda} {d}}) }}) right) ^ {2}}$

${ displaystyle = N left ( delta ^ {2} -O left ({ dfrac { lambda} {d}} right) right)}$ ${ displaystyle rightarrow (1)}$

Если ${ displaystyle S}$ линейный код скорости ${ displaystyle r}$, длина кода блока ${ displaystyle d}$, и минимальное относительное расстояние ${ displaystyle delta}$, и если ${ displaystyle B}$ является графом инцидентности вершин ребер ${ displaystyle d}$ - регулярный граф со вторым по величине собственным значением ${ displaystyle lambda}$, то код ${ Displaystyle С (В, S)}$ имеет рейтинг не менее ${ displaystyle 2r_ {o} -1}$ и минимальное относительное расстояние не менее ${ displaystyle left ( left ({ dfrac { delta - left ({ dfrac { lambda} {d}} right)} {1- left ({ dfrac { lambda} {d}) } right)}} right) right) ^ {2}}$.

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

Позволять ${ displaystyle B}$ быть выведенным из ${ displaystyle d}$ регулярный график ${ displaystyle G}$. Итак, количество переменных ${ Displaystyle С (В, S)}$ является ${ displaystyle left ({ dfrac {dn} {2}} right)}$ а количество ограничений равно ${ displaystyle n}$. По словам Алон-Чанга,^[4] если ${ displaystyle X}$ является подмножеством вершин ${ displaystyle G}$ размера ${ displaystyle gamma n}$, то количество ребер, содержащихся в подграфе, индуцируется ${ displaystyle X}$ в ${ displaystyle G}$ самое большее ${ displaystyle left ({ dfrac {dn} {2}} right) left ( gamma ^ {2} + ({ dfrac { lambda} {d}}) gamma left (1- гамма право) право)}$.

В результате любой набор ${ displaystyle left ({ dfrac {dn} {2}} right) left ( gamma ^ {2} + left ({ dfrac { lambda} {d}} right) gamma left (1- gamma right) right)}$ переменные будут иметь не менее ${ displaystyle gamma n}$ ограничения как соседи. Таким образом, среднее количество переменных на ограничение составляет: ${ displaystyle left ({ dfrac {({ dfrac {2nd} {2}}) left ( gamma ^ {2} + ({ dfrac { lambda} {d}}) gamma left ( 1- gamma right) right)} { gamma n}} right)}$${ displaystyle = d left ( gamma + ({ dfrac { lambda} {d}}) left (1- gamma right) right)}$ ${ displaystyle rightarrow (2)}$

Так что если ${ displaystyle d left ( gamma + ({ dfrac { lambda} {d}}) left (1- gamma right) right) < gamma d}$, то слово относительного веса ${ displaystyle left ( gamma ^ {2} + ({ dfrac { lambda} {d}}) gamma left (1- gamma right) right)}$, не может быть кодовым словом ${ Displaystyle С (В, S)}$. Неравенство ${ Displaystyle (2)}$ удовлетворен для ${ displaystyle gamma < left ({ dfrac {1 - ({ dfrac { lambda} {d}})} { delta - ({ dfrac { lambda} {d}})}} right )}$. Следовательно, ${ Displaystyle С (В, S)}$ не может иметь ненулевое кодовое слово относительного веса ${ displaystyle left ({ dfrac { delta - ({ dfrac { lambda} {d}})} {1 - ({ dfrac { lambda} {d}})}} right) ^ { 2}}$ или менее.

В матрице ${ displaystyle G}$, можно считать, что ${ displaystyle lambda / d}$ ограничен от ${ displaystyle 1}$. Для этих значений ${ displaystyle d}$ в котором ${ displaystyle d-1}$ нечетное простое число, существуют явные конструкции последовательностей ${ displaystyle d}$ - правильные двудольные графы со сколь угодно большим числом вершин такие, что каждый граф ${ displaystyle G}$ в последовательности есть График Рамануджана. Он называется графом Рамануджана, поскольку удовлетворяет неравенству ${ displaystyle lambda (G) leq 2 { sqrt {d-1}}}$. Некоторые свойства расширения видны на графике ${ displaystyle G}$ как расстояние между собственными значениями ${ displaystyle d}$ и ${ displaystyle lambda}$. Если график ${ displaystyle G}$ является графом Рамануджана, то это выражение ${ displaystyle (1)}$ станет ${ displaystyle 0}$ в конце концов, как ${ displaystyle d}$ становится большим.

Алгоритм Земора

Алгоритм итеративного декодирования, описанный ниже, чередует вершины ${ displaystyle A}$ и ${ displaystyle B}$ в ${ displaystyle G}$ и исправляет кодовое слово ${ displaystyle C_ {o}}$ в ${ displaystyle A}$ а затем переключается на исправление кодового слова ${ displaystyle C_ {o}}$ в ${ displaystyle B}$. Здесь ребра, связанные с вершиной на одной стороне графа, не инцидентны другой вершине на этой стороне. На самом деле, не имеет значения, в каком порядке набор узлов ${ displaystyle A}$ и ${ displaystyle B}$ обрабатываются. Обработка вершин также может выполняться параллельно.

Декодер ${ displaystyle mathbb {D}: mathbb {F} ^ {d} rightarrow C_ {o}}$расшифровывается как декодер для ${ displaystyle C_ {o}}$ который правильно восстанавливается с любыми кодовыми словами с менее чем ${ displaystyle left ({ dfrac {d} {2}} right)}$ ошибки.

Алгоритм декодера

Получено слово: ${ displaystyle w = (w_ {e}), e in E}$
${ displaystyle z leftarrow w}$
За ${ displaystyle t leftarrow 1}$ к ${ displaystyle m}$ делать //${ displaystyle m}$ это количество итераций
{ если (${ displaystyle t}$ нечетно) // Здесь алгоритм будет чередовать свои два набора вершин.
${ Displaystyle X leftarrow A}$
еще ${ Displaystyle X leftarrow B}$
Итерация ${ displaystyle t}$: Для каждого ${ displaystyle v in X}$, позволять ${ Displaystyle (г) _ {v} leftarrow mathbb {D} ((г) _ {v})}$ // Декодирование ${ displaystyle z_ {v}}$ до ближайшего кодового слова.
}
Выход: ${ displaystyle z}$

Пояснение к алгоритму

С ${ displaystyle G}$ двудольный, множество ${ displaystyle A}$ вершин индуцирует разбиение множества ребер ${ displaystyle E}$ = ${ displaystyle cup _ {v in A} E_ {v}}$ . Набор ${ displaystyle B}$ вызывает другое разделение, ${ displaystyle E}$ = ${ Displaystyle чашка _ {v in B} E_ {v}}$ .

Позволять ${ Displaystyle ш в {0,1 } ^ {N}}$ - полученный вектор, и напомним, что ${ Displaystyle N = dn}$. Первая итерация алгоритма состоит в применении полного декодирования кода, индуцированного ${ displaystyle E_ {v}}$ для каждого ${ displaystyle v in A}$ . Это означает, что для замены на каждые ${ displaystyle v in A}$, вектор ${ Displaystyle влево (w_ {v (1)}, w_ {v (2)}, ldots, w_ {v (d)} right)}$ одним из ближайших кодовых слов ${ displaystyle C_ {o}}$. Поскольку подмножества ребер ${ displaystyle E_ {v}}$ не пересекаются для ${ displaystyle v in A}$, расшифровка этих ${ displaystyle n}$ подвекторы ${ displaystyle w}$ можно делать параллельно.

Итерация даст новый вектор ${ displaystyle z}$. Следующая итерация состоит в применении предыдущей процедуры к ${ displaystyle z}$ но с ${ displaystyle A}$ заменен на ${ displaystyle B}$. Другими словами, он состоит из декодирования всех подвекторов, индуцированных вершинами ${ displaystyle B}$. В следующих итерациях эти два шага повторяются, поочередно применяя параллельное декодирование к подвекторам, индуцированным вершинами ${ displaystyle A}$ и подвекторам, индуцированным вершинами ${ displaystyle B}$.
Примечание: [Если ${ displaystyle d = n}$ и ${ displaystyle G}$ полный двудольный граф, то ${ displaystyle C}$ код продукта ${ displaystyle C_ {o}}$ с самим собой, и приведенный выше алгоритм сводится к естественному жесткому итеративному декодированию кодов продуктов].

Здесь количество итераций, ${ displaystyle m}$ является ${ displaystyle left ({ dfrac {( log {n})} { log (2- alpha)}} right)}$. В общем, описанный выше алгоритм может исправить кодовое слово, вес Хэмминга которого не превышает ${ displaystyle ({ dfrac {1} {2}}). альфа N delta left (({ dfrac { delta} {2}}) - ({ dfrac { lambda} {d}} ) right) = left (({ dfrac {1} {4}}). alpha N ( delta ^ {2} -O ({ dfrac { lambda} {d}}) right)}$ для ценностей ${ Displaystyle альфа <1}$. Здесь алгоритм декодирования реализован в виде схемы размером ${ displaystyle O (N log {N})}$ и глубина ${ Displaystyle О ( журнал {N})}$ который возвращает кодовое слово, если вес вектора ошибки меньше ${ Displaystyle альфа N дельта ^ {2} (1- epsilon) / 4}$ .

Теорема

Если ${ displaystyle G}$ является графом Рамануджана достаточно высокой степени для любого ${ Displaystyle альфа <1}$, алгоритм декодирования может исправить ${ displaystyle ({ dfrac { alpha delta _ {o} ^ {2}} {4}}) (1- дюйм) N}$ ошибки, в ${ Displaystyle О ( журнал {п})}$ раундов (где большой- ${ displaystyle O}$ обозначение скрывает зависимость от ${ displaystyle alpha}$). Это может быть реализовано за линейное время на одном процессоре; на ${ displaystyle n}$ процессоров каждый раунд может быть реализован в постоянное время.

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

Так как алгоритм декодирования нечувствителен к значению ребер и линейности, мы можем предположить, что переданное кодовое слово является вектором всех нулей. Пусть полученное кодовое слово будет ${ displaystyle w}$. Учитывается набор ребер, имеющий неверное значение при декодировании. Здесь под неверным значением мы подразумеваем ${ displaystyle 1}$ в любой из бит. Позволять ${ Displaystyle ш = ш ^ {0}}$ быть начальным значением кодового слова, ${ Displaystyle ш ^ {1}, ш ^ {2}, ldots, ш ^ {т}}$ быть значениями после первого, второго. . . ${ displaystyle t}$ этапы декодирования. Здесь, ${ displaystyle X ^ {i} = {е in E | x_ {e} ^ {i} = 1}}$, и ${ Displaystyle S ^ {я} = {v in V ^ {i} | E_ {v} cap X ^ {i + 1}! = emptyset}}$. Здесь ${ Displaystyle S ^ {я}}$ соответствует тому набору вершин, который не смог успешно декодировать свое кодовое слово в ${ displaystyle i ^ {th}}$ круглый. Из приведенного выше алгоритма ${ Displaystyle S ^ {1}$ количество неуспешных вершин будет корректироваться на каждой итерации. Мы можем доказать, что ${ Displaystyle S ^ {0}> S ^ {1}> S ^ {2}> cdots}$убывающая последовательность. ${ Displaystyle | S_ {я + 1} | <= ({ dfrac {1} {2- alpha}}) | S_ {i} |}$. Как мы предполагаем, ${ Displaystyle альфа <1}$, приведенное выше уравнение находится в геометрическая убывающая последовательность. Так когда ${ displaystyle | S_ {i} |$, больше, чем ${ displaystyle log_ {2- alpha} n}$ раунды необходимы. Более того, ${ Displaystyle сумма | S_ {я} | = п сумма ({ dfrac {1} {(2- альфа) ^ {i}}}) = О (п)}$, и если мы реализуем ${ displaystyle i ^ {th}}$ круглый в ${ Displaystyle O (| S_ {i} |)}$ time, то общее время последовательной работы будет линейным.

Недостатки алгоритма Земора