В теории кодирования граф Таннера , названный в честь Майкла Таннера, представляет собой двудольный граф , используемый для установления ограничений или уравнений, которые определяют коды с исправлением ошибок . В теории кодирования графы Таннера используются для построения более длинных кодов из меньших. И кодеры, и декодеры широко используют эти графики.
Графы Таннера были предложены Майклом Таннером [1] как средство создания более крупных кодов с исправлением ошибок из меньших с использованием рекурсивных методов. Он обобщил методы Элиаса для кодов продуктов.
Таннер обсудил нижние границы кодов, полученных из этих графов, независимо от конкретных характеристик кодов, которые использовались для построения более крупных кодов.
Графы Таннера разделены на узлы субкодов и узлы цифр. Для линейных блочных кодов узлы субкода обозначают строки матрицы проверки на четность H. Цифровые узлы представляют столбцы матрицы H. Ребро соединяет узел субкода с цифровым узлом, если ненулевая запись существует в пересечении соответствующего строка и столбец.
Таннер доказал следующие оценки
Пусть – скорость результирующего линейного кода, пусть степень цифровых узлов равна , а степень узлов субкода равна . Если каждый узел субкода связан с линейным кодом (n,k) со скоростью r = k/n, то скорость кода ограничена
Преимущество этих рекурсивных методов заключается в том, что они легко обрабатываются с помощью вычислений. Алгоритм кодирования графов Таннера на практике чрезвычайно эффективен, хотя его сходимость не гарантируется, за исключением графов без циклов, которые, как известно, не допускают асимптотически хороших кодов. [2]
Алгоритм декодирования Земора , представляющий собой рекурсивный подход низкой сложности к построению кода, основан на графах Таннера.
