List decoding of error-correcting codes
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2001.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/8700 |
| _version_ | 1826193074951290880 |
|---|---|
| author | Guruswami, Venkatesan, 1976- |
| author2 | Madhu Sudan. |
| author_facet | Madhu Sudan. Guruswami, Venkatesan, 1976- |
| author_sort | Guruswami, Venkatesan, 1976- |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2001. |
| first_indexed | 2024-09-23T09:33:22Z |
| format | Thesis |
| id | mit-1721.1/8700 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T09:33:22Z |
| publishDate | 2005 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/87002019-04-11T09:09:46Z List decoding of error-correcting codes Guruswami, Venkatesan, 1976- Madhu Sudan. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2001. Includes bibliographical references (p. 303-315). Error-correcting codes are combinatorial objects designed to cope with the problem of reliable transmission of information on a noisy channel. A fundamental algorithmic challenge in coding theory and practice is to efficiently decode the original transmitted message even when a few symbols of the received word are in error. The naive search algorithm runs in exponential time, and several classical polynomial time decoding algorithms are known for specific code families. Traditionally, however, these algorithms have been constrained to output a unique codeword. Thus they faced a "combinatorial barrier" and could only correct up to d/2 errors, where d is the minimum distance of the code. An alternate notion of decoding called list decoding, proposed independently by Elias and Wozencraft in the late 50s, allows the decoder to output a list of all codewords that differ from the received word in a certain number of positions. Even when constrained to output a relatively small number of answers, list decoding permits recovery from errors well beyond the d/2 barrier, and opens up the possibility of meaningful error-correction from large amounts of noise. However, for nearly four decades after its conception, this potential of list decoding was largely untapped due to the lack of efficient algorithms to list decode beyond d/2 errors for useful families of codes. This thesis presents a detailed investigation of list decoding, and proves its potential, feasibility, and importance as a combinatorial and algorithmic concept. (cont.) We prove several combinatorial results that sharpen our understanding of the potential and limits of list decoding, and its relation to more classical parameters like the rate and minimum distance. The crux of the thesis is its algorithmic results, which were lacking in the early works on list decoding. Our algorithmic results include: * Efficient list decoding algorithms for classically studied codes such as Reed-Solomon codes and algebraic-geometric codes. In particular, building upon an earlier algorithm due to Sudan, we present the first polynomial time algorithm to decode Reed-Solomon codes beyond d/2 errors for every value of the rate. * A new soft list decoding algorithm for Reed-Solomon and algebraic-geometric codes, and novel decoding algorithms for concatenated codes based on it. * New code constructions using concatenation and/or expander graphs that have good (and sometimes near-optimal) rate and are efficiently list decodable from extremely large amounts of noise. * Expander-based constructions of linear time encodable and decodable codes that can correct up to the maximum possible fraction of errors, using unique (not list) decoding. by Venkatesan Guruswami. Ph.D. 2005-08-23T22:28:06Z 2005-08-23T22:28:06Z 2001 2001 Thesis http://hdl.handle.net/1721.1/8700 49839380 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 315 p. 32954515 bytes 32954269 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Guruswami, Venkatesan, 1976- List decoding of error-correcting codes |
| title | List decoding of error-correcting codes |
| title_full | List decoding of error-correcting codes |
| title_fullStr | List decoding of error-correcting codes |
| title_full_unstemmed | List decoding of error-correcting codes |
| title_short | List decoding of error-correcting codes |
| title_sort | list decoding of error correcting codes |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/8700 |
| work_keys_str_mv | AT guruswamivenkatesan1976 listdecodingoferrorcorrectingcodes |