'Čarobna' shema odpravljanja napak se je izkazala za neučinkovito | Revija Quanta

Če ste že kdaj poslali besedilno sporočilo, predvajali CD ali shranili datoteko v oblak, ste imeli koristi od popravljanja napak. Ta revolucionarna zamisel izvira iz 1940. let prejšnjega stoletja, ko so raziskovalci prvič ugotovili, da je mogoče vsako sporočilo prepisati v obliki, ki omogoča, da se kasnejša pokvarjenost zlahka obrne.

Z leti so raziskovalci razvili številne domiselne sheme, imenovane kode za popravljanje napak, ki kodirajo podatke na različne načine in uporabljajo različne postopke za odpravljanje napak. Toda za teoretične računalniške znanstvenike je le malo tako prepričljivih kot tako imenovane lokalno popravljive kode. Te kode imajo dve istočasni lastnosti, ki se slišita skoraj protislovno: vsako napako je mogoče popraviti z branjem kodiranih podatkov na samo nekaj mestih, vendar noben napadalec ne more preprečiti tega postopka popravka s selektivnim poseganjem v kodo. Kot da bi lahko obnovili katero koli stran, iztrgano iz knjige, tako da bi samo pogledali nekaj drugih.

"To je prav čaroben pojav," je rekel Tom Gur, računalniški znanstvenik na Univerzi v Cambridgeu. "A priori ni očitno, da bi tak matematični objekt sploh lahko obstajal."

Toda ta čarovnija ima visoke stroške. Edini znani primeri lokalno popravljivih kod so izjemno neučinkoviti - kodiranje katerega koli sporočila ga tudi eksponentno podaljša. Celotne knjige, kodirane na ta način, bi bile preveč okorne.

Računalniški znanstveniki so se dolgo spraševali, ali so možne boljše lokalno popravljive kode. Posebej so se osredotočili na kode, ki uporabljajo samo tri poizvedbe za popravljanje morebitne napake, v upanju, da bo zaradi te stroge omejitve te kode lažje razumljive. Toda tudi ta preprost primer bega raziskovalce že več kot 20 let.

Zdaj računalničar Pravesh Kothari Univerze Carnegie Mellon in njegov podiplomski študent Peter Manohar končno dokazano da je nemogoče zgraditi lokalno popravljivo kodo s tremi poizvedbami, ki se izogne ​​tem eksponentnim stroškom. Morda je rezultat negativen, a vse, kar pojasnjuje meje popravljanja napak, je za raziskovalce vznemirljivo, zlasti zato, ker se matematika lokalno popravljivih kod pojavi na območjih, ki so daleč od komunikacije.

"Ta rezultat je neverjeten," je rekel Shubhangi Saraf, računalniški znanstvenik na Univerzi v Torontu. "To je velik preboj."

Moč v številkah

Da bi razumeli odpravljanje napak, si predstavljajte podatke, ki jih želite zaščititi, kot zaporedje bitov ali 0 in 1. Napaka v tem modelu je lahko vsaka neželena sprememba 0 v 1 ali obratno, ne glede na to, ali je to posledica naključnega nihanja ali namernega poseganja.

Recimo, da želite poslati sporočilo prijatelju, vendar vas skrbi, da bi napake lahko spremenile pomen. Ena preprosta strategija je, da vsako 0 v svojem sporočilu zamenjate z 000 in vsako 1 s 111. Če vaš prijatelj vidi del sporočila, ki ne vsebuje treh enakih bitov v vrsti, bo vedel, da je prišlo do napake. In če so napake naključne in razmeroma redke, potem je veliko bolj verjetno, da bo kateri koli niz 110 pokvarjen 111 kot pokvarjen 000. Za popravo večine napak zadostuje navadna večina glasov znotraj vsakega trojčka.

Ta shema, imenovana ponavljajoča se koda, je preprosta, vendar je malo drugega za priporočljivo. Prvič, zahteva potrojitev dolžine vsakega sporočila samo za obravnavo razmeroma redkih napak, in če obstaja primerna možnost za dve sosednji napaki, bomo potrebovali še več redundance. Še huje, hitro postane neuporaben, če napake niso naključne, na primer, ko napadalci aktivno poskušajo sabotirati kodo. V kodi za ponavljanje so vse informacije, potrebne za popravek danega bita, shranjene v samo nekaj drugih bitih, zaradi česar je ranljiv za ciljni napad.

Na srečo se številne kode za popravljanje napak odrežejo bolje. En znan primer, imenovan Reed-Solomonova koda, deluje tako, da sporočila pretvori v polinome — matematične izraze, kot je x² + 3x + 2, ki so sestavljeni iz različnih izrazov, seštetih skupaj, vsak s spremenljivko (kot je x) dvignjen na drugo potenco. Kodiranje sporočila z uporabo Reed-Solomonove kode vključuje gradnjo polinoma z enim izrazom za vsak znak v sporočilu, nato risanje polinoma kot krivulje na grafu in shranjevanje koordinat točk, ki ležijo na krivulji (vzemite vsaj še eno točka kot število znakov). Napake lahko potisnejo nekaj teh točk s krivulje, a če napak ni preveč, bo skozi večino točk šla samo ena polinomska krivulja. Ta krivulja skoraj zagotovo ustreza pravemu sporočilu.

Kode Reed-Solomon so hiperučinkovite - za popravljanje napak morate shraniti le nekaj dodatnih točk, zato je vsako kodirano sporočilo le malo daljše od izvirnika. Prav tako so manj ranljivi za vrste ciljnih motenj, ki bi povzročile katastrofo za ponavljajočo se kodo, saj so informacije, ki se uporabljajo za popravljanje napak kjer koli, porazdeljene po celotnem kodiranem sporočilu.

Misli globalno, deluj lokalno

Moč kodeksa Reed-Solomon izhaja iz medsebojne povezanosti. Toda ravno zaradi te medsebojne povezanosti ni načina, da bi odpravili eno napako v kodiranem sporočilu, ne da bi prebrali celotno sporočilo. To morda ne zveni kot težava v kontekstu komunikacije: če pošiljate sporočilo, verjetno želite, da prejemnik prebere vse. Toda to je lahko težava pri shranjevanju podatkov - še ena pomembna uporaba odpravljanja napak.

Razmislite o podjetju, ki shranjuje e-poštna sporočila uporabnikov v oblaku – to je na širokem naboru strežnikov. Celotno zbirko e-poštnih sporočil si lahko predstavljate kot eno dolgo sporočilo. Zdaj pa predpostavimo, da se en strežnik zruši. S kodo Reed-Solomon bi morali opraviti obsežno računanje, ki bi vključevalo vse kodirane podatke, da bi obnovili svojo e-pošto s tega izgubljenega strežnika. "Moral bi pogledati vse," je rekel Zeev Dvir, računalniški znanstvenik na univerzi Princeton. "To bi lahko bile milijarde in milijarde e-poštnih sporočil - lahko traja zelo dolgo."

Raziskovalci uporabljajo izraz "lokalno" za opis kod, ki uporabljajo le delček kodiranega sporočila opaziti napake ali jih popravite. Enostavna ponavljajoča se koda ima nekaj lokalnega značaja, vendar je ravno to tisto, zaradi česar je tako ranljiva za posege. Nasprotno pa lokalno popravljiva koda izkoristi najboljše iz obeh svetov – lahko popravi napako v katerem koli bitu s samo nekaj poizvedbami, ne da bi izgubila medsebojno povezanost, zaradi katere so Reed-Solomonove kode tako odporne.

"To je res strog pojem," je dejal Kothari.

Najbolj znani primeri lokalno popravljivih kod so različice častitljive kode za popravljanje napak, ki so jo leta 1954 izumili matematiki David Muller in Irving Reed (ki je tudi pomagal razviti Reed-Solomonove kode). Tako kot Reed-Solomonove kode tudi Reed-Mullerjeve kode uporabljajo polinome z veliko dodanimi izrazi za kodiranje dolgih sporočil.

Polinomi, uporabljeni v Reed-Solomonovih kodah, vključujejo eno spremenljivko, x, zato je edini način za dodajanje več izrazov uporaba višjih potenc x. Posledica tega je krivulja s številnimi nihanji, ki jo je mogoče določiti le s pogledom na veliko točk. Reed-Mullerjeve kode namesto tega uporabljajo polinome, v katerih lahko vsak izraz vsebuje več spremenljivk, pomnoženih skupaj. Več spremenljivk pomeni več načinov za njihovo kombiniranje, kar posledično ponuja način za povečanje števila polinomskih členov brez dvigovanja katere koli posamezne spremenljivke na tako visoke potence.

Reed-Mullerjeve kode so zelo prilagodljive. Daljša sporočila lahko kodirate tako, da povečate največjo moč, ki se pojavi v polinomu, povečate število spremenljivk ali oboje. Če želite narediti Reed-Mullerjevo kodo lokalno popravljivo, preprosto omejite največjo moč vsake spremenljivke na majhno konstantno vrednost in obravnavate daljša sporočila tako, da povečate samo število spremenljivk.

Za lokalno popravljivo kodo s tremi poizvedbami je največja moč nastavljena na 2. Kar zadeva vsako posamezno spremenljivko, polinom, ki kodira sporočilo, izriše preprosto parabolo. Če želite določiti natančno obliko te parabole, morate preučiti krivuljo le v treh točkah. Še več, s številnimi spremenljivkami obstaja veliko takih parabol, od katerih se lahko katera koli uporabi za popravljanje napak. To je tisto, zaradi česar so kode Reed-Muller tako odporne.

Na žalost ima Reed-Mullerjeva koda resno pomanjkljivost: število bitov, potrebnih za kodiranje sporočila, eksponentno narašča s številom spremenljivk. Če želite visoko lokalno kodo, ki popravlja napake s samo peščico poizvedb, boste potrebovali veliko spremenljivk za dolga sporočila in Reed-Mullerjeva koda bo v praksi hitro postala neuporabna.

"Eksponentno je v tem primeru zelo slabo," je dejal Dvir. Toda ali je neizogibno?

Popravljivo ali dekodirano?

Ko so računalničarji poskušali najti učinkovitejše lokalno popravljive kode, a jim ni uspelo, so začeli sumiti, da takšne kode sploh niso mogoče. Leta 2003 dva raziskovalca dokazano da ni mogoče premagati kode Reed-Muller z uporabo samo dveh poizvedb. Ampak to je vse, kar je kdorkoli prišel.

"Ko greš na tri, postane naše znanje zelo pomanjkljivo," je dejal Kothari.

Naslednji preboj je zadeve samo še bolj zapletel. V dveh člankih, objavljenih v 2008 in 2009, sta računalniška znanstvenika Sergey Yekhanin in Klim Efremenko pokazala, kako sestaviti kode s tremi poizvedbami, ki so bile učinkovitejše od Reed-Mullerjevih kod, vendar te kode niso bile povsem lokalno popravljive. Namesto tega so imeli subtilno drugačno lastnost, imenovano lokalna dekodabilnost.

Da bi razumeli razliko, si znova predstavljajmo ponudnika shranjevanja v oblaku, ki združuje podatke uporabnikov v eno dolgo sporočilo in ga ščiti s kodo za popravljanje napak. Tako kode, ki jih je mogoče lokalno popraviti, kot kode, ki jih je mogoče lokalno dekodirati, lahko popravijo napako v katerem koli bitu izvirnega sporočila z le nekaj poizvedbami.

Toda vsaka koda za popravljanje napak zahteva tudi dodatne bite, ki jih ni bilo v izvirnem sporočilu - zato kodiranje podaljša sporočilo. Obe vrsti kod se razlikujeta v tem, kako obravnavata te dodatne bite. Kode, ki jih je mogoče lokalno dekodirati, ne obljubljajo števila poizvedb, potrebnih za popravljanje napak v teh bitih. Toda v kodi, ki jo je mogoče lokalno popraviti, je mogoče napako v katerem koli od dodatnih bitov popraviti na popolnoma enak način kot napako v katerem koli bitu izvirnega sporočila.

"Vse, kar shranite, ne glede na to, ali gre za izvirne podatke uporabnikov ali redundanco in podatke o preverjanju - vse to je mogoče lokalno popraviti," je dejal Madhu Sudan, računalniški znanstvenik na univerzi Harvard.

Čeprav sta bili načeloma različni, sta se lokalni popravljivost in lokalna dekodabilnost v praksi pred letom 2008 vedno zdeli zamenljivi - vsaka znana lokalno dekodljiva koda je bila tudi lokalno popravljiva. Odkritje Yekhanina in Efremenka je povečalo možnost temeljne razlike med obema pogojema. Ali pa je bilo mogoče spremeniti kode Yekhanina in Efremenka, da bi jih naredili lokalno popravljive. To bi oba pogoja znova postavilo na enak položaj, vendar bi to tudi pomenilo, da so se raziskovalci zmotili glede tega, kako učinkovite so lahko lokalno popravljive kode s tremi poizvedbami. Kakor koli že, konvencionalna modrost bi se morala spremeniti.

Logika izposoje

Kothari in Manohar sta to napetost končno razrešila s prilagoditvijo tehnike z drugega področja računalništva: študija tako imenovanih problemov zadovoljevanja omejitev. Poskus usklajevanja načrtov za večerjo s skupino prijateljev je svojevrsten problem zadovoljstva z omejitvami. Vsak ima izbiro, ki jo bo sprejel, in izbiro, na katero bo dal veto. Vaša naloga je bodisi najti načrt, ki bo zadovoljil vse, bodisi, če takega načrta ni, to čim prej ugotoviti.

Med tema dvema možnima izidoma obstaja neločljiva asimetrija. Sprejemljive rešitve morda ni enostavno najti, a ko jo enkrat imate, je zlahka prepričati koga drugega, da bo delovala. Toda tudi če veste, da je težava res »nezadovoljiva«, morda ne obstaja primer, ki bi zagotovil dokaz.

Leta 2021 sta Kothari in Manohar skupaj z Venkatesanom Guruswamijem s kalifornijske univerze Berkeley naredila velik preboj pri preučevanju težav z zadovoljevanjem omejitev z uporabo nove teoretične tehnike za prepoznavanje teh zapletenih nezadovoljivih primerov. Sumili so, da bo nova metoda močno orodje tudi za reševanje drugih problemov, Guruswamijev podiplomski študent Omar Alrabiah pa je predlagal, da si ogledajo kode, ki jih je mogoče lokalno dekodirati s tremi poizvedbami.

"To je bil žebelj s kladivom v naši roki, tako rekoč," je dejal Kothari.

Presenetljivi rezultati Yekhanina in Efremenka so pokazali, da so lahko kode s tremi poizvedbami, ki jih je mogoče lokalno dekodirati, učinkovitejše od kod Reed-Muller. Toda ali so bile njihove kode najboljše možne ali bi lahko kode s tremi poizvedbami, ki jih je mogoče lokalno dekodirati, postale še učinkovitejše? Kothari, Manohar, Guruswami in Alrabiah so mislili, da bi njihova nova tehnika lahko dokazala omejitve učinkovitosti takšnih kod. Njihov načrt je bil zgraditi logično formulo, ki bi zajemala strukturo vseh možnih treh poizvedbnih lokalno dekodljivih kod dane velikosti, in dokazati, da je nezadovoljiva, s čimer bi pokazali, da taka koda ne more obstajati.

Štirje raziskovalci so leta 2022 naredili prvi korak v tej smeri in postavili a nova meja o največji učinkovitosti kod s tremi poizvedbami, ki jih je mogoče lokalno dekodirati. Rezultat je precej presegel tisto, kar so raziskovalci lahko dosegli z drugimi tehnikami, vendar ni izključil vseh kod, učinkovitejših od Yekhaninovih in Efremenkovih.

Kothari in Manohar sta slutila, da bi lahko šla dlje. Toda napredek je zastal, dokler Manohar ni zapisal hitrega izračuna na zadnji strani ovojnice, ki je pokazal, da bi tehnika lahko delovala še bolje za lokalno popravljive kode kot za tiste, ki jih je bilo mogoče lokalno dekodirati.

Nekaj ​​mesecev pozneje, po številnih napačnih začetkih, zaradi katerih so se bali, da so preveč optimistični, je tehnika končno izpolnila svojo obljubo. Kothari in Manohar sta dokazala, da je, kot so domnevali raziskovalci, nemogoče, da bi katera koli koda s tremi poizvedbami, ki jo je mogoče lokalno popraviti, delovala občutno bolje kot kode Reed-Muller. To eksponentno skaliranje je temeljna omejitev. Njihov rezultat je bil tudi dramatičen dokaz, da se lokalna popravljivost in lokalna dekodabilnost, čeprav sta na videz podobni, res razlikujeta na temeljni ravni: slednjo je nedvoumno lažje uresničiti kot prvo.

Kothari in Manohar zdaj upata, da bosta svoje tehnike razširila na preučevanje kod, ki lahko izvajajo več kot tri poizvedbe, saj je o njih zdaj zelo malo znanega. In napredek v teoriji odpravljanja napak ima pogosto posledice na drugih na videz nepovezanih področjih. Zlasti lokalno popravljive kode presenečajo povsod od problema iskanja po zasebnih zbirkah podatkov v kriptografiji do dokazov izreki v kombinatoriki. Prezgodaj je reči, kako bo tehnika Kotharija in Manoharja vplivala na ta različna področja, vendar so raziskovalci optimistični.

"Tukaj je res lepa nova ideja," je dejal Dvir. "Mislim, da obstaja veliko potenciala."