LDPC

Kody LDPC (ang. Low-Density Parity Check) – klasa liniowych kodów korekcyjnych, umożliwiających korekcję błędów w blokach danych cyfrowych, w szczególności powstałych w trakcie transmisji danych przez kanał komunikacyjny z zakłóceniami.

Detekcja i korekcja błędów odbywa się z wykorzystaniem tzw. macierzy kontroli parzystości ${\displaystyle \mathbf {H} .}$ Blok (wektor) danych binarnych ${\displaystyle \mathbf {c} =[c_{1},c_{2},\dots ,c_{N}]}$ jest prawidłowym (nieprzekłamanym) wektorem kodu definiowanego przez ${\displaystyle \mathbf {H} }$ wtedy i tylko wtedy, gdy spełnione jest równanie kontrolne: ${\displaystyle \mathbf {H} \mathbf {c} ^{T}=\mathbf {0} .}$ W tym równaniu macierzowym operacje mnożenia i dodawania są wykonywane w ciele Galois drugiego rzędu, a inaczej: iloczyn jest iloczynem logicznym, a suma – sumą modulo 2.

W czasach, gdy zostały opisane przez R.G. Gallagera^[1], systemy transmisji nie były na tyle rozwinięte, aby konieczne było stosowanie zaawansowanych metod kodowania korekcyjnego. Poza tym praktyczne wykorzystanie kodów LDPC wymaga stosunkowo dużych zasobów obliczeniowych, przerastających technologie dostępne w tamtych czasach. Poważne zainteresowanie naukowców i inżynierów zostało zapoczątkowane dopiero po latach, przez publikacje D.J.C. MacKaya^[2].

Kody LDPC są to takie liniowe kody blokowe, których macierz kontroli parzystości ${\displaystyle \mathbf {H} }$ jest macierzą rzadką, tzn. liczba niezerowych elementów w każdej kolumnie macierzy jest znacznie mniejsza niż rozmiar kolumny, a liczba niezerowych elementów w każdym wierszu – znacznie mniejsza niż rozmiar wiersza.

Kody LDPC są stosowane wszędzie tam, gdzie potrzebne są zaawansowane metody korekcji błędów, a dostępne zasoby obliczeniowe nie są mocno ograniczone. Współcześnie wykorzystywane są między innymi w standardach DVB-S2, DVB-T2, Ethernet 10GBase-T, wi-fi 802.11n i 802.11ac.