A Complete Classification of Partial-MDS (Maximally Recoverable) Codes Correcting one Additional Erasure
Type
conference lecture
Date Issued
2017-06-07
Author(s)
Abstract
Partial-MDS (PMDS) codes are a family of locally repairable codes, mainly used for distributed storage. They are defined to be able to correct any pattern of s additional erasures, after a given number of erasures per locality group have occurred. This makes them also maximally recoverable (MR) codes, another class of locally repairable codes.
It is known that MR codes in general, and PMDS codes in particular,
exist for any set of parameters, if the field size is large enough. Moreover, some explicit constructions of PMDS codes are known, mostly with a strong restriction on the number of erasures that can be corrected per locality group.
In this talk we give a general construction of PMDS codes that can correct any number of erasures per locality group, with the restriction s = 1, i.e., only one additional erasure can be corrected. Furthermore, we show that all PMDS codes for the given parameters are of this form, i.e., we give a classification of
these codes. This implies a necessary and sufficient condition on the underlying field size for the existence of these codes (assuming that the MDS conjecture is true). This bound on the field size is in general much smaller than the previously known ones.
It is known that MR codes in general, and PMDS codes in particular,
exist for any set of parameters, if the field size is large enough. Moreover, some explicit constructions of PMDS codes are known, mostly with a strong restriction on the number of erasures that can be corrected per locality group.
In this talk we give a general construction of PMDS codes that can correct any number of erasures per locality group, with the restriction s = 1, i.e., only one additional erasure can be corrected. Furthermore, we show that all PMDS codes for the given parameters are of this form, i.e., we give a classification of
these codes. This implies a necessary and sufficient condition on the underlying field size for the existence of these codes (assuming that the MDS conjecture is true). This bound on the field size is in general much smaller than the previously known ones.
Language
English
HSG Classification
contribution to scientific community
Event Title
Fq13 - the 13th international conference on finite fields and their applications
Event Location
Gaeta, Italien
Event Date
5.-10.6.2017
Subject(s)
Division(s)
Eprints ID
251041
File(s)![Thumbnail Image]()
open.access
Name
PMDS_Codes.pdf
Size
430.73 KB
Format
Adobe PDF
Checksum (MD5)
768c9fcb42165e4470a400940f28febe