Inleiding tot Low-Density Parity-Check Codes

Low-Density Parity-Check (LDPC) codes behoren tot de meest krachtige foutcorrectie codes in moderne digitale communicatie. Eerst geïntroduceerd door Robert Gallager in zijn 1960 PhD-scriptie, deze codes werden grotendeels vergeten voordat ze opnieuw ontdekt in het midden van de jaren negentig. Hun vermogen om de Shannon limiet te benaderen met praktische decodering complexiteit heeft hen de hoeksteen van talloze systemen, van satelliet televisie uitzendingen tot 5G nieuwe radio en NAND-flash opslag. De sleutel tot hun prestaties ligt in een zeer schaarse pariteit-check matrix: de meeste items zijn nul, die de grafiek-gebaseerde decodering algoritmes die kunnen worden geïmplementeerd in hardware vereenvoudigt.

In high-throughput omgevingen, software-gebaseerde decodering gewoon niet kunnen bijhouden. Als datasnelheden klimmen naar 100 Gbps en verder in optische transportnetwerken, de eisen op LDPC decoders worden extreem. Dit heeft de industrie naar speciale hardware versnellers die parallellisme op elk niveau te exploiteren. De vooruitgang beschreven in dit artikel vertegenwoordigt de stand van de techniek in parallel decoderen architecturen, biedt zowel snelheid en efficiëntie voor real-world toepassingen.

Related technology: Voor een overzicht van de basisbeginselen van de LDPC-code, zie Wikipedia artikel over LDPC codes.

Theoretische achtergrond: algoritmen voor het decoderen van algoritmen

Voordat hardwarearchitecturen worden onderzocht, is het essentieel om de algoritmen te begrijpen die LDPC decoderen ondersteunen. Het meest gebruikte algoritme is de geloofspropagatie (BP) decoder, ook bekend als het sum-product algoritme. Het werkt op een twee-party grafiek .De Tanner grafiek bestaat uit variabele knooppunten (representeren codewoord bits) en controleknopen (representeren pariteit beperkingen). Berichten worden iteratief doorgegeven tussen knooppunten, het bijwerken van de waarschijnlijkheden totdat de pariteit vergelijkingen zijn voldaan of een maximale iteratie telling wordt bereikt.

De berekeningskosten van BP zijn aanzienlijk vanwege de hyperbolische tangensfuncties die nodig zijn voor waarschijnlijkheidsberekeningen. Een praktische benadering is het min-sum algoritme, dat de complexe functie vervangt door min- en sign operaties. Hoewel dit een licht prestatieverlies veroorzaakt, is de vereenvoudiging van cruciaal belang voor de implementatie van hardware met hoge snelheid. Onderzoekers hebben vele varianten ontwikkeld die min-sum, genormaliseerd min-sum en zelf-reduceerde min-sum.Dit zorgt voor een verwisseling van complexiteit voor foutcorrectieprestaties.

De iteratieve aard van deze algoritmen betekent dat decoderingslatentie direct evenredig is met het aantal iteraties en de tijdperceratie. Parallelle architecturen streven ernaar de tijdperceratie te verminderen door meerdere updates gelijktijdig uit te voeren, of door overlappende iteraties door pipelining.

Traditionele Decoderingsarchitectuur en hun beperkingen

Vroege hardware LDPC decoders gebruikt een volledig sequentiële aanpak: een enkele verwerkingseenheid update elke variabele knooppunt op zijn beurt, vervolgens elke controle knooppunt op zijn beurt, herhalen tot convergentie. Deze seriële architectuur vereist de minste hardware middelen . Slechts een rekeneenheid .maar lijdt aan hoge latentie en lage doorvoer. Bijvoorbeeld, een decoder die een codelengte van 10.000 bits kan tientallen microseconden periteratie, die onaanvaardbaar is voor moderne multi-gigabit systemen.

Een andere beperking is geheugenbandbreedte. In seriële architecturen moeten alle tussenliggende berichten in het geheugen op de chip worden opgeslagen en herhaaldelijk worden benaderd. Dit zorgt voor een knelpunt, aangezien de toegangstijd van het geheugen de dominante factor wordt in de iteratieduur. Bovendien maakt het sequentiële updateschema geen gebruik van het feit dat veel variabele en controleer node-updates onafhankelijk zijn en gelijktijdig kunnen worden berekend.

De inefficiëntie van seriele methoden motiveerde de ontwikkeling van gedeeltelijk en volledig parallel decoders. De uitdaging is om parallelisme te verhogen zonder het probleem van de middelen of het overtreden van het voor convergentie vereiste schema voor boodschappen-passing.

Parallelle Decoderingsarchitectuur: stand van de techniek

Moderne hardware LDPC decoders maken gebruik van een verscheidenheid van parallelle technieken, vaak in combinatie. De meest prominente benaderingen zijn gelaagde decoderen, pipelined processing, en volledig parallelle architecturen. Elk biedt verschillende trade-offs tussen doorvoer, gebied, macht, en foutcorrectie vermogen.

Gelaagde decodering

Decodering van lagen reorganiseert de pariteitscontrolematrix in lagen die doorgaans rijen of groepen rijen zijn die overeenkomen met niet-overlappende deelverzamelingen van controlevergelijkingen. Binnen elke laag worden alle variabele knooppuntupdates die de laag kunnen aanraken gelijktijdig verwerkt, mits ze niet dezelfde variabele knooppunt delen. Dit vereist een zorgvuldig matrixontwerp om ervoor te zorgen dat kolomgewichten laag genoeg zijn om conflicten te voorkomen.

Het gelaagde schema versnelt de convergentie dramatisch. Terwijl een standaard overstromingsschema alle variabele knooppunten bijwerkt dan alle controleknooppunten per iteratie, de gelaagde schema updates zowel variabele en controleer knooppunten in elke laag in een enkele pas. Dit effectief vermindert het aantal vereiste iteraties met een factor twee of meer. Bijvoorbeeld, een gelaagde decoder kan convergen in 5

Layered decoders bieden ook intermediaire verwerkingsvoordelen. Aangezien alleen de berichten voor één laag tegelijk moeten worden opgeslagen, zijn de geheugenvereisten kleiner dan in volledig parallelle ontwerpen, waardoor gelaagde decodering aantrekkelijk is voor FPGA-implementatie waar blok RAM beperkt is. Grote FPGA-leveranciers bieden IP-kernen die gelaagde LDPC-decoders implementeren die compatibel zijn met Wi-Fi, 5G en satellietstandaarden.

Voorbeeld: Een gelaagde decoder voor een (64800, 64800.07280) code die in DVB-S2 wordt gebruikt, kan een verwerkingscapaciteit bereiken van meer dan 1 Gbps op moderne Xilinx FPGA's, zoals beschreven in ]dit IEEE-papier op hoge doorvoer LDPC-decoders[.

Gepijpleidingde verwerking

Pipelinering is een klassieke digitale ontwerptechniek die een berekening in meerdere fasen breekt, elk in één klokcyclus, met registers tussen fasen die tussenresultaten bevatten. In LDPC-decoders kan pipelining op verschillende niveaus worden toegepast: binnen één iteratie (intra-iteratie pipelining) of over meerdere iteraties (inter-iteratie pipelining).

Intra-iteration pipelining verdeelt de berichtberekening voor een variabele of controleer knooppunt in kleinere rekenstappen . Zoals min-finding, product-of-signs, en normalisatie . waardoor de hardware te draaien op een hogere klokfrequentie . Echter , dit verhoogt latency periteratie , die de verwerkingswinst kan compenseren als niet zorgvuldig beheerd .

Inter-iteratie pijplijn is agressiever: het overlapt de verwerking van iteratie i met iteratie i+1. Dit vereist ontkoppeling van de herinneringen zodat men kan worden geschreven terwijl een ander wordt gelezen. De diepte van de pijpleiding kan meerdere iteraties zijn, en er moet speciale aandacht worden besteed aan het vermijden van datarisico's waar een latere iteratie afhangt van de resultaten die nog niet zijn geproduceerd. Sommige onderzoeken hebben aangetoond dat look-ahead technieken of gewijzigde update schema's deze gevaren kunnen oplossen, waardoor een hoge mate van inter-iteratie parallelisme mogelijk is.

De architecturen worden vaak gebruikt in ASIC implementaties waar de decoder deel uitmaakt van een grotere System-on-Chip (SoC). Zo heeft de LDPC decoder in een 5G basisband processor vaak een 4-traps pijpleiding om een doorvoercapaciteit van 20 Gbps te behouden terwijl hij past binnen een strikte power envelop.

Volledige parallelle architectuur

Het ultieme parallelisme is een volledig parallelle decoder die een speciale verwerkingseenheid toewijst aan elke variabele knooppunt en elke controleknop in de Tanner grafiek. Alle knooppunten kunnen hun berichten bijwerken in één enkele klokcyclus, met behulp van een overstromingsschema. Dit elimineert de sequentiële bovenliggende of pijpleiding benaderingen, waardoor de hoogst mogelijke doorvoer wordt bereikt.

De prijs is enorm complex hardware. Een volledig parallelle decoder voor een code met 10.000 variabele knooppunten en 5.000 controleknooppunten zou 15.000 verwerkingselementen vereisen, plus een routering netwerk om ze te verbinden volgens de pariteit-check matrix. De bedrading domineert het gebied van de chip. Historisch gezien, slechts zeer korte LDPC codes (met een paar honderd bits) volledig parallel kunnen worden geïmplementeerd op een enkele chip.

Echter, vooruitgang in ASIC-technologie krimpprocesknooppunten, dichte 3D-integratie, en hoge bandbreedte on-chip netwerken .. hebben volledig parallelle decoders meer verteerbaar gemaakt. Recente onderzoeksprototypes tonen volledig parallelle decoders voor codes van lengte 2000 4000 bits die kunnen werken op 1 . 10 Gbps. Deze zijn nog steeds niet geschikt voor zeer lange codes (bijv. 64k bits voor DVB-S2), maar ze zijn ideaal voor latentie-gevoelige toepassingen zoals optische interconnects en lage-aard-baan satellietverbindingen.

Case study: Een volledig parallelle LDPC-decoder voor de IEEE 802.11ad-standaard (60 GHz WiGig) werd aangetoond in een 28 nm CMOS-chip, die 10 Gbps met 350 mW vermogen bereikte, zoals beschreven in dit IEEE Journal of Solid-State Circuits paper.

Andere opvallende benaderingen

Verschillende aanvullende parallelisatietechnieken verdienen vermelding:

  • Stochastische decodering: Representeert berichten als reeksen willekeurige bits, waardoor extreem eenvoudige hardware (een enkele flip-flop per bericht) ten koste van een tragere convergentie mogelijk is. Parallelisme is natuurlijk hoog omdat elke knoop onafhankelijk werkt. Stochastische decoders zijn onderzocht voor zeer lage vermogen toepassingen zoals geïmplanteerde medische hulpmiddelen.
  • Quasi-cyclische (QC) LDPC-decoders: De meeste moderne standaarden gebruiken quasi-cyclische LDPC-codes, waarbij de pariteitscontrolematrix bestaat uit cirkelvormige verschoven identiteitssubmatrices. Deze structuur maakt het decoder mogelijk om vatwisselaars of permutatienetwerken te gebruiken om berichten tussen verwerkingselementen te routeren, waardoor het interconnect sterk wordt vereenvoudigd. Bijna alle gelaagde en gedeeltelijk parallelle decoders voor QC-LDPC-codes maken gebruik van deze regelmaat.
  • Partimentele parallelle architecturen: Een compromis tussen gelaagde en volledig parallelle ontwerpen, gedeeltelijk parallelle decoders toewijzen een vast aantal verwerkingseenheden om meerdere nodes te verwerken over verschillende klokcycli. Door zorgvuldig plannen van bewerkingen, kunnen ze doorvoers dicht bij volledig parallel bereiken terwijl ze veel minder oppervlakte gebruiken.

Hardwareplatforms voor LDPC Decoder Implementatie

De keuze van platforms .FPGA, ASIC, of GPU . sterk invloed op de haalbare parallellisme en ontwerp trade-offs.

FPGA-gebaseerde decoders

FPGA's bieden herconfigureerbaarheid, waardoor ze populair zijn voor prototyping en voor systemen die meerdere standaarden moeten ondersteunen. Moderne FPGA's bevatten duizenden DSP-slices en overvloedig blok RAM, waardoor gelaagde decoders met een matig parallellisme mogelijk zijn. Volledig parallelle decoders worden zelden geïmplementeerd op FPGA's als gevolg van routeringscongestie, maar gedeeltelijk parallel en gelaagde ontwerpen kunnen multi-gigabit doorvoer bereiken. De flexibiliteit van FPGA's maakt ook runtime aanpassing van codeparameters mogelijk, wat waardevol is voor software-gedefinieerde radio's.

ASIC-gebaseerde decoders

Toepassingsspecifieke geïntegreerde schakelingen (ASIC's) zijn de werkpaarden van massa-markt communicatiechips. Ze kunnen honderden verwerkingselementen integreren met aangepaste geheugenhiërarchieën en speciale routing. ASIC-decoders voor 5G NR en Wi-Fi 6 zijn routinematig meer dan 10 Gbps met gelaagde of pijplijnvormige architecturen. Power efficiency is een belangrijk voordeel: een goed geoptimaliseerd ASIC-decoder kan onder 1 pJ per gedecodeerde bit bereiken.

GPU-gebaseerde decoders

Grafische verwerkingseenheden (GPU's) worden doorgaans niet gebruikt in productiecommunicatieontvangers, maar ze zijn van onschatbare waarde voor onderzoek en offline decodering. Een moderne GPU kan duizenden node-updates parallel simuleren met behulp van de SIMT (single-instruction, multiple-thread) architectuur. Onderzoekers gebruiken GPU-gebaseerde decoders om nieuwe algoritmen en codeontwerpen te testen zonder zich te binden aan hardware. Echter, geheugenlatentie tussen CPU en GPU, evenals de overhead van kernellanceringen, beperkt de doorvoercapaciteit voor real-time decodering van hoog-snelheid datastromen.

Uitdagingen in Parallel Decoder Design

Ondanks indrukwekkende vooruitgang blijven er nog verschillende obstakels bestaan voordat parallelle LDPC-decoders aan alle toepassingseisen kunnen voldoen.

  • Power consumption: Parallelle verwerkingseenheden verbruiken significant dynamisch vermogen. Voor batterij-aangedreven apparaten, kan het budget van de macht de mate van parallelisme beperken. Klokaanslag, spanningsschaalvorming, en bij benadering computing zijn actieve onderzoeksgebieden om de stroom te verminderen zonder grote doorvoer sancties.
  • Hardware complexiteit: De routering en het geheugen die nodig zijn voor hoge parallelisme verhogen chip gebied en ontwerp inspanning. Voor volledig parallelle decoders, de interconnect kan meer dan 70% van het die gebied bezetten. Hiërarchische en netwerk-op-chip architecturen worden onderzocht om complexiteit te beheren.
  • Foutvloer: Sommige parallelle architecturen introduceren quantisatie-effecten of vereenvoudigde algoritmen die een foutvloer veroorzaken een gebied waar de bitfoutsnelheid stopt met verbeteren als signaal-ruisverhouding toeneemt. Verminderen van foutvloeren vaak vereisen zorgvuldige algoritme-tuning of post-processing stappen die latentie toevoegen.
  • Schaalbaarheid: Naarmate LDPC codelengtes groeien (tot 64k of 128k bits), wordt het behoud van concurrency zonder geheugenconflicten moeilijker. Gelaagde decoders vereisen dat elke laag zonder conflicten wordt verwerkt; matrixontwerp en gelaagdheidsalgoritmen zijn een actief onderzoeksveld.

Toekomstige aanwijzingen

De volgende generatie LDPC-decoders zal waarschijnlijk parallelisme combineren met nieuwe computerparadigma's.

  • Machine leren ..ondersteund decoderen: Neurale netwerken kunnen worden opgeleid om de geloofsvermeerdering algoritme, potentieel verminderen iteratie tellen terwijl de prestaties. Bijvoorbeeld, neurale geloof propagatie decoders gebruiken geleerd gewichten en offsets, en ze kunnen worden geïmplementeerd in hardware met minimale overhead. De uitdaging is om het aanpassingsvermogen aan verschillende kanaalomstandigheden te handhaven.
  • Herkenbare en adaptieve architecturen: Toekomstige decoders kunnen hun mate van parallelisme dynamisch aanpassen op basis van kanaalkwaliteit en doorvoervereisten. Zo kan een decoder in real time schakelen tussen gelaagde en volledig parallelle modi. Dit vereist een flexibele communicatiestof en runtime control logica.
  • Integratie met kwantumfoutcorrectie: Naarmate quantumcomputing rijpt, zal foutcorrectie voor qubits zeer snelle decoders vereisen in de volgorde van nanoseconden. Parallelle LDPC-decoders geïnspireerd door klassieke ontwerpen worden geëvalueerd voor oppervlaktecodes en andere quantumfoutcorrigerende codes, hoewel de beperkingen heel verschillend zijn (bijvoorbeeld het meten van het syndroom is niet-destructief).
  • 3D integratie en optische interconnects: Stacking geheugen sterft direct op de top van de logica die sterft kan geheugen bandbreedte knelpunten verlichten. Optische on-chip interconnects kunnen wereldwijde draadroutes in volledig parallelle decoders vervangen, waardoor latency en stroom verminderen.

Meer uitgebreide enquêtes zijn te vinden in dit IEEE Communications Surveys & Tutorials paper over LDPC decoder architecturen en in dit ACM Computing Surveys artikel over energie-efficiënte LDPC decoders.

Conclusie

Parallelle decoderingsarchitecturen hebben LDPC-codes van een theoretische nieuwsgierigheid omgezet in een praktische enabler van moderne high-speed communicatie. Gelaagd, pijpleiding, en volledig parallel ontwerpen elk adres verschillende punten in het ontwerp van de ruimte van doorvoer, gebied, en macht. Voortgezette vooruitgang in halfgeleidertechnologie en algoritme optimalisatie belofte nog sneller en efficiënter decoders in de komende jaren. Of in de basisstations van 5G-netwerken, de terrestrische omroepinfrastructuur, of de exaschaal computercentra van morgen, parallelle LDPC-decoders zullen een cruciaal onderdeel van de wereldwijde informatie-infrastructuur blijven.