Wykres Tannera

W teorii kodowania wykres Tannera , nazwany na cześć Michaela Tannera, jest dwudzielnym wykresem używanym do określania ograniczeń lub równań, które określają kody korygujące błędy . W teorii kodowania grafy Tannera służą do konstruowania dłuższych kodów z mniejszych. Zarówno kodery, jak i dekodery szeroko wykorzystują te wykresy.

Pochodzenie

Wykresy Tannera zostały zaproponowane przez Michaela Tannera jako sposób na tworzenie większych kodów korygujących błędy z mniejszych przy użyciu technik rekurencyjnych. Uogólnił techniki Eliasa dla kodów produktów.

Tanner omówił dolne granice kodów uzyskanych z tych grafów, niezależnie od specyficznych cech kodów, które były używane do konstruowania większych kodów.

Wykresy Tannera dla liniowych kodów blokowych

Tanner graph with subcode and digit nodes

Wykresy Tannera są podzielone na węzły kodu podrzędnego i węzły cyfrowe. W przypadku liniowych kodów blokowych węzły subkodu oznaczają wiersze macierzy kontroli parzystości H. Węzły cyfr reprezentują kolumny macierzy H. Krawędź łączy węzeł subkodu z węzłem cyfry, jeśli na przecięciu odpowiednich wiersz i kolumna.

Granice udowodnione przez Tannera

Tanner udowodnił następujące granice

Niech będzie szybkością wynikowego kodu stopień węzłów cyfr będzie a stopień węzłów kodu podrzędnego . Jeśli każdy węzeł podkodu jest powiązany z kodem liniowym (n, k) o szybkości r = k/n, to szybkość kodu jest ograniczona przez

Złożoność obliczeniowa metod opartych na grafach Tannera

Zaletą tych rekurencyjnych technik jest to, że można je obliczyć. Algorytm kodowania grafów Tannera jest w praktyce niezwykle wydajny, chociaż nie ma gwarancji zbieżności, z wyjątkiem grafów bez cykli, o których wiadomo, że nie dopuszczają asymptotycznie dobrych kodów.

Zastosowania wykresu Tannera

Algorytm dekodowania Zemora , który jest rekurencyjnym podejściem do konstrukcji kodu o niskiej złożoności, jest oparty na grafach Tannera.

Notatki