List Decoding of Error-Correcting Codes纠错码的列表解码

北京燕山出版社  

Guruswami, Venkatesan  

350  

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.

1　Introduction　1.1　Basics of Error-Correcting Codes　1.2　The Decoding Problem for Error-Correcting Codes　1.3　List Decoding　　1.3.1　Definition　　1.3.2　Is List Decoding a Useful Relaxation of Unique Decoding?　　1.3.3　The Challenge of List Decoding　　1.3.4　Early Work on List Decoding　1.4　Contributions of This Work　1.5　Background Assumed of the Reader　1.6　Comparison with Doctcral Thesis Submitted to MIT2　Preliminaries and Monograph Structure　2.1　Preliminaries and Definitions　　2.1.1　Basic Definitions for Codes　　2.1.2　Code Families　　2.1.3　Linear Codes　　2.1.4　Definitions Relating to List Decoding　　2.1.5　Commonly Used Notation　2.2　Basic Code Families　　2.2.1　Reed-Solomon Codes　　2.2.2　Reed-Muller Codes　　2.2.3　Algebraic-Geometric Codes　　2.2.4　Concatenated Codes　　2.2.5　Number-Theoretic Codes　2.3　Detailed Description of Book Chapters　　2.3.1　Combinatorial Results　　2.3.2　Algorithmic Results　　2.3.3　Applications　　2.3.4　Conclusions　　2.3.5　Dependencies Among ChaptersPart I Combinatorial Bounds　3　Johnson-Type Bounds and Applications to List Decoding.　　3.1　Introduction　　3.2　Definitions and Notation　　3.3　The Johnson Bound on List Decoding Radius　　　3.3.1　Proof of Theorem 3.1　　　3.3.2　Geometric Lemmas　　3.4　Generalization in Presence of Weights　　3.5　Notes　4　 Limits to List Decodability　　4.1　Introduction　　4.2　Informal Description of Results　　4.3　Formal Description of Results　　　4.3.1　The Result for Non-linear Codes　　　4.3.2　Definitions　　　4.3.3　Statement of Results　　4.4　Super-constant List Size at Johnson Radius　　　4.4.1　The Basic Construction　　　4.4.2　Related Constructions　　　4.4.3　The Technical "Linear-Algebraic" Lemma　　4.5　Super-polynomial List Size Below Minimum Distance　　　4.5.1　Proof of Theorem 4.10　　4.6　Explicit Constructions with Polynomial-Sized Lists　　　4.6.1　Fourier Analysis and Group Characters　　　4.6.2　Idea Behind the Construction　　　4.6.3　Proof of Theorem 4.8　　　4.6.4　Proof of Theorem 4.9　　　4.6.5　Proof of Theorem 4.16　　4.7　Super-polynomial List Sizes at the Johnson Bound　　　4.7.1　Proof Idea　　　4.7.2　The Technical Proof　　　4.7.3　Unconditional Proof of Tightness of Johnson Bound ..　　4.8　Notes and Open Questions　5　List Decodability Vs. Rate　　5.1　Introduction　　5.2　Definitions　　5.3　Main Results　　　5.3.1　Basic Lower Bounds　　　5.3.2　An Improved Lower Bound for Binary Linear Codes ..　　　5.3.3　Upper Bounds on the Rate Function　　　5.3.4　"Optimality" of Theorem 5.8……Part II Code Constructions and AlgorithmsPart III ApplicationsA GMD Decoding of Concatenated CodesReferencesIndex

List Decoding of Error-Correcting Codes纠错码的列表解码 PDF格式下载