Decodarea listei - List decoding

În informatică , în special în teoria codificării , decodarea listelor este o alternativă la decodificarea unică a codurilor de corectare a erorilor pentru rate mari de eroare. Noțiunea a fost propusă de Elias în anii '50. Ideea principală din spatele decodării listei este aceea că algoritmul de decodare în loc să emită un singur mesaj posibil emite o listă de posibilități dintre care una corectă. Aceasta permite gestionarea unui număr mai mare de erori decât cea permisă prin decodarea unică.

Modelul unic de decodare din teoria codificării , care este constrâns să scoată un singur cod de cod valabil din cuvântul primit nu a putut tolera o fracțiune mai mare de erori. Aceasta a dus la un decalaj între performanța de corectare a erorilor pentru modelele de zgomot stochastic (propuse de Shannon ) și modelul de zgomot adversar (considerat de Richard Hamming ). De la mijlocul anilor 90, progresul semnificativ algoritmic al comunității teoriei codificării a redus acest decalaj. O mare parte din acest progres se bazează pe un model relaxat de corectare a erorilor numit decodare de listă, în care decodorul scoate la dispoziție o listă de coduri pentru modelele de eroare patologice din cel mai rău caz în care codul transmis efectiv este inclus în lista de ieșiri. În cazul unor tipare tipice de eroare, decodorul scoate un cod unic unic, dat un cuvânt primit, care este aproape întotdeauna cazul (Cu toate acestea, acest lucru nu se știe că este adevărat pentru toate codurile). Îmbunătățirea este semnificativă prin faptul că performanța de corectare a erorilor se dublează. Acest lucru se datorează faptului că acum decodificatorul nu se limitează la bariera distanței pe jumătate minimă. Acest model este foarte atrăgător, deoarece a avea o listă de coduri de coduri este cu siguranță mai bună decât să renunți. Noțiunea de decodare a listelor are multe aplicații interesante în teoria complexității .

Modul în care este modelat zgomotul canalului joacă un rol crucial prin faptul că guvernează ritmul în care este posibilă o comunicare fiabilă. Există două școli principale de gândire în modelarea comportamentului canalului:

• Model probabilistic de zgomot studiat de Shannon în care zgomotul canalului este modelat tocmai în sensul că comportamentul probabilistic al canalului este bine cunoscut și probabilitatea apariției de prea multe sau prea puține erori este scăzută
• Modelul cu cel mai rău caz sau zgomot adversar considerat de Hamming în care canalul acționează ca un adversar care corupe în mod arbitrar codul de comandă supus unui număr limitat de erori.

Punctul culminant al decodării listelor este că, chiar și în condiții de zgomot adversar, este posibil să se obțină o compensare optimă informațional-teoretică între rata și fracția erorilor care pot fi corectate. Prin urmare, într-un anumit sens, este ca și cum ai îmbunătăți performanțele de corectare a erorilor la cele posibile, în cazul unui model de zgomot mai slab și stocastic.

Formulare matematice

Să fie un cod de corectare a erorilor; cu alte cuvinte, este un cod de lungime , dimensiune și distanță minimă peste un alfabet de mărime . Problema de decodare a listei poate fi formulată astfel: ${\ displaystyle {\ mathcal {C}}}$${\ displaystyle (n, k, d) _ {q}}$${\ displaystyle {\ mathcal {C}}}$${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle d}$${\ displaystyle \ Sigma}$${\ displaystyle q}$

Intrare: Cuvânt primit , eroare legată${\ displaystyle x \ in \ Sigma ^ {n}}$ ${\ displaystyle e}$

Rezultat: O listă a tuturor codewords a căror distanță Hamming de cel mult . ${\ displaystyle x_ {1}, x_ {2}, \ ldots, x_ {m} \ in {\ mathcal {C}}}$${\ displaystyle x}$${\ displaystyle e}$

Motivația pentru decodarea listei

Având în vedere un cuvânt primit , care este o versiune zgomotoasă a unui cod de cuvânt transmis , decoderul încearcă să scoată codul transmis transmis prin punerea pariului pe un cod de ordine care este „cel mai apropiat” de cuvântul primit. Distanța Hamming între două coduri de cuvânt este folosită ca metrică pentru găsirea celui mai apropiat cod de cuvânt, dat fiind cuvântul primit de decodificator. Dacă este distanța minimă de Hamming a unui cod , atunci există două taste de cod și care diferă exact în poziții. Acum, în cazul în care cuvântul primit este echidistant de la codurile de cuvânt și , decodarea fără ambiguitate devine imposibilă, întrucât decodificatorul nu poate decide care dintre ele și care vor ieși ca cod de ordine transmis original. Drept urmare, jumătatea distanței minime acționează ca o barieră combinatorie dincolo de care este imposibilă corectarea de eroare fără echivoc, dacă insistăm doar pe o decodare unică. Cu toate acestea, cuvintele primite, precum cele menționate mai sus, apar doar în cel mai rău caz și dacă ne uităm la modul în care bilele Hamming sunt împachetate într-un spațiu de dimensiuni mari, chiar și pentru modele de eroare care depășesc jumătatea distanței minime, există doar un singur cod de ordine în cadrul Distanțare de la cuvântul primit. S-a dovedit că această afirmație are o probabilitate ridicată pentru un cod aleator ales dintr-un ansamblu natural și mai mult pentru cazul codurilor Reed – Solomon, care este bine studiat și destul de omniprezent în aplicațiile din lumea reală. De fapt, dovada Shannon a teoremei capacității pentru canale simetrice q poate fi vizualizată în lumina revendicării de mai sus pentru coduri aleatorii. ${\ 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}$

Sub mandatul de decodare a listelor, pentru erorile cele mai grave, decoderului i se permite să emită o mică listă de coduri de ordine. Cu anumite informații specifice contextului sau lateral, poate fi posibilă redarea listei și recuperarea codului de comandă transmis original. Prin urmare, în general, acesta pare a fi un model mai puternic de recuperare a erorilor decât decodarea unică.

Potențialul de decodare a listelor

Pentru a exista un algoritm de decodificare a listei de timp polinomial, avem nevoie de garanția combinatorie că orice minge de rază Hamming în jurul unui cuvânt primit (unde este fracția de erori în ceea ce privește lungimea blocului ) are un număr mic de coduri. Acest lucru se datorează faptului că dimensiunea listei în sine este în mod clar o limitare mai mică pe timpul de rulare al algoritmului. Prin urmare, solicităm ca dimensiunea listei să fie un polinom în lungimea blocului codului. O consecință combinatorie a acestei cerințe este aceea că impune o limită superioară asupra ratei unui cod. Listează promisiunile de decodare pentru a îndeplini această limită superioară. S-a demonstrat neconstructiv că există coduri de rată care pot fi decodate în listă până la o fracțiune de erori apropiate . Cantitatea este menționată în literatura de specialitate ca capacitate de decodare a listei. Acesta este un câștig substanțial în comparație cu modelul unic de decodare, deoarece avem acum posibilitatea de a corecta de două ori mai multe erori. În mod firesc, trebuie să avem cel puțin o fracțiune din simbolurile transmise pentru a fi corecte pentru a recupera mesajul. Aceasta este o informație teoretică mai mică legată de numărul de simboluri corecte necesare pentru efectuarea decodării și cu decodarea listei, putem atinge această limită teoretică informațională. Cu toate acestea, pentru a realiza acest potențial, avem nevoie de coduri explicite (coduri care pot fi construite în timp polinomial) și algoritmi eficienți pentru a efectua codarea și decodarea. ${\ displaystyle pn}$${\ displaystyle r}$${\ displaystyle p}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle R}$${\ displaystyle 1-R}$${\ displaystyle 1-R}$${\ displaystyle R}$

( p , L ) -list-decodabilitate

Pentru orice fracțiune de eroare și un întreg , un cod se spune ca este lista decodable până la o fracțiune de erori cu o dimensiune listă de cel mult sau -list-decoda dacă pentru fiecare , numărul de codewords în cadrul Hamming distanță de cel mult${\ 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.}$

Combinatorie de decodare a listelor

Relația dintre decodabilitatea listei unui cod și alți parametri fundamentali, cum ar fi distanța minimă și rata, au fost destul de bine studiate. S-a demonstrat că fiecare cod poate fi decodat cu ajutorul unor liste mici care depășesc jumătate din distanța minimă până la o delimitate numită raza Johnson. Acest lucru este destul de semnificativ, deoarece dovedește existența unor coduri -list-decodabile cu o rată bună, cu o rază de decodare a listei mult mai mare decât Cu alte cuvinte, Johnson bound exclude posibilitatea de a avea un număr mare de codwords într-o bilă de Hamming din rază puțin mai mare decât ceea ce înseamnă că este posibilă corectarea mult mai multor erori cu decodarea listei. ${\ displaystyle (p, L)}$${\ displaystyle {\ tfrac {d} {2}}.}$${\ displaystyle {\ tfrac {d} {2}}}$

Capacitatea de decodare a listei

Teorema (capacitatea de decodare a listei). Let și următoarele două instrucțiuni mențin o lungime de bloc suficient de mare . ${\ displaystyle q \ geqslant 2,0 \ leqslant p \ leqslant 1 - {\ tfrac {1} {q}}}$${\ displaystyle \ epsilon \ geqslant 0.}$${\ displaystyle n}$

i) Dacă , există un cod decodificabil -list.${\ displaystyle R \ leqslant 1-H_ {q} (p) - \ epsilon}$${\ displaystyle (p, O (1 / \ epsilon))}$

ii) Dacă , atunci fiecare cod-listă decodificabil are .${\ displaystyle R \ geqslant 1-H_ {q} (p) + \ epsilon}$${\ displaystyle (p, L)}$${\ displaystyle L = q ^ {\ Omega (n)}}$

Unde

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

este funcția de entropie -ary definită pentru și extinsă prin continuitate la${\ displaystyle q}$${\ displaystyle p \ in (0,1)}$${\ displaystyle [0,1].}$

Ceea ce înseamnă acest lucru este că pentru ratele care se apropie de capacitatea canalului, există coduri decodabile cu liste cu dimensiuni polinomiale care permit algoritmi eficienți de decodare, în timp ce pentru rate care depășesc capacitatea canalului, dimensiunea listei devine exponențială, care exclude existența algoritmilor de decodare eficienți.

Dovada capacității de decodare a listei este una semnificativă, întrucât corespunde exact capacității unui canal simetric . De fapt, termenul „capacitate de decodare a listelor” ar trebui citit de fapt ca capacitatea unui canal advers în cadrul decodării listei. De asemenea, dovada capacității de decodare a listelor este un rezultat important care indică diferența optimă între rata unui cod și fracția de erori care poate fi corectată în cadrul decodării listei. ${\ displaystyle q}$${\ displaystyle qSC_ {p}}$

Schiță de dovadă

Ideea din spatele dovezii este similară cu cea a probei Shannon pentru capacitatea canalului simetric binar unde este selectat un cod aleatoriu și arătând că acesta este -list-decodificabil cu probabilitate ridicată atâta timp cât rata pentru ratele care depășesc cantitatea de mai sus, acesta poate fi arătat că dimensiunea listei devine super-polinomial mare. ${\ displaystyle BSC_ {p}}$${\ displaystyle (p, L)}$${\ displaystyle R \ leqslant 1-H_ {q} (p) - {\ tfrac {1} {L}}.}$${\ displaystyle L}$

Un eveniment „rău” este definit ca unul în care, dat un cuvânt și mesaje primite , se întâmplă astfel încât , pentru fiecare loc în care este fracția de erori pe care dorim să o corectăm și este mingea de rază Hamming cu cuvântul primit ca centru . ${\ displaystyle y \ in [q] ^ {n}}$${\ displaystyle L + 1}$${\ displaystyle m_ {0}, \ ldots, m_ {L} \ in [q] ^ {k},}$${\ displaystyle {\ mathcal {C}} (m_ {i}) \ in B (y, pn)}$${\ displaystyle 0 \ leqslant i \ leqslant L}$${\ displaystyle p}$${\ displaystyle B (y, pn)}$${\ displaystyle pn}$${\ displaystyle y}$

Acum, probabilitatea ca un cod de cuvânt asociat cu un mesaj fix să fie dat de o minge Hamming este dată de ${\ displaystyle {\ mathcal {C}} (m_ {i})}$${\ displaystyle m_ {i} \ in [q] ^ {k}}$${\ displaystyle B (y, pn)}$

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

unde cantitatea este volumul unei bile de Hamming cu raza cu cuvântul primit ca centru. Inegalitatea în relația de mai sus rezultă de la limita superioară a volumului unei bile de Hamming. Cantitatea oferă o estimare foarte bună asupra volumului unei bile de Hamming cu rază centrată pe orice cuvânt în alte cuvinte , volumul unei bile Hamming este invariant de traducere. Pentru a continua cu schița dovezii, conjurăm unirea legată în teoria probabilității care ne spune că probabilitatea ca un eveniment rău să se întâmple pentru un dat este delimitată de cantitate . ${\ 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))}}$

Având în vedere cele de mai sus, probabilitatea de a se întâmpla "orice" eveniment rău să fie mai mică decât . Pentru a arăta acest lucru, ne descurcăm peste toate cuvintele posibile primite și orice subset posibil de mesaje în${\ displaystyle 1}$${\ displaystyle y \ in [q] ^ {n}}$${\ displaystyle L}$${\ displaystyle [q] ^ {k}.}$

Revenind acum la dovada părții (ii), trebuie să arătăm că există super-polinomial multe coduri în jurul valorii de fiecare dată când rata depășește capacitatea de decodare a listei. Trebuie să arătăm că este super-polinomial mare dacă rata . Remediați un cod de ordine . Acum, pentru fiecare ales la întâmplare, avem ${\ 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 \ in B (y, pn)] = \ Pr [y \ in B (c, pn)]}$

din moment ce mingile Hamming sunt invariante de traducere. De la definiția volumului unei mingi de Hamming și de la faptul că este aleasă uniform la întâmplare, avem și noi ${\ displaystyle y}$${\ displaystyle [q] ^ {n}}$

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

Să definim acum o variabilă indicator, astfel încât ${\ displaystyle X_ {c}}$

${\ displaystyle X_ {c} = {\ begin {cases} 1 & c \ in B (y, pn) \\ 0 & {\ text {altfel}} \ end {cases}}}$

Luând așteptarea volumului unei mingi de Hamming avem

${\ displaystyle {\ begin {align} E [| B (y, pn) |] & = \ sum _ {c \ in {\ mathcal {C}}} E [X_ {c}] \\ [4pt] & = \ sumă {{c \ in {\ mathcal {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)} \ end {aliniat}}}$

Prin urmare, prin metoda probabilistică, am arătat că dacă rata depășește capacitatea de decodare a listei, atunci dimensiunea listei devine super-polinomial mare. Aceasta completează schița de probă pentru capacitatea de decodare a listei.

Algoritmi de decodificare a listelor

În perioada 1995-2007, comunitatea teoriei codificării a dezvoltat algoritmi progresiv mai eficienți de decodare a listelor. Algoritmi pentru Reed - codurile Solomon care pot decoda până la raza Johnson care există acolo unde este distanța normalizată sau distanța relativă. Cu toate acestea, pentru codurile Reed-Solomon, ceea ce înseamnă că o parte din erori poate fi corectată. Unii dintre cei mai proeminenți algoritmi de decodare a listelor sunt următorii: ${\ displaystyle 1 - {\ sqrt {1- \ delta}}}$${\ displaystyle \ delta}$${\ displaystyle \ delta = 1-R}$${\ displaystyle 1 - {\ sqrt {R}}}$

• Sudan '95 - Primul algoritm de descodificare a listelor non-banale cunoscut pentru codurile Reed – Solomon care a obținut o decodificare eficientă a listelor până la erori dezvoltate de Madhu Sudan .${\ displaystyle 1 - {\ sqrt {2R}}}$
• Guruswami – Sudan ’98 - O îmbunătățire a algoritmului de mai sus pentru decodificarea listei Reed – Solomon codifică erorile de Madhu Sudan și de studentul său de atunci, Venkatesan Guruswami .${\ displaystyle 1 - {\ sqrt {R}}}$
• Parvaresh – Vardy '05 - Într-un articol avansat, Farzad Parvaresh și Alexander Vardy au prezentat coduri care pot fi listate decodate dincolo de raza pentru tarife mici . Codurile lor sunt variante de coduri Reed-Solomon care sunt obținute prin evaluarea polinoamelor corelate în loc ca în cazul codurilor Reed-Solomon obișnuite.${\ displaystyle 1 - {\ sqrt {R}}}$${\ displaystyle R}$${\ displaystyle m \ geqslant 1}$${\ displaystyle 1}$
• Guruswami – Rudra ’06 - În încă o descoperire, Venkatesan Guruswami și Atri Rudra dau coduri explicite care ating capacitatea de decodare a listelor, adică pot fi decodate în listă până la raza pentru orice . Cu alte cuvinte, aceasta este corectarea erorilor cu redundanță optimă. Acest lucru a răspuns la o întrebare deschisă de aproximativ 50 de ani. Această lucrare a fost invitată la secțiunea Repere de cercetare din Comunicările ACM (care este „consacrată celor mai importante rezultate ale cercetării publicate în Informatică în ultimii ani”) și a fost menționată într-un articol intitulat „Codare și Calculare Unire Forțe”. în numărul 21 septembrie 2007 al revistei Science. Codurile cărora li se oferă sunt numite coduri Reed-Solomon pliate, care nu sunt decât coduri simple Reed-Solomon, dar văzute ca un cod peste un alfabet mai mare prin gruparea atentă a simbolurilor de coduri.${\ displaystyle 1-R- \ epsilon}$${\ displaystyle \ epsilon> 0}$

Datorită ubicuității lor și a proprietăților algebraice frumoase pe care le dețin, algoritmii de decodare a listelor pentru codurile Reed-Solomon au fost un obiectiv principal al cercetătorilor. Problema de decodare a listelor pentru codurile Reed – Solomon poate fi formulată după cum urmează:

Intrare : Pentru un cod Reed-Solomon, ni se oferă perechea pentru , unde este al treilea bit al cuvântului primit și „sunt puncte distincte în câmpul finit și un parametru de eroare . ${\ 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}$

Rezultat : Scopul este de a găsi toate polinoamele de grad maxim, care este lungimea mesajului astfel încât cel puțin pentru valori . Aici, am dori să avem un număr cât mai mic pentru a putea fi tolerate un număr mai mare de erori. ${\ displaystyle P (X) \ in F_ {q} [X]}$${\ displaystyle k}$${\ displaystyle p (\ alpha _ {i}) = y_ {i}}$${\ displaystyle t}$${\ displaystyle i}$${\ displaystyle t}$

Cu formularea de mai sus, structura generală a algoritmilor de decodare a listelor pentru codurile Reed-Solomon este următoarea:

Etapa 1 : (interpolarea) Găsiți un bivariat nenulă polinomială astfel încât pentru . ${\ displaystyle Q (X, Y)}$${\ displaystyle Q (\ alpha _ {i}, y_ {i}) = 0}$${\ displaystyle 1 \ leq i \ leq n}$

Pasul 2 : (Găsirea rădăcinii / Factorizarea) Ieșirea tuturor polinoamelor de grad, astfel încât este un factor adică . Pentru fiecare dintre aceste polinoame, verificați dacă există cel puțin valori ale . Dacă da, includeți un astfel de polinom în lista de ieșiri. ${\ 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)}$

Având în vedere faptul că polinoamele bivariate pot fi considerate eficient, algoritmul de mai sus rulează în timp polinomial.

Aplicații în teoria complexității și criptografie

Algoritmii dezvoltați pentru decodarea listelor mai multor familii de coduri interesante au găsit aplicații interesante în complexitatea calculației și în domeniul criptografiei . Urmează o listă de exemple de aplicații în afara teoriei codificării:

• Construirea predicatelor cu miez dur din permutările unidirecționale .
• Prezicerea martorilor pentru probleme de căutare NP.
• Duritatea amplificatoare a funcțiilor booleane.
• Duritatea medie a cazului permanent al matricilor aleatorii.
• Extractoare și generatoare de pseudorandom .
• Trasarea eficientă a trădătorilor.

linkuri externe

• Un studiu privind decodificarea listei de către Madhu Sudan
• Note de la un curs predat de Madhu Sudan
• Note de la un curs predat de Luca Trevisan
• Note de la un curs predat de Venkatesan Guruswami
• Note de la un curs predat de Atri Rudra
• P. Elias, „Decodarea listelor pentru canalele zgomotoase”, Raportul tehnic 335, Laboratorul de cercetare în electronică, MIT, 1957.
• P. Elias, „Coduri de corectare a erorilor pentru decodarea listelor”, Tranzacții IEEE pe teoria informațiilor, vol. 37, p. 5–12, 1991.
• JM Wozencraft, „Decodarea listei”, Raportul de progres trimestrial, Laboratorul de cercetare în domeniul electronicii, MIT, vol. 48, p. 90–95, 1958.
• Teza de doctorat a lui Venkatesan Guruswami
• Rezultate algoritmice în decodarea listelor
• Reed pliat - cod Solomon