Tannerův graf - Tanner graph

v teorie kódování, a Tannerův graf, pojmenovaný podle Michaela Tannera, je bipartitní graf používá se ke stanovení omezení nebo rovnic, které specifikují chyba opravující kódy. v teorie kódování „Tannerovy grafy se 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^[1] jako prostředek k vytvoření větších kódů pro opravu chyb z menších pomocí rekurzivních technik. Zobecnil techniky Elias 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ělené do uzlů subkódů a digitálních uzlů. 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 subkódu s digitálním uzlem, pokud v průsečíku odpovídajícího řádku a sloupce existuje nenulová položka.

Hranice prokázal Tanner

Tanner dokázal následující hranice

Nechat ${ displaystyle R}$ je míra výsledného lineárního kódu, nechť je stupeň číslicových uzlů ${ displaystyle m}$ a stupeň uzlů subkódu ${ displaystyle n}$. 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 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é. Kódovací algoritmus 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.^[2]

Aplikace Tannerova grafu

Zemorův dekódovací algoritmus, což je rekurzivní přístup 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