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

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

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

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

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

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

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

${\displaystyle R\geqslant 1-(1-r)m\,}$

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

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

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

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.