Lista avkodning - List decoding

Inom datavetenskap , särskilt inom kodningsteori , är listavkodning ett alternativ till unik avkodning av felkorrigerande koder för stora felfrekvenser. Begreppet föreslogs av Elias på 1950-talet. Huvudtanken bakom listavkodning är att avkodningsalgoritmen istället för att mata ut ett enda möjligt meddelande matar ut en lista över möjligheter, varav en är korrekt. Detta möjliggör hantering av ett större antal fel än det som tillåts genom unik avkodning.

Den unika avkodningsmodellen i kodningsteorin , som är begränsad att mata ut ett enda giltigt kodord från det mottagna ordet, kunde inte tolerera större bråkdel av fel. Detta resulterade i ett gap mellan felkorrigeringsprestanda för stokastiska bullermodeller (föreslagna av Shannon ) och den motsatta brusmodellen (betraktad av Richard Hamming ). Sedan mitten av 90-talet har betydande algoritmiska framsteg från kodningsteorinsamhället övergett detta gap. Mycket av detta framsteg baseras på en avslappnad felkorrigeringsmodell som kallas listavkodning, varvid avkodaren matar ut en lista med kodord för värsta fall patologiska felmönster där det faktiska överförda kodordet ingår i utgångslistan. Vid typiska felmönster matar avkodaren emellertid ut ett unikt enskilt kodord med ett mottaget ord, vilket nästan alltid är fallet (detta är dock inte känt för att vara sant för alla koder). Förbättringen här är betydelsefull genom att felkorrigeringsprestanda fördubblas. Detta beror på att avkodaren nu inte begränsas av avståndsbarriären som är halva minima. Den här modellen är väldigt tilltalande eftersom det är säkert bättre att ha en lista med kodord än att bara ge upp. Begreppet listavkodning har många intressanta tillämpningar inom komplexitetsteorin .

Det sätt på vilket kanalbruset modelleras spelar en avgörande roll genom att det styr hastigheten med vilken tillförlitlig kommunikation är möjlig. Det finns två huvudskolor i att modellera kanalens beteende:

• Probabilistisk brusmodell studerad av Shannon i vilken kanalbruset modelleras exakt i den meningen att kanalens probabilistiska beteende är välkänt och sannolikheten för uppträdande av för många eller för få fel är låg
• Värsta fall eller motsatsbrusmodell som Hamming betraktar där kanalen fungerar som en motståndare som godtyckligt skadar kodordet med förbehåll för det totala antalet fel.

Höjdpunkten med listavkodning är att även under motsatta brusförhållanden är det möjligt att uppnå den informationsteoretiska optimala avvägningen mellan hastighet och bråk av fel som kan korrigeras. I en viss mening är det här som att förbättra felkorrigeringsprestanda till det som är möjligt i fallet med en svagare, stokastisk brusmodell.

Matematisk formulering

Låt vara en felkorrigerande kod; med andra ord är en kod för längd , dimension och minsta avstånd över ett alfabet i storlek . Listavkodningsproblemet kan nu formuleras enligt följande: ${\ displaystyle {\ mathcal {C}}}$${\ displaystyle (n, k, d) _ {q}}$${\ displaystyle {\ mathcal {C}}}$${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle d}$${\ displaystyle \ Sigma}$${\ displaystyle q}$

Inmatning: Mottaget ord , felbundet${\ displaystyle x \ in \ Sigma ^ {n}}$ ${\ displaystyle e}$

Output: En lista med alla kodord vars hammaravstånd från är högst . ${\ displaystyle x_ {1}, x_ {2}, \ ldots, x_ {m} \ i {\ mathcal {C}}}$${\ displaystyle x}$${\ displaystyle e}$

Motivation för listavkodning

Med tanke på ett mottaget ord , som är en bullrig version av något överfört kodord , försöker avkodaren att mata ut det överförda kodordet genom att placera sin satsning på ett kodord som är "närmast" till det mottagna ordet. Hammingavståndet mellan två kodord används som en metrisk för att hitta det närmaste kodordet, givet det mottagna ordet av avkodaren. Om det är det minsta Hammingavståndet för en kod , finns det två kodord och som skiljer sig exakt i positioner. I det fall där det mottagna ordet är lika långt ifrån kodorden och otvetydig avkodning blir omöjlig eftersom avkodaren inte kan bestämma vilken av och att mata ut som det ursprungliga överförda kodordet. Som ett resultat fungerar det halva minimileavståndet som en kombinatorisk barriär utöver vilken entydig felkorrigering är omöjlig om vi bara insisterar på unik avkodning. Emellertid uppnådda mottagna ord som ovan beaktas endast i värsta fall och om man ser på hur Hamming-bollar är packade i högdimensionellt utrymme, även för felmönster över halva minsta avstånd, finns det bara ett enda kodord inom Hammande avstånd från det mottagna ordet. Detta påstående har visat sig ha stor sannolikhet för en slumpmässig kod som valts från en naturlig ensemble och mera för fallet med Reed – Solomon-koder som är väl studerade och ganska allestädes närvarande i den verkliga världen applikationer. I själva verket kan Shannons bevis på kapacitetssatsen för q -ary symmetriska kanaler ses mot bakgrund av ovanstående krav på slumpmässiga 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}$

Under mandat för listavkodning, för värsta fall, tillåter avkodaren att mata ut en liten lista med kodord. Med viss sammanhangsspecifik information eller sidoinformation kan det vara möjligt att beskära listan och återställa det ursprungliga överförda kodordet. I allmänhet verkar det här vara en starkare felåterställningsmodell än unik avkodning.

Listavkodningspotential

För att en polynom-tid-lista-avkodningsalgoritm ska kunna existera, behöver vi den kombinerande garantin att varje Hamming-boll med radie runt ett mottaget ord (där är bråkdelen av fel i termer av blockets längd ) har ett litet antal kodord. Detta beror på att själva liststorleken tydligt är en lägre gräns för algoritmens körtid. Därför kräver vi att liststorleken är ett polynom i kodens blocklängd . En kombinatorisk konsekvens av detta krav är att det ålägger en övre gräns för hastigheten för en kod. Listavkodning lovar att möta denna övre gräns. Det har visats på ett icke-konstruktivt sätt att det finns en kod som kan avkodas upp till en bråkdel av fel som närmar sig . Mängden benämns i litteraturen som listavkodningskapacitet. Detta är en betydande vinst jämfört med den unika avkodningsmodellen eftersom vi nu har potential att korrigera dubbelt så många fel. Naturligtvis måste vi ha minst en bråkdel av de överförda symbolerna för att vara korrekta för att återställa meddelandet. Detta är en informationsteoretisk nedre gräns för antalet korrekta symboler som krävs för att utföra avkodning och med listavkodning kan vi potentiellt uppnå denna informationsteoretiska gräns. För att förverkliga denna potential behöver vi emellertid explicita koder (koder som kan konstrueras i polynom tid) och effektiva algoritmer för att utföra kodning och avkodning. ${\ displaystyle pn}$${\ displaystyle r}$${\ displaystyle p}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle R}$${\ displaystyle 1-R}$${\ displaystyle 1-R}$${\ displaystyle R}$

( p , L ) -lista-avkodbarhet

För varje fel fraktion och ett heltal , en kod sägs vara lista avkodningsbart upp till en bråkdel av fel med listan storlek som mest eller -lista-avkodnings om för varje antalet kodord i Hamming avstånd från är som mest${\ 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 för listavkodning

Förhållandet mellan listavkodningsbarhet för en kod och andra grundläggande parametrar såsom minsta avstånd och hastighet har studerats ganska väl. Det har visats att varje kod kan listas av avkodad med hjälp av små listor utöver halva minsta avståndet upp till en gräns kallad Johnson-radien. Detta är ganska betydelsefullt eftersom det bevisar förekomsten av -lista-avkodningsbara koder med bra hastighet med en listavkodningsradie som är mycket större än Med andra ord utesluter Johnson bunden möjligheten att ha ett stort antal kodord i en Hamming-boll av radie något större än vilket innebär att det är möjligt att korrigera mycket fler fel med listavkodning. ${\ displaystyle (p, L)}$${\ displaystyle {\ tfrac {d} {2}}.}$${\ displaystyle {\ tfrac {d} {2}}}$

Lista-avkodningskapacitet

Ställe (Lista-avkodningskapacitet). Låt och Följande två påståenden gäller för tillräckligt stor blocklängd . ${\ displaystyle q \ geqslant 2,0 \ leqslant p \ leqslant 1 - {\ tfrac {1} {q}}}$${\ displaystyle \ epsilon \ geqslant 0.}$${\ displaystyle n}$

i) Om det finns en- lista avkodbar kod.${\ displaystyle R \ leqslant 1-H_ {q} (p) - \ epsilon}$${\ displaystyle (p, O (1 / \ epsilon))}$

ii) Om , har varje- list-avkodbar kod .${\ displaystyle R \ geqslant 1-H_ {q} (p) + \ epsilon}$${\ displaystyle (p, L)}$${\ displaystyle L = q ^ {\ Omega (n)}}$

Var

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

är den entala entropifunktionen definierad för och utvidgas med kontinuitet till${\ displaystyle q}$${\ displaystyle p \ in (0,1)}$${\ displaystyle [0,1].}$

Vad detta betyder är att för hastigheter som närmar sig kanalkapaciteten finns det listade avkodningsbara koder med listor av polynomstorlek som möjliggör effektiva avkodningsalgoritmer, medan för hastigheter som överstiger kanalkapaciteten blir liststorleken exponentiell som utesluter förekomsten av effektiva avkodningsalgoritmer.

Beviset för listavkodningskapacitet är betydande genom att det exakt matchar kapaciteten för en- symmetrisk kanal . I själva verket bör termen "listavkodningskapacitet" faktiskt läsas som kapaciteten för en motsatt kanal under listavkodning. Dessutom är beviset för listavkodningskapacitet ett viktigt resultat som stifter pekar på den optimala avvägningen mellan hastigheten för en kod och den bråkdel av fel som kan korrigeras under listavkodning. ${\ displaystyle q}$${\ displaystyle qSC_ {p}}$

Skiss av bevis

Idén bakom beviset liknar Shannons bevis för kapacitet för den binära symmetriska kanalen där en slumpmässig kod väljs och visar att den är -lista-avkodbar med stor sannolikhet så länge som hastigheten för hastigheter som överstiger ovanstående mängd, kan visas att liststorleken blir superpolynomiellt stor. ${\ displaystyle BSC_ {p}}$${\ displaystyle (p, L)}$${\ displaystyle R \ leqslant 1-H_ {q} (p) - {\ tfrac {1} {L}}.}$${\ displaystyle L}$

En "dålig" händelse definieras som en sådan, med tanke på ett mottaget ord och meddelanden så händer det att för varje var är den bråkdel av fel som vi vill korrigera och är Hamming-radien med det mottagna ordet som centrum . ${\ displaystyle y \ in [q] ^ {n}}$${\ displaystyle L + 1}$${\ displaystyle m_ {0}, \ ldots, m_ {L} \ in [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 ges sannolikheten för att ett kodord associerat med ett fast meddelande ligger i en Hamming-boll${\ displaystyle {\ mathcal {C}} (m_ {i})}$${\ displaystyle m_ {i} \ in [q] ^ {k}}$${\ displaystyle B (y, pn)}$

${\ displaystyle \ Pr \ vänster [C (m_ {i}) \ i B (y, pn) \ höger] = {\ frac {\ mathrm {Vol} _ {q} (y, pn)} {q ^ { n}}} \ leqslant q ^ {- n (1-H_ {q} (p))},}$

där kvantiteten är volymen på en Hamming-boll med radie med det mottagna ordet som centrum. Ojämlikheten i ovanstående relation följer från den övre gränsen på volymen på en Hamming-boll. Mängden ger en mycket bra uppskattning på volymen på en Hamming-boll med radie centrerad på något ord på Sätt på ett annat sätt, volymen på en Hamming-boll är översättnings-invariant. För att fortsätta med bevisskissen, trycker vi fram den förbundna bundna i sannolikhetsteorin som säger att sannolikheten för att en dålig händelse inträffar för en given övre gräns av 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 tanke på ovanstående kan sannolikheten för "någon" dålig händelse hända att vara mindre än . För att visa detta arbetar vi på alla möjliga mottagna ord och alla möjliga delmängder meddelanden i${\ displaystyle 1}$${\ displaystyle y \ in [q] ^ {n}}$${\ displaystyle L}$${\ displaystyle [q] ^ {k}.}$

Nu när vi vänder oss till beviset för del (ii) måste vi visa att det finns superpolynomiskt många kodord runt varje gång frekvensen överstiger listavkodningskapaciteten. Vi måste visa att det är superpolynomiskt stort om hastigheten . Fixa ett kodord . Nu har vi det för varje utvalda slumpmässigt ${\ 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)]}$

eftersom Hamming-bollar är översättnings-invariant. Från definitionen av volymen på en Hamming-boll och det faktum som väljs enhetligt slumpmässigt från vi har också ${\ 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)}}$

Låt oss nu definiera en indikatorvariabel så ${\ displaystyle X_ {c}}$

${\ displaystyle X_ {c} = {\ börja {fall} 1 & c \ i B (y, pn) \\ 0 & {\ text {annars}} \ slut {fall}}}$

Ta förväntningarna på volymen på en Hamming-boll vi har

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

Därför har vi med den probabilistiska metoden visat att om hastigheten överskrider listavkodningskapaciteten blir liststorleken superpolynomiskt stor. Detta kompletterar provskissen för listavkodningskapacitet.

Listavkodningsalgoritmer

Under perioden 1995 till 2007 utvecklade kodningsteorinsamhället successivt effektivare listavkodningsalgoritmer. Algoritmer för Reed – Solomon-koder som kan avkoda upp till Johnson-radien som finns där är det normaliserade avståndet eller det relativa avståndet. Men för Reed-Solomon-koder, vilket betyder att en bråkdel av fel kan korrigeras. Några av de mest framträdande listavkodningsalgoritmerna är följande: ${\ displaystyle 1 - {\ sqrt {1- \ delta}}}$${\ displaystyle \ delta}$${\ displaystyle \ delta = 1-R}$${\ displaystyle 1 - {\ sqrt {R}}}$

• Sudan '95 - Den första kända icke-triviala listavkodningsalgoritmen för Reed – Solomon-koder som uppnådde effektiv listavkodning upp till fel utvecklade av Madhu Sudan .${\ displaystyle 1 - {\ sqrt {2R}}}$
• Guruswami – Sudan '98 - En förbättring av ovanstående algoritm för listavkodning av Reed – Solomon koder upp till fel av Madhu Sudan och hans dåvarande doktorand Venkatesan Guruswami .${\ displaystyle 1 - {\ sqrt {R}}}$
• Parvaresh – Vardy '05 - I ett banbrytande papper presenterade Farzad Parvaresh och Alexander Vardy koder som kan listas avkodade bortom radien för låga priser . Deras koder är varianter av Reed-Solomon-koder som erhålls genom att utvärdera korrelerade polynom i stället för precis som i vanliga Reed-Solomon-koder.${\ displaystyle 1 - {\ sqrt {R}}}$${\ displaystyle R}$${\ displaystyle m \ geqslant 1}$${\ displaystyle 1}$
• Guruswami – Rudra '06 - I ännu ett genombrott ger Venkatesan Guruswami och Atri Rudra uttryckliga koder som uppnår listavkodningskapacitet, det vill säga att de kan listas avkodas upp till radien för alla . Med andra ord är detta felkorrigering med optimal redundans. Detta svarade på en fråga som hade varit öppen i cirka 50 år. Detta arbete har bjudits in till avsnittet Forskningshöjdpunkter i ACM: s kommunikation (som är "ägnat åt de viktigaste forskningsresultaten som publicerats i datavetenskap de senaste åren") och nämndes i en artikel med titeln "Coding and Computing Join Forces" i 21 september 2007-numret av tidningen Science. Koderna som de ges kallas vikta Reed-Solomon-koder, som ingenting är annat än vanliga Reed-Solomon-koder men ses som en kod över ett större alfabet genom noggrann paketning av kodordssymboler.${\ displaystyle 1-R- \ epsilon}$${\ displaystyle \ epsilon> 0}$

På grund av deras allestädes närhet och de fina algebraiska egenskaperna som de har, var listavkodningsalgoritmer för Reed – Solomon-koderna ett huvudfokus för forskare. Listavkodningsproblemet för Reed – Solomon-koder kan formuleras enligt följande:

Inmatning : För en Reed-Solomon-kod ges vi paret för , var är det bitar av det mottagna ordet och 's är distinkta punkter i det finita fältet och en felparameter . ${\ 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 är att hitta alla polynom av grad högst som är meddelandelängden så att åtminstone värderingar . Här skulle vi vilja ha så litet som möjligt så att ett större antal fel kan tolereras. ${\ displaystyle P (X) \ in F_ {q} [X]}$${\ displaystyle k}$${\ displaystyle p (\ alpha _ {i}) = y_ {i}}$${\ displaystyle t}$${\ displaystyle i}$${\ displaystyle t}$

Med ovanstående formulering är den allmänna strukturen för listavkodningsalgoritmer för Reed-Solomon-koder som följer:

Steg 1 : (Interpolation) Hitta en icke-noll bivariat polynom så att för . ${\ displaystyle Q (X, Y)}$${\ displaystyle Q (\ alpha _ {i}, y_ {i}) = 0}$${\ displaystyle 1 \ leq i \ leq n}$

Steg 2 : (Root konstaterandet / faktorisering) Utgång alla graders polynomials sådan att är en faktor av dvs . För vart och ett av dessa polynomer, kontrollera om det finns minst värden på . Om så är fallet, inkludera ett sådant polynom i utgångslistan. ${\ 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)}$

Med tanke på det faktum att bivariata polynomier kan faktoreras effektivt körs ovanstående algoritm under polynomial tid.

Tillämpningar inom komplexitetsteori och kryptografi

Algoritmer utvecklade för listavkodning av flera intressanta kodfamiljer har hittat intressanta applikationer inom beräkningskomplexitet och kryptografifältet . Följande är en lista över applikationer utanför kodningsteorin:

• Konstruktion av hårdkärna predicerar från envägspermutationer .
• Förutsäga vittnen för NP-sökproblem.
• Förstärkande hårdhet för booleska funktioner.
• Genomsnittlig fallhårdhet för permanenta slumpmässiga matriser.
• Extraktorer och Pseudorandom generatorer .
• Effektiv förrättspårning.

externa länkar

• En undersökning av listavkodning av Madhu Sudan
• Anteckningar från en kurs undervisad av Madhu Sudan
• Anteckningar från en kurs undervisad av Luca Trevisan
• Anteckningar från en kurs undervisad av Venkatesan Guruswami
• Anteckningar från en kurs undervisad av Atri Rudra
• P. Elias, "Lista avkodning för bullriga kanaler," Teknisk rapport 335, Research Laboratory of Electronics, MIT, 1957.
• P. Elias, "Felkorrigeringskoder för listavkodning," IEEE-transaktioner om informationsteori, vol. 37, s. 5–12, 1991.
• JM Wozencraft, "Listavkodning", kvartalsvis framstegsrapport, Research Laboratory of Electronics, MIT, vol. 48, sid 90–95, 1958.
• Venkatesan Guruswami 's doktorsavhandling
• Algoritmiska resultat i listavkodning
• Vikta vass – Salomonkod