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  kood ja olgu  koodisõna, mis koosneb sümbolitest. Kui iga sümboli  puhul, kus  kuulub hulka , leidub selline  elemendist koosnev hulk  , nii et hulka   kuuluvatel indeksitel asuvate elementide põhjal on võimalik taastada element , siis  on -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  koodi  koordinaatide alamhulka . Olgu  puhul defineeritud koodisõnade hulk . Öeldakse, et koodil  on  ühisosata taastehulka, kui iga  jaoks leidub  paarikaupa ühisosata alamhulka  nii, et iga  puhul kehtib võrdusPTK-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: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  . Rawati jt artiklis ning Wangi jt artiklis on tõestatud järgmine tõke koodi miinimumkauguse kohta: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ähistab taastehulkade arvu ja  tähistab taastehulkade elementide arvu:
 Kooditeguri tõkked 
Gopalan jt ning Papailioulos ja Dimakis on tõestanud ühe taastehulgaga (n,k,r)-PTK-de kooditeguri kohta järgmise tulemuse:Ühe või rohkema (ühisosata) taastehulgaga koodide kohta on Tamo jt artiklis tõestatud järgmine kooditeguri ülemine tõke, kus  on koodi taastehulkade arv ja  on koodi paiksus: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  

Silberstein jt on kirjeldanud konstruktsiooni optimaalsete -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  tipust, millest igaüks sisaldab mingi arvu sümboleid. Ühe tipu sümbolid saab taastada, kasutades ülimalt  teist tippu nn paikse grupi seast, mille suurus on . Selliste koodide kohta on artiklis tõestatud järgmine tõke, kus  ja  on paiksuse parameetrid,  on tipu sümbolite arv ning  on koodi  mõõde: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 

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 

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  korral, ,  miinimumkauguse tõke   mis tõestab konstruktsiooni optimaalsust. Antud juhul on koodi tähestiku suurus võrreldav koodi pikkusega , 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 artiklisMunuera, Carlos (detsember 2018). "Locally Recoverable codes with local error detection" (PDF). arXiv:1812.00834v1 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.

 Viited 

Kategooria:Kodeerimine