I detta dokument presenterar vi felkorrigerande koder som uppnår informations-teoretiskt bästa möjliga avvägning mellan hastighet och felkorrigeringsradie. Specifikt, för varje 0 < R < 1 och " > 0, presenterar vi en explicit konstruktion av felkorrigerande koder för hastighet R som kan listas avkodas i polynom tid upp till ett bråk (1 0 R 0 ") av värsta fall fel. Åtminstone teoretiskt möter detta en av de centrala utmaningarna inom algoritmisk kodningsteori. Våra koder är enkla att beskriva: de är vikta Reed-Solomon koder, som i själva verket är exakt Reed-Solomon (RS) koder, men betraktas som en kod över ett större alfabet genom noggrann kombination av kodord symboler. Med tanke på allestädes närvarande RS-koder, är detta ett tilltalande inslag i vårt resultat, och i själva verket våra metoder ger direkt bättre avkodning algoritmer för RS-koder när fel uppstår i stegvisa utbrott. Alfabetstorleken på dessa vikta RS-koder är polynom i blocklängden. Vi kan reducera detta till en konstant (beroende på ") användning av befintliga idéer om "lista återhämtning" och expander-baserade koder. Konkatera de vikta RS-koderna med lämpliga inre koder, får vi binära koder som effektivt kan avkodas upp till två gånger den radie som uppnås genom den vanliga GMD-avkodningen.
De första explicita koder för att på ett tydligt sätt uppnå kapacitet var Vikna Reed-Solomon koder av Guruswami och Rudra REF.
Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Mathematics', 'Computer Science']}