Tannerův graf - Tanner graph

V teorii kódování je Tannerův graf , pojmenovaný po Michaelovi Tannerovi, bipartitní graf používaný ke stanovení omezení nebo rovnic, které specifikují kódy opravující chyby . V teorii kódování se Tannerovy grafy používají ke konstrukci delších kódů z menších. Kodéry i dekodéry tyto grafy hojně využívají.

Počátky

Tannerovy grafy navrhl Michael Tanner jako prostředek k vytvoření větších kódů pro opravu chyb z menších pomocí rekurzivních technik. Zobecnil techniky Eliase pro kódy produktů.

Tanner hovořil o dolních mezích kódů získaný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 pro lineární blokové kódy

Tannerovy grafy jsou rozděleny na uzly subkódů a číslicové uzly. U lineárních blokových kódů označují uzly dílčích kódů řádky matice kontroly parity H. Číselné uzly představují sloupce matice H. Okraj spojuje uzel dílčího kódu s číslicovým uzlem, pokud v průsečíku odpovídajícího bodu existuje nenulová položka řádek a sloupec.

Hranice prokázal Tanner

Tanner dokázal následující hranice

Nechť je rychlost výsledného lineárního kódu, nechť je stupeň digitálních uzlů a stupeň uzlů subkódů . Pokud je každý uzel subkódu spojen s lineárním kódem (n, k) s rychlostí r = k / n, pak je rychlost kódu omezena ${\ displaystyle R}$${\ displaystyle m}$${\ displaystyle n}$

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

Výpočetní složitost metod založených na Tannerově grafu

Výhodou těchto rekurzivních technik je, že jsou výpočtově využitelné. Algoritmus kódování pro Tannerovy grafy je v praxi extrémně efektivní, i když není zaručeno, že konverguje, s výjimkou cyklů bez grafů, o nichž je známo, že nepřijímají asymptoticky dobré kódy.

Aplikace Tannerova grafu

Zemorův dekódovací algoritmus , který je rekurzivním přístupem ke konstrukci kódu s nízkou složitostí, je založen na Tannerových grafech.

Poznámky

• Originální papír Michaela Tannera
• Stránka Michaela Tannera