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
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
- ^ R. Michael Tanner profesor informatyki, School of Engineering University of California, Santa Cruz Zeznanie przed przedstawicielami Urzędu ds. Praw Autorskich Stanów Zjednoczonych 10 lutego 1999 r.
- ^ T. Etzion, A. Trachtenberg i A. Vardy , Które kody mają wolne od cykli wykresy Tannera?, IEEE Trans. Inf. Teoria, 45:6.