Abstract-Decodingen av Low-Density Parity-Check koder av Belief Propagation (BP) algoritmen ses över. Vi kontrollerar den iterativa algoritmen för dess konvergens till ett kodord (termination), vi kör Monte Carlo simuleringar för att hitta sannolikhetsfördelning funktion av termineringstiden, nit. Testad på ett exempel [155, 64, 20] kod, denna termineringskurva visar en maximal och en förlängd algebraisk svans vid de högsta värdena av nit. Syftet är att minska svansen av termineringskurvan vi anser en familj av iterativa algoritmer som ändrar standard BP med hjälp av en enkel avkoppling. Avslappningsparametern styr konvergensen av den modifierade BP-algoritmen till ett minimum av Betefri energi. Förbättringen demonstreras experimentellt för Tillsatsen-Vit-Gaussian Bullerkanal i något område av signal-till-buller-förhållandet. Vi diskuterar också kompromissen mellan avslappningsparametern för det förbättrade iterativa systemet och antalet iterationer. Low-Density Parity-Check (LDPC) koder [1], [2] är de bästa linjära block felkorrigering koder kända idag [3]. Förutom att vara bra koder, d.v.s. kan avkoda utan fel i den termodynamiska gränsen för en oändligt lång blocklängd, kan dessa koder också avkodas effektivt. Huvudidén med Belief Propagation (BP) avkodning är att approximera den faktiska grafiska modellen, framtagen för att lösa statistiska inferens maximal sannolikhet (ML) eller Maximum-A-Postereri (MAP) problem, av en trädliknande struktur utan slingor. Att vara effektiv men suboptimal BP algoritmen misslyckas på vissa konfigurationer av kanalen buller när nära till optimal (men ineffektiv) MAP avkodning skulle vara framgångsrik. BP-avkodning tillåter en viss dualitet i tolkningen. Först av allt, och efter den så kallade Bete-fria energivariationstänkande [4], kan BP förstås som en uppsättning ekvationer för övertygelser (BP-ekvationer) lösa ett begränsat minimering problem. Å andra sidan är en mer traditionell metod att tolka BP i termer av ett iterativt förfarande - så kallad BP iterativ algoritm [1], [5], [2]. Att vara identisk på ett träd (som då BP ekvationer löses explicit genom iterationer från blad till trädcentrum) de två tillvägagångssätt är dock distinkt för ett grafiskt problem med slingor. När det gäller konvergensen finner BP-algoritmerna ett minimum av den Bethe fria energin [4], [6], [7], men i ett allmänt fall garanteras inte konvergens för den standardiserade iterativa BP-standarden. Det är också underförstått att BP misslyckas med att konvergera främst på grund av cirkling av meddelanden i processen för iterationer över att genomdriva konvergens av iterativ algoritm till ett minimum av Bethe Free energi ett antal ändringar av standard iterativ BP diskuterades under de senaste åren. Den trädbaserade omparametriseringsramen [8] tyder på att begränsa kommunikationen på loopy grafen, skär några kanter på ett dynamiskt sätt så att de oönskade effekterna av cirklarna undertrycks. Ett annat, så kallat konkavakonvext förfarande, som infördes [9] och generaliserades [10], tyder på att bryta ner Bethe fri energi i konkava och konvexa delar på så sätt dela upp iterationer i två sekventiella delsteg. När vi lägger märke till att konvergensen av BP-standarden främst beror på att iterationer har överskridits, utvecklar vi i detta dokument en avslappning (dämpande) som botar problemet. Jämfört med de ovan nämnda alternativa metoderna kan detta tillvägagångssätt vara praktiskt taget mer fördelaktigt på grund av dess enkelhet och tonfiskbarhet. I sin enklaste form ges vår ändring av BP iterative förfarande av var latin och grekiska index står för bitar och kontroller och bit / kontrollera relationer, t.ex.. i  till α, α  och i uttrycker LDPC-koden som beaktas, h i är det kanalbullerberoende värdet för log-likelihoods, och η (n) iα är det meddelande som vid nth iterationen associeras med kanten (av respektive tannergraf) som förbinder i-th bit och α-th kontroll. .. är en kvantifierbar parameter. Genom att välja ett tillräckligt litet alternativ kan man garantera konvergens av det iterativa förfarandet till ett minimum av den Bethe fria energin. Å andra sidan är det exakt lika med den iterativa BP-standarden. I uppföljaren härleder och förklarar vi den ändrade iterativa proceduren (1) i detalj. Manuskriptet är organiserat enligt följande. Vi introducerar Bethe fri energi, BP ekvationen och standard iterativ BP i Avsnitt I. Prestanda av standard iterativ BP, analyseras med en termineringskurva, diskuteras i Avsnitt II. Avsnitt III beskriver kontinuerliga och sekventiella diskreta (iterativa) versioner av vår avslappningsmetod. Vi diskuterar prestanda av det modifierade iterativa systemet i avsnitt IV, där Bit-Error-Rate och termineringskurvan för en LDPC-kod som utförs över Additive-White-Gaussian-Noise (AWGN) kanal diskuteras för en rad intressanta värden av Signal-to-Noise-Ratios (SNR). Vi diskuterar också här kompromissen mellan konvergens och antal.
I REF är BP-algoritmen väl studerad i perspektivet av Bethe energi och hur det misslyckas i närvaro av cykler.
Improving convergence of Belief Propagation decoding
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}