Paritetskontrolkode med lav densitet - Low-density parity-check code

I informationsteori er en LDPC- kode ( low-density parity-check ) en lineær fejlkorrektionskode , en metode til transmission af en meddelelse over en støjende transmissionskanal. En LDPC er konstrueret ved hjælp af en sparsom Tanner-graf (underklasse af bipartitgrafen ). LDPC-koder er kapacitetstilnærmende koder , hvilket betyder, at der findes praktiske konstruktioner, der gør det muligt at indstille støjgrænsen meget tæt på det teoretiske maksimum ( Shannon-grænsen ) for en symmetrisk hukommelsesfri kanal. Støjgrænsen definerer en øvre grænse for kanalstøj, op til hvilken sandsynligheden for mistet information kan gøres så lille som ønsket. Anvendelse iterative tro formering teknikker kan LDPC-koder dekodes i tid lineær deres bloklængden.

LDPC-koder finder stigende anvendelse i applikationer, der kræver pålidelig og meget effektiv informationsoverførsel over båndbreddebegrænsede eller tilbagekanal-begrænsede links i nærvær af ødelæggende støj. Implementeringen af ​​LDPC-koder har haltet bagefter andre koder, især turbokoder . Det grundlæggende patent på turbokoder udløb den 29. august 2013.

LDPC-koder er også kendt som Gallager-koder til ære for Robert G. Gallager , der udviklede LDPC-konceptet i sin doktorafhandling ved Massachusetts Institute of Technology i 1960.

Historie

Upraktisk at implementere, da LDPC-koder først blev udviklet af Gallager i 1963, blev glemt, indtil hans arbejde blev genopdaget i 1996. Turbokoder , en anden klasse af kapacitetstilnærmende koder opdaget i 1993, blev det valgte kodningsskema i slutningen af ​​1990'erne, der blev brugt til applikationer såsom Deep Space Network og satellitkommunikation . Imidlertid har fremskridtene med paritetskontrolkoder med lav densitet set dem overgå turbokoder med hensyn til fejlgulv og ydeevne i det højere kodehastighedsområde , hvilket efterlader turbokoder bedre egnet til de lavere kodepriser.

Ansøgninger

I 2003 slog en uregelmæssig gentagen akkumulering (IRA) stil LDPC-kode seks turbokoder for at blive den fejlkorrektionskode i den nye DVB-S2- standard til satellittransmission af digitalt tv . DVB-S2-udvælgelseskomitéen foretog estimater for dekoder-kompleksitet for Turbo-kodeforslagene ved hjælp af en meget mindre effektiv seriel dekoderarkitektur snarere end en parallel dekoderarkitektur. Dette tvang Turbo-kodeforslagene til at bruge rammestørrelser i størrelsesordenen halvdelen af ​​rammestørrelsen af ​​LDPC-forslagene.

I 2008 LDPC slog foldningskoder turbo-koder som den fremadgående fejlkorrektion system til (FEC) ITU-T G.hn standarden. G.hn valgte LDPC-koder frem for turbokoder på grund af deres lavere afkodningskompleksitet (især når de opererer med datahastigheder tæt på 1,0 Gbit / s), og fordi de foreslåede turbokoder udviser en betydelig fejlgulv i det ønskede driftsområde.

LDPC-koder bruges også til 10GBASE-T Ethernet, der sender data med 10 gigabit pr. Sekund over snoede par kabler. Fra 2009 er LDPC-koder også en del af Wi-Fi 802.11-standarden som en valgfri del af 802.11n og 802.11ac i PHY-specifikationen High Throughput (HT).

Nogle OFDM- systemer tilføjer en yderligere ydre fejlkorrektion, der løser lejlighedsvise fejl ("fejlgulvet"), der kommer forbi LDPC-korrektionens indre kode, selv ved lave bitfejlrater . For eksempel: Reed-Solomon-koden med LDPC-kodet modulering (RS-LCM) bruger en Reed-Solomon-ydre kode. DVB-S2, DVB-T2 og DVB-C2-standarderne bruger alle en ydre kode af BCH- koden til at tørre resterende fejl op efter LDPC-afkodning.

Operationel anvendelse

LDPC-koder er funktionelt defineret af en sparsom paritetskontrolmatrix . Denne sparsomme matrix er ofte tilfældigt genereret med forbehold af sparsity constraints- LDPC-kode konstruktion diskuteres senere . Disse koder blev først designet af Robert Gallager i 1960.

Nedenfor er et graffragment af et eksempel på LDPC-kode ved hjælp af Forneys faktorgrafnotation . I denne graf er n variable knudepunkter i toppen af ​​grafen forbundet med ( n - k ) begrænsningsknuder i bunden af ​​grafen.

Dette er en populær måde at grafisk repræsentere en ( n ,  k ) LDPC-kode. Bitene i en gyldig meddelelse, når de placeres på T'erne øverst i grafen, tilfredsstiller de grafiske begrænsninger. Specifikt har alle linjer, der forbinder til en variabel node (boks med et '=' tegn) den samme værdi, og alle værdier, der forbinder til en faktorknude (boks med et '+' tegn) skal summe, modulo to, til nul (i med andre ord, de skal summe til et lige tal, eller der skal være et lige antal ulige værdier).

Ignorerer linier, der går ud af billedet, er der otte mulige seks-bit strenge, der svarer til gyldige kodeord: (dvs. 000000, 011001, 110010, 101011, 111100, 100101, 001110, 010111). Dette LDPC-kodefragment repræsenterer en tre-bit besked kodet som seks bit. Redundans bruges her til at øge chancen for at komme sig efter kanalfejl. Dette er en (6, 3) lineær kode med n  = 6 og k  = 3.

Igen ignorerer linjer, der går ud af billedet, paritetskontrolmatrixen, der repræsenterer dette graffragment, er

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

I denne matrix repræsenterer hver række en af ​​de tre paritetskontrolbegrænsninger, mens hver kolonne repræsenterer en af ​​de seks bits i det modtagne kodeord.

I dette eksempel kan de otte kodeord fås ved at placere paritetskontrolmatrixen H i denne form gennem grundlæggende rækkeoperationer i GF (2) : ${\ displaystyle {\ begin {bmatrix} -P ^ {T} | I_ {nk} \ end {bmatrix}}}$

${\ displaystyle \ mathbf {H} = {\ start {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 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ slut {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 & 1 & 0 & 0 \ 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \\\ slut {pmatrix}} _ {4}.}$

Trin 1: H.

Trin 2: Række 1 føjes til række 3.

Trin 3: Række 2 og 3 byttes.

Trin 4: Række 1 tilføjes til række 3.

Ud fra dette kan generatormatricen G opnås som (bemærker, at i det særlige tilfælde, hvor dette er en binær kode ), eller specifikt: ${\ displaystyle {\ begin {bmatrix} I_ {k} | P \ end {bmatrix}}}$${\ displaystyle P = -P}$

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

Endelig opnås alle otte gyldige kodeord ved at multiplicere alle otte mulige 3-bit strenge med G. For eksempel opnås kodeordet for bitstrengen '101' ved:

$" \\ afslutning {pmatrix}}}$ ,

hvor er symbol på mod 2 multiplikation. ${\ displaystyle \ odot}$

Som en kontrol er rækkeområdet for G vinkelret på H således, at ${\ displaystyle G \ odot H ^ {T} = 0}$

Bitstrengen '101' findes som de første 3 bits i kodeordet '101011'.

Eksempel på koder

Figur 1 illustrerer de funktionelle komponenter i de fleste LDPC-kodere.

Under kodningen af ​​en ramme gentages inputdatabitene (D) og distribueres til et sæt bestående kodere. Komponentkoderne er typisk akkumulatorer, og hver akkumulator bruges til at generere et paritetssymbol. En enkelt kopi af de originale data (S0 _{, K-1} ) transmitteres med paritetsbitene (P) for at udgøre kodesymbolerne. S-bitene fra hver komponentkoder kasseres.

Paritetsbiten kan bruges inden for en anden bestandskode.

I et eksempel ved anvendelse af DVB-S2-hastighed 2/3-koden er den kodede blokstørrelse 64800 symboler (N = 64800) med 43200 databits (K = 43200) og 21600 paritetsbits (M = 21600). Hver bestandskode (kontrolknude) koder for 16 databits undtagen den første paritetsbit, der koder for 8 databits. De første 4680 databitar gentages 13 gange (bruges i 13 paritetskoder), mens de resterende databitar bruges i 3 paritetskoder (uregelmæssig LDPC-kode).

Til sammenligning bruger klassiske turbokoder typisk to bestandskoder, der er konfigureret parallelt, som hver koder for hele inputblokken (K) af databits. Disse komponentkodere er rekursive foldningskoder (RSC) med moderat dybde (8 eller 16 tilstande), der er adskilt af en kodeinterfolier, der sammenfletter en kopi af rammen.

LDPC-koden bruger derimod mange komponenter med lav dybde (akkumulatorer) parallelt, som hver kun koder for en lille del af inputrammen. De mange komponentkoder kan ses som mange 'dybde' konvolusionskoder ', der er forbundet via gentagelses- og distribueringsoperationerne. Gentagelses- og distribueringshandlingerne udfører interleaverens funktion i turbokoden.

Evnen til mere nøjagtigt at styre forbindelserne mellem de forskellige bestandskoder og redundansniveauet for hver inputbit giver mere fleksibilitet i designet af LDPC-koder, hvilket i nogle tilfælde kan føre til bedre ydeevne end turbokoder. Turbokoder ser stadig ud til at fungere bedre end LDPC'er ved lave kodepriser, eller i det mindste er design af velfungerende lave hastighedskoder lettere for Turbokoder.

Som en praktisk sag genbruges den hardware, der danner akkumulatorerne, under kodningsprocessen. Når det første sæt paritetsbits er genereret, og paritetsbitene er gemt, bruges den samme akkumulatorhardware til at generere et næste sæt paritetsbits.

Afkodning

Som med andre koder er den maksimale sandsynlighed for afkodning af en LDPC-kode på den binære symmetriske kanal et NP-komplet problem. Det er ikke praktisk at udføre optimal afkodning for en NP-komplet kode af enhver anvendelig størrelse.

Men under det optimale teknikker baseret på iterativ tro formering afkodning giver fremragende resultater og kan gennemføres i praksis. De suboptimale afkodningsteknikker ser hver paritetskontrol, der udgør LDPC, som en uafhængig SPC-kode (single parity check). Hver SPC kode afkodes separat under anvendelse blød-i-soft-out (SISO) teknikker såsom Sova , BCJR , MAP og andre derivater deraf. Den bløde beslutningsinformation fra hver SISO-afkodning krydskontrolleres og opdateres med andre overflødige SPC-afkodninger af den samme informationsbit. Hver SPC-kode afkodes derefter igen ved hjælp af de opdaterede bløde beslutningsoplysninger. Denne proces gentages, indtil et gyldigt kodeord opnås, eller afkodningen er udtømt. Denne type afkodning omtales ofte som sum-produkt-afkodning.

Afkodningen af ​​SPC-koderne omtales ofte som "kontrolknudeprocessering", og krydskontrol af variablerne omtales ofte som "variabelknudeprocessering".

I en praktisk implementering af LDPC-dekoder afkodes sæt SPC-koder parallelt for at øge kapaciteten.

I modsætning hertil er trosformering på den binære sletningskanal særlig enkel, når den består af iterativ begrænsningstilfredshed.

Overvej for eksempel, at det gyldige kodeord, 101011, fra eksemplet ovenfor, transmitteres over en binær sletningskanal og modtages med den første og fjerde bit slettet for at give? 01? 11. Da den transmitterede meddelelse skal have opfyldt kodebegrænsningerne, kan meddelelsen repræsenteres ved at skrive den modtagne besked øverst på faktorgrafen.

I dette eksempel kan den første bit endnu ikke gendannes, fordi alle de begrænsninger, der er forbundet med den, har mere end en ukendt bit. For at fortsætte med afkodning af meddelelsen skal begrænsninger, der forbinder til kun en af ​​de slettede bits, identificeres. I dette eksempel er kun den anden begrænsning tilstrækkelig. Når man undersøger den anden begrænsning, skal den fjerde bit have været nul, da kun et nul i denne position ville tilfredsstille begrænsningen.

Denne procedure gentages derefter. Den nye værdi for den fjerde bit kan nu bruges sammen med den første begrænsning til at gendanne den første bit som vist nedenfor. Dette betyder, at den første bit skal være en for at tilfredsstille den yderste begrænsning.

Således kan meddelelsen afkodes iterativt. For andre kanalmodeller er meddelelserne, der sendes mellem de variable knudepunkter og kontrolknudepunkter, reelle tal , der udtrykker sandsynligheder og sandsynligheder for tro.

Dette resultat kan valideres ved at gange det korrigerede kodeord r med paritetskontrolmatrixen H :

${\ displaystyle \ mathbf {z} = \ mathbf {H \ odot r} = {\ begin {pmatrix} 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 0 \ 0 \ end {pmatrix}} \ odot {\ begin {pmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 1 \\\ end {pmatrix}} = {\ begin {pmatrix} 0 \\ 0 \\ 0 \\\ end {pmatrix}}.}$

Da resultatet z ( syndromet ) af denne operation er tre × en nul-vektor, er det resulterende kodeord r valideret med succes.

Efter afkodningen er afsluttet, kan de originale beskedbits '101' ekstraheres ved at se på de første 3 bits i kodeordet.

Selvom det er illustrativt, viser dette sletningseksempel ikke brugen af ​​afkodning af blød beslutning eller meddelelse af blød beslutning, som bruges i stort set alle kommercielle LDPC-dekodere.

Opdatering af nodeoplysninger

I de senere år har der også været brugt meget arbejde på at undersøge effekterne af alternative tidsplaner for opdatering af variabel node og begrænsning-node. Den originale teknik, der blev brugt til afkodning af LDPC-koder, blev kendt som oversvømmelse . Denne type opdatering krævede, at alle begrænsningsknuder skulle opdateres, før de opdateres en variabel node, og omvendt. I senere arbejde af Vila Casado et al. , blev alternative opdateringsteknikker undersøgt, hvor variable noder opdateres med de nyeste tilgængelige kontrolnodeoplysninger.

Intuitionen bag disse algoritmer er, at variable noder, hvis værdier varierer mest, er dem, der skal opdateres først. Meget pålidelige noder, hvis log-sandsynlighed ratio (LLR) størrelse er stor og ikke ændrer sig væsentligt fra den ene opdatering til den næste, kræver ikke opdateringer med den samme frekvens som andre noder, hvis tegn og størrelse svinger mere bredt. Disse planlægningsalgoritmer viser større konvergenshastighed og lavere fejlgulve end dem, der bruger oversvømmelse. Disse lavere fejlgulve opnås ved hjælp af IDS-algoritmen (Informed Dynamic Scheduling) til at overvinde fangstsæt med nær kodeord.

Når der bruges planlægningsalgoritmer til ikke-oversvømmelse, anvendes en alternativ definition af iteration. For en ( n ,  k ) LDPC-kode for hastighed k / n opstår en fuld iteration , når n variable og n  -  k begrænsningsknuder er blevet opdateret, uanset rækkefølgen, i hvilken de blev opdateret.

Kodekonstruktion

For store blokstørrelser konstrueres ofte LDPC-koder ved først at undersøge dekodernes adfærd. Da blokstørrelsen har en tendens til uendelig, kan LDPC-dekodere vises at have en støjgrænse, under hvilken dekodning opnås pålideligt, og over hvilken dekodning ikke opnås, i det mindste benævnt klippeeffekten . Denne tærskel kan optimeres ved at finde den bedste andel af buer fra kontrolnoder og buer fra variable noder. En tilnærmet grafisk tilgang til visualisering af denne tærskel er et EXIT-diagram .

Konstruktionen af ​​en bestemt LDPC-kode efter denne optimering falder i to hovedtyper af teknikker:

• Pseudorandom nærmer sig
• Kombinatoriske tilgange

Konstruktion ved hjælp af en pseudo-tilfældig tilgang bygger på teoretiske resultater, der ved stor blokstørrelse giver en tilfældig konstruktion god afkodningsydelse. Generelt har pseudorandom-koder komplekse kodere, men pseudorandom-koder med de bedste dekodere kan have enkle kodere. Der anvendes ofte forskellige begrænsninger for at hjælpe med at sikre, at de ønskede egenskaber, der forventes ved den teoretiske grænse for uendelig blokstørrelse, forekommer ved en endelig blokstørrelse.

Kombinatoriske tilgange kan bruges til at optimere egenskaberne for små LDPC-koder i blokstørrelse eller til at oprette koder med enkle kodere.

Nogle LDPC-koder er baseret på Reed-Solomon-koder , såsom RS-LDPC-koden, der bruges i 10 Gigabit Ethernet- standarden. Sammenlignet med tilfældigt genererede LDPC-koder kan strukturerede LDPC-koder - såsom LDPC-koden, der anvendes i DVB-S2- standarden - have enklere og derfor billigere hardware - især koder konstrueret således, at H-matrixen er en cirkulerende matrix .

Endnu en anden måde at konstruere LDPC-koder på er at bruge endelige geometrier . Denne metode blev foreslået af Y. Kou et al. i 2001.

LDPC-koder vs. turbokoder

LDPC-koder kan sammenlignes med andre kraftfulde kodningsordninger, f.eks. Turbokoder. På den ene side påvirkes BER- ydeevnen af ​​Turbo-koder af lave kodebegrænsninger. LDPC-koder har ingen begrænsninger for mindste afstand, hvilket indirekte betyder, at LDPC-koder kan være mere effektive på relativt store kodehastigheder (f.eks. 3/4, 5/6, 7/8) end Turbo-koder. LDPC-koder er dog ikke den komplette erstatning: Turbokoder er den bedste løsning til de lavere koderater (f.eks. 1/6, 1/3, 1/2).

Se også

Mennesker

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

Teori

• Trosforplantning
• Grafteori
• Hamming-kode
• Lineær kode
• Spartegrafkode
• Udvidelseskode

Ansøgninger

• G.hn/G.9960 (ITU-T Standard til netværk via strømledninger, telefonledninger og koaksialkabler)
• 802.3an eller 10GBASE-T (10 Giga-bit / s Ethernet over Twisted pair)
• CMMB (China Multimedia Mobile Broadcasting)
• DVB-S2 / DVB-T2 / DVB-C2 (Digital videoudsendelse, 2. generation)
• DMB-T / H (digital videoudsendelse)
• WiMAX (IEEE 802.16e standard til mikrobølgekommunikation)
• IEEE 802.11n-2009 ( Wi-Fi- standard)
• DOCSIS 3.1

Andre koder, der nærmer sig kapacitet

• Turbokoder
• Serielle sammenkædede foldningskoder
• Onlinekoder
• Springvandskoder
• LT-koder
• Raptor koder
• Gentag-akkumulere koder (en klasse med enkle turbokoder)
• Tornado-koder (LDPC-koder designet til sletningskodning )
• Polarkoder

Referencer

eksterne links

• Introduktion af paritetskontrolkoder med lav densitet (af Sarah J Johnson, 2010)
• LDPC-koder - en kort vejledning (af Bernhard Leiner, 2005)
• LDPC-koder (TU Wien)
• Online-lærebogen: Informationsteori, inferens og læringsalgoritmer af David JC MacKay diskuterer LDPC-koder i kapitel 47.
• Iterativ afkodning af koder med lav tæthedskontrol af paritet (af Venkatesan Guruswami, 2006)
• LDPC-koder: En introduktion (af Amin Shokrollahi, 2003)
• Tro-formering afkodning af LDPC-koder (af Amir Bennatan, Princeton University)
• Turbo- og LDPC-koder: Implementering, simulering og standardisering (West Virginia University)
• Informationsteori og kodning (Marko Hennhöfer, 2011, TU Ilmenau) - diskuterer LDPC-koder på side 74-78.
• LDPC-koder og resultater
• DVB-S.2 Link, inklusive LDPC-kodning (MatLab)
• Kildekode til kodning, afkodning og simulering af LDPC-koder er tilgængelig fra en række forskellige steder:
  • Binære LDPC-koder i C
  • Binære LDPC-koder til Python (kernealgoritme i C)
  • LDPC-indkoder og LDPC-dekoder i MATLAB
  • En hurtig fremad fejlkorrektionsværktøjskasse (AFF3CT) i C ++ 11 til hurtige LDPC-simuleringer