Przejdź do treści
Wróć do wyników wyszukiwania

Kody LDPC (Low-Density Parity-Check Codes)

Autor metody
Robert Gallager
Rok
1962
Typ
linear error-correcting code
Rodzina
Coding theory

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

Kody LDPC, wynalezione przez Roberta Gallagera w 1962 roku i ponownie odkryte w latach 90. przez MacKay'a, to liniowe kody poprawiające błędy, zdefiniowane przez rzadkie macierze parzystości.

Osiągają one wydajność w granicach 0,4 dB od granicy Shannona przy iteracyjnym dekodowaniu propagacji wiary i stały się standardem dla nowoczesnych sieci bezprzewodowych (WiFi-6, 5G NR, Digital Video Broadcasting). W przeciwieństwie do kodów turbo, kody LDPC mają bardziej elegancką strukturę grafowo-teoretyczną i dojrzalszą analizę teoretyczną.

Intuicja stojąca za metodą

Standardowe kody liniowe wykorzystują gęste macierze parzystości, co czyni dekodowanie obliczeniowo kosztownym. Kody LDPC odwracają tę zależność: macierz parzystości jest rzadka (większość elementów to zera), więc każda kontrola parzystości dotyczy tylko kilku bitów. Po stronie odbiornika konstruowany jest graf dwudzielny, w którym węzły zmiennych reprezentują transmitowane bity, a węzły kontrolne reprezentują ograniczenia parzystości. Dekodowanie staje się iteracyjnym przekazywaniem komunikatów w tym grafie: każdy węzeł zmiennej zbiera informacje od swoich sąsiadów, aktualizuje swoje przekonanie o wartości bitu i wysyła udoskonalone estymaty z powrotem. Rzadkość zapewnia szybką zbieżność i wydajność zbliżoną do granicy Shannona.

Historia

Gallager wynalazł kody LDPC w 1962 roku, ale teoria pozostawała w tyle za praktyczną implementacją. W 1995 roku MacKay ponownie je odkrył i wykazał ich wydajność zbliżoną do granicy Shannona za pomocą symulacji. Obszerne badania w latach 2000. doprowadziły do opracowania wydajnych algorytmów kodowania, dekodowania i konstruowania grafów. Kody LDPC zostały przyjęte w standardzie WiFi-6 (802.11ax, 2021) i 5G NR (2018). Stały się one bardziej rozpowszechnione niż kody turbo w nowych systemach ze względu na lepszą wydajność i czystszą strukturę.

Kiedy stosować

Kody LDPC są preferowane nad kodami turbo w nowoczesnych systemach ze względu na lepszą wydajność i prostszą architekturę. Używaj LDPC dla szerokich zakresów SNR (bez nagłego progu); działają dobrze od niskiego do wysokiego SNR. LDPC jest standardem dla WiFi-6, komunikacji satelitarnej i 5G NR. Unikaj LDPC tylko wtedy, gdy kompatybilność wsteczna wymaga kodów turbo. LDPC nadaje się również do bardzo krótkich pakietów (>30 bitów), ponieważ struktura kodu jest rozdzielna.

Ograniczenia i uwagi

  • Konstrukcja grafu i przechowywanie macierzy stają się złożone dla bardzo długich kodów (>10 tys. bitów)
  • Wydajność jest wrażliwa na struktury grafu małej skali (obwody, zbiory absorbujące); wymaga starannego projektowania
  • Propagacja wiary zakłada graf z pętlami, ale grafy mają cykle; zbieżność do optymalnego rozwiązania nie jest gwarantowana
  • Opóźnienie dekodowania (iteracje) rośnie logarytmicznie wraz z SNR; nie jest zerowe jak w niektórych klasycznych kodach
  • Kwantyzacja komunikatów (w sprzęcie stałoprzecinkowym) wpływa na wydajność; potrzebna jest staranna alokacja bitów

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Wydajność w granicach 0,4 dB od granicy Shannona (nieco lepsza niż kody turbo)
  • Prostsza struktura grafowo-teoretyczna; czystsza analiza teoretyczna niż w kodach turbo
  • Dekodowanie iteracyjne unika nagłych zmian progu (w przeciwieństwie do turbo)
  • Elastyczne projektowanie kodu poprzez konstrukcję grafu; łatwe do dostosowania do konkretnych zastosowań
  • Wydajny sprzęt do dekodowania równoległego; przekazywanie komunikatów nadaje się do implementacji VLSI/GPU
  • Działa dobrze zarówno dla długich, jak i umiarkowanie krótkich słów kodowych

Zastosowania

  • WiFi-6 (802.11ax): sieci lokalne o wysokiej przepustowości z LDPC zapewniające niezawodne dostarczanie danych
  • 5G NR: kodowanie kanałowe zarówno dla kanałów danych, jak i sterujących, zastępujące kody turbo z 4G
  • Komunikacja satelitarna: cyfrowe nadawanie wideo (DVB-S2) i misje w dalekiej przestrzeni kosmicznej wykorzystujące LDPC z długimi słowami kodowymi
  • Komunikacja w sieci energetycznej (PLC): niezawodna transmisja danych przez szumiące sieci elektryczne
  • Systemy pamięci flash: korekcja błędów dla pamięci masowej NAND flash bez zużycia spowodowanego częstym odświeżaniem

Jak to działa

Jak to działa

1

Bity informacyjne są kodowane przy użyciu rzadkiej macierzy parzystości H; zakodowane bity są rozwiązaniem równania H*c = 0 (mod 2), gdzie c jest słowem kodowym.

2

Macierz parzystości H jest skonstruowana tak, aby była rzadka (np. każdy wiersz/kolumna ma stałą niską wagę 3-5). Ta struktura jest wykorzystywana do efektywnego kodowania.

3

Zakodowane bity są transmitowane przez szumiący kanał; odebrane bity to wartości miękkie (stosunki wiarygodności lub logarytmy stosunków wiarygodności).

4

Konstruowany jest graf dwudzielny: węzły lewe = węzły zmiennych (bity), węzły prawe = węzły kontrolne (równania parzystości). Krawędzie łączą zmienne z kontrolami, w których występują.

5

Iteracyjna propagacja wiary: węzły zmiennych agregują komunikaty od węzłów kontrolnych, aktualizują estymaty bitów i wysyłają udoskonalone komunikaty z powrotem. Po iteracjach podejmowane są twarde decyzje; jeśli kontrole parzystości są spełnione, dekodowanie jest udane.

Częste pułapki

  • Użycie źle zaprojektowanego rzadkiego grafu z krótkimi cyklami; krótkie cykle powodują oscylacje propagacji wiary
  • Nadmierne iteracje poza zbieżnością; niepotrzebne iteracje marnują energię bez poprawy
  • Założenie, że dekodowanie min-sum jest tak dobre jak sum-product; aproksymacje powodują utratę wydajności, szczególnie przy niskim SNR
  • Pomijanie efektów skończonej długości; grafy zaprojektowane do analizy asymptotycznej mogą działać gorzej na krótkich pakietach
  • Nie uwzględnianie kwantyzacji w implementacji sprzętowej; symulacja zmiennoprzecinkowa różni się od rzeczywistości stałoprzecinkowej

Najczęściej zadawane pytania

Co sprawia, że dekodowanie LDPC jest tak wydajne w porównaniu do ogólnych kodów liniowych?

Rzadkość macierzy parzystości oznacza, że każdy bit uczestniczy tylko w kilku kontrolach parzystości. Podczas dekodowania, przekazywanie komunikatów w grafie dwudzielnym jest liniowe względem liczby krawędzi, a nie długości kodu. W przypadku kodów gęstych dekodowanie wymagałoby odwrócenia macierzy, co jest sześcienne względem długości kodu. Rzadkość sprawia, że dekodowanie jest quasi-liniowe i praktyczne dla długich kodów.

Czym jest zbiór absorbujący i dlaczego ma znaczenie?

Zbiór absorbujący to mały podzbiór grafu, który może uwięzić dekodowanie propagacji wiary, uniemożliwiając zbieżność do poprawnego rozwiązania. Są one główną przyczyną podłogi błędu (nie-wykładniczy spadek BER przy niskim SNR). Projektanci kodów unikają krótkich zbiorów absorbujących poprzez staranne konstruowanie grafu; narzędzia analityczne (np. analiza zbiorów zatrzymujących) identyfikują problematyczne struktury.

Jak LDPC porównuje się do kodów polarnych?

Oba osiągają wydajność zbliżoną do granicy Shannona. Kody polarne mają strukturę rekurencyjną i udowodnioną optymalność przy dekodowaniu sukcesywnym anulowaniem dla nieskończonej długości kodu. Kody LDPC są bardziej elastyczne i empirycznie mają lepszą wydajność dla skończonych długości. 5G NR wykorzystuje kody polarne dla kanałów sterujących (krótkie pakiety) i LDPC dla kanałów danych (długie pakiety), wykorzystując mocne strony każdego kodu.

Dlaczego obwód grafu jest ważny w kodach LDPC?

Obwód to długość najkrótszego cyklu w grafie dwudzielnym. Krótkie cykle (obwód < 6) powodują, że propagacja wiary wykorzystuje skorelowane informacje (komunikaty wracają po pętli), pogarszając wydajność. Kody o wysokim obwodzie (obwód ≥ 6) lepiej przełamują korelacje. Kody są często projektowane tak, aby zmaksymalizować obwód przy zachowaniu ograniczeń rzadkości.

Pokrewne metody

Źródła

  1. Gallager, R. G. (1962). Low-density parity-check codes. IRE Transactions on Information Theory, 8(1), 21-28.

    Otwórz odnośnik DOI
    Skopiowano.
  2. Richardson, T. J., & Urbanke, R. L. (2001). The capacity of low-density parity-check codes under message-passing decoding. IEEE Transactions on Information Theory, 47(2), 599-618.

    Otwórz odnośnik DOI
    Skopiowano.