A Caltech Library Service

New Approaches to the Analysis and Design of Reed-Solomon Related Codes


El-Khamy, Mostafa Said (2007) New Approaches to the Analysis and Design of Reed-Solomon Related Codes. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/TQRJ-GM19.


The research that led to this thesis was inspired by Sudan's breakthrough that demonstrated that Reed-Solomon codes can correct more errors than previously thought. This breakthrough can render the current state-of-the-art Reed-Solomon decoders obsolete. Much of the importance of Reed-Solomon codes stems from their ubiquity and utility. This thesis takes a few steps toward a deeper understanding of Reed-Solomon codes as well as toward the design of efficient algorithms for decoding them.

After studying the binary images of Reed-Solomon codes, we proceeded to analyze their performance under optimum decoding. Moreover, we investigated the performance of Reed-Solomon codes in network scenarios when the code is shared by many users or applications. We proved that Reed-Solomon codes have many more desirable properties. Algebraic soft decoding of Reed-Solomon codes is a class of algorithms that was stirred by Sudan's breakthrough. We developed a mathematical model for algebraic soft decoding. By designing Reed-Solomon decoding algorithms, we showed that algebraic soft decoding can indeed approach the ultimate performance limits of Reed-Solomon codes. We then shifted our attention to products of Reed-Solomon codes. We analyzed the performance of linear product codes in general and Reed-Solomon product codes in particular. Motivated by these results we designed a number of algorithms, based on Sudan's breakthrough, for decoding Reed-Solomon product codes. Lastly, we tackled the problem of analyzing the performance of sphere decoding of lattice codes and linear codes, e.g., Reed-Solomon codes, with an eye on the tradeoff between performance and complexity.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:algebraic soft decoding; error-correcting codes; iterative decoding; list decoding; multiuser; product codes; Reed-Solomon
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • McEliece, Robert J.
Thesis Committee:
  • McEliece, Robert J. (chair)
  • Hassibi, Babak
  • Divsalar, Dariush
  • Fossorier, Marc
  • Vaidyanathan, P. P.
Defense Date:6 September 2006
Record Number:CaltechETD:etd-10102006-120159
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:4016
Deposited By: Imported from ETD-db
Deposited On:12 Oct 2006
Last Modified:16 Mar 2020 23:47

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page