The Original View of Reed-Solomon Coding and the Welch-Berlekamp Decoding Algorithm

Persistent Link:
http://hdl.handle.net/10150/301533
Title:
The Original View of Reed-Solomon Coding and the Welch-Berlekamp Decoding Algorithm
Author:
Mann, Sarah Edge
Issue Date:
2013
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
Abstract:
Reed-Solomon codes are a class of maximum distance separable error correcting codes with known fast error correction algorithms. They have been widely used to assure data integrity for stored data on compact discs, DVDs, and in RAID storage systems, for digital communications channels such as DSL internet connections, and for deep space communications on the Voyager mission. The recent explosion of storage needs for "Big Data'' has generated renewed interest in large storage systems with extended error correction capacity. Reed-Solomon codes have been suggested as one potential solution. This dissertation reviews the theory of Reed-Solomon codes from the perspective taken in Reed and Solomon's original paper on them. It then derives the Welch-Berlekamp algorithm for solving certain polynomial equations, and connects this algorithm to the problem of error correction. The discussion is mathematically rigorous, and provides a complete and consistent discussion of the error correction process. Numerous algorithms for encoding, decoding, erasure recovery, error detection, and error correction are provided and their computational cost is analyzed and discussed thus allowing this dissertation to serve as a manual for engineers interested in implementing Reed-Solomon coding.
Type:
text; Electronic Dissertation
Keywords:
Key Equation; RAID; Reed-Solomon codes; Welch-Berelkamp algorithm; Applied Mathematics; error correcting codes
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Graduate College; Applied Mathematics
Degree Grantor:
University of Arizona
Advisor:
Rychlik, Marek

Full metadata record

DC FieldValue Language
dc.language.isoenen_US
dc.titleThe Original View of Reed-Solomon Coding and the Welch-Berlekamp Decoding Algorithmen_US
dc.creatorMann, Sarah Edgeen_US
dc.contributor.authorMann, Sarah Edgeen_US
dc.date.issued2013-
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.abstractReed-Solomon codes are a class of maximum distance separable error correcting codes with known fast error correction algorithms. They have been widely used to assure data integrity for stored data on compact discs, DVDs, and in RAID storage systems, for digital communications channels such as DSL internet connections, and for deep space communications on the Voyager mission. The recent explosion of storage needs for "Big Data'' has generated renewed interest in large storage systems with extended error correction capacity. Reed-Solomon codes have been suggested as one potential solution. This dissertation reviews the theory of Reed-Solomon codes from the perspective taken in Reed and Solomon's original paper on them. It then derives the Welch-Berlekamp algorithm for solving certain polynomial equations, and connects this algorithm to the problem of error correction. The discussion is mathematically rigorous, and provides a complete and consistent discussion of the error correction process. Numerous algorithms for encoding, decoding, erasure recovery, error detection, and error correction are provided and their computational cost is analyzed and discussed thus allowing this dissertation to serve as a manual for engineers interested in implementing Reed-Solomon coding.en_US
dc.typetexten_US
dc.typeElectronic Dissertationen_US
dc.subjectKey Equationen_US
dc.subjectRAIDen_US
dc.subjectReed-Solomon codesen_US
dc.subjectWelch-Berelkamp algorithmen_US
dc.subjectApplied Mathematicsen_US
dc.subjecterror correcting codesen_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.disciplineApplied Mathematicsen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.contributor.advisorRychlik, Mareken_US
dc.contributor.committeememberLin, Kevinen_US
dc.contributor.committeememberWang, Donen_US
dc.contributor.committeememberRychlik, Mareken_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.