Locally Recoverable Codes
Translated title
Locally Recoverable Codes: Construction and Properties of Locally Recoverable Codes
Author
Olesen, Rasmus Bod
Term
4. term
Education
Publication year
2023
Submitted on
2023-06-14
Pages
46
Abstract
This thesis studies and builds locally recoverable codes (LRCs)—error-correcting codes that allow a lost symbol to be reconstructed from only a few other symbols. It begins by defining Reed–Solomon codes and redundant residue codes, highlighting limitations of that approach for achieving locality. The work then formalizes locality and constructs Reed–Solomon-like LRCs. A key ingredient is the notion of a “nice polynomial” (a special class of polynomials with properties that enable the construction), and several methods for constructing such polynomials are provided. The thesis presents extensions of the basic construction, including how to obtain LRCs by combining multiple Reed–Solomon codes. It proves a Singleton-like bound on the minimum distance (a measure of how many errors the code can handle) and shows that almost all of the LRCs constructed here meet this bound with equality, i.e., they are optimal with respect to that trade-off. Finally, it defines cyclic LRCs and describes their subfield subcodes (codes restricted to a smaller alphabet), giving results on the size of recovering sets—the small sets of symbols needed to rebuild a missing symbol—for these subfield subcodes.
Denne afhandling undersøger og konstruerer lokalt genoprettelige koder (LRC’er) – fejlkorrigerende koder, hvor et mistet symbol kan genskabes ud fra kun få andre symboler. Først defineres Reed–Solomon-koder og redundante restklassekoder, og der peges på begrænsninger ved denne form for kodning i forhold til lokalitet. Afhandlingen introducerer begrebet lokalitet og konstruerer Reed–Solomon-lignende LRC’er. Et centralt element er begrebet “nice polynomial” (en særlig type polynomium med egenskaber, der gør konstruktionen mulig), og der gives flere metoder til at bygge sådanne polynomier. Der præsenteres også flere udvidelser af den grundlæggende konstruktion, herunder hvordan LRC’er kan opnås ved at kombinere flere Reed–Solomon-koder. Afhandlingen beviser en Singleton-lignende grænse for minimumsafstanden (et mål for hvor mange fejl koden kan håndtere) og viser, at næsten alle de konstruerede LRC’er opfylder denne grænse med lighed, dvs. er optimale i denne forstand. Til sidst defineres cykliske LRC’er og deres underkoder over et underfelt (subfield subcodes), og der gives resultater om størrelsen af de genopretningssæt (de små mængder af symboler, der kræves for at genskabe et mistet symbol) for disse underfeltskoder.
[This apstract has been rewritten with the help of AI based on the project's original abstract]
Keywords