Nízkohustotní kód s kontrolou parity

Nízkohustotní kód s kontrolou parity (anglicky low-density parity-check code, LDPC) je v teorii informace lineární samoopravný kód, který umožňuje přenášet zprávy zarušeným přenosovým kanálem. LDPC se konstruují pomocí řídkého Tannerova grafu (podtřída bipartitních grafů). LDPC patří mezi kódy s výkonností blízkou kapacitě kanálu, což znamená, že existuje praktická konstrukce, při která lze šumovou mez nastavit velmi blízko teoretické maximální Shannonově mezi pro symetrický bezpaměťový kanál. Šumová mez určuje horní mez pro kanálový šum, pod kterou lze dosáhnout libovolně malé pravděpodobnosti ztráty informace. Při použití iterativního šíření přesvědčení lze LDPC kódy dekódovat v čase přímo úměrném délce bloku.

LDPC kódy nacházejí rostoucí využití v aplikacích vyžadujících spolehlivý a vysoce efektivní přenos informací kanálem s omezenou šířkou pásma nebo kanálem s omezeným zpětným kanálem v přítomnosti šumu. K implementaci LDPC kódů došlo později, než byly implementovány jiné kódy, především turbokódy. Základní patent pro turbokódy vypršel 29. srpna 2013.

LDPC kódy jsou také známy jako Gallagerovy kódy, na počest Roberta G. Gallagera, který je popsal ve svém disertaci na Massachusetts Institute of Technology v roce 1960.

Historie

Implementace LPDC kódů byla v roce 1963, kdy je Gallager navrhl, příliš náročná, takže LDPC kódy byly zapomenuty až do roku 1996, kdy byla jeho práce znovuobjevena. Na konci 90. let 20. století se staly preferovaným kódovacím schématem turbokódy objevené v roce 1993. Turbokódy jsou jinou třídou kódů s výkonností blízkou kapacitě kanálu, které se používají pro aplikace jako je Deep Space Network a pro satelitní komunikaci. Díky technologickému pokroku však začaly být kódy s nízkohustotní kontrolou parity prakticky realizovatelné, a zdá se, že překonávají turbokódy svým nižším chybovým prahem a výkonností ve větším rozsahu kódových poměrů, zatímco turbokódy jsou stále výhodnější pro nižší kódové poměry.

Aplikace

V roce 2003 nepravidelný opakovací akumulační kód (anglicky irregular repeat accumulate, IRA) z rodiny LDPC kódů překonal šest turbokódů a byl vybrán jako samoopravný kód pro nový standard DVB-S2 pro satelitní vysílání digitální televize. Výbor pro výběr DVB-S2 provedl odhady složitosti dekodéru pro návrhy turbokódu, které používaly sériovou architekturu dekodéru, která je mnohem méně efektivní než paralelní architektura. Kvůli tomu turbokód používal přibližně poloviční rámce než LDPC.

Při výběru samoopravného kódu (FEC) pro ITU-T standard G.hn v roce 2008 zvítězily LDPC nad konvolučními turbokódy. V G.hn byla dána přednost LDPC kódům před turbokódy díky jejich nižší dekódovací složitosti (která je důležitá při přenosové rychlosti blízké 1.0 Gbit/s) a protože navržené turbokódy vykazovaly významný chybový práh pro požadovaný režim fungování.

LDPC kódy využívá také Ethernetová technologie 10GBASE-T, které používá kabel s kroucenými páry pro přenos dat rychlostí 10 gigabitů za sekundu. Od roku 2009 jsou LDPC kódy také součástí Wi-Fi standardu 802.11 jako nepovinná část 802.11n a 802.11ac ve specifikaci High Throughput (HT) PHY.

Některé OFDM systémy přidávají dodatečnou vnější opravu chyb, která opravuje občasné chyby („chybový práh“) které překonávají vnitřní opravný kód LDPC i při nízkých bitových chybovostech. Například: Reedovy–Solomonovy kódy s LDPC Coded Modulation (RS-LCM) používá Reedův-Solomonův vnější kód. Standardy DVB-S2, DVB-T2 a DVB-C2 používají BCH kód jako vnější kód pro odstraňování zbytkových chyb po LDPC dekódování.

Aktuální využití

Funkčně jsou LDPC kódy definovány řídkou kontrolní maticí. Tato řídká matice je často náhodně generovaná tak, aby splňovala omezení pro řídkost. Konstrukce LDPC kódu je diskutována níže. Tyto kódy objevil Robert Gallager v roce 1962.

Následuje ukázka LDPC kódu na fragmentu grafu využívajícím Forneyovu notaci faktorového grafu. V tomto grafu je n proměnných uzlů v horní části grafu propojeno s (n−k) uzly omezení ve spodní části grafu.

Toto je oblíbený způsob grafické reprezentace (n, k) LDPC kódu. Pokud jsou jednotlivé bity platné zprávy připsány na téčka v horní části grafu, musí splňovat graficky znázorněná omezení: všechny hrany vedoucí do některého proměnného uzlu (označeného symbolem '=') musí mít stejnou hodnotu a součet všech hodnot vedoucích do některého faktorového uzlu (označeného symbolem '+') musí být sudý (neboli jejich součet modulo dva musí být nulový).

Pokud zanedbáme hrany opouštějící obraz, existuje osm šestibitových řetězců odpovídajících platným kódovým slovům: (řetězce 000000, 011001, 110010, 101011, 111100, 100101, 001110, 010111). Tento fragment LDPC kódu reprezentuje tříbitovou zprávu zakódovanou do šesti bitů. Tato redundance slouží ke zvýšení pravděpodobnosti zotavení z kanálové chyby. Jde o (6, 3) lineární kód, s n = 6 a k = 3.

Pokud opět zanedbáme hrany opouštějící obraz, kontrolní matice reprezentující tento fragment grafu je

$\mathbf {H} ={\begin{pmatrix}1&1&1&1&0&0\\0&0&1&1&0&1\\1&0&0&1&1&0\\\end{pmatrix}}.$

V této matici reprezentuje každý řádek jedno ze tří paritních omezení, a každý sloupec reprezentuje jeden ze šesti bitů přijatého kódového slova.

V tomto příkladě můžeme získat osm kódových slov rozšířením kontrolní matice H na tvar ${\begin{bmatrix}-P^{T}|I_{n-k}\end{bmatrix}}$ pomocí elementárních řádkových operací v tělese GF(2):

$\mathbf {H} ={\begin{pmatrix}1&1&1&1&0&0\\0&0&1&1&0&1\\1&0&0&1&1&0\\\end{pmatrix}}_{1}\sim {\begin{pmatrix}1&1&1&1&0&0\\0&0&1&1&0&1\\0&1&1&0&1&0\\\end{pmatrix}}_{2}\sim {\begin{pmatrix}1&1&1&1&0&0\\0&1&1&0&1&0\\0&0&1&1&0&1\\\end{pmatrix}}_{3}\sim {\begin{pmatrix}1&1&1&1&0&0\\0&1&1&0&1&0\\1&1&0&0&0&1\\\end{pmatrix}}_{4}.$

Krok 1: H.

Krok 2: Řádek 1 je přičten k řádku 3.

Krok 3: Řádky 2 a 3 jsou prohozeny.

Krok 4: Řádek 1 je přičten k řádku 3.

Odtud lze získat generující matici G jako ${\begin{bmatrix}I_{k}|P\end{bmatrix}}$ (přičemž v tomto speciálním případě, kdy pracujeme s dvojkovým kódem je $P=-P$), tedy konkrétně:

$\mathbf {G} ={\begin{pmatrix}1&0&0&1&0&1\\0&1&0&1&1&1\\0&0&1&1&1&0\\\end{pmatrix}}.$

Nakonec vynásobením všech osmi možných tříbitových řetězců maticí G získáme všech osm platných kódových slov. Například kódové slovo pro bitový řetězec '101' se získá takto:

${\begin{pmatrix}1&0&1\\\end{pmatrix}}\cdot {\begin{pmatrix}1&0&0&1&0&1\\0&1&0&1&1&1\\0&0&1&1&1&0\\\end{pmatrix}}={\begin{pmatrix}1&0&1&0&1&1\\\end{pmatrix}}.$

Pro kontrolu lze použít, že prostor řádků matice G je ortogonální k H, takže $GH^{T}=0$.

Bitový řetězec '101' dostaneme jako první 3 bity kódového slova '101011'.

Ukázkový kodér

Obrázek 1 znázorňuje funkční komponenty většiny LDPC kodérů.

Obr. 1. LDPC enkodér

Při kódování rámce se vstupní datové bity (D) kopírují a distribuují do sady složkových kodérů. Složkové kodéry jsou typicky akumulátory a každý akumulátor se používá pro generování paritního symbolu. Jedná kopie původních dat (S_0,K-1) se odešle s paritní bity (P), které tvoří kódové symboly. S bitů z každého složkového kodéru se zahodí.

Paritní bit může být použit v jiném složkovém kódu.

Například při použití kódu DVB-S2 s poměrem 2/3 má zakódovaný blok velikost 64800 symbolů (N=64800), z čehož je 43200 datových bitů (K=43200) a 21600 paritních bitů (M=21600). Každý složkový kód (kontrolní uzel) kóduje 16 datových bitů, s výjimkou prvního paritního bitu, který kóduje 8 datových bitů. Prvních 4680 datových bitů se 13krát opakuje (je použito ve třinácti paritních kódech), zatímco zbývající datové bity se používají ve 3 paritních kódech (nepravidelný LDPC kód).

Pro srovnání, klasické turbokódy typicky používají dva složkové kódy aplikované paralelně, z nichž každý kóduje celý vstupní blok (K) datových bitů. Tyto složkové kodéry používají rekurzivní konvoluční kódy (RSC) malé hloubky (8 nebo 16 stavů), které jsou rozprostřeny prokladačem kódu, který rozptyluje jednu kopii rámce.

Naproti tomu LDPC kódy používají mnoho složkových kódů malé hloubky (akumulátorů) paralelně, z nichž každý kóduje pouze malou část vstupního rámce. Množství složkových kódů lze chápat jako mnoho 'konvolučních kódů' malé hloubky (dvoustavových), které jsou propojeny operacemi opakování a distribuce. Opakování a distribuce mají stejnou funkci jako prokladač v turbokódu.

Schopnost přesněji řídit spojení různých složkových kódů a úroveň redundance pro každý vstupní bit zvyšuje pružnost návrhu LDPC kódů, díky čemuž mohou mít lepší výkonnost, než mají některé turbokódy. Zdá se, že turbokódy mají lepší výkonnost než LDPC při nízkých kódových poměrech, nebo že je návrh výkonných kódů s nízkým poměrem pro turbokódy snazší.

Hardwarová realizace akumulátorů se s výhodou používá i při kódování. To znamená, že jakmile se vygeneruje první sada paritních bitů, a paritní bity jsou uloženy, tentýž akumulátor se použije pro generování další sady paritních bitů.

Dekódování

Maximálně věrohodné dekódování LDPC kódu na binárním symetrickém kanálu je (podobně jako u jiných kódů) NP-úplný problém. Optimální dekódování kódu jakékoli užitečné velikosti tedy není prakticky možné.

Je však možné prakticky implementovat suboptimální techniky založené na dekódování s iterativním šířením přesvědčení, které dávají vynikající výsledky. Suboptimální dekódovací techniky pohlížejí na každý paritní bit, z nichž se skládá LDPC, jako na samostatný nezávislý paritní kód (anglicky single parity check, SPC). Každý SPC kód je dekódován odděleně pomocí Soft-in soft-out dekodéru (SISO), jakým je například Viterbiho algoritmus s měkkým výstupem (SOVA), BCJR, MAP a další z nich odvozené. Informace o měkkém rozhodnutí z každého SISO dekodéru je křížově zkontrolována a aktualizována podle ostatních redundantních SPC dekódování stejného informačního bitu. Každý SPC kód je pak znovu dekódován na základě aktualizovaných informací o měkkých rozhodnutích. Tento proces se opakuje, dokud se nezíská platné kódové slovo nebo se nevyčerpají všechny možnosti. Tento typ dekódování se často nazývá součtově-součinové dekódování (anglicky sum-product decoding).

Dekódování SPC kódů se často nazývá zpracování „kontrolních uzlů“ a křížová kontrola proměnných se nazývá zpracování „proměnných uzlů“.

Při praktické implementaci LDPC dekodéru se sada SPC kódů dekóduje paralelně pro zvýšení propustnosti.

Naproti tomu, šíření přesvědčení u kanálu s binárním vymazáváním je obzvláště jednoduché, pokud je realizováno iterativním uspokojováním omezení.

Uvažujme například, že platné kódové slovo 101011 z příkladu výše, se přenáší kanálem s binárním vymazáváním a je přijato s poškozeným prvním a čtvrtým bitem, takže je přijato ?01?11. Protože přenášená zpráva musí splňovat kódová omezení, lze přijatou zprávu reprezentovat jejím zapsáním do horní části faktorového grafu.

V tomto příkladě nelze zatím obnovit první bit, protože všechna omezení s ním spojená mají více než jeden neznámý bit. Aby bylo možné pokračovat s dekódováním zprávy, je třeba identifikovat omezení vztahující se pouze k jednomu z vymazaných bitů. V tomto případě stačí druhé omezení. Jeho prověřením lze zjistit, že čtvrtý bit musí být nulový, protože pouze nula v této pozici vyhovuje omezením.

Celý postup se pak opakuje. Nyní může být použita nová hodnota čtvrtého bitu spolu s prvním omezením pro získání hodnoty prvního bitu, jak uvidíme dále. Jeho hodnota musí vyhovovat omezení úplně vlevo.

Zprávu lze tedy dekódovat iterativně. Pro jiné kanálové modely jsou zprávy předávané mezi proměnnými uzly a kontrolními uzly reálná čísla, která vyjadřují pravděpodobnosti a věrohodnosti určité hodnoty.

Výsledek lze zkontrolovat vynásobením opraveného kódového slova r paritní maticí H:

$\mathbf {z} =\mathbf {Hr} ={\begin{pmatrix}1&1&1&1&0&0\\0&0&1&1&0&1\\1&0&0&1&1&0\\\end{pmatrix}}{\begin{pmatrix}1\\0\\1\\0\\1\\1\\\end{pmatrix}}={\begin{pmatrix}0\\0\\0\\\end{pmatrix}}.$

Protože výsledek z (syndrom) této operace je třikrát nulový vektor, výsledné kódové slovo r je úspěšně potvrzeno.

Po skončení dekódování lze původní bity zprávy '101' získat použitím prvních 3 bitů kódového slova.

Tento příklad je sice ilustrativní, ale neukazuje použití dekódování nebo předávání zpráv s měkkým rozhodováním, které se používá prakticky ve všech komerčních LDPC dekodérech.

Aktualizace informací v uzlu

V posledních letech bylo velké množství práce věnováno také studiu účinků alternativních rozvrhů aktualizace proměnných uzlů a uzlů omezení. Původní technika používaná pro dekódování LDPC kódů bylo tak zvané zaplavování (anglicky flooding). Tento typ aktualizace vyžaduje, aby před aktualizací proměnného uzlu byly aktualizovány všechny uzly omezení a naopak. Vila Casado se svými spolupracovníky ve své pozdější práci zkoumá alternativní techniky aktualizace, ve kterých jsou proměnné uzly aktualizovány nejnovější dostupnou informací z kontrolního uzlu.

Důvodem této úpravy je fakt, že jako první je třeba aktualizovat proměnné uzly, jejichž hodnoty se mění nejčastěji. Vysoce spolehlivé uzly, které mají velkou magnitudu poměru log-věrohodnosti (anglicky log-likelihood ratio, LLR), a při aktualizacích se výrazně nemění, nevyžadují tak časté aktualizace jako ty uzly, jejichž znaménko a magnituda kolísá více. Tyto plánovací algoritmy mají větší rychlost konvergence a nižší chybové prahy než algoritmy používající flooding. Tyto nižší chybové prahy jsou dosaženy díky schopnosti algoritmu Informed Dynamic Scheduling (IDS) zabránit uvěznění sad blízkých kódových slov.

Při použití nezáplavových (anglicky nonflooding) plánovacích algoritmů se používá jiná definice iterace. Pro (n, k) LDPC kód s poměrem k/n se jedná o plnou iteraci, pokud byla aktualizována proměnná n a uzly omezení n − k, bez ohledu na pořadí aktualizace.

Dekódování s vyhledávací tabulkou

LDPC kódy lze dekódovat mikroprocesorem s poměrně nízkým výkonem díky použití vyhledávacích tabulek.

Zatímco kódy jako například LDPC se obecně implementují na procesorech s vysokým výkonem pro velké délky bloku, existují také aplikace, které používají procesory s nižším výkonem a malou délkou bloku (1024).

Proto je možné předem spočítat výstupní bit na základě předem určených vstupních bitů. Lze vygenerovat tabulku, která obsahuje n položek (pro délku bloku 1024 bitů bude dlouhá 1024 bitů) a obsahuje všechny možné položky pro všechny možné vstupní stavy (chybové i nechybové).

Jednotlivé vstupní bity pak vstupují do posuvného registru, jehož hodnota se použije pro vyhledání relevantního výstupu v tabulce obsahující předpočítané hodnoty.

Tato metoda vyžaduje velkou paměť pro vyhledávací tabulku, ale nároky na procesor jsou relativně malé, takže dekódování LDPC je možné dokonce na PIC čipu s hodinovou frekvencí 4 MHz.

Konstrukce kódu

Při konstrukci LDPC kódů pro velké bloky se obvykle začíná studiem chování dekodérů. Pro velikost bloku blížící se k nekonečnu lze ukázat, že pokud je šumová mez LDPC dekodéru nižší, pak je dekódování spolehlivé, a pokud je vyšší, pak dekódování nefunguje, což se hovorově označuje jako efekt útesu. Tuto mez lze optimalizovat hledáním nejlepšího poměru mezi hranami z kontrolních uzlů a z proměnných uzlů. Přibližný grafický přístup k zobrazování toto mez je EXIT tabulka.

Pro konstrukci určitého LDPC kódu po této optimalizaci lze použít dvě hlavní techniky:

• Pseudonáhodné přístupy
• Kombinatorické přístupy

Konstrukce pseudonáhodným přístupem vychází z teoretických výsledků, podle kterých náhodná konstrukce dává pro velké bloky dobrou dekódovací výkonnost. Pseudonáhodné kódy mají obecně složité kodéry, ale pseudonáhodné kódy s nejlepšími dekodéry mohou mít kodéry jednoduché. Často se aplikují různá omezení, aby se zajistilo, že požadované vlastnosti očekávané při teoretickém limitu nekonečné velikosti bloku se objeví i pro bloky konečné velikosti.

Pro optimalizaci vlastností LDPC kódů pro bloky malé velikosti a pro vytváření kódů s jednoduchými kodéry lze použít kombinatorické přístupy.

Některé LDPC kódy vycházejí z Reedových–Solomonových kódů, například RS-LDPC kód používaný ve standardu 10gigabitového Ethernetu. Sestrojení hardwaru pro strukturované LDPC kódy může být jednodušší a proto levnější než pro náhodně generované LDPC kódy, například pokud H je cirkulantní matice; příkladem je LDPC kód používaný ve standardu DVB-S2.

Jiný způsob konstrukce LDPC kódů používá konečné geometrie. Tuto metodu navrhl Y. Kou a kolektiv v roce 2001.

LDPC kódy vs. turbokódy

LDPC kódy lze porovnat s jinými výkonnými kódování schémata, například turbokódy. Na jedné straně je bitová chybovost (BER) turbokódů ovlivněna jejich nízkými omezeními; LDPC kódy nemají žádné omezení minimální vzdálenosti, což nepřímo znamená, že LDPC kódy může být efektivnější při relativně velkém rozsahu kódových poměrů (například 3/4, 5/6, 7/8) než turbokódy. Nicméně LDPC kódy nejsou jejich úplnou náhradou: turbokódy jsou nejlepším řešením pro nižší kódové poměry (například 1/6, 1/3, 1/2).

People

• Robert G. Gallager
• Richard Hamming
• Claude Shannon
• David J. C. MacKay
• Irving S. Reed
• Michael Luby

Teorie

• Šíření přesvědčení
• Teorie grafů
• Hammingův kód
• Lineární kód
• Řídký grafový kód
• Expandérový kód

Aplikace

• G.hn/G.9960 (ITU-T Standard pro přenos dat energetickým vedením, telefonními linkami a koaxiálními kabely)
• 802.3an nebo 10GBASE-T (10 Giga-bit/s Ethernet po kroucené dvojlince)
• CMMB (China Multimedia Mobile Broadcasting)
• DVB-S2 / DVB-T2 / DVB-C2 (Digitální vysílání televize 2. generace)
• DMB-T/H (Digitální plošné vysílání videa)
• WiMAX (IEEE 802.16e standard pro mikrovlnnou komunikaci)
• IEEE 802.11n-2009 (Wi-Fi standard)
• DOCSIS 3.1

Jiné kódy s výkonností blízkou kapacitě kanálu

• Turbokódy
• Sériové zřetězené konvoluční kódy
• Spřažené kódy
• Fountain kódy
• LT kódy
• Raptor kódy
• Opakovací akumulační kódy (třída jednoduchých turbokódů)
• Tornádo kódy (LDPC kódy navržené pro kanál s binárním vymazáváním)
• Polární kódy

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Low-density parity-check code na anglické Wikipedii.

Externí odkazy

• Introducing Low-Density Parity-Check Codes (by Sarah J Johnson, 2010) Archivováno 7. 11. 2019 na Wayback Machine.
• LDPC Codes – a brief Tutorial (by Bernhard Leiner, 2005)
• LDPC Codes (TU Wien) Archivováno 28. 2. 2019 na Wayback Machine.
• The on-line textbook: Information Theory, Inference, and Learning Algorithms, by David J.C. MacKay, discusses LDPC codes in Chapter 47.
• Iterative Decoding of Low-Density Parity Check Codes (by Venkatesan Guruswami, 2006)
• LDPC Codes: An Introduction (by Amin Shokrollahi, 2003) Archivováno 17. 5. 2017 na Wayback Machine.
• Belief-Propagation Decoding of LDPC Codes (by Amir Bennatan, Princeton University)
• Turbo and LDPC Codes: Implementation, Simulation, and Standardization (West Virginia University)
• Information theory and coding (Marko Hennhöfer, 2011, TU Ilmenau) Archivováno 30. 8. 2017 na Wayback Machine. - diskutuje LDPC kódy na stranách 74-78.
• LDPC codes and performance results
• DVB-S.2 Link, Including LDPC Coding (MatLab)
• Zdrojový kód pro kódování, dekódování a simulaci LDPC kódů je dostupný na různých místech:
  • Binary LDPC codes in C
  • Binary LDPC codes for Python (hlavní algoritmus v jazyce C)
  • LDPC encoder and LDPC decoder in MATLAB
  • A Fast Forward Error Correction Toolbox rychlé simulace LDPC v C++11 – viz AFF3CT