Граф Таннера (Ijgs Mguuyjg)

Перейти к навигации Перейти к поиску

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

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

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

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

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

[править | править код]
Граф Таннера с узлами подкодов и знаков
Граф Таннера с узлами подкодов и знаков

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

Границы, доказанные Таннером

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

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

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

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

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

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

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

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

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

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

Примечания

[править | править код]
  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 года.
  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 года.

Литература

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