1. FNT-Based Reed-Solomon Erasure Codes
- Author
-
Jérôme Lacan, Alexandre Soro, and Institut Supérieur de l'Aéronautique et de l'Espace - ISAE-SUPAERO (FRANCE)
- Subjects
FOS: Computer and information sciences ,Block code ,Reed-solomon ,Computer science ,Error floor ,Computer Science - Information Theory ,Information Theory (cs.IT) ,Concatenated error correction code ,FNT ,Code word ,Data_CODINGANDINFORMATIONTHEORY ,Binary erasure channel ,Luby transform code ,Linear code ,Online codes ,Reed–Solomon error correction ,Linear network coding ,Erasure channel ,Fountain code ,Tornado code ,Erasure code ,Automatique / Robotique ,Algorithm ,Decoding methods ,Raptor code - Abstract
This paper presents a new construction of Maximum-Distance Separable (MDS) Reed-Solomon erasure codes based on Fermat Number Transform (FNT). Thanks to FNT, these codes support practical coding and decoding algorithms with complexity O(n log n), where n is the number of symbols of a codeword. An open-source implementation shows that the encoding speed can reach 150Mbps for codes of length up to several 10,000s of symbols. These codes can be used as the basic component of the Information Dispersal Algorithm (IDA) system used in a several P2P systems., Comment: submitted in CCNC'10
- Published
- 2010