Граф Таннера - Tanner graph

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

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

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

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

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

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

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

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

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

{ Displaystyle R GEQ 1- (1-р) м ,}

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

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

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

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

Примечания

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

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

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

[1]

[2]