'Magisk' fejlkorrektionsskema har vist sig at være ineffektivt | Quanta Magasinet

Hvis du nogensinde har sendt en sms, afspillet en cd eller gemt en fil i skyen, har du nydt godt af fejlretning. Denne revolutionerende idé går tilbage til 1940'erne, hvor forskerne først indså, at det er muligt at omskrive ethvert budskab i en form, der gør det nemt at vende senere korruption.

Gennem årene har forskere udviklet mange geniale skemaer, kaldet fejlkorrigerende koder, der koder data på forskellige måder og bruger forskellige procedurer til at rette fejl. Men for teoretiske dataloger er få så overbevisende som såkaldte lokalt korrigerbare koder. Disse koder har to samtidige egenskaber, der lyder næsten modstridende: Enhver fejl kan rettes ved at læse de kodede data på nogle få steder, men ingen angriber kan forhindre denne korrektionsprocedure ved selektivt at manipulere med koden. Det er, som om du kunne genvinde en hvilken som helst side revet ud af en bog ved blot at kigge på et par andre.

"Det er et ret magisk fænomen," sagde Tom Gur, en datalog ved University of Cambridge. "A priori er det ikke indlysende, at sådan et matematisk objekt overhovedet kunne eksistere."

Men denne magi har en høj pris. De eneste kendte eksempler på lokalt korrigerbare koder er ekstremt ineffektive - kodning af enhver meddelelse gør den også eksponentielt længere. Hele bøger kodet på denne måde ville være alt for uhåndterlige.

Dataloger har længe spekuleret på, om bedre lokalt korrigerbare koder er mulige. De har især fokuseret på koder, der kun bruger tre forespørgsler til at rette enhver fejl, i håb om, at denne alvorlige begrænsning kan gøre disse koder lettere at forstå. Men selv denne simple sag har forbløffet forskere i over 20 år.

Nu datalogen Pravesh Kothari fra Carnegie Mellon University og hans kandidatstuderende Peter Manohar har endelig bevist at det er umuligt at bygge en tre-forespørgsel lokalt korrigerbar kode, der undgår de eksponentielle omkostninger. Det kan være et negativt resultat, men alt, der tydeliggør grænserne for fejlkorrektion, er spændende for forskere, især fordi matematikken i lokalt korrigerbare koder dukker op i områder langt væk fra kommunikation.

"Dette resultat er fantastisk," sagde Shubhangi Saraf, en datalog ved University of Toronto. "Det er et kæmpe gennembrud."

Styrke i tal

For at forstå fejlkorrektion skal du forestille dig de data, du gerne vil beskytte, som en sekvens af bits eller 0'er og 1'ere. En fejl i denne model kan være et hvilket som helst uønsket flip af et 0 til et 1 eller omvendt, uanset om det skyldes en tilfældig udsving eller bevidst manipulation.

Antag, at du vil sende en besked til en ven, men du er bekymret for, at fejl kan ændre betydningen. En simpel strategi er at erstatte hver 0 i din besked med 000 og hver 1 med 111. Hvis din ven ser en del af beskeden, der ikke indeholder tre identiske bits i en række, vil de vide, at der er opstået en fejl. Og hvis fejl er tilfældige og relativt sjældne, så er enhver streng på 110 meget mere tilbøjelig til at være en beskadiget 111 end en beskadiget 000. Et simpelt flertal inden for hver triplet vil være tilstrækkeligt til at rette de fleste fejl.

Denne ordning, kaldet gentagelseskoden, har fordelen af ​​enkelhed, men ikke meget andet at anbefale det. For det første kræver det tredobling af længden af ​​hver besked bare for at håndtere relativt sjældne fejl, og hvis der er en anstændig chance for to tilstødende fejl, har vi brug for endnu mere redundans. Endnu værre, det bliver hurtigt ubrugeligt, hvis fejl ikke er tilfældige, såsom når angribere aktivt forsøger at sabotere koden. I gentagelseskoden er al den information, der er nødvendig for at rette en given bit, gemt i blot nogle få andre bits, hvilket efterlader den sårbar over for et målrettet angreb.

Heldigvis klarer mange fejlkorrigerende koder det bedre. Et berømt eksempel, kaldet Reed-Solomon kode, virker ved at omdanne meddelelser til polynomier - matematiske udtryk som f.eks x² + 3x + 2, der består af forskellige udtryk lagt sammen, hver med en variabel (f.eks x) hævet til en anden magt. Kodning af en meddelelse ved hjælp af en Reed-Solomon-kode involverer at bygge et polynomium med et led for hvert tegn i meddelelsen, derefter plotte polynomiet som en kurve på en graf og gemme koordinaterne for punkter, der ligger på kurven (tager mindst én mere punkt end antallet af tegn). Fejl kan skubbe nogle få af disse punkter væk fra kurven, men hvis der ikke er for mange fejl, vil kun én polynomielkurve passere gennem de fleste af punkterne. Den kurve svarer næsten helt sikkert til det sande budskab.

Reed-Solomon-koder er hypereffektive - du behøver kun at gemme et par ekstra point for at rette fejl, så enhver kodet besked er kun marginalt længere end originalen. De er også mindre sårbare over for den slags målrettede forstyrrelser, der ville betyde katastrofe for gentagelseskoden, fordi den information, der bruges til at rette en fejl hvor som helst, er fordelt over hele den kodede meddelelse.

Tænk globalt, handle lokalt

Styrken af ​​Reed-Solomon-koden stammer fra indbyrdes forbundethed. Men netop på grund af den indbyrdes sammenhæng, er der ingen måde at rette en enkelt fejl i en kodet besked uden at læse det hele. Det lyder måske ikke som et problem i kommunikationssammenhæng: Hvis du sender en besked, vil du sandsynligvis have, at modtageren læser det hele. Men det kan være et ansvar i datalagring - en anden stor anvendelse af fejlkorrektion.

Overvej en virksomhed, der gemmer brugernes e-mails i skyen - det vil sige på en bred vifte af servere. Du kan tænke på hele samlingen af ​​e-mails som én lang besked. Antag nu, at en server går ned. Med en Reed-Solomon-kode skal du udføre en massiv beregning, der involverer alle de kodede data, for at gendanne dine e-mails fra den ene tabte server. "Du skulle se på alt," sagde Zeev Dvir, en datalog ved Princeton University. "Det kan være milliarder og milliarder af e-mails - det kan tage rigtig lang tid."

Forskere bruger udtrykket "lokal" til at beskrive koder, der kun bruger en brøkdel af den kodede besked til spot fejl eller rette dem. Den simple gentagelseskode har noget af denne lokale karakter, men det er netop det, der gør den så sårbar over for manipulation. En lokalt korrigerbar kode får derimod det bedste fra begge verdener - den kan rette en fejl i en hvilken som helst bit med blot nogle få forespørgsler, alt sammen uden at miste den indbyrdes forbindelse, der gør Reed-Solomon-koder så modstandsdygtige.

"Dette er en virkelig stringent opfattelse," sagde Kothari.

De mest berømte eksempler på lokalt korrigerbare koder er versioner af en ærværdig fejlkorrigerende kode opfundet i 1954 af matematikerne David Muller , Irving Reed (som også hjalp med at udvikle Reed-Solomon-koder). Ligesom Reed-Solomon-koder bruger Reed-Muller-koder polynomier med mange termer lagt sammen for at kode lange beskeder.

Polynomier brugt i Reed-Solomon koder involverer en enkelt variabel, x, så den eneste måde at tilføje flere udtryk er at bruge højere kræfter af x. Dette resulterer i en kurve med mange vrikker, der kun kan fastgøres ved at se på mange punkter. Reed-Muller-koder bruger i stedet polynomier, hvor hvert led kan indeholde flere variable ganget sammen. Flere variabler betyder flere måder at kombinere dem på, hvilket igen tilbyder en måde at øge antallet af polynomielle termer uden at hæve nogen individuel variabel til så høje potenser.

Reed-Muller-koder er meget fleksible. Du kan kode længere meddelelser ved at øge den højeste potens, der vises i polynomiet, øge antallet af variable eller begge dele. For at gøre en Reed-Muller-kode lokalt korrigerbar, skal du blot begrænse den maksimale effekt af hver variabel til en lille konstant værdi og håndtere længere meddelelser ved kun at øge antallet af variable.

Specifikt for en lokalt korrigerbar kode med tre forespørgsler er den maksimale effekt sat til 2. For så vidt angår hver enkelt variabel sporer polynomiet, der koder meddelelsen, en simpel parabel. For at bestemme den nøjagtige form af den parabel behøver du kun at undersøge kurven på tre punkter. Hvad mere er, med mange variabler er der mange sådanne paraboler, som alle kan bruges til at rette fejl. Det er det, der gør Reed-Muller-koder så modstandsdygtige.

Desværre har Reed-Muller-koden en alvorlig ulempe: Antallet af bits, der kræves for at kode en meddelelse, stiger eksponentielt med antallet af variable. Hvis du vil have en meget lokal kode, der retter fejl med blot en håndfuld forespørgsler, skal du bruge en masse variable til lange beskeder, og Reed-Muller-koden bliver hurtigt ubrugelig i praksis.

"Eksponentiel i dette tilfælde er meget dårlig," sagde Dvir. Men er det uundgåeligt?

Kan korrigeres eller afkodes?

Da dataloger forsøgte og undlod at finde mere effektive lokalt korrigerbare koder, begyndte de at mistænke, at sådanne koder overhovedet ikke var mulige. I 2003 to forskere bevist at der ikke er nogen måde at slå Reed-Muller-koden ved kun at bruge to forespørgsler. Men det er så langt, som nogen nåede.

"Når du går til tre, bliver vores viden meget skitseagtig," sagde Kothari.

Det næste gennembrud komplicerede bare sagerne yderligere. I to artikler udgivet i 2008 , 2009, viste datalogerne Sergey Yekhanin og Klim Efremenko, hvordan man konstruerede tre-forespørgselskoder, der var mere effektive end Reed-Muller-koder, men disse koder var ikke helt lokalt korrigerbare. I stedet havde de en subtilt anderledes egenskab kaldet lokal afkodbarhed.

For at forstå forskellen, lad os igen forestille os en cloud storage-udbyder, der kombinerer brugernes data i en lang besked og beskytter dem ved hjælp af en fejlkorrigerende kode. Både lokalt korrigerbare koder og lokalt afkodbare koder kan rette en fejl i enhver del af den originale meddelelse med blot nogle få forespørgsler.

Men hver fejlkorrigerende kode kræver også ekstra bits, der ikke var i den oprindelige meddelelse - det er derfor, at kodning af en meddelelse gør den længere. De to typer koder adskiller sig i, hvordan de behandler disse ekstra bits. Lokalt afkodbare koder giver ingen løfter om antallet af forespørgsler, der er nødvendige for at rette fejl i disse bits. Men i en lokalt korrigerbar kode kan en fejl i enhver af de ekstra bits rettes på nøjagtig samme måde som en fejl i en hvilken som helst bit af den oprindelige besked.

"Alt, hvad du gemmer, uanset om det er brugernes originale data eller redundansen og kontroloplysningerne - alt dette kan korrigeres lokalt," sagde Madhu Sudan, en datalog ved Harvard University.

Selvom det i princippet var forskelligt, syntes lokal korrigerbarhed og lokal afkodbarhed altid udskiftelige i praksis før 2008 - enhver kendt lokalt afkodbar kode var også lokalt korrigerbar. Yekhanin og Efremenkos opdagelse rejste muligheden for en grundlæggende forskel mellem de to forhold. Eller måske var det muligt at ændre Yekhanin og Efremenkos koder for at gøre dem lokalt korrigerbare. Det ville stille de to betingelser på lige fod igen, men det ville også betyde, at forskere havde taget fejl af, hvor effektive tre-forespørgsler, lokalt korrigerbare koder kunne blive. Uanset hvad, ville konventionel visdom skulle ændres.

Lånelogik

Kothari og Manohar løste endelig denne spænding ved at tilpasse en teknik fra et andet område inden for datalogi: studiet af såkaldte constraint satisfaction problemer. At prøve at koordinere middagsplaner med en gruppe venner er et slags tilfredshedsproblem. Alle har valg, de vil acceptere, og valg, de vil nedlægge veto. Din opgave er enten at finde en plan, der tilfredsstiller alle, eller, hvis der ikke er en sådan plan, finde ud af det så hurtigt som muligt.

Der er en iboende asymmetri mellem disse to mulige resultater. En acceptabel løsning er måske ikke let at finde, men når du først har den, er det nemt at overbevise andre om, at det vil virke. Men selvom du ved, at problemet virkelig er "utilfredsstillende", er der måske ikke et eksempel, der giver bevis.

I 2021 lavede Kothari og Manohar sammen med Venkatesan Guruswami fra University of California, Berkeley en stort gennembrud i studiet af problemer med begrænsningstilfredshed ved at bruge en ny teoretisk teknik til at identificere disse vanskelige utilfredsstillende tilfælde. De havde mistanke om, at den nye metode også ville være et kraftfuldt værktøj til at løse andre problemer, og Guruswamis kandidatstuderende Omar Alrabiah foreslog, at de skulle se på lokalt afkodbare koder med tre forespørgsler.

"Dette var et søm med en hammer i hånden, så at sige," sagde Kothari.

Yekhanin og Efremenkos overraskende resultater havde vist, at lokalt afkodbare koder med tre forespørgsler kunne være mere effektive end Reed-Muller-koder. Men var deres koder de bedst mulige, eller kunne tre-forespørgsler lokalt afkodelige koder blive endnu mere effektive? Kothari, Manohar, Guruswami og Alrabiah mente, at deres nye teknik måske kunne bevise grænser for, hvor effektive sådanne koder kunne blive. Deres plan var at bygge en logisk formel, der omfatter strukturen af ​​alle mulige tre-forespørgsler lokalt afkodelige koder af en given størrelse, og bevise den utilfredsstillende, og derved vise, at en sådan kode ikke kunne eksistere.

De fire forskere tog et første skridt i den retning i 2022 og satte en ny grænse om den maksimale effektivitet af lokalt afkodbare koder med tre forespørgsler. Resultatet gik langt ud over, hvad forskere havde været i stand til at opnå med andre teknikker, men det udelukkede ikke, at alle koder var mere effektive end Yekhanin og Efremenkos.

Kothari og Manohar havde mistanke om, at de kunne gå længere. Men fremskridtet gik i stå, indtil Manohar nedskrev en hurtig bagside-af-kuvert-beregning, der indikerede, at teknikken måske ville fungere endnu bedre for lokalt korrigerbare koder, end den havde for lokalt afkodbare koder.

Et par måneder senere, efter mange flere falske start, der fik dem til at frygte, at de havde været for optimistiske, holdt teknikken endelig sit løfte. Kothari og Manohar beviste, at som forskere havde mistænkt, er det umuligt for en lokalt korrigerbar kode med tre forespørgsler at fungere væsentligt bedre end Reed-Muller-koder. Den eksponentielle skalering er en fundamental begrænsning. Deres resultat var også en dramatisk demonstration af, at lokal korrigerbarhed og lokal afkodbarhed, selvom de overfladisk ligner hinanden, virkelig adskiller sig på et grundlæggende niveau: Sidstnævnte er utvetydigt lettere at realisere end førstnævnte.

Kothari og Manohar håber nu at kunne udvide deres teknikker til at studere koder, der har lov til at lave mere end tre forespørgsler, da meget lidt er kendt om dem nu. Og fremskridt i teorien om fejlkorrektion har ofte implikationer på andre tilsyneladende ikke-relaterede områder. Især lokalt korrigerbare koder gør overraskende optrædener overalt fra problemet med søgninger i private databaser i kryptografi til beviser for teoremer i kombinatorik. Det er for tidligt at sige, hvordan Kothari og Manohars teknik vil påvirke disse forskellige felter, men forskerne føler sig optimistiske.

"Der er en virkelig smuk ny idé her," sagde Dvir. "Jeg tror, ​​der er et stort potentiale."