A divide-and-conquer approach to perform the bivariate polynomial interpolation procedure is discussed in Chapter 3. This method can potentially reduce the interpolation complexity of algebraic soft-decision decoding of Reed-Solomon code.

Algebraic soft-decision decoding (ASD) algorithms of Reed-Solomon (RS) codes have attracted much interest due to their significant coding gain and polynomial complexity. Practical ASD algorithms include the Koetter-Vardy, low-complexity Chase (LCC) and bit-level generalized minimum distance (BGMD) decodings. This thesis focuses on the design of efficient VLSI architectures for ASD decoders. One major step of ASD algorithms is the interpolation. Available interpolation algorithms can only add interpolation points or increase interpolation multiplicities. However, backward interpolation, which eliminates interpolation points or reduces multiplicities, is indispensable to enable the re-using of interpolation results. In this thesis, a novel backward interpolation is first proposed for the LCC decoding through constructing equivalent Grbner bases. In the LCC decoding, 2 test vectors need to be interpolated over. With backward interpolation, the interpolation result for each of the second and later test vectors can be computed by only one backward and one forward interpolation iterations. Compared to the previous design, the proposed backward-forward interpolation scheme can lead to significant memory saving. To reduce the interpolation latency of the LCC decoding, a unified backward-forward interpolation is proposed to carry out both interpolations in a single iteration. With only 40percent area overhead, the proposed unified interpolation architecture can almost double the throughput when large is adopted. Moreover, a reduced-complexity multi-interpolator scheme is developed for the low-latency LCC decoding. The proposed backward interpolation is further extended to the iterative BGMD decoding. By reusing the interpolation results, at least 40 percent of the interpolation iterations can be saved for a (255, 239) code while the area overhead is small. Further speedup of the BGMD interpolation is limited by the inherent serial nature of the interpolation algorithm. In this thesis, a novel interpolation scheme that can combine multiple interpolation iterations is developed. Efficient architectures are presented to integrate the combined and backward interpolation techniques. A combined-backward interpolator of a (255, 239) code is implemented and can achieve a throughput of 440 Mbps on a Xilinx XC2V4000 FPGA device. Compared to the previous fastest implementation, our implementation can achieve a speedup of 64percent with 51percent less FPGA resource. The factorization is another major step of ASD algorithms. In the re-encoded LCC decoding, it is proved that the factorization step can be eliminated. Hence, the LCC decoder can be further simplified. In the reencoded ASD decoders, a re-encoder and an erasure decoder need to be added. These two blocks can take a significant proportion of the overall decoder area and may limit the achievable throughput. An efficient re-encoder design is proposed by computing the erasure locator and evaluator through direct multiplications and reformulating other involved computations. When applied to a (255, 239) code, our re-encoder can achieve 82percent higher throughput than the previous design with 11percent less area. With minor modifications, the proposed design can also be used to implement erasure decoder. After applying available complexity-reducing techniques, complexity comparisons for three practical ASD decoders were carried out. It is derived that the LCC decoder can achieve similar or higher coding gain with lower complexity for high-rate codes. This thesis also provides discussions on how the hardware complexities of ASD decoders change with codeword length, code rate and other parameters.

All modern communication systems use some form of forward error correction coding. Generally, coding gain is improved when soft decision decoding is used instead of hard decision decoding. While soft decision decoding is a mature technology for convolutional codes, practical soft decision decoding for the commonly used Reed-Solomon (RS) non-binary block code has only recently been developed and is currently limited to use with bandwidth efficient modulation schemes such as M-ary phase-shift keying. Since JTIDS/Link-16 uses quasi-orthogonal, cyclic code-shift keying (CCSK), in this thesis, soft decision decoding of RS encoded symbols is extended to M-ary frequency-shift keying, a power efficient modulation scheme. In addition, the soft decision decoding scheme recently developed, actually a hybrid hard decision-soft decision (HD SD) decoding scheme, is improved for both bandwidth efficient and power efficient modulation schemes. Finally, the effect of the hybrid HD SD decoding technique on signals corrupted by additive white Gaussian noise (AWGN) and other interference, including Pulse Noise Interference (PNI), is examined. The performances of various systems using the hybrid HD SD decoding technique were investigated using both analysis and simulation. It was found that HD SD decoding is generally effective in minimizing the degradation in system performance due to PNI but has only a small benefit when only AWGN is present.

This monograph is a thoroughly revised and extended version of the author's PhD thesis, which was selected as the winning thesis of the 2002 ACM Doctoral Dissertation Competition. Venkatesan Guruswami did his PhD work at the MIT with Madhu Sudan as thesis adviser. Starting with the seminal work of Shannon and Hamming, coding theory has generated a rich theory of error-correcting codes. This theory has traditionally gone hand in hand with the algorithmic theory of decoding that tackles the problem of recovering from the transmission errors efficiently. This book presents some spectacular new results in the area of decoding algorithms for error-correcting codes. Specificially, it shows how the notion of list-decoding can be applied to recover from far more errors, for a wide variety of error-correcting codes, than achievable before The style of the exposition is crisp and the enormous amount of information on combinatorial results, polynomial time list decoding algorithms, and applications is presented in well structured form.

Electrical Engineering/Communications/Information Theory "The Berlekamp article alone will make this book worth having." --David Forney, Vice President, Motorola Codex Reed-Solomon Codes and Their Applications Edited by Stephen B. Wicker, Georgia Institute of Technology and Vijay K. Bhargava, University of Victoria On the Voyager spacecraft, they were responsible for sending clear pictures of the planets back to earth. They have also played a key role in the digital audio revolution. They are Reed-Solomon error codes: the extremely powerful codes that provide critical error control for many different types of digital communications systems. This outstanding collection of thirteen original articles written by leading researchers in the field provides a uniquely comprehensive overview of the history and practical applications--some never before published--of these important codes. Key features include: * Thirteen original articles from leading researchers in the field, with a historical overview by Reed and Solomon * An explanation of how Reed-Solomon codes were used in the Voyager spacecraft and how they are currently used in the compact disc player * Specific applications for digital audio, data transfer over mobile radio, satellite communications, spread spectrum systems, and more * New techniques for improving the performance of your own communications systems This book will be of interest to design and research engineers in the telecommunications field, particularly those in the aerospace/satellite and mobile radio industries. It is also well-suited for use as an advanced-level textbook on the subject of error control coding. Books of Related Interest from IEEE Press Clauide Elwood Shannon: Collected Papers Edited by N. J. A. Sloane and A. D. Wyner. AT&T Bell Labs The first published collection of papers by Claude E. Shannon, including his seminal article "The Mathematical Theory of Communication." 1993 Hardcover 968 pp IEEE Order Number PC0331-9 ISBN 0-7803-0434-9 Multiple Access Communications: Foundations for Emerging Technologies Edited by Norman Abramson, University of Hawaii at Manoa The first book to explain the connection between spread spectrum and ALOHA channels, providing a collection of key developments in the theory and practice of multiple user communications channels. 1993 Hardcover 528pp IEEE Order Number PC0287-3 ISBN 0-87942-292-0