Paikselt taastatav kood

Paikselt taastatav kood (ka Locally Recoverable Code, Locally Repairable Code, LRC) on kodeerimisteoorias kooditüüp, kus koodisõna iga sümbol on esitatav funktsioonina mingist väiksest osast ülejäänud sümbolitest.

Paikselt taastatavaid koode (edaspidi lühendatud PTK) kasutatakse andmesalvestuses, eriti pilv- ja hajussalvestuses. Kui osa andmebaasi sisust ei ole kättesaadav, siis PTK-d võimaldavad puuduva info ülejäänud andmete põhjal tõhusalt taastada. Seetõttu kasutatakse neid selleks, et suurendada salvestussüsteemide veataluvust.

Definitsioon

Paikselt taastatav kood on üks kustutuskoodi liik. PTK-d loodi, kuna klassikaliste kustutuskoodide puhul (mille hulka kuuluvad nt Reed-Solomoni koodid) on vaja ühe sümboli taastamiseks nii palju teisi sümboleid, et taastamise protsess muutub ebatõhusaks ja aeglaseks. Paiksuse (locality) ja paikselt taastatavate koodide eesmärk on vähendada ühe sümboli taastamiseks vajaminevate sümbolite arvu.

PTK-sid kirjeldatakse üldiselt kujul (n, k, r)-PTK, kus n tähistab koodi pikkust, k tähistab koodi mõõdet ja r tähistab koodisõnade paiksust.

Paikselt taastatava koodi definitsioon

Öeldakse, et koodil on paiksus r, kui tema iga koodisõna puhul on võimalik mistahes sümbolit taastada, kasutades r sümbolit ülejäänud koodisõnast. Teisisõnu, koodisõna iga sümbol peab olema esitatav funktsioonina mingist väiksest osast ülejäänud sümbolitest. Formaalsem koodi paiksuse kirjeldus on järgmine: Olgu $C\subset Q^{n}$ kood ja olgu $x\in C$ koodisõna, mis koosneb sümbolitest. Kui iga sümboli $x_{i}$ puhul, kus $i$ kuulub hulka $[n]={1,2,...,n}$, leidub selline $r$ elemendist koosnev hulk $R_{i}\subset [n]\setminus {i},|R_{i}|\leq r$ , nii et hulka $R_{i}$ kuuluvatel indeksitel asuvate elementide põhjal on võimalik taastada element $x_{i}$, siis $C$ on $r$-paikne.

Indeksite hulka, millel asuvatest elementidest on võimalik otsitav element taastada, nimetatakse elemendi taastehulgaks (recovery set).

t-paikselt taastatava koodi definitsioon

Paikselt taastavatel koodidel võib olla üks või mitu taastehulka. Taastehulkade arvu rõhutamiseks võib PTK-sid tähistada kujul t-PTK ehk (n, k, r, t)-PTK.

Taastehulkade arv defineeritakse järgmiselt: Tähistagu $C_{I}$ koodi $C$ koordinaatide alamhulka $I\subset [n]$. Olgu $a\in \mathbb {F} _{q}$ puhul defineeritud koodisõnade hulk $C(i,a)=\left\{x\in C:x_{i}=a\right\},i\in [n]$. Öeldakse, et koodil $C$ on $t$ ühisosata taastehulka, kui iga $i\in [n]$ jaoks leidub $t$ paarikaupa ühisosata alamhulka $R_{i,1},...,R_{i,t}\subset [n]$ nii, et iga $j=1,...,t$ puhul kehtib võrdus

$$C_{R_{i,j}}(i,a)\cap C_{R_{i,j}}(i,a')=\emptyset ,\qquad a\neq a'.$$

PTK-de kasutamisel andmesalvestussüsteemides kehtib põhimõte, et mida rohkem on taastehulki, seda parem on andmete kättesaadavus, sest siis saab korraga anda rohkematele kasutajatele juurdepääsu samadele andmetele.

Tõestused parameetrite kohta

Paikselt taastatavate koodide parameetrite kohta on tõestatud erinevaid tõkkeid.

Miinimumkauguse tõkked

Gopalani jt artiklis ning Papailiopoulose ja Dimakise artiklis tõestatakse järgmine tõke ühe taastehulgaga (n, k, d)-PTK-de kohta, kus paiksus on r ja d on koodi miinimumkaugus:

$$d\leq k-n-\left\lceil {\frac {k}{r}}\right\rceil +2.$$

Koode, mis saavutavad selle tõkke võrdusega, peetakse optimaalseteks PTK-deks, nt püramiidkoodid. See tõke on ühtlasi Singletoni tõkke üldistus: Singletoni tõkke saab kätte siis, kui ülaltoodud avaldises võtta $r=k$ . Rawati jt artiklis ning Wangi jt artiklis on tõestatud järgmine tõke koodi miinimumkauguse kohta:

$$d_{min}(C)\leq n-k-\left\lceil {\frac {t(k-1)+1}{t(r-1)+1}}\right\rceil +2.$$

Tegemist on eelmise tõkke üldistusega juhtudele, kus koodisõna igal sümbolil on üks või rohkem taastehulka. Tamo jt artiklis on veel tõestatud järgmine miinimumkauguse ülemine tõke, kus $t$ tähistab taastehulkade arvu ja $r$ tähistab taastehulkade elementide arvu:

$$d\leq n-\sum _{i=0}^{t}\left\lfloor {\frac {k-1}{r^{i}}}\right\rfloor .$$

Kooditeguri tõkked

Gopalan jt ning Papailioulos ja Dimakis on tõestanud ühe taastehulgaga (n,k,r)-PTK-de kooditeguri kohta järgmise tulemuse:

$${\frac {k}{n}}\leq {\frac {r}{r+1}}.$$

Ühe või rohkema (ühisosata) taastehulgaga koodide kohta on Tamo jt artiklis tõestatud järgmine kooditeguri ülemine tõke, kus $t$ on koodi taastehulkade arv ja $r$ on koodi paiksus:

$${\frac {k}{n}}\leq {\frac {1}{\prod _{j=1}^{t}(1+{\frac {1}{jr}})}}.$$

Lisaks miinimumkauguse ja kooditeguri tõketele on tõestatud, et mida väiksem on koodi paiksus, seda madalam on veataluvus.

Optimaalsete paikselt taastatavate koodide konstruktsioonid

Nagu eelpool mainitud, peetakse optimaalseteks PTK-deks neid koode, mille puhul kehtib võrdus ${\textstyle d=n-k-\left\lceil {\frac {k}{r}}\right\rceil +2.}$

Silberstein jt on kirjeldanud konstruktsiooni optimaalsete $(r,\delta ,\alpha )$-PTK-de jaoks, mis põhineb Gabidulini koodidel (Gabidulini koodid on MRD-koodid). Konstruktsioonis kasutatakse paikse grupi (local group) mõistet. Nimelt, töös kirjeldatav andmetalletussüsteem koosneb $n$ tipust, millest igaüks sisaldab mingi arvu sümboleid. Ühe tipu sümbolid saab taastada, kasutades ülimalt $r$ teist tippu nn paikse grupi seast, mille suurus on $r+\delta -1<n$. Selliste koodide kohta on artiklis tõestatud järgmine tõke, kus $\delta \geq 2$ ja $r$ on paiksuse parameetrid, $\alpha$ on tipu sümbolite arv ning $\mathrm {M}$ on koodi $C$ mõõde:

$$d_{min}(C)\leq n-\left\lceil {\frac {\mathrm {M} }{\alpha }}\right\rceil +1-\left(\left\lceil {\frac {\mathrm {M} }{r\alpha }}\right\rceil -1\right)(\delta -1).$$

Teine konstruktsioon on kirjeldatud Tamo jt artiklis. See konstruktsioon põhineb MDS-koodidel ja Reed-Solomoni koodidel. Töös on tõestatud ka optimaalsuse tingimust kinnitav võrdus ${\textstyle d=n-k-\left\lceil {\frac {k}{r}}\right\rceil +2.}$

Prakashi jt artiklis on kirjeldatud konstruktsioon ühe taastehulgaga optimaalsete PTK-de jaoks. Kirjeldatud konstruktsioonis on tehtud oluline edasiminek võrreldes eelnevate konstruktsioonidega: koodi tähestiku suurus ehk on võrreldav koodi pikkusega n. See-eest, koodi pikkus on piiratud täpse väärtuseni${\textstyle \left\lceil {\frac {k}{r}}\right\rceil (r+1).}$

Koodi pikkuse piirangust saadakse mööda Tamo ja Bargi artiklis. Artiklis on toodud ühe taastehulgaga optimaalsete PTK-de konstruktsioon, mis põhineb Reed-Solomoni koodide üldistusel. Selliselt konstrueeritud koodide kohta tõestatakse artiklis iga $r$ korral, $1<r<k$, miinimumkauguse tõke ${\textstyle d=n-k-\left\lceil {\frac {k}{r}}\right\rceil +2,}$ mis tõestab konstruktsiooni optimaalsust. Antud juhul on koodi tähestiku suurus võrreldav koodi pikkusega $n$, ilma et koodi pikkusele oleks seatud piiranguid.

Edasiarendused

Maksimaalse taastatavusega paikselt taastatavad koodid

Maksimaalse taastatavusega paikselt taastatavad koodid on sellised koodid, mis suudavad parandada samaaegselt kõik vead, mida on informatsiooniteoreetiliselt võimalik parandada, arvestades paiksusega. Selliseid koode kasutatakse nt Microsofti pilvsalvestussüsteemis Microsoft Azure.

Kvantpaikselt taastatavad koodid

Louis Golowichi jt artiklis tutvustatakse kvantpaiksuse kontseptsiooni ja defineeritakse kvant-PTK mõiste. Mainitakse, et kvant-PTK võiks leida rakendust kvantandmesalvestuses ning kirjeldatakse kvant-PTK-de konstruktsioone, parameetrite tõkkeid ja muid omadusi.

Paikse veatuvastusega paikselt taastatavad koodid

Carlos Munuera artiklis on kirjeldatud koodimudelit, mis ühendab paikse taastatavuse paikse veatuvastusega. Eesmärgiks on tuvastada olukordi, kus paiksel taastamisel kasutatavate elementide väärtused on vigased ja seetõttu tuleb taastamise tulemus vigane.