Abstract-Vi illustrerar nyttan av den nyligen utvecklade loopkalkylen [1], [2] för att förbättra algoritmen Trof Propagation (BP). Om algoritmen som minimerar den Bethe fria energin misslyckas ändrar vi den fria energin genom att redovisa för en kritisk loop i en grafisk representation av koden. Den log-likelihood specifika kritiska slingan hittas med hjälp av slingan kalkyl. Den allmänna metoden testas med hjälp av ett exempel på avkodning av linjär programmering (LP), som kan ses som en särskild gräns för BP-avkodningen. Med tanke på (155, 64, 20) koden som utför över Additive-White-Gaussian kanal visar vi att loopen kalkyl förbättrar LP avkodning och korrigerar alla tidigare hittat farliga konfigurationer av log-likelihoods relaterade till pseudo-kodord med lågt effektivt avstånd, vilket minskar kodens fel-golv. Trosförökning (BP) utgör en effektiv approximation, liksom en algoritm, som gäller många inference problem i statistisk fysik [3] [9], och datavetenskap [10]. Alla dessa problem kan anges i form av beräkning av marginell sannolikhet på ett faktordiagram. Om den underliggande grafstrukturen inte innehåller några loopar, dvs. Det är ett träd, BP är exakt, är bara en approximation i fallet med en allmän graf. BP approximationen kan omräknas i termer av en variationsprincip [11], [12], [13], där BP ekvationer beskriver ett minimum av den så kallade Bethe fri energi, och standard BP algoritm [6], [7] innebär att lösa BP ekvationer iterativt. I kodningsteorin spelar BP en speciell roll som avkodning av valet för Low Density Parity Check (LDPC) Koder införs av R. Gallager [6]. Dessa koder, som beskrivs i termer av glesa (Tanner) grafer, är bland de bäst presterande koder som hittills varit kända. Faktiskt, dessa koder fungerar så bra exakt på grund av hög kvalitet prestanda för beräkningseffektiv BP avkodningssystem [6], [8], [9]. I vattenfallsdomänen, d.v.s. Vid låga och måttliga Signalto-Noise Ratios (SNR), kommer Frame-Error-Rate (FER) eller BitError-Rate (Berror-Rate) av en LDPC-kod avkodad med hjälp av BP nära den optimala men ineffektiva Maximi-likviditet och Maximum-a-Posterori avkodningar. Men i den låga bullerregim BP avkodning klart misslyckas med att approxima ML i praktiska (finita storlek) LDPC-koder, vilket orsakar felet- Vi är tacksamma till M. Stepanov för många stora kommentarer och diskussioner. Detta arbete utfördes under överinseende av National Nuclear Security Administration of the U.S. [12] på problem inom informations- och datavetenskap. GBP har visat sig fungera bra för problemen med många korta slingor, som Inter-Symbol Interference på en regelbunden tvådimensionell lattice [28], där övergången till en grovkornig kluster erbjuder en förbättring jämfört med standard BP. Den enda allvarliga nackdelen med metoden är kostnaden för en overhead som skalar exponentiellt med klusterstorleken. Ett effektivt alternativ till GBP, som påstås vara framgångsrikt när det gäller att beskriva vissa slumpmässiga grafer och slumpmässiga spinnmodeller på gitter, har nyligen diskuterats i [26]. Metoden är baserad på att stänga systemet av hålrum ekvationer och föreslår ett sätt att redogöra för korrelationer (många slingor) på alla skalor. Trots deras potential när det gäller att hantera mycket degenererade problem där den blotta BP-metoden misslyckas verkar de ovan nämnda metoderna/algoritmerna (kanske med undantag för en eventuell förlängning av [26]) inte lämpliga när det gäller att hantera problemet med felgolvet. I själva verket förväntar man sig att varje faktisk kod (i motsats till ensemble av koder) har en diskret uppsättning av väldefinierade och relativt enkla bråkmakare (pseudo-kodord) lokaliserade på en subgraf. Därför, för varje (sällsynt) fel på standard BP måste man identifiera och korrigera för en relativt lång korrelerad konfiguration som är lokaliserad dock på en liten del av det totala antalet bitar. I detta dokument föreslås ett effektivt tillvägagångssätt som generaliserar BP algoritmen och som kan minska oönskade fel golvet effekt. Vår metod är baserad på det nyligen utvecklade analysverktyget, slingkalkyl [1], [2], som representerar partitionsfunktionen (och därmed marginalsannolikheten) i termer av en ändlig serie där varje term är associerad med en generaliserad slinga på grafen och nollan bidrag motsvarar den nakna BP approximationen. Vi antar att för en ögonblicksljudkonfiguration som orsakar ett BP-fel finns det alltid en relativt enkel loopkorrigering till den kala BP (i terminologin för loopkalkylen) som ger ett lika eller jämförbart bidrag till partitionsfunktionen. Vi föreslår vidare ett förbättrat avkodningssystem baserat på att hitta denna kritiska loop korrigering (i fallet med den nakna BP fel) följt av att korrigera felet. Detta uppnås genom en korrekt modifiering av Bethe fri energi och BP ekvationer. Dessa idéer verifieras med ett exempel på Tanner (155, 64, 20) kod [29] som utför över AdditiveWhite-Gaussian-Noise (AWGN) kanal och avkodas med Linjär programmering (LP) avkodning [30]. Vi bygger detta test på analys av uppsättningen pseudo-kodord som nyligen hittats för denna kod av LP-baserade pseudo-kodordssökning algoritm [31]. Vi introducerar LP-erasure-avkodningen som motsvarar den vanliga LP-avkodningen med fullständig eller partiell radering av information vid bitarna längs den kritiska slingan. Vi visar att LP-erasuralgoritmen korrigerar fel i samband med alla tidigare funna pseudo-kodord i Tanner-koden (- 200 av dem) som helt täpper till felgolvsklyftan mellan den lägsta LP-instanton, med det effektiva avståndet -16.4037, och Hamming-avståndet 20 av koden. Manuskriptet är organiserat enligt följande. Ett utvidgat inledande avsnitt I består av fyra underavsnitt. Underavsnitt I-A introducerar notationer och korta översikter avkodning av en binär linjär kod. Underavsnitt I-B beskriver loopkalkylen [1], [2] som också kompletterar den med en ny variationstolkning som inte diskuterades i de ursprungliga dokumenten. Underavsnitt I-C beskriver beräkningen av a-posteriori log-likelihoods (magnetiseringar) inom loopkalkylen. Genom underavsnitt I-D upprättas en koppling mellan Bethe free energy approach och loopkalkylen och LP-avkodningen. Avsnitt II visar en underliggande loopstruktur, t.ex. Uppkomst av vissa kritiska slingor, för familjen av instantons som visas i (155, 64, 20) kod som utför över AWGN-kanalen och avkodas av LP [31]. Den effektiva fria energimetoden, som föreslår en ändring av BP-mätarna för att ta hänsyn till den kritiska slingan, införs i avsnitt III. En förbättrad LP-avkodning, kallad LP-erasure, presenteras i avsnitt IV. Numeriskt test av LP-erasuralgoritmen med hjälp av ett exempel på (155, 64, 20) koden diskuteras i underavsnitt IV-A där vi också visar att alla tidigare hittade bare LP-instansons (mest skadliga bullerkonfigurationer) faktiskt korrigeras genom LP-erasurförfarandet vilket helt minskar det felgolv som observerats för standard LP-avkodning. Det slutliga avsnitt V innehåller slutsatser och diskussioner.
Slutligen, för att gå längre än trosutbredning, har det funnits metoder för att använda högre ordertermer för slingan expansion, se till exempel REF för en tillämpning på lågdensitet paritet kontrollkoder.
Loop Calculus Helps to Improve Belief Propagation and Linear Programming Decodings of Low-Density-Parity-Check Codes
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science', 'Physics']}