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
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
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.
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.
Zakodowane bity są transmitowane przez szumiący kanał; odebrane bity to wartości miękkie (stosunki wiarygodności lub logarytmy stosunków wiarygodności).
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ą.
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
Gallager, R. G. (1962). Low-density parity-check codes. IRE Transactions on Information Theory, 8(1), 21-28.
Otwórz odnośnik DOISkopiowano.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 DOISkopiowano.