Kod med låg densitet av paritetskontroller

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 22 maj 2020; kontroller kräver 7 redigeringar .

Low-density parity -check code ( LDPC-kod från engelskan. Low-density parity-check code, LDPC-code , low- density code ) är en kod som används vid informationsöverföring, ett specialfall av en linjär blockkod med paritet kolla upp. En funktion är den låga tätheten av viktiga element i kontrollmatrisen , på grund av vilken den relativa enkelheten i implementeringen av kodningsverktyg uppnås.

Kallas även Gallagher-koden , efter författaren till det första verket på ämnet LDPC-koder.

Bakgrund

1948 publicerade Shannon sitt arbete om teorin om informationsöverföring. Ett av de viktigaste resultaten av arbetet är informationsöverföringssatsen för en bullrig kanal , som indikerar möjligheten att minimera sannolikheten för ett överföringsfel över kanalen genom att välja en tillräckligt stor nyckelordslängd - en informationsenhet som sänds över kanalen [ 1] .

Vid överföring av information delas dess ström in i block av en viss (oftast) längd, som omvandlas av kodaren (kodas) till block som kallas nyckelord. Nyckelord sänds över kanalen, eventuellt med distorsion. På den mottagande sidan omvandlar avkodaren nyckelorden till en ström av information och korrigerar (om möjligt) överföringsfel.

Shannons teorem säger att under vissa förutsättningar kan sannolikheten för ett avkodningsfel (det vill säga avkodarens oförmåga att korrigera ett överföringsfel) minskas genom att välja en längre nyckelordslängd. Denna sats (och arbetet i allmänhet) visar dock inte hur man väljer en stor längd, utan snarare hur man effektivt organiserar processen att koda och avkoda information med en stor längd av nyckelord. Om vi antar att kodaren och avkodaren har några överensstämmelsetabeller mellan inmatningsblocket med information och motsvarande kodord, kommer sådana tabeller att ta upp mycket utrymme. För en binär symmetrisk kanal utan minne (för att uttrycka det enkelt, kodarens ingång är en ström av nollor och ettor) är antalet olika block 2 n , där n är antalet bitar (nollor eller ettor) som kommer att vara omvandlas till ett kodord. För 8 bitar är dessa 256 informationsblock, som vart och ett kommer att innehålla motsvarande kodord. Dessutom är kodordet vanligtvis längre, eftersom det innehåller ytterligare bitar för att skydda mot dataöverföringsfel. Därför är en av kodningsmetoderna användningen av en kontrollmatris, som tillåter avkodning av kodordet i en matematisk operation (multiplicera en rad med en matris). På ett liknande sätt motsvarar varje kontrollmatris en genererande matris , på ett liknande sätt, genom en operation att multiplicera en rad med en matris som genererar ett kodord.

För relativt korta kodord kan kodare och avkodare helt enkelt lagra alla möjliga alternativ i minnet, eller till och med implementera dem i form av en halvledarkrets. För ett större kodord är det mer effektivt att lagra generatorn och paritetsmatrisen. Men med blocklängder på flera tusen bitar blir lagring av matriser med respektive storlek i megabit redan ineffektiv. Ett av sätten att lösa detta problem är att använda koder med låg densitet av paritetskontroller, när antalet enheter i paritetskontrollmatrisen är relativt litet, vilket gör det möjligt att organisera matrislagringsprocessen mer effektivt eller direkt implementera avkodningsprocessen med hjälp av en halvledarkrets.

Det första arbetet med detta ämne var Robert Gallaghers 1963 Low-Density Parity-Check Codes [2] (som grundades i hans doktorsavhandling 1960 ). I arbetet beskrev forskaren kraven på sådana koder, beskrev möjliga konstruktionsmetoder och metoder för deras utvärdering. Därför kallas LDPC-koder ofta för Gallagher-koder. I rysk vetenskaplig litteratur kallas koder även för lågdensitetskoder eller koder med låg densitet av paritetskontroller.

Men på grund av svårigheten att implementera kodare och avkodare, användes dessa koder inte och glömdes bort tills Gallaghers verk återupptäcktes 1996 [3] [4] . Med utvecklingen av telekommunikationsteknologier har intresset för att överföra information med minimala fel ökat igen. Trots komplexiteten i implementeringen jämfört med turbokoden , gjorde avsaknaden av hinder för användning (oskyddade av patent) LDPC-koder attraktiva för telekommunikationsindustrin, och blev i själva verket standarden de facto. 2003 blev LDPC-koden, istället för turbokoden, en del av DVB-S2- standarden för satellitdataöverföring för digital-tv. En liknande ersättning har skett i DVB-T2-standarden för digital marksänd tv-sändning [5] .

LDPC-koder

LDPC-koder beskrivs av en paritetsmatris med låg densitet som innehåller mestadels nollor och ett relativt litet antal ettor. Per definition, om varje rad i matrisen innehåller exakt och varje kolumn innehåller exakt ettor, kallas koden regelbunden (annars, oregelbunden ). I det allmänna fallet har antalet ettor i matrisen storleksordningen , det vill säga det växer linjärt med en ökning av längden på kodblocket (antalet kolumner i kontrollmatrisen). $k<n$ $j<r$ $O\left(n\right)$

Matriser av stora storlekar övervägs vanligtvis. Till exempel använder Gallaghers arbete i avsnittet med experimentella resultat "små" antal rader n=124, 252, 504 och 1008 rader (antalet kolumner i kontrollmatrisen är något större). I praktiken används matriser med ett stort antal element - från 10 till 100 tusen rader. Antalet ettor per rad eller kolumn förblir dock ganska litet, vanligtvis mindre än 10. Det har observerats att koder med samma antal element per rad eller kolumn, men med en större storlek, har bättre prestanda.

En viktig egenskap hos LDPC-kodmatrisen är frånvaron av cykler av en viss storlek. En cykel av längd 4 förstås som bildandet av en rektangel i kontrollmatrisen, i vars hörn det finns enheter. Frånvaron av en cykel med längd 4 kan också bestämmas genom den skalära produkten av kolumnerna (eller raderna) i matrisen. Om varje parvis skalär produkt av alla kolumner (eller rader) i matrisen inte är mer än 1, indikerar detta frånvaron av en cykel med längd 4. Cykler med längre längd (6, 8, 10, etc.) kan vara bestäms om en graf är inbyggd i kontrollmatrisen , med hörn vars kanter är alla möjliga anslutningar av hörn parallella med matrisens sidor (det vill säga vertikala eller horisontella linjer). Den minsta cykeln i denna kolumn kommer att vara den minsta cykeln i kontrollmatrisen för LDPC-koden. Uppenbarligen kommer cykeln att ha en längd på minst 4, inte 3, eftersom kanterna på grafen måste vara parallella med matrisens sidor. I allmänhet kommer varje cykel i denna graf att ha en jämn längd, den minsta storleken är 4, och den maximala storleken spelar vanligtvis ingen roll (även om det uppenbarligen inte är fler än antalet noder i grafen, det vill säga n × k).

Beskrivningen av LDPC-koden är möjlig på flera sätt:

kontrollera matris
tvådelad graf
ett annat grafiskt sätt
speciella sätt

Den senare metoden är en konventionell beteckning för en grupp kodrepresentationer som är byggda enligt givna regler-algoritmer, så att för att återskapa koden igen räcker det med att bara känna till algoritmens initialiseringsparametrar, och naturligtvis , själva konstruktionsalgoritmen. Denna metod är dock inte universell och kan inte beskriva alla möjliga LDPC-koder.

Metoden att specificera en kod med en kontrollmatris är allmänt accepterad för linjära koder, när varje rad i matrisen är ett element i en viss uppsättning kodord. Om alla rader är linjärt oberoende, kan raderna i matrisen betraktas som basen för uppsättningen av alla kodvektorer i koden. Användningen av denna metod skapar emellertid svårigheter för att representera matrisen i kodarens minne - det är nödvändigt att lagra alla rader eller kolumner i matrisen som en uppsättning binära vektorer, på grund av vilka storleken på matrisen blir lika med bitar . $j\times k$

Ett vanligt grafiskt sätt är att representera koden som en tvådelad graf. Låt oss jämföra alla rader i matrisen med grafens nedre hörn, och alla kolumner med de övre hörnen, och koppla samman de övre och nedre hörnen av grafen om det finns enheter i skärningspunkten mellan motsvarande rader och kolumner. $k$ $k$ $n$

Andra grafiska metoder inkluderar tvådelade graftransformationer som sker utan att faktiskt ändra själva koden. Till exempel kan du representera alla de övre hörnen i grafen som trianglar och alla de nedre hörnen som kvadrater, och sedan arrangera kanterna och hörnen på grafen på en tvådimensionell yta i en ordning som är bekväm för visuell förståelse av kodstrukturen. Till exempel används en sådan representation som illustrationer i böcker av David McKay.

Genom att införa ytterligare regler för grafisk visning och konstruktion av LDPC-koden är det möjligt att uppnå att koden får vissa egenskaper under byggprocessen. Till exempel, om vi använder en graf vars hörn bara är kolumnerna i kontrollmatrisen, och raderna representeras av polyedrar som är byggda på grafens hörn, tillåter vi att följa regeln "två polyedrar delar inte en kant" bli av med cykler av längd 4.

När man använder speciella kodkonstruktionsprocedurer kan deras egna metoder för representation, lagring och bearbetning (kodning och avkodning) användas.

Kodbyggande

För närvarande används två principer för att konstruera en kodkontrollmatris. Den första är baserad på att generera en initial kontrollmatris med hjälp av en pseudoslumpgenerator. Koder som erhålls på detta sätt kallas random ( engelska random-like codes ). Den andra är användningen av speciella metoder baserade till exempel på grupper och slutfält . Koder som erhålls med dessa metoder kallas strukturerade koder . Det är slumpmässiga koder som visar de bästa resultaten vid felkorrigering, men strukturerade koder tillåter användning av metoder för att optimera lagrings-, kodnings- och avkodningsprocedurer, samt erhålla koder med mer förutsägbara egenskaper.

I sitt arbete valde Gallagher att använda en pseudo-slumptalsgenerator för att skapa en initial liten checkmatris med specificerade egenskaper, och sedan öka dess storlek genom att duplicera matrisen [6] och använda metoden att blanda rader och kolumner för att få bli av med cykler av en viss längd.

2003 föreslog James McGowan och Robert Williamson ett sätt att ta bort cykler från matrisen för en LDPC-kod, och därför blev det möjligt att först generera en matris med givna egenskaper (n, j, k) och sedan ta bort cykler från den. Detta är vad som händer i Ozarov-Weiner-schemat [7] .

2007 publicerades en artikel i tidskriften "IEEE Transactions on Information Threory" om användningen av finita fält för att konstruera kvasicykliska LDPC-koder för additiv vita Gaussiska bruskanaler och binära raderingskanaler.

För att öka dimensionen på koden kan en multipel slutprodukt av genererande matriser användas [6] .

Avkodning

Som för alla andra linjära koder används ortogonalitetsegenskapen för de genererande och transponerade kontrollmatriserna för avkodning:

G\odot H^{T}=0

där är den genererande matrisen, och är kontrollmatrisen , är symbolen för multiplikation modulo 2 (om ett tal som är en multipel av 2 erhålls som ett element i den resulterande matrisen, så skrivs noll istället). Sedan, för varje kodord som tas emot utan fel, relationen $G$ $H$ $\odot$

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

och för det mottagna kodordet med ett fel:

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

där är den accepterade vektorn, är syndromet . Om noll erhålls, efter att ha multiplicerat det mottagna kodordet med den transponerade paritetsmatrisen, anses blocket mottaget utan fel. Annars används speciella metoder för att lokalisera felet och rätta till det. För en LDPC-kod visar sig standardkorrigeringsmetoderna vara för tidskrävande - de klassificeras som NP-kompletta problem, som med tanke på den stora blocklängden inte kan tillämpas i praktiken. Istället använder de metoden probabilistisk iterativ avkodning, som korrigerar en stor del av felen bortom halva kodavståndet [8] . $v$ $s$

Betrakta [9] en symmetrisk minneslös kanal med input och additivt Gaussiskt brus . För det mottagna kodordet måste man hitta den motsvarande mest sannolika vektorn , så att $\pm a$ $\sigma ^{2}=1$ $y$ $x$

H\odot x=0\mod 2

Låt oss definiera $f_{n}^{1}={1/{\mathord {\left(1+\exp \left(-2ay_{n}/{\mathord {\sigma ^{2))}\right) \höger)}}}$ ; ${\displaystyle f_{n}^{0}=1-f_{n}^{1))$ ; där är det mottagna värdet för den n:te symbolen i kodordet (som för en given kanal har ett godtyckligt värde, vanligtvis inom ). $y_{n}$ $\pm (a+3\sigma )$
Vi kommer att använda ordet "bit" för att beteckna individuella element i vektorn , och ordet "check" för att beteckna rader i kontrollmatrisen . Beteckna med den uppsättning bitar som kommer att delta i den m:te kontrollen. På liknande sätt, låt oss beteckna uppsättningen kontroller där bit n deltar. (Det vill säga, vi listar indexen för element som inte är noll för varje rad och för varje kolumn i kontrollmatrisen ). $x$ $H$ $N\left(m\right)\equiv \{n:H_{nm}=1\}$ $M\left(n\right)\equiv \{m:H_{nm}=1\}$ $H$
Vi initialiserar matriser och värden resp $q_{mn}^{0}$ ${\displaystyle q_{mn}^{1))$ ${\displaystyle f_{n}^{0))$ ${\displaystyle f_{n}^{1))$
(horisontellt steg) ${\displaystyle \delta q_{mn}=q_{mn}^{0}-q_{mn}^{1))$ $\delta r_{mn}=\prod \limits _{n'\in N(m)\backslash n}{\delta q_{mn'}}$ $r_{mn}^{0}={1 \över 2}\left({1+\delta r_{mn}}\right)$ $r_{mn}^{1}={1 \över 2}\left({1-\delta r_{mn}}\right)$
(vertikal stigning) $q_{mn}^{0}=\alpha _{mn}f_{n}^{0}\prod \limits _{m'\in M\left(n\right)\backslash m}{r_ {m'n}^{0}}$ $q_{mn}^{1}=\alpha _{mn}f_{n}^{1}\prod \limits _{m'\in M\left(n\right)\backslash m}{r_ {m'n}^{1}}$ där för varje och vald ger: $m$ $n$ $\alpha _{mn}$ $q_{mn}^{0}+q_{mn}^{1}=1$ Nu uppdaterar vi också de "pseudo-posteriora sannolikheterna" som vektorns bitar tar på värdena 0 eller 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}^ {ett}}$ Också, som tidigare, väljs på ett sådant sätt att $\alpha_{n}$ $q_{n}^{0}+q_{n}^{1}=1$

Dessa värden används för att återskapa x-vektorn. Om den resulterande vektorn uppfyller , avbryts algoritmen, annars upprepas de horisontella och vertikala stegen. Om algoritmen fortsätter upp till ett visst steg (till exempel 100), så avbryts den och blocket förklaras accepterat med ett fel. $H\odot x=0\mod 2$

Det är känt att denna algoritm ger det exakta värdet på vektorn (det vill säga sammanfaller med de klassiska metoderna) om kontrollmatrisen inte innehåller cykler [10] . $x$ $H$

Anteckningar

↑ Shannon CE En matematisk teori om kommunikation // Bell System Technical Journal. - 1948 . - T. 27 . - S. 379-423, 623-656 .
↑ Gallager, R. G. Kontrollkoder för lågdensitetsparitet . — Cambridge : MIT Press, 1963 . — S. 90.
↑ David JC MacKay och Radford M. Neal, "Near Shannon Limit Performance of Low Density Parity Check Codes," Electronics Letters, juli 1996
↑ David JC MacKay. Informationsteori, slutlednings- och inlärningsalgoritmer . - CUP, 2003. - ISBN 0-521-64298-1 .
↑ Dr. Lin Nan Lee. LDPC-koder, tillämpning på nästa generations kommunikationssystem // IEEE Semiannual Vehicular Technology Conference. - Oktober 2003. Arkiverad från originalet den 8 oktober 2006.
↑ 1 2 Slyusar V. I. Syntes av LDPC och polära koder baserat på slutprodukten av matriser.// Development of Education, Science and Business: Results 2020: abstracts of the International Scientific and Practical Internet Conference, 3-4 december 2020. – Del 2. - S. 393-396. [1] Arkiverad 25 januari 2021 på Wayback Machine .
↑ Yu.V. Kosolapov. Om tillämpningen av Ozarov-Weiner-schemat för informationsskydd i trådlösa flerkanaliga dataöverföringssystem // Information Counteraction to Terrorism Threats : Scientific and Practical Journal. — 2007 . - Nr 10 . - S. 111-120 . Arkiverad från originalet den 24 juni 2013.
↑ V. B. Afanasiev, D. K. Zigangirov "Om vissa konstruktioner av lågdensitetskoder med en komponent Reed-Solomon-kod"
↑ David JC MacKay, Radford M. Neal nära Shannon Limit Performance of Low Density Parity Check Codes . Hämtad 28 augusti 2008. Arkiverad från originalet 17 april 2007. (obestämd)
↑ J. Pearl. Probabilistiska resonemang i intelligenta system: nätverk av rimliga slutledningar. Morgan Kaufmann, San Mateo, 1988.