Граф Таннера

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

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

Истоки

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

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

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

Граф Таннера с узлами подкодов и знаков

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

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

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

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

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

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

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

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

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

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