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

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

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

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

Алгоритм Земора основан на типе графики расширителей называется Граф Таннера. Построение кода впервые было предложено Таннером.^[3] Коды основаны на двойная крышка ${\displaystyle d}$, обычный эспандер ${\displaystyle G}$, который является двудольным графом. ${\displaystyle G}$ =${\displaystyle \left(V,E\right)}$, куда ${\displaystyle V}$ - множество вершин и ${\displaystyle E}$ - множество ребер и ${\displaystyle V}$ = ${\displaystyle A}$ ${\displaystyle \cup }$ ${\displaystyle B}$ и ${\displaystyle A}$ ${\displaystyle \cap }$ ${\displaystyle B}$ = ${\displaystyle \emptyset }$, куда ${\displaystyle A}$ и ${\displaystyle B}$ обозначает набор из 2-х вершин. Позволять ${\displaystyle n}$ - количество вершин в каждой группе, т.е., ${\displaystyle |A|=|B|=n}$. Набор кромок ${\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 x\in \mathbb {F} ^{N}}$ раздел на ${\displaystyle n}$ неперекрывающиеся подслова ${\displaystyle \left(x\right)_{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 \left(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 \left(n,k\right)}$ и оценить ${\displaystyle r=\left({\dfrac {k}{n}}\right)}$ связан с каждым из узлов подкода, то ${\displaystyle k\geq 1-\left(1-r\right)m}$.

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

Позволять ${\displaystyle R}$ - скорость линейного кода, равная ${\displaystyle K/N}$Пусть есть ${\displaystyle S}$ узлы подкода в графе. Если степень подкода равна ${\displaystyle n}$, то код должен иметь ${\displaystyle \left({\dfrac {n}{m}}\right)S}$ цифр, поскольку каждый цифровой узел подключен к ${\displaystyle m}$ из ${\displaystyle \left(n\right)S}$ ребра в графе. Каждый узел подкода вносит свой вклад ${\displaystyle (n-k)}$ уравнения к матрице проверки на четность для всего ${\displaystyle \left(n-k\right)S}$. Эти уравнения не могут быть линейно независимыми. Следовательно, ${\displaystyle \left({\dfrac {K}{N}}\right)\geq \left({\dfrac {({\dfrac {n}{m}})S-(n-k)S}{({\dfrac {n}{m}})S}}\right)}$
${\displaystyle \geq 1-m\left({\dfrac {n-k}{n}}\right)}$
${\displaystyle \geq 1-m\left(1-r\right)}$, Поскольку значение ${\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 C(B,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 C(B,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-\gamma \right)\right)}$.

В результате любой набор ${\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 C(B,S)}$. Неравенство ${\displaystyle (2)}$ удовлетворен для ${\displaystyle \gamma <\left({\dfrac {1-({\dfrac {\lambda }{d}})}{\delta -({\dfrac {\lambda }{d}})}}\right)}$. Следовательно, ${\displaystyle C(B,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 (z)_{v}\leftarrow \mathbb {D} ((z)_{v})}$ // Декодирование ${\displaystyle z_{v}}$ до ближайшего кодового слова.
}
Выход: ${\displaystyle z}$

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

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

Позволять ${\displaystyle w\in \{0,1\}^{N}}$ - полученный вектор, и напомним, что ${\displaystyle N=dn}$. Первая итерация алгоритма состоит в применении полного декодирования кода, индуцированного ${\displaystyle E_{v}}$ для каждого ${\displaystyle v\in A}$ . Это означает, что для замены на каждые ${\displaystyle v\in A}$, вектор ${\displaystyle \left(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}}).\alpha N\delta \left(({\dfrac {\delta }{2}})-({\dfrac {\lambda }{d}})\right)=\left(({\dfrac {1}{4}}).\alpha N(\delta ^{2}-O({\dfrac {\lambda }{d}})\right)}$ для ценностей ${\displaystyle \alpha <1}$. Здесь алгоритм декодирования реализован в виде схемы размером ${\displaystyle O(N\log {N})}$ и глубина ${\displaystyle O(\log {N})}$ который возвращает кодовое слово, если вес вектора ошибки меньше ${\displaystyle \alpha N\delta ^{2}(1-\epsilon )/4}$ .

Теорема

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

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

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

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

1. Это длительный процесс, так как количество итераций ${\displaystyle m}$ в алгоритме декодера принимает ${\displaystyle [(\log {n})/(\log(2-\alpha ))]}$
2. Алгоритм декодирования Земора затрудняет декодирование стирания. Подробный способ улучшения алгоритма:

приведены в.^[5]

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

• Коды расширителей
• Граф Таннера
• Линейное временное кодирование и декодирование кодов с исправлением ошибок

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

1. Жиль Земор
2. http://www.cs.washington.edu/education/courses/cse590vg/03wi/scribes/1-27.ps
3. http://www.cs.washington.edu/education/courses/cse533/06au/lecnotes/lecture14.pdf
4. http://math.ucsd.edu/~fan/mypaps/fanpap/93tolerant.pdf
5. «Архивная копия». Архивировано из оригинал 14 сентября 2004 г.. Получено 1 мая, 2012.