Liste dekodning - List decoding

Inden for datalogi , især inden for kodningsteori , er listekodning et alternativ til unik afkodning af fejlkorrektionskoder til store fejlhastigheder. Forestillingen blev foreslået af Elias i 1950'erne. Hovedideen bag listekodning er, at afkodningsalgoritmen i stedet for at udsende en enkelt mulig meddelelse udsender en liste over muligheder, hvoraf den ene er korrekt. Dette giver mulighed for at håndtere et større antal fejl end det, der er tilladt ved unik afkodning.

Den unikke afkodningsmodel i kodningsteori , som er begrænset til at udsende et enkelt gyldigt kodeord fra det modtagne ord, kunne ikke tolerere større brøkdel af fejl. Dette resulterede i et mellemrum mellem fejlkorrektionens ydeevne for stokastiske støjmodeller (foreslået af Shannon ) og den modstridende støjmodel (overvejet af Richard Hamming ). Siden midten af ​​90'erne har betydelige algoritmiske fremskridt fra kodningsteorifællesskabet overført dette hul. Meget af denne fremgang er baseret på en afslappet fejlkorrektionsmodel kaldet listekodning, hvor dekoderen udsender en liste over kodeord til værste tilfælde patologiske fejlmønstre, hvor det faktiske transmitterede kodeord er inkluderet i outputlisten. I tilfælde af typiske fejlmønstre udsender dekoderen imidlertid et unikt enkelt kodeord, der får et modtaget ord, hvilket næsten altid er tilfældet (dog vides det ikke at være sandt for alle koder). Forbedringen her er betydelig, idet fejlkorrektionens ydelse fordobles. Dette skyldes, at dekoderen nu ikke er begrænset af den halve minimum afstandsbarriere. Denne model er meget tiltalende, fordi det er bestemt bedre at have en liste med kodeord end bare at give op. Forestillingen om listekodning har mange interessante anvendelser i kompleksitetsteorien .

Den måde, hvorpå kanalstøj modelleres, spiller en afgørende rolle, idet den styrer den hastighed, med hvilken pålidelig kommunikation er mulig. Der er to hovedskoler i modellering af kanalens adfærd:

• Probabilistisk støjmodel studeret af Shannon, hvor kanalstøj er modelleret nøjagtigt i den forstand, at kanalens probabilistiske opførsel er velkendt, og sandsynligheden for forekomst af for mange eller for få fejl er lav
• Worst-case eller adversarial støjmodel betragtet af Hamming, hvor kanalen fungerer som en modstander, der vilkårligt ødelægger kodeordet underlagt et bundet antal af det samlede antal fejl.

Højdepunktet ved afkodning af lister er, at selv under ugunstige støjforhold er det muligt at opnå den informationsteoretiske optimale afvejning mellem hastighed og brøkdel af fejl, der kan rettes. På en måde er dette som at forbedre fejlkorrektionens ydeevne til det, der er muligt i tilfælde af en svagere, stokastisk støjmodel.

Matematisk formulering

Lad være en fejlkorrektionskode; er med andre ord en kode for længde , dimension og mindsteafstand over et alfabet i størrelse . List-afkodningsproblemet kan nu formuleres som følger: ${\ displaystyle {\ mathcal {C}}}$${\ displaystyle (n, k, d) _ {q}}$${\ displaystyle {\ mathcal {C}}}$${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle d}$${\ displaystyle \ Sigma}$${\ displaystyle q}$

Input: Modtaget ord , fejlbundet${\ displaystyle x \ in \ Sigma ^ {n}}$ ${\ displaystyle e}$

Output: En liste over alle kodeord, hvis hammingsafstand fra højst er . ${\ displaystyle x_ {1}, x_ {2}, \ ldots, x_ {m} \ i {\ mathcal {C}}}$${\ displaystyle x}$${\ displaystyle e}$

Motivation til listekodning

Givet et modtaget ord , som er en støjende version af noget transmitteret kodeord , prøver dekoderen at udsende det transmitterede kodeord ved at placere sit væddemål på et kodeord, der er "tættest" på det modtagne ord. Hamming-afstanden mellem to kodeord bruges som en måling til at finde det nærmeste kodeord, givet det modtagne ord af dekoderen. Hvis er den mindste Hamming afstand af en kode , så der findes to kodeord og som afviger i nøjagtig positioner. I det tilfælde, hvor det modtagne ord er ens i forhold til kodeordene, og entydig afkodning bliver umulig, da dekoderen ikke kan beslutte, hvilken af og til at udgive som det originale transmitterede kodeord. Som et resultat fungerer halvdelen af ​​minimumsafstanden som en kombinatorisk barriere, ud over hvilken entydig fejlkorrektion er umulig, hvis vi kun insisterer på unik afkodning. Modtagne ord som betragtet ovenfor forekommer dog kun i værste tilfælde, og hvis man ser på den måde, Hamming-kugler er pakket i højdimensionelt rum, selv for fejlmønstre ud over halvdelen af ​​minimumsafstanden, er der kun et enkelt kodeord inden for Hamming afstand fra det modtagne ord. Denne påstand har vist sig at have stor sandsynlighed for en tilfældig kode valgt fra et naturligt ensemble og mere for tilfældet med Reed – Solomon-koder, som er godt studeret og ganske allestedsnærværende i den virkelige verden applikationer. Faktisk kan Shannons bevis for kapacitetsteoremet for q -ary symmetriske kanaler ses i lyset af ovenstående påstand om tilfældige koder. ${\ displaystyle y}$${\ displaystyle c}$${\ displaystyle d}$${\ displaystyle {\ mathcal {C}}}$${\ displaystyle c_ {1}}$${\ displaystyle c_ {2}}$${\ displaystyle d}$${\ displaystyle y}$${\ displaystyle c_ {1}}$${\ displaystyle c_ {2}}$${\ displaystyle c_ {1}}$${\ displaystyle c_ {2}}$${\ displaystyle y}$${\ displaystyle e}$${\ displaystyle c}$${\ displaystyle e}$

I henhold til mandatet for listekodning, for worst-case-fejl, tillader dekoderen at udsende en lille liste med kodeord. Med nogle kontekstspecifikke eller sideoplysninger kan det være muligt at beskære listen og gendanne det originale transmitterede kodeord. Derfor synes det generelt at være en stærkere gendannelsesmodel end unik afkodning.

Liste-dekodningspotentiale

For at der kan findes en polynomisk-liste-dekodningsalgoritme, har vi brug for den kombinerende garanti, at enhver Hamming-kugle med radius omkring et modtaget ord (hvor er brøkdelen af ​​fejl i form af bloklængden ) har et lille antal kodeord. Dette skyldes, at selve listestørrelsen klart er en lavere grænse for algoritmens køretid. Derfor kræver vi, at listestørrelsen er et polynom i kodelængden af koden. En kombinatorisk konsekvens af dette krav er, at det pålægger en øvre grænse for kodens hastighed. Liste dekodning lover at opfylde denne øvre grænse. Det er vist ikke-konstruktivt, at der findes en kodningskode, der kan listes afkodet op til en brøkdel af fejl, der nærmer sig . Mængden omtales i litteraturen som listekodningskapacitet. Dette er en betydelig gevinst sammenlignet med den unikke dekodningsmodel, da vi nu har potentialet til at rette dobbelt så mange fejl. Naturligvis skal vi have mindst en brøkdel af de transmitterede symboler for at være korrekte for at gendanne meddelelsen. Dette er en informationsteoretisk nedre grænse for antallet af korrekte symboler, der kræves for at udføre dekodning, og med listekodning kan vi potentielt opnå denne informationsteoretiske grænse. For at realisere dette potentiale har vi dog brug for eksplicitte koder (koder, der kan konstrueres i polynomisk tid) og effektive algoritmer til at udføre kodning og afkodning. ${\ displaystyle pn}$${\ displaystyle r}$${\ displaystyle p}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle R}$${\ displaystyle 1-R}$${\ displaystyle 1-R}$${\ displaystyle R}$

( p , L ) -liste-afkodbarhed

For enhver fejlfraktion og et helt tal siges en kode at være afkodelig på listen op til en brøkdel af fejl med højst listestørrelse eller -liste-afkodelig, hvis antallet af kodeord inden for Hamming-afstand fra højst er${\ displaystyle 0 \ leqslant p \ leqslant 1}$${\ displaystyle L \ geqslant 1}$${\ displaystyle {\ mathcal {C}} \ subseteq \ Sigma ^ {n}}$${\ displaystyle p}$${\ displaystyle L}$${\ displaystyle (p, L)}$${\ displaystyle y \ in \ Sigma ^ {n}}$${\ displaystyle c \ in C}$${\ displaystyle pn}$${\ displaystyle y}$${\ displaystyle L.}$

Kombinatorik af afkodning af lister

Forholdet mellem en kodes listerafkodbarhed og andre grundlæggende parametre som minimum afstand og hastighed er blevet undersøgt forholdsvis godt. Det er vist, at hver kode kan afkodes på listen ved hjælp af små lister ud over halvdelen af ​​minimumsafstanden op til en grænse kaldet Johnson-radius. Dette er ret vigtigt, fordi det beviser eksistensen af -liste-afkodelige koder med god hastighed med en listeafkodningsradius, der er meget større end Med andre ord udelukker Johnson bunden muligheden for at have et stort antal kodeord i en Hamming-kugle af radius lidt større end hvilket betyder, at det er muligt at rette langt flere fejl med listekodning. ${\ displaystyle (p, L)}$${\ displaystyle {\ tfrac {d} {2}}.}$${\ displaystyle {\ tfrac {d} {2}}}$

Liste-afkodningskapacitet

Sætning (List-dekodningskapacitet). Lad og De følgende to udsagn gælder for blok nok længde . ${\ displaystyle q \ geqslant 2,0 \ leqslant p \ leqslant 1 - {\ tfrac {1} {q}}}$${\ displaystyle \ epsilon \ geqslant 0.}$${\ displaystyle n}$

i) Hvis der findes en -liste afkodelig kode.${\ displaystyle R \ leqslant 1-H_ {q} (p) - \ epsilon}$${\ displaystyle (p, O (1 / \ epsilon))}$

ii) Hvis alle -liste-afkodelige koder har .${\ displaystyle R \ geqslant 1-H_ {q} (p) + \ epsilon}$${\ displaystyle (p, L)}$${\ displaystyle L = q ^ {\ Omega (n)}}$

Hvor

${\ displaystyle H_ {q} (p) = p \ log _ {q} (q-1) -p \ log _ {q} p- (1-p) \ log _ {q} (1-p)}$

er den ærlige entropiefunktion defineret for og udvidet af kontinuitet til${\ displaystyle q}$${\ displaystyle p \ in (0,1)}$${\ displaystyle [0,1].}$

Hvad dette betyder, er, at der for hastigheder, der nærmer sig kanalkapaciteten, findes listen afkodelige koder med lister i polynomstørrelse, der muliggør effektive afkodningsalgoritmer, medens for størrelser, der overstiger kanalkapaciteten, bliver listestørrelsen eksponentiel, hvilket udelukker eksistensen af ​​effektive afkodningsalgoritmer.

Beviset for listekodningskapacitet er en betydelig, idet det nøjagtigt matcher kapaciteten til en- symmetrisk kanal . Faktisk bør udtrykket "listekodningskapacitet" faktisk læses som kapaciteten til en modstandskanal under listekodning. Beviset for listekodningskapacitet er også et vigtigt resultat, der peger på den optimale kompromis mellem hastigheden af ​​en kode og den brøkdel af fejl, der kan rettes under listekodning. ${\ displaystyle q}$${\ displaystyle qSC_ {p}}$

Skitse af bevis

Ideen bag beviset svarer til Shannons bevis for kapacitet på den binære symmetriske kanal, hvor en tilfældig kode vælges og viser, at den er -liste-afkodelig med stor sandsynlighed, så længe frekvensen for satser, der overstiger ovennævnte mængde, er kan vises, at listestørrelsen bliver superpolynomisk stor. ${\ displaystyle BSC_ {p}}$${\ displaystyle (p, L)}$${\ displaystyle R \ leqslant 1-H_ {q} (p) - {\ tfrac {1} {L}}.}$${\ displaystyle L}$

En "dårlig" begivenhed er defineret som en, hvor, givet et modtaget ord og budskaber er det sådan, at for hver hvor er den del af fejl, som vi ønsker at rette og er Hamming kugle af radius med den modtagne ord som centrum . ${\ displaystyle y \ in [q] ^ {n}}$${\ displaystyle L + 1}$${\ displaystyle m_ {0}, \ ldots, m_ {L} \ i [q] ^ {k},}$${\ displaystyle {\ mathcal {C}} (m_ {i}) \ i B (y, pn)}$${\ displaystyle 0 \ leqslant i \ leqslant L}$${\ displaystyle p}$${\ displaystyle B (y, pn)}$${\ displaystyle pn}$${\ displaystyle y}$

Nu, sandsynligheden for, at et kodeord knyttet til en fast besked ligger i en Hamming bold er givet ved ${\ displaystyle {\ mathcal {C}} (m_ {i})}$${\ displaystyle m_ {i} \ i [q] ^ {k}}$${\ displaystyle B (y, pn)}$

${\ displaystyle \ Pr \ venstre [C (m_ {i}) \ i B (y, pn) \ højre] = {\ frac {\ mathrm {Vol} _ {q} (y, pn)} {q ^ { n}}} \ leqslant q ^ {- n (1-H_ {q} (p))},}$

hvor mængden er volumen på en Hamming-kugle med radius med det modtagne ord som centrum. Uligheden i ovennævnte forhold følger fra den øvre grænse på lydstyrken på en Hamming-kugle. Mængden giver et meget godt skøn over lydstyrken på en Hamming-kugle med radius centreret på ethvert ord på Sagt på en anden måde, lydstyrken på en Hamming-kugle er oversættelses invariant. For at fortsætte med bevisskitse trygler vi foreningen bundet i sandsynlighedsteori, der fortæller os, at sandsynligheden for, at en dårlig begivenhed sker for en given, er øvre grænse af mængden . ${\ displaystyle Vol_ {q} (y, pn)}$${\ displaystyle pn}$${\ displaystyle y}$${\ displaystyle q ^ {H_ {q} (p)}}$${\ displaystyle p}$${\ displaystyle [q] ^ {n}.}$${\ displaystyle (y, m_ {0}, \ dots, m_ {L})}$${\ displaystyle q ^ {- n (L + 1) (1-H_ {q} (p))}}$

Med det ovenstående i tankerne kan sandsynligheden for, at "enhver" dårlig begivenhed sker, være mindre end . For at vise dette, arbejder vi os hen over alle mulige modtagne ord og alle mulige undergrupper af meddelelser i${\ displaystyle 1}$${\ displaystyle y \ in [q] ^ {n}}$${\ displaystyle L}$${\ displaystyle [q] ^ {k}.}$

Når vi nu vender os mod beviset for del (ii), er vi nødt til at vise, at der er superpolynomisk mange kodeord omkring hver, når hastigheden overstiger listekodningskapaciteten. Vi er nødt til at vise, at det er superpolynomielt stort, hvis hastigheden . Fix et kodeord . Nu har vi det for hver plukket tilfældigt ${\ displaystyle y \ in [q] ^ {n}}$${\ displaystyle | {\ mathcal {C}} \ cap B (y, pn) |}$${\ displaystyle R \ geqslant 1-H_ {q} (p) + \ epsilon}$${\ displaystyle c \ in {\ mathcal {C}}}$${\ displaystyle y \ in [q] ^ {n}}$

${\ displaystyle \ Pr [c \ i B (y, pn)] = \ Pr [y \ i B (c, pn)]}$

da Hamming-kugler er oversættelsesinvolant. Fra definitionen af ​​lydstyrken på en Hamming-kugle og det faktum, at vi vælges ensartet tilfældigt fra vi har også ${\ displaystyle y}$${\ displaystyle [q] ^ {n}}$

${\ displaystyle \ Pr [c \ i B (y, pn)] = \ Pr [y \ i B (c, pn)] = {\ frac {\ mathrm {Vol} (y, pn)} {q ^ { n}}} \ geqslant q ^ {- n (1-H_ {q} (p)) - o (n)}}$

Lad os nu definere en indikatorvariabel sådan ${\ displaystyle X_ {c}}$

${\ displaystyle X_ {c} = {\ begynde {cases} 1 & c \ i B (y, pn) \\ 0 & {\ text {ellers}} \ end {cases}}}$

At tage forventningen til lydstyrken på en Hamming-kugle, vi har

${\ displaystyle {\ begin {align} E [| B (y, pn) |] & = \ sum _ {c \ i {\ mathcal {C}}} E [X_ {c}] \\ [4pt] & = \ sum _ {c \ i {\ matematisk {C}}} \ Pr [X_ {c} = 1] \\ [4pt] & \ geqslant \ sum q ^ {- n (1-H_ {q} (p ) + o (n))} \\ [4pt] & = \ sum q ^ {n (R-1 + H_ {q} (p) + o (1))} \\ [4pt] & \ geqslant q ^ {\ Omega (n)} \ ende {justeret}}}$

Derfor har vi med den sandsynlige metode vist, at hvis hastigheden overstiger listekodningskapaciteten, bliver listestørrelsen superpolynomisk stor. Dette afslutter bevisskitse for listekodningskapacitet.

Liste-afkodningsalgoritmer

I perioden 1995 til 2007 udviklede kodningsteori-samfundet gradvist mere effektive algoritmer til dekodning af lister. Algoritmer til Reed – Solomon-koder, der kan dekode op til Johnson-radius, som findes, hvor er den normaliserede afstand eller den relative afstand. For Reed-Solomon-koder, hvilket betyder, at en brøkdel af fejl kan rettes. Nogle af de mest fremtrædende algoritmer til dekodning af lister er følgende: ${\ displaystyle 1 - {\ sqrt {1- \ delta}}}$${\ displaystyle \ delta}$${\ displaystyle \ delta = 1-R}$${\ displaystyle 1 - {\ sqrt {R}}}$

• Sudan '95 - Den første kendte ikke-trivielle listekodningsalgoritme for Reed – Solomon-koder, der opnåede effektiv listekodning op til fejl udviklet af Madhu Sudan .${\ displaystyle 1 - {\ sqrt {2R}}}$
• Guruswami – Sudan '98 - En forbedring af den ovennævnte algoritme til listekodning af Reed – Solomon koder op til fejl fra Madhu Sudan og hans daværende doktorand Venkatesan Guruswami .${\ displaystyle 1 - {\ sqrt {R}}}$
• Parvaresh – Vardy '05 - I et gennembrudspapir præsenterede Farzad Parvaresh og Alexander Vardy koder, der kan listes dekodet ud over radius for lave priser . Deres koder er varianter af Reed-Solomon-koder, som opnås ved at evaluere korrelerede polynomer i stedet for lige som i tilfældet med sædvanlige Reed-Solomon-koder.${\ displaystyle 1 - {\ sqrt {R}}}$${\ displaystyle R}$${\ displaystyle m \ geqslant 1}$${\ displaystyle 1}$
• Guruswami – Rudra '06 - I endnu et gennembrud giver Venkatesan Guruswami og Atri Rudra eksplicitte koder, der opnår listekodningskapacitet , det vil sige, de kan lister dekodes op til radius for enhver . Med andre ord er dette fejlkorrektion med optimal redundans. Dette besvarede et spørgsmål, der havde været åbent i omkring 50 år. Dette arbejde er blevet inviteret til afsnittet Forskningshøjdepunkter i Kommunikationen af ​​ACM (som er "helliget de vigtigste forskningsresultater, der er offentliggjort i Computer Science i de senere år") og blev nævnt i en artikel med titlen "Coding and Computing Join Forces" i 21. september 2007-udgaven af ​​Science-magasinet. Koderne, de får, kaldes foldede Reed-Solomon-koder, som kun er almindelige Reed-Solomon-koder, men ses som en kode over et større alfabet ved omhyggelig bundtning af kodeordssymboler.${\ displaystyle 1-R- \ epsilon}$${\ displaystyle \ epsilon> 0}$

På grund af deres allestedsnærværende og de smukke algebraiske egenskaber, de har, var listekodningsalgoritmer til Reed – Solomon-koder et hovedfokus for forskere. Listekodningsproblemet for Reed – Solomon-koder kan formuleres som følger:

Input : For en Reed-Solomon-kode får vi parret til , hvor er th bit af det modtagne ord og 's er forskellige punkter i det endelige felt og en fejlparameter . ${\ displaystyle [n, k + 1] _ {q}}$${\ displaystyle (\ alpha _ {i}, y_ {i})}$${\ displaystyle 1 \ leq i \ leq n}$${\ displaystyle y_ {i}}$${\ displaystyle i}$${\ displaystyle \ alpha _ {i}}$${\ displaystyle F_ {q}}$${\ displaystyle e = nt}$

Output : Målet er at finde alle polynomier på graden som højst, hvilket er meddelelsens længde, så det er mindst værdier for . Her vil vi gerne have så lille som muligt, så større antal fejl kan tolereres. ${\ displaystyle P (X) \ i F_ {q} [X]}$${\ displaystyle k}$${\ displaystyle p (\ alpha _ {i}) = y_ {i}}$${\ displaystyle t}$${\ displaystyle i}$${\ displaystyle t}$

Med ovenstående formulering er den generelle struktur for listekodningsalgoritmer til Reed-Solomon-koder som følger:

Trin 1 : (Interpolation) Find en ikke-nul-bivariat polynom, sådan som for . ${\ displaystyle Q (X, Y)}$${\ displaystyle Q (\ alpha _ {i}, y_ {i}) = 0}$${\ displaystyle 1 \ leq i \ leq n}$

Trin 2 : (Root fund / Faktorisering) Output alle grad polynomier således at er en faktor dvs. . For hvert af disse polynomer skal du kontrollere, om der er mindst værdier på . Hvis dette er tilfældet, skal du inkludere et sådant polynom i outputlisten. ${\ displaystyle k}$${\ displaystyle p (X)}$${\ displaystyle Yp (X)}$${\ displaystyle Q (X, Y)}$${\ displaystyle Q (X, p (X)) = 0}$${\ displaystyle p (\ alpha _ {i}) = y_ {i}}$${\ displaystyle t}$${\ displaystyle i \ in [n]}$${\ displaystyle p (X)}$

I betragtning af det faktum, at bivariate polynomer kan faktoreres effektivt, kører ovennævnte algoritme i polynomietid.

Anvendelser inden for kompleksitetsteori og kryptografi

Algoritmer udviklet til listekodning af flere interessante kodefamilier har fundet interessante anvendelser inden for beregningskompleksitet og kryptografiområdet . Følgende er en eksempleliste over applikationer uden for kodningsteori:

• Konstruktion af hard-core predikater fra envejs permutationer .
• Forudsigelse af vidner for NP-søgningsproblemer.
• Forstærker hårdheden af ​​boolske funktioner.
• Gennemsnitlig sagshårdhed for permanente tilfældige matrixer
• Ekstraktorer og Pseudorandom-generatorer .
• Effektiv forrædersporing.

eksterne links

• En undersøgelse af listen dekodning af Madhu Sudan
• Noter fra et kursus undervist af Madhu Sudan
• Noter fra et kursus undervist af Luca Trevisan
• Noter fra et kursus undervist af Venkatesan Guruswami
• Noter fra et kursus undervist af Atri Rudra
• P. Elias, "Liste dekodning for støjende kanaler," Teknisk rapport 335, Research Laboratory of Electronics, MIT, 1957.
• P. Elias, "Fejlkorrektion af koder til listekodning," IEEE-transaktioner om informationsteori, vol. 37, s. 5–12, 1991.
• JM Wozencraft, "List dekodning", kvartalsvis statusrapport, Research Laboratory of Electronics, MIT, vol. 48, s. 90–95, 1958.
• Venkatesan Guruswami 's ph.d.-afhandling
• Algoritmiske resultater i listekodning
• Foldet Reed – Solomon-kode