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.[1]
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.[2]
Definitsioon
muudaPaikselt 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.[3]
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.[1]
Paikselt taastatava koodi definitsioon
muudaÖ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.[1]
Indeksite hulka, millel asuvatest elementidest on võimalik otsitav element taastada, nimetatakse elemendi taastehulgaks (recovery set).[1]
t-paikselt taastatava koodi definitsioon
muudaPaikselt 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.[4]
Taastehulkade arv defineeritakse järgmiselt[4]: 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õrdus
Tõestused parameetrite kohta
muudaPaikselt taastatavate koodide parameetrite kohta on tõestatud erinevaid tõkkeid.
Miinimumkauguse tõkked
muudaGopalani jt artiklis[5] ning Papailiopoulose ja Dimakise artiklis[6] tõestatakse järgmine tõke ühe taastehulgaga (n, k, d)-PTK-de kohta, kus paiksus on r ja d on koodi miinimumkaugus:
Kooditeguri tõkked
muudaGopalan jt[5] ning Papailioulos ja Dimakis[6] on tõestanud ühe taastehulgaga (n,k,r)-PTK-de kooditeguri kohta järgmise tulemuse:
Optimaalsete paikselt taastatavate koodide konstruktsioonid
muudaNagu eelpool mainitud, peetakse optimaalseteks PTK-deks neid koode, mille puhul kehtib võrdus [5]
Silberstein jt[8] 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:
Prakashi jt artiklis[10] 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 [10]
Koodi pikkuse piirangust saadakse mööda Tamo ja Bargi artiklis[11]. 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.[11]
Edasiarendused
muudaMaksimaalse taastatavusega paikselt taastatavad koodid
muudaMaksimaalse taastatavusega paikselt taastatavad koodid on sellised koodid, mis suudavad parandada samaaegselt kõik vead, mida on informatsiooniteoreetiliselt võimalik parandada, arvestades paiksusega[2]. Selliseid koode kasutatakse nt Microsofti pilvsalvestussüsteemis Microsoft Azure[12].
Kvantpaikselt taastatavad koodid
muudaLouis Golowichi jt artiklis[13] 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
muudaCarlos Munuera artiklis[14] 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
muuda- ↑ 1,0 1,1 1,2 1,3 1,4 1,5 1,6 1,7 Tamo, Itzhak; Barg, Alexander; Frolov, Alexey (juuni 2016). "Bounds on the Parameters of Locally Recoverable Codes" (PDF). IEEE Transactions on Information Theory. 62 (6). arXiv:1506.07196.
- ↑ 2,0 2,1 Guruswami, Venkatesan; Jin, Lingfei; Xing, Chaoping (oktoober 2020). "Constructions of maximally recoverable local reconstruction codes via function fields" (PDF). IEEE Transactions on Information Theory. 66 (10). arXiv:1808.04539v1.
- ↑ 3,0 3,1 Rawat, Ankit Singh; Papailiopoulos, Dimitris S.; Dimakis, Alexandros G.; Vishwanath, Sriram (august 2016). "Locality and Availability in Distributed Storage". IEEE Transactions on Information Theory. 62 (8). DOI:10.1109/TIT.2016.2524510.
- ↑ 4,0 4,1 4,2 Tamo, Itzhak; Barg, Alexander (2014). "Bounds on Locally Recoverable Codes with Multiple Recovering Sets" (PDF). 2014 IEEE International Symposium on Information Theory. arXiv:1402.0916v1.
- ↑ 5,0 5,1 5,2 5,3 5,4 Gopalan, Parikshit; Huang, Cheng; Simitci, Huseyin; Yekhanin, Sergey (november 2012). "On the Locality of Codeword Symbols" (PDF). IEEE Transactions on Information Theory. 58 (11). arXiv:1106.3625v1.
- ↑ 6,0 6,1 Papailiopoulos, Dimitris S.; Dimakis, Alexandros G. (oktoober 2014). "Locally Repairable Codes" (PDF). IEEE Transactions on Information Theory. 60 (10). arXiv:1206.3804v2.
- ↑ Wang, Anyu; Zhang, Zhifang (november 2014). "Repair Locality With Multiple Erasure Tolerance" (PDF). IEEE Transactions on Information Theory. 60 (11). arXiv:1306.4774v1.
- ↑ Silberstein, Natalia; Rawat, Ankit Singh; Koyluoglu, O. Ozan; Vishwanath, Sriram (2013). "Optimal locally repairable codes via rank-metric codes". 2013 IEEE International Symposium on Information Theory. DOI:10.1109/ISIT.2013.6620541.
- ↑ Tamo, Itzhak; Papailiopoulos, Dimitris S.; Dimakis, Alexandros G. (detsember 2016). "Optimal Locally Repairable Codes and Connections to Matroid Theory". IEEE Transactions on Information Theory. 62 (12). DOI:10.1109/TIT.2016.2555813.
- ↑ 10,0 10,1 Prakash, N.; Kamath, Govinda M.; Lalitha, V.; Vijay Kumar, P. (2012). "Optimal linear codes with a local-error-correction property" (PDF). 2012 IEEE International Symposium on Information Theory Proceedings. arXiv:1202.2414v1.
- ↑ 11,0 11,1 Tamo, Itzhak; Barg, Alexander (august 2014). "A family of optimal locally recoverable codes" (PDF). IEEE Transactions on Information Theory. 60 (8). arXiv:1311.3284v2.
- ↑ Gopi, Sivakanth (16. jaanuar 2018). "Maximally Recoverable Local Reconstruction Codes". microsoft.com. Vaadatud 13. jaanuaril 2024.
- ↑ Golowich, Louis; Guruswami, Venkatesan (november 2023). "Quantum Locally Recoverable Codes" (PDF). IEEE Transactions on Information Theory. 60 (8). arXiv:2311.08653.
- ↑ Munuera, Carlos (detsember 2018). "Locally Recoverable codes with local error detection" (PDF). arXiv:1812.00834v1