Computer algebra and practical decoding algorithms
Amin Shokrollahi (École Polytechnique Fédérale de Lausanne, Switzerland)
Reed-Solomon codes are one the most widely used error-correcting codes. Thanks to their use in modern storage systems, they amount to over 75 percent of all codes used in practice. The need for larger storage media has called for a major change in this industry, leading to the near adoption of 4KB sector sizes of hard disks, as opposed to 512 bytes which has been the de-facto standard for the last decade. This change has caused a rethinking of the error-correcting technology used. One of the proposals in this regard is the use of long Reed-Solomon codes. A major bottleneck of traditional decoders for long codes is finding roots of a univariate polynomial over a finite field. In this talk we will show how to use tools from computer algebra to solve this problem and produce decoders that are fast in software and, not surprisingly, also in hardware.