Kode med en lav tæthed af paritetstjek

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 22. maj 2020; checks kræver 7 redigeringer .

Low-density parity -check code ( LDPC-kode fra engelsk. Low-density parity-check code, LDPC-code , low- density code ) er en kode, der bruges i informationstransmission, et specialtilfælde af en lineær blokkode med paritet kontrollere. En funktion er den lave tæthed af væsentlige elementer i kontrolmatrixen , på grund af hvilken den relative enkelhed af implementeringen af kodningsværktøjer opnås.

Også kaldet Gallagher-koden , efter forfatteren af det første værk om emnet LDPC-koder.

Baggrund

I 1948 udgav Shannon sit arbejde om teorien om informationstransmission. Et af de vigtigste resultater af arbejdet er informationstransmissionssætningen for en støjende kanal , som angiver muligheden for at minimere sandsynligheden for en transmissionsfejl over kanalen ved at vælge en tilstrækkelig stor nøgleordslængde - en informationsenhed transmitteret over kanalen [ 1] .

Ved overførsel af information er dens strøm opdelt i blokke af en vis (oftest) længde, som konverteres af indkoderen (indkodet) til blokke kaldet nøgleord. Nøgleord sendes over kanalen, eventuelt med forvrængning. På den modtagende side konverterer dekoderen nøgleordene til en strøm af information og retter (hvis muligt) transmissionsfejl.

Shannons sætning siger, at sandsynligheden for en afkodningsfejl (det vil sige dekoderens manglende evne til at rette en transmissionsfejl) under visse betingelser kan reduceres ved at vælge en længere nøgleordslængde. Denne sætning (og arbejdet generelt) viser dog ikke, hvordan man vælger en stor længde, men derimod hvordan man effektivt organiserer processen med indkodning og afkodning af information med en stor længde af nøgleord. Hvis vi antager, at indkoderen og dekoderen har nogle korrespondancetabeller mellem inputblokken af information og det tilsvarende kodeord, så vil sådanne tabeller optage meget plads. For en binær symmetrisk kanal uden hukommelse (for at sige det enkelt, indkoderens input er en strøm af nuller og enere) er antallet af forskellige blokke 2 n , hvor n er antallet af bit (nuller eller enere), der vil være konverteret til ét kodeord. For 8 bit er disse 256 blokke af information, som hver vil indeholde det tilsvarende kodeord. Desuden er kodeordet normalt længere, da det indeholder yderligere bits for at beskytte mod datatransmissionsfejl. Derfor er en af kodningsmetoderne brugen af en kontrolmatrix, som gør det muligt at afkode kodeordet i én matematisk operation (multiplicere en række med en matrix). På en lignende måde svarer hver kontrolmatrix til en genererende matrix , på en lignende måde, ved én operation med at gange en række med en matrix, der genererer et kodeord.

For relativt korte kodeord kan indkodere og dekodere simpelthen gemme alle mulige muligheder i hukommelsen eller endda implementere dem i form af et halvlederkredsløb. For et større kodeord er det mere effektivt at gemme generatoren og paritetsmatrixen. Men med bloklængder på flere tusinde bit bliver lagring af matricer med henholdsvis en størrelse i megabit allerede ineffektiv. En af måderne at løse dette problem på er at bruge koder med en lav tæthed af paritetstjek, når antallet af enheder i paritetstjekmatricen er relativt lille, hvilket gør det muligt at organisere matrixlagringsprocessen mere effektivt eller direkte implementere afkodningsprocessen ved hjælp af et halvlederkredsløb.

Det første arbejde om dette emne var Robert Gallaghers 1963 Low-Density Parity-Check Codes [2] (som blev grundlagt i hans 1960 Ph.D.-afhandling ). I arbejdet beskrev videnskabsmanden kravene til sådanne koder, beskrev mulige konstruktionsmetoder og metoder til deres evaluering. Derfor kaldes LDPC-koder ofte Gallagher-koder. I russisk videnskabelig litteratur kaldes koder også lavdensitetskoder eller koder med lav tæthed af paritetstjek.

Men på grund af vanskeligheden med at implementere indkodere og dekodere, blev disse koder ikke brugt og blev glemt, indtil Gallaghers arbejde blev genopdaget i 1996 [3] [4] . Med udviklingen af telekommunikationsteknologier er interessen for at transmittere information med minimale fejl igen steget. På trods af kompleksiteten af implementeringen sammenlignet med turbokoden , gjorde manglen på barrierer for brug (ubeskyttet af patenter) LDPC-koder attraktive for telekommunikationsindustrien og blev faktisk de facto-standarden. I 2003 blev LDPC-koden, i stedet for turbokoden, en del af DVB-S2- satellitdatatransmissionsstandarden for digitalt tv. En lignende udskiftning har fundet sted i DVB-T2-standarden for digital jordbaseret tv-udsendelse [5] .

LDPC-koder

LDPC -koder er beskrevet af en lavdensitetsparitetsmatrix , der hovedsageligt indeholder nuller og et relativt lille antal enere. Per definition, hvis hver række i matrixen indeholder nøjagtigt, og hver kolonne indeholder nøjagtigt dem, kaldes koden regulær (ellers uregelmæssig ). I det generelle tilfælde har antallet af enere i matricen størrelsesordenen , det vil sige, at det vokser lineært med en stigning i længden af kodeblokken (antallet af kolonner i kontrolmatrixen). $k<n$ $j<r$ $O\left(n\right)$

Matricer af store størrelser overvejes normalt. For eksempel bruger Gallaghers arbejde i sektionen med eksperimentelle resultater "små" antal rækker n=124, 252, 504 og 1008 rækker (antallet af kolonner i kontrolmatrixen er lidt større). I praksis bruges matricer med et stort antal elementer - fra 10 til 100 tusinde rækker. Antallet af ener pr. række eller kolonne forbliver dog ret lille, normalt mindre end 10. Det er blevet observeret, at koder med det samme antal elementer pr. række eller kolonne, men med en større størrelse, har bedre ydeevne.

Et vigtigt kendetegn ved LDPC-kodematrixen er fraværet af cyklusser af en vis størrelse. En cyklus med længde 4 forstås som dannelsen af et rektangel i tjekmatricen, i hvis hjørner der er enheder. Fraværet af en cyklus med længde 4 kan også bestemmes gennem skalarproduktet af søjlerne (eller rækkerne) i matrixen. Hvis hvert parvist skalarprodukt af alle søjler (eller rækker) i matrixen ikke er mere end 1, indikerer dette fraværet af en cyklus med længde 4. Cykler af større længde (6, 8, 10 osv.) kan være bestemmes, om der er indbygget en graf i tjekmatricen , med spidser, hvis kanter alle er mulige forbindelser af spidser parallelle med siderne af matricen (det vil sige lodrette eller vandrette linjer). Minimumscyklussen i denne kolonne vil være minimumscyklussen i kontrolmatrixen for LDPC-koden. Det er klart, at cyklussen vil have en længde på mindst 4, ikke 3, da grafens kanter skal være parallelle med siderne af matrixen. Generelt vil enhver cyklus i denne graf have en lige længde, minimumsstørrelsen er 4, og den maksimale størrelse er normalt ligegyldig (selvom den naturligvis ikke er mere end antallet af noder i grafen, dvs. n × k).

Beskrivelsen af LDPC-koden er mulig på flere måder:

tjek matrix
todelt graf
en anden grafisk måde
særlige måder

Sidstnævnte metode er en konventionel betegnelse for en gruppe af koderepræsentationer, der er bygget i henhold til givne regler-algoritmer, således at for at gengive koden igen, er det nok kun at kende initialiseringsparametrene for algoritmen, og selvfølgelig , selve konstruktionsalgoritmen. Denne metode er dog ikke universel og kan ikke beskrive alle mulige LDPC-koder.

Metoden til at specificere en kode ved hjælp af en kontrolmatrix er generelt accepteret for lineære koder, når hver række i matrixen er et element i et bestemt sæt kodeord. Hvis alle rækker er lineært uafhængige, kan rækkerne i matrixen betragtes som grundlaget for sættet af alle kodevektorer i koden. Brugen af denne metode skaber imidlertid vanskeligheder med at repræsentere matricen i koderens hukommelse - det er nødvendigt at gemme alle rækker eller kolonner i matrixen som et sæt binære vektorer, på grund af hvilke størrelsen af matricen bliver lig med bits . $j\times k$

En almindelig grafisk måde er at repræsentere koden som en todelt graf. Lad os sammenligne alle rækkerne i matricen med grafens nederste spidser og alle kolonnerne med de øverste spidser og forbinde grafens øvre og nedre spidser, hvis der er enheder i skæringspunktet mellem de tilsvarende rækker og kolonner. $k$ $k$ $n$

Andre grafiske metoder omfatter todelte graftransformationer, der forekommer uden faktisk at ændre selve koden. For eksempel kan du repræsentere alle de øverste hjørner af grafen som trekanter og alle de nederste spidser som firkanter og derefter arrangere kanterne og spidserne af grafen på en todimensional overflade i en rækkefølge, der er praktisk for visuel forståelse af kodestrukturen. For eksempel bruges en sådan fremstilling som illustrationer i bøger af David McKay.

Ved at indføre yderligere regler for grafisk visning og opbygning af LDPC-koden er det muligt at opnå, at koden får visse egenskaber under byggeprocessen. Hvis vi f.eks. bruger en graf, hvis toppunkter kun er kolonnerne i kontrolmatrixen, og rækkerne er repræsenteret af polyedre bygget på grafens hjørner, så gør det os muligt at følge reglen "to polyedre deler ikke en kant" slippe af med cyklusser af længde 4.

Ved brug af specielle kodekonstruktionsprocedurer kan deres egne metoder til repræsentation, lagring og behandling (kodning og afkodning) bruges.

Kodebygning

I øjeblikket anvendes to principper til at konstruere en kodekontrolmatrix. Den første er baseret på generering af en indledende kontrolmatrix ved hjælp af en pseudo-tilfældig generator. Koder opnået på denne måde kaldes random ( engelsk random-like codes ). Den anden er brugen af specielle metoder baseret på for eksempel grupper og afsluttende felter . Koder opnået ved disse metoder kaldes strukturerede koder . Det er tilfældige koder, der viser de bedste resultater i fejlkorrektion, dog tillader strukturerede koder at bruge metoder til optimering af lagring, indkodning og afkodningsprocedurer, samt opnåelse af koder med mere forudsigelige karakteristika.

I sit arbejde valgte Gallagher at bruge en pseudo-tilfældig talgenerator til at skabe en indledende kontrolmatrix i lille størrelse med specificerede karakteristika, og derefter øge dens størrelse ved at duplikere matricen [6] og bruge metoden til at blande rækker og kolonner for at få slippe af med cyklusser af en vis længde.

I 2003 foreslog James McGowan og Robert Williamson en måde at fjerne cyklusser fra matrixen af en LDPC-kode, og derfor blev det muligt først at generere en matrix med givne karakteristika (n, j, k) og derefter fjerne cyklusser fra den. Dette er, hvad der sker i Ozarov-Weiner-ordningen [7] .

I 2007 blev der publiceret en artikel i tidsskriftet "IEEE Transactions on Information Threory" om brugen af endelige felter til at konstruere kvasicykliske LDPC-koder for additive hvide Gaussiske støjkanaler og binære slettekanaler.

For at øge dimensionen af koden kan et multipelt slutprodukt af generering af matricer bruges [6] .

Afkodning

Som for enhver anden lineær kode bruges ortogonalitetsegenskaben for de genererede og transponerede kontrolmatricer til afkodning:

G\odot H^{T}=0

hvor er den genererende matrix, og er kontrolmatrixen , er symbolet for multiplikation modulo 2 (hvis et tal, der er et multiplum af 2, opnås som et element i den resulterende matrix, så skrives nul i stedet). Derefter, for hvert kodeord modtaget uden fejl, relationen $G$ $H$ $\odot$

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

og for det modtagne kodeord med en fejl:

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

hvor er den accepterede vektor, er syndromet . Hvis der efter multiplicering af det modtagne kodeord med den transponerede paritetsmatrix opnås nul, betragtes blokken som modtaget uden fejl. Ellers bruges specielle metoder til at lokalisere fejlen og rette den. For en LDPC-kode viser standardkorrektionsmetoderne sig at være for tidskrævende - de klassificeres som NP-komplette problemer, som på grund af den store bloklængde ikke kan anvendes i praksis. I stedet bruger de metoden med probabilistisk iterativ afkodning, som retter en stor del af fejl ud over halvdelen af kodeafstanden [8] . $v$ $s$

Overvej [9] en symmetrisk hukommelsesløs kanal med input og additiv Gaussisk støj . For det modtagne kodeord skal man finde den tilsvarende mest sandsynlige vektor , sådan $\pm a$ $\sigma ^{2}=1$ $y$ $x$

H\odot x=0\mod 2

Lad os definere $f_{n}^{1}={1/{\mathord {\left(1+\exp \left(-2ay_{n}/{\mathord {\sigma ^{2))}\right) \ret)}}}$ ; ${\displaystyle f_{n}^{0}=1-f_{n}^{1))$ ; hvor er den modtagne værdi af det n'te symbol i kodeordet (som for en given kanal har en vilkårlig værdi, normalt inden for ). $y_{n}$ $\pm (a+3\sigma )$
Vi vil bruge ordet "bit" til at angive individuelle elementer i vektoren , og ordet "tjek" til at angive rækker i kontrolmatrixen . Angiv med det sæt bits, der vil deltage i den m-te check. Lad os på samme måde betegne det sæt af kontroller, hvor bit n deltager. (Det vil sige, at vi lister indekserne for ikke-nul-elementer for hver række og for hver kolonne i kontrolmatrixen ). $x$ $H$ ${\displaystyle N\left(m\right)\equiv \{n:H_{nm}=1\))$ ${\displaystyle M\left(n\right)\equiv \{m:H_{nm}=1\))$ $H$
Vi initialiserer matricer og værdier og hhv $q_{mn}^{0}$ $q_{mn}^{1}$ $f_{n}^{0}$ ${\displaystyle f_{n}^{1))$
(vandret trin) ${\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 \over 2}\left({1+\delta r_{mn}}\right)$ $r_{mn}^{1}={1 \over 2}\left({1-\delta r_{mn}}\right)$
(lodret tonehøjde) $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}}$ hvor for hver og udvalgt giver: $m$ $n$ $\alpha _{mn}$ $q_{mn}^{0}+q_{mn}^{1}=1$ Nu opdaterer vi også de "pseudo-posteriore sandsynligheder", som vektorens bits antager værdierne 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}^ {en}}$ Også, som før, er valgt på en sådan måde, at $\alpha_{n}$ $q_{n}^{0}+q_{n}^{1}=1$

Disse værdier bruges til at genskabe x-vektoren. Hvis den resulterende vektor opfylder , afbrydes algoritmen, ellers gentages de vandrette og lodrette trin. Hvis algoritmen fortsætter op til et bestemt trin (for eksempel 100), afbrydes den, og blokken erklæres accepteret med en fejl. $H\odot x=0\mod 2$

Det er kendt, at denne algoritme giver den nøjagtige værdi af vektoren (det vil sige sammenfaldende med de klassiske metoder), hvis tjekmatricen ikke indeholder cyklusser [10] . $x$ $H$

Noter

↑ Shannon CE A Mathematical Theory of Communication // Bell System Technical Journal. - 1948 . - T. 27 . - S. 379-423, 623-656 .
↑ Gallager, R. G. Low Density Parity Check Codes . — Cambridge : MIT Press, 1963 . — S. 90.
↑ David JC MacKay og Radford M. Neal, "Near Shannon Limit Performance of Low Density Parity Check Codes," Electronics Letters, juli 1996
↑ David JC MacKay. Informationsteori, inferens og læringsalgoritmer . - CUP, 2003. - ISBN 0-521-64298-1 .
↑ Dr. Lin Nan Lee. LDPC-koder, anvendelse på næste generations kommunikationssystemer // IEEE Semiannual Vehicular Technology Conference. - oktober 2003. Arkiveret fra originalen den 8. oktober 2006.
↑ 1 2 Slyusar V. I. Syntese af LDPC og polære koder baseret på slutproduktet af matricer.// Development of Education, Science and Business: Results 2020: abstracts of the International Scientific and Practical Internet Conference, December 3-4, 2020. – Del 2. - S. 393-396. [1] Arkiveret 25. januar 2021 på Wayback Machine .
↑ Yu.V. Kosolapov. Om anvendelsen af Ozarov-Weiner-ordningen for informationsbeskyttelse i trådløse multikanals datatransmissionssystemer // Information Counteraction to Terrorism Threats: Scientific and Practical Journal. – 2007 . - Nr. 10 . - S. 111-120 . Arkiveret fra originalen den 24. juni 2013.
↑ V. B. Afanasiev, D. K. Zigangirov "Om nogle konstruktioner af lavdensitetskoder med en komponent Reed-Solomon-kode"
↑ David JC MacKay, Radford M. Neal Near Shannon Limit Performance of Low Density Parity Check Codes . Hentet 28. august 2008. Arkiveret fra originalen 17. april 2007. (ubestemt)
↑ J. Pearl. Probabilistisk ræsonnement i intelligente systemer: netværk af plausible slutninger. Morgan Kaufmann, San Mateo, 1988.