Hrabě z Tanner

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.

Origins

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 pro kódy liniových bloků

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.

Limity prověřené Tannerem

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ýpočtová složitost metod založených na Tannerově grafu

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] .

Aplikace hraběte Tannera

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] .

Poznámky

  1. R. Michael Tanner Profesor informatiky, School of Engineering University of California, Santa Cruz Svědectví před zástupci Úřadu pro autorská práva Spojených států amerických 10. února 1999 . Získáno 8. března 2019. Archivováno z originálu 8. května 2017.
  2. Etzion, Trachtenberg, Vardy, 1998 .
  3. Xiao-Yu Hu, E. Eleftheriou, DM Arnold. Pravidelné a nepravidelné progresivní grafy progresivního růstu hran  // IEEE Transactions on Information Theory. — 2005-1. - T. 51 , č.p. 1 . — S. 386–398 . — ISSN 0018-9448 . - doi : 10.1109/TIT.2004.839541 . Archivováno z originálu 27. února 2021.

Literatura