Tannerův graf je bipartitní graf používaný k omezení stavů nebo rovností, které definují kódy opravy chyb . V teorii kódování byly Tannerovy grafy použity ke konstrukci delších kódů z menších. Jak kodéry, tak dekodéry tyto grafy hojně využívají.
Pojmenováno po Michaelu Tannerovi.
Tannerovy grafy navrhl Michael Tanner [1] pro generování delších kódů pro opravu chyb z menších kódů pomocí rekurzivních technik. Shrnul techniky Petera Eliáše pro odvozování kódů.
Tanner diskutoval o spodních mezích kódů odvozených z těchto grafů, bez ohledu na specifické vlastnosti kódů, které byly použity ke konstrukci větších kódů.
Tannerovy grafy jsou rozděleny na podkódové uzly a znakové uzly. U lineárních blokových kódů uzly subkódu definují řádky paritní kontrolní matice H. Znaménkové uzly představují sloupce matice H. Hrana spojuje uzel subkódu s uzlem znaménka, pokud je v matici nenulový prvek. matice na průsečíku řádku a sloupce.
Tanner dokázal následující meze.
Nechť je rychlost výsledného lineárního kódu, stupeň znaménkových uzlů nechť je a stupeň uzlů podkódu nechť je . Pokud je každý uzel subkódu spojen s řádkovým kódem (n,k) s rychlostí r = k/n, pak je kódová rychlost omezena
Výhodou těchto rekurzivních technik je, že jsou výpočetně nenáročné. Kódovací algoritmus pro Tannerovy grafy je v praxi extrémně účinný, i když nezaručuje konvergenci, s výjimkou bezcyklových grafů, o kterých je známo, že nedávají asymptoticky dobré kódy [2] .
Zemorův dekódovací algoritmus , což je rekurzivní přístup s nízkou složitostí ke konstrukci kódů, je založen na Tannerových grafech.
Řídkou matici pro kód s nízkou hustotou paritních kontrol lze reprezentovat jako Tannerův graf, který umožňuje použití takových grafů jako podpůrné datové struktury v algoritmu matice kontroly parity známém jako progresivní růst okraje [3] .