Den klassiska familjen av [n, k] q Reed-Solomon koder över ett fält F q består av utvärderingar av polynom f  till F q [X] av grad < k vid n distinkta fältelement. I detta arbete överväger vi en nära besläktad familj av koder, kallade (order m) derivatkoder och definierade över områden av stora karaktäristika, som består av utvärderingar av f samt dess första m - 1 formella derivat på n distinkta fältelement. För tillräckligt stora m visar vi att dessa koder kan listas avkodas i polynomtid från en felfraktion som närmar sig 1 − R, där R = k/(nm) är kodens hastighet. Detta ger en alternativ konstruktion till vikta Reed-Solomon koder för att uppnå optimal avvägning mellan hastighet och lista felkorrigeringsradie. Vår avkodning algoritm är linjär-algebraic, och innebär att lösa ett linjärt system för att interpolera en multivariat polynom, och sedan lösa ett annat strukturerat linjärt system för att hämta listan över kandidat polynomials f. Algoritmen för derivatkoder erbjuder vissa fördelar jämfört med en liknande för vikta Reed-Solomon koder i termer av effektiv unik avkodning i närvaro av sidoinformation.
I REF visades också liknande resultat för derivatkoder, där kodning av ett polynom f består av utvärderingarna av f och dess första m-1 härleds från olika fältelement.
Optimal rate list decoding via derivative codes
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}