Kód s nízkou hustotou paritních kontrol

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 22. května 2020; kontroly vyžadují 7 úprav .

Low-density parity -check code ( LDPC-code z angl. Low-density parity-check code, LDPC-code , low- density code ) je kód používaný při přenosu informací, speciální případ blokového lineárního kódu s paritou . šek. Charakteristickým rysem je nízká hustota významných prvků kontrolní matice , díky které je dosaženo relativní jednoduchosti implementace kódovacích nástrojů.

Také nazývaný Gallagherův kód podle autora první práce na téma LDPC kódů.

Pozadí

V roce 1948 Shannon publikoval svou práci o teorii přenosu informace. Jedním z klíčových výsledků práce je teorém přenosu informace pro zašuměný kanál , který naznačuje možnost minimalizace pravděpodobnosti chyby přenosu na kanálu volbou dostatečně velké délky klíčového slova -- jednotky informace přenášené kanálem [ 1] .

Při přenosu informace je její proud rozdělen do bloků určité (nejčastěji) délky, které jsou kodérem převedeny (zakódovány) na bloky zvané klíčová slova. Klíčová slova jsou přenášena kanálem, možná se zkreslením. Na přijímací straně dekodér převádí klíčová slova na proud informací a opravuje (pokud je to možné) chyby přenosu.

Shannonova věta říká, že za určitých podmínek lze snížit pravděpodobnost chyby dekódování (tedy neschopnosti dekodéru opravit chybu přenosu) volbou delší délky klíčového slova. Tato věta (a práce obecně) však neukazuje, jak volit velkou délku, ale spíše jak efektivně organizovat proces kódování a dekódování informací s velkou délkou klíčových slov. Pokud předpokládáme, že kodér a dekodér mají nějaké korespondenční tabulky mezi vstupním blokem informací a odpovídajícím kódovým slovem, pak takové tabulky zaberou hodně místa. Pro binární symetrický kanál bez paměti (zjednodušeně řečeno, vstup kodéru je proud nul a jedniček) je počet různých bloků 2 n , kde n je počet bitů (nul nebo jedniček), které budou převedeny na jedno kódové slovo. Pro 8 bitů se jedná o 256 bloků informací, z nichž každý bude obsahovat odpovídající kódové slovo. Kromě toho je kódové slovo obvykle delší, protože obsahuje další bity na ochranu před chybami přenosu dat. Jedním ze způsobů kódování je proto použití kontrolní matice, která umožňuje dekódování kódového slova v jedné matematické operaci (vynásobení řádku maticí). Podobným způsobem každá kontrolní matice odpovídá generující matici , podobným způsobem, jednou operací násobení řádku maticí generující kódové slovo.

Pro relativně krátká kódová slova tedy mohou kodéry a dekodéry jednoduše uložit všechny možné možnosti do paměti, nebo je dokonce implementovat ve formě polovodičového obvodu. Pro větší kódové slovo je efektivnější uložit generátor a paritní matici. Při délkách bloků několik tisíc bitů se však ukládání matic o velikosti, respektive v megabitech , již stává neefektivním. Jedním ze způsobů, jak tento problém vyřešit, je použití kódů s nízkou hustotou paritních kontrol, kdy je počet jednotek v matici paritní kontroly relativně malý, což umožňuje organizovat proces ukládání matice efektivněji nebo přímo. implementovat proces dekódování pomocí polovodičového obvodu.

První prací na toto téma byla práce Roberta Gallaghera z roku 1963 Low-Density Parity-Check Codes [2] (která byla založena v jeho Ph.D. práci z roku 1960 ). V práci vědec popsal požadavky na takové kódy, popsal možné konstrukční metody a způsoby jejich vyhodnocení. Proto se kódy LDPC často nazývají Gallagherovy kódy. V ruské vědecké literatuře se kódy také nazývají kódy s nízkou hustotou nebo kódy s nízkou hustotou kontroly parity.

Vzhledem k obtížnosti implementace kodérů a dekodérů však tyto kódy nebyly použity a byly zapomenuty, dokud nebyla v roce 1996 znovu objevena Gallagherova práce [3] [4] . S rozvojem telekomunikačních technologií opět vzrostl zájem o přenos informací s minimální chybovostí. Navzdory složitosti implementace ve srovnání s turbo kódem , nedostatek překážek pro použití (nechráněných patenty) učinil LDPC kódy atraktivní pro telekomunikační průmysl a ve skutečnosti se staly de facto standardem. V roce 2003 se kód LDPC namísto turbo kódu stal součástí standardu satelitního přenosu dat DVB-S2 pro digitální televizi. K podobnému nahrazení došlo i ve standardu DVB-T2 pro digitální pozemní televizní vysílání [5] .

LDPC kódy

Kódy LDPC jsou popsány pomocí matice parity s nízkou hustotou obsahující většinou nuly a relativně malý počet jedniček. Pokud každý řádek matice obsahuje přesně jedničky a každý sloupec obsahuje přesně jedničky, pak se kód podle definice nazývá regulární (jinak nepravidelný ). V obecném případě má počet jedniček v matici řád , to znamená, že roste lineárně se zvětšováním délky bloku kódu (počtu sloupců kontrolní matice). $k<n$ $j<r$ $O\left(n\right)$

Obvykle se uvažují matice velkých rozměrů. Například Gallagherova práce v sekci experimentálních výsledků používá „malé“ počty řádků n=124, 252, 504 a 1008 řádků (počet sloupců kontrolní matice je o něco větší). V praxi se používají matice s velkým počtem prvků - od 10 do 100 tisíc řádků. Počet jednotek na řádek nebo sloupec však zůstává poměrně malý, obvykle méně než 10. Bylo pozorováno, že kódy se stejným počtem prvků na řádek nebo sloupec, ale s větší velikostí, mají lepší výkon.

Důležitou charakteristikou kódové matice LDPC je absence cyklů určité velikosti. Cyklus délky 4 je chápán jako vytvoření obdélníku v kontrolní matici, v jehož rozích jsou jednotky. Absenci cyklu délky 4 lze také určit pomocí skalárního součinu sloupců (nebo řádků) matice. Pokud každý párový skalární součin všech sloupců (nebo řádků) matice není větší než 1, znamená to nepřítomnost cyklu délky 4. Cykly větší délky (6, 8, 10 atd.) mohou být určuje, zda je v kontrolní matici zabudován graf s vrcholy, jejichž hrany jsou všechna možná spojení vrcholů rovnoběžných se stranami matice (tj. svislé nebo vodorovné čáry). Minimální cyklus v tomto sloupci bude minimálním cyklem v kontrolní matici kódu LDPC. Je zřejmé, že cyklus bude mít délku alespoň 4, nikoli 3, protože okraje grafu musí být rovnoběžné se stranami matice. Obecně platí, že jakýkoli cyklus v tomto grafu bude mít sudou délku, minimální velikost je 4 a na maximální velikosti obvykle nezáleží (ačkoli to samozřejmě není více než počet uzlů v grafu, tedy n × k).

Popis kódu LDPC je možný několika způsoby:

kontrolní matice
bipartitní graf
jiný grafický způsob
zvláštní způsoby

Posledně jmenovaný způsob je konvenční označení pro skupinu reprezentací kódu, které jsou sestaveny podle daných pravidel-algoritmů, takže k opětovné reprodukci kódu stačí znát pouze inicializační parametry algoritmu a samozřejmě , samotný konstrukční algoritmus. Tato metoda však není univerzální a nemůže popsat všechny možné kódy LDPC.

Metoda zadávání kódu pomocí kontrolní matice je obecně přijímána pro lineární kódy, kdy každý řádek matice je prvkem určité sady kódových slov. Pokud jsou všechny řádky lineárně nezávislé, lze řádky matice považovat za základ množiny všech kódových vektorů kódu. Použití této metody však vytváří potíže pro reprezentaci matice v paměti kodéru - je nutné uložit všechny řádky nebo sloupce matice jako sadu binárních vektorů, díky čemuž se velikost matice rovná bitům . $j\times k$

Běžným grafickým způsobem je reprezentovat kód jako bipartitní graf. Porovnejme všechny řádky matice s dolními vrcholy grafu a všechny sloupce s horními vrcholy a spojme horní a dolní vrcholy grafu, pokud jsou na průsečíku odpovídajících řádků a sloupců jednotky. $k$ $k$ $n$

Mezi další grafické metody patří transformace bipartitních grafů, ke kterým dochází bez skutečné změny samotného kódu. Můžete například znázornit všechny horní vrcholy grafu jako trojúhelníky a všechny spodní vrcholy jako čtverce a poté uspořádat okraje a vrcholy grafu na dvourozměrném povrchu v pořadí, které je vhodné pro vizuální pochopení strukturu kódu. Například takové znázornění se používá jako ilustrace v knihách Davida McKaye.

Zavedením dalších pravidel pro grafické zobrazení a konstrukci kódu LDPC je možné dosáhnout toho, že kód během procesu konstrukce získá určité vlastnosti. Pokud například použijeme graf, jehož vrcholy jsou pouze sloupce kontrolní matice a řádky jsou reprezentovány mnohostěny postavenými na vrcholech grafu, pak dodržení pravidla „dva mnohostěny nesdílejí jednu hranu“ nám umožňuje zbavit se cyklů délky 4.

Při použití speciálních postupů konstrukce kódu lze použít jejich vlastní metody reprezentace, ukládání a zpracování (kódování a dekódování).

Tvorba kódu

V současné době se používají dva principy pro konstrukci kontrolní matice kódu. První je založen na generování počáteční kontrolní matice pomocí pseudonáhodného generátoru. Takto získané kódy se nazývají náhodné ( anglicky random-like codes ). Druhým je použití speciálních metod založených například na skupinách a finálních polích . Kódy získané těmito metodami se nazývají strukturované kódy . Jsou to náhodné kódy, které vykazují nejlepší výsledky v opravě chyb, nicméně strukturované kódy umožňují použití metod pro optimalizaci postupů ukládání, kódování a dekódování a také získávání kódů s předvídatelnějšími charakteristikami.

Gallagher se ve své práci rozhodl použít generátor pseudonáhodných čísel k vytvoření počáteční kontrolní matice malé velikosti se specifikovanými charakteristikami a poté zvětšil její velikost duplikací matice [6] a použitím metody míchání řádků a sloupců k získání zbavit cyklů určité délky.

V roce 2003 James McGowan a Robert Williamson navrhli způsob, jak odstranit cykly z matice kódu LDPC, a proto bylo možné nejprve vygenerovat matici s danými charakteristikami (n, j, k) a poté z ní cykly odstranit. To se děje v Ozarov-Weinerově schématu [7] .

V roce 2007 byl v časopise „IEEE Transactions on Information Threory“ publikován článek o použití konečných polí ke konstrukci kvazicyklických LDPC kódů pro aditivní kanály bílého gaussovského šumu a kanály binárního výmazu.

Pro zvětšení dimenze kódu lze použít vícenásobný konečný produkt generování matic [6] .

Dekódování

Stejně jako u jakéhokoli jiného lineárního kódu se pro dekódování používá vlastnost ortogonality generujících a transponovaných kontrolních matic:

G\odot H^{T}=0

kde je generující matice a je kontrolní matice, je symbol násobení modulo 2 (pokud je jako prvek výsledné matice získáno číslo, které je násobkem 2, pak se místo toho zapíše nula). Potom pro každé kódové slovo přijaté bez chyb, vztah $G$ $H$ $\odot$

s=v\odot H^{T}=0

a pro přijaté kódové slovo s chybou:

s=v\odot H^{T}\neq 0

kde je přijímaný vektor, je syndrom . Jestliže se po vynásobení přijatého kódového slova transponovanou paritní maticí získá nula, blok je považován za přijatý bez chyb. V opačném případě se k nalezení chyby a její opravě používají speciální metody. U kódu LDPC se standardní korekční metody ukazují jako příliš časově náročné - jsou klasifikovány jako NP-úplné problémy, které vzhledem k velké délce bloku nelze v praxi aplikovat. Místo toho používají metodu pravděpodobnostního iterativního dekódování, která opravuje velkou část chyb za poloviční vzdáleností kódu [8] . $proti$ $s$

Uvažujme [9] symetrický bezpaměťový kanál se vstupem a aditivním Gaussovým šumem . Pro přijaté kódové slovo je třeba najít odpovídající nejpravděpodobnější vektor , např $\pm a$ $\sigma ^{2}=1$ $y$ $X$

H\odot x=0\mod 2

Pojďme definovat $f_{n}^{1}={1/{\mathord {\left(1+\exp \left(-2ay_{n}/{\mathord {\sigma ^{2))}\right) \že jo)}}}$ ; $f_{n}^{0}=1-f_{n}^{1}$ ; kde je přijatá hodnota n-tého symbolu kódového slova (které má pro daný kanál libovolnou hodnotu, obvykle v rámci ). $y_{n}$ $\pm (a+3\sigma )$
Pro označení jednotlivých prvků vektoru použijeme slovo "bit" a pro označení řádků kontrolní matice slovo "check" . Označme množinou bitů, které se budou podílet na m-té kontrole. Podobně označme množinu kontrol, kterých se bit n účastní. (To znamená, že uvádíme indexy nenulových prvků pro každý řádek a pro každý sloupec kontrolní matice ). $X$ $H$ ${\displaystyle N\left(m\right)\equiv \{n:H_{nm}=1\))$ ${\displaystyle M\left(n\right)\equiv \{m:H_{nm}=1\))$ $H$
Inicializujeme matice a hodnoty resp ${\displaystyle q_{mn}^{0))$ ${\displaystyle q_{mn}^{1))$ ${\displaystyle f_{n}^{0))$ ${\displaystyle f_{n}^{1))$
(horizontální krok) ${\displaystyle \delta q_{mn}=q_{mn}^{0}-q_{mn}^{1))$ $\delta r_{mn}=\prod \limits _{n'\in N(m)\obrácené lomítko n}{\delta q_{mn'}}$ $r_{mn}^{0}={1 \over 2}\left({1+\delta r_{mn}}\right)$ $r_{mn}^{1}={1 \over 2}\left({1-\delta r_{mn}}\right)$
(vertikální rozteč) $q_{mn}^{0}=\alpha _{mn}f_{n}^{0}\prod \limits _{m'\in M\left(n\right)\obrácené lomítko m}{r_ {m'n}^{0}}$ $q_{mn}^{1}=\alpha _{mn}f_{n}^{1}\prod \limits _{m'\in M\left(n\right)\obrácené lomítko m}{r_ {m'n}^{1}}$ kde pro každého a vybraného dává: $m$ $n$ $\alpha _{mn}$ $q_{mn}^{0}+q_{mn}^{1}=1$ Nyní také aktualizujeme "pseudoposteriorní pravděpodobnosti", že bity vektoru nabývají hodnot 0 nebo 1: $X$ $q_{n}^{0}=\alpha _{n}f_{n}^{0}\prod \limits _{m\in M\left(n\right)}{r_{mn}^ {0}}$ $q_{n}^{1}=\alpha _{n}f_{n}^{1}\prod \limits _{m\in M\left(n\right)}{r_{mn}^ {jeden}}$ Také, jako dříve, je vybrána takovým způsobem, že $\alpha_{n}$ $q_{n}^{0}+q_{n}^{1}=1$

Tyto hodnoty se používají k opětovnému vytvoření vektoru x. Pokud výsledný vektor vyhovuje , pak je algoritmus přerušen, jinak se horizontální a vertikální kroky opakují. Pokud algoritmus pokračuje až do určitého kroku (například 100), pak je přerušen a blok je prohlášen za přijatý s chybou. $H\odot x=0\mod 2$

Je známo, že tento algoritmus dává přesnou hodnotu vektoru (tedy shodující se s klasickými metodami), pokud kontrolní matice neobsahuje cykly [10] . $X$ $H$

Poznámky

↑ Shannon CE A Matematická teorie komunikace // Bell System Technical Journal. - 1948 . - T. 27 . - S. 379-423, 623-656 .
↑ Gallager, R. G. Low Density Parity Check Codes . — Cambridge : MIT Press, 1963 . — str. 90.
↑ David JC MacKay a Radford M. Neal, "Near Shannon Limit Performance of Low Density Parity Check Codes," Electronics Letters, červenec 1996
↑ David JC MacKay. Teorie informace, inference a algoritmy učení . - CUP, 2003. - ISBN 0-521-64298-1 .
↑ Dr. Lin Nan Lee. Kódy LDPC, aplikace na komunikační systémy nové generace // Semiannual Vehicular Technology Conference IEEE. - říjen 2003. Archivováno z originálu 8. října 2006.
↑ 1 2 Slyusar V. I. Syntéza LDPC a polárních kódů na základě konečného produktu matic.// Rozvoj vzdělávání, vědy a podnikání: Výsledky 2020: abstrakty Mezinárodní vědecké a praktické internetové konference, 3.–4. prosince 2020. – Část 2. - Pp. 393-396. [1] Archivováno 25. ledna 2021 na Wayback Machine .
↑ Yu.V. Kosolapov. O aplikaci Ozarov-Weinerova schématu pro ochranu informací v bezdrátových vícekanálových systémech přenosu dat // Information Counteration to Terrorism Threats: Scientific and Practical Journal. — 2007 . - č. 10 . - S. 111-120 . Archivováno z originálu 24. června 2013.
↑ V. B. Afanasiev, D. K. Zigangirov „O některých konstrukcích kódů s nízkou hustotou s komponentním Reed-Solomonovým kódem“
↑ David JC MacKay, Radford M. Neal Near Near Shannon Limit Performance of Low Density Parity Check Codes . Získáno 28. srpna 2008. Archivováno z originálu dne 17. dubna 2007. (neurčitý)
↑ J. Pearl. Pravděpodobnostní uvažování v inteligentních systémech: Sítě věrohodné inference. Morgan Kaufmann, San Mateo, 1988.