Граф Таннера

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

Происхождение

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

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

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

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

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

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

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

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

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

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

Применение графа Таннера

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

Примечания

^ Р. Майкл Таннер, профессор компьютерных наук, инженерный факультет Калифорнийского университета, Санта-Крус. Свидетельские показания перед представителями Бюро авторских прав США, 10 февраля 1999 г.
^ Т. Эцион, А. Трахтенберг и А. Варди , Какие коды имеют безцикловые графы Таннера?, IEEE Trans. Инф. Теория, 45:6.

[1] Р. Майкл Таннер, профессор компьютерных наук, инженерный факультет Калифорнийского университета, Санта-Крус. Свидетельские показания перед представителями Бюро авторских прав США, 10 февраля 1999 г.

[2] Т. Эцион, А. Трахтенберг и А. Варди , Какие коды имеют безцикловые графы Таннера?, IEEE Trans. Инф. Теория, 45:6.

[1]

[2]