Граф Таннера

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

Назван в честь Майкла Таннера.

ИстокиПравить

Графы Таннера предложил Майкл Таннер^[1], чтобы создать более длинные коды с коррекцией ошибок из более мелких кодов с помощью рекурсивных техник. Он обобщил техники Питера Элиаса для получения кодов.

Таннер обсуждал нижние границы на коды, полученные из этих графов, независимо от специфичных характеристик кодов, которые были использованы для построения бо́льших кодов.

Графы Таннера для кодов линейных блоковПравить

Графы Таннера разбиты на узлы подкодов и узлы знаков. Для линейных блочных кодов узлы подкодов определяют строки проверочной матрицы чётности^[en] H. Узлы знаков представляют столбцы матрицы H. Ребро соединяет узел подкода с узлом знака, если в матрице на пересечении строки и столбца существует ненулевой элемент.

Границы, доказанные ТаннеромПравить

Таннер доказал следующие границы.

Пусть $\text{[math]}$ $\text{[math]}$ $R$ является скоростью^[en] результирующего линейного кода, пусть степень узлов знаков равна $\text{[math]}$ $\text{[math]}$ $m$ , а степень узлов подкодов будет $\text{[math]}$ $\text{[math]}$ $n$ . Если каждый узел подкода ассоциирован с линейным кодом (n,k) со скоростью r = k/n, то скорость кода ограничена величиной

\text{[math]}

R\geqslant 1-(1-r)m\,

Вычислительная сложность методов, основанных на графе ТаннераПравить

Преимущество этих рекурсивных техник заключается в том, что они вычислительно удобны. Алгоритм кодирования для графов Таннера крайне эффективен на практике, хотя он не гарантирует сходимость, за исключением графов без циклов, для которых известно, что они не дают асимптотически хороших кодов^[2].

Приложения графа ТаннераПравить

Алгоритм декодирования Земора^[en], который является рекурсивным подходом низкой сложности к построению кодов, основан на графах Таннера.

Разреженная матрица для кода с малой плотностью проверок на чётность представима в виде графа Таннера, что позволяет использовать такие графы как опорную структуру данных в алгоритме построения проверочной матрицы, известного как Progressive Edge Growth^[3].

ПримечанияПравить

↑ R. Michael Tanner Professor of Computer Science, School of Engineering University of California, Santa Cruz Testimony before Representatives of the United States Copyright Office February 10, 1999 (неопр.). Дата обращения: 8 марта 2019. Архивировано 8 мая 2017 года.
↑ Etzion, Trachtenberg, Vardy, 1998.
↑ Xiao-Yu Hu, E. Eleftheriou, D.M. Arnold. Regular and irregular progressive edge-growth tanner graphs // IEEE Transactions on Information Theory. — 2005-1. — Т. 51, вып. 1. — С. 386–398. — ISSN 0018-9448. — doi:10.1109/TIT.2004.839541. Архивировано 27 февраля 2021 года.

ЛитератураПравить

Michael Tanner's Original paper
Michael Tanner's page
Etzion T., Trachtenberg A., Vardy A. Which Codes have Cycle-Free Tanner Graphs? // IEEE Trans. Inf. Theory. — 1998. — Т. 45, вып. 6.

[1] R. Michael Tanner Professor of Computer Science, School of Engineering University of California, Santa Cruz Testimony before Representatives of the United States Copyright Office February 10, 1999 (неопр.). Дата обращения: 8 марта 2019. Архивировано 8 мая 2017 года.

[_5afa77bdd4e1e006-2] Etzion, Trachtenberg, Vardy, 1998.

[3] Xiao-Yu Hu, E. Eleftheriou, D.M. Arnold. Regular and irregular progressive edge-growth tanner graphs // IEEE Transactions on Information Theory. — 2005-1. — Т. 51, вып. 1. — С. 386–398. — ISSN 0018-9448. — doi:10.1109/TIT.2004.839541. Архивировано 27 февраля 2021 года.

[1]

[2]

[3]