Logo - springer
Slogan - springer

Computer Science - Security and Cryptology | List Decoding of Error-Correcting Codes - Winning Thesis of the 2002 ACM Doctoral Dissertation

List Decoding of Error-Correcting Codes

Winning Thesis of the 2002 ACM Doctoral Dissertation Competition

Guruswami, Venkatesan

2005, XIX, 350 p. Also available online.

Available Formats:
eBook
Information

Springer eBooks may be purchased by end-customers only and are sold without copy protection (DRM free). Instead, all eBooks include personalized watermarks. This means you can read the Springer eBooks across numerous devices such as Laptops, eReaders, and tablets.

You can pay for Springer eBooks with Visa, Mastercard, American Express or Paypal.

After the purchase you can directly download the eBook file or read it online in our Springer eBook Reader. Furthermore your eBook will be stored in your MySpringer account. So you can always re-download your eBooks.

 
$79.99

(net) price for USA

ISBN 978-3-540-30180-6

digitally watermarked, no DRM

Included Format: PDF

download immediately after purchase


learn more about Springer eBooks

add to marked items

Softcover
Information

Softcover (also known as softback) version.

You can pay for Springer Books with Visa, Mastercard, American Express or Paypal.

Standard shipping is free of charge for individual customers.

 
$109.00

(net) price for USA

ISBN 978-3-540-24051-8

free shipping for individuals worldwide

usually dispatched within 3 to 5 business days


add to marked items

  • About this book

How can one exchange information e?ectively when the medium of com- nication introduces errors? This question has been investigated extensively starting with the seminal works of Shannon (1948) and Hamming (1950), and has led to the 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 errors e?ciently. This thesis presents some spectacular new results in the area of decoding algorithms for error-correctingcodes. Speci?cally,itshowshowthenotionof“list-decoding” can be applied to recover from far more errors, for a wide variety of err- correcting codes, than achievable before. A brief bit of background: error-correcting codes are combinatorial str- tures that show how to represent (or “encode”) information so that it is - silient to a moderate number of errors. Speci?cally, an error-correcting code takes a short binary string, called the message, and shows how to transform it into a longer binary string, called the codeword, so that if a small number of bits of the codewordare ?ipped, the resulting string does not look like any other codeword. The maximum number of errorsthat the code is guaranteed to detect, denoted d, is a central parameter in its design. A basic property of such a code is that if the number of errors that occur is known to be smaller than d/2, the message is determined uniquely. This poses a computational problem,calledthedecodingproblem:computethemessagefromacorrupted codeword, when the number of errors is less than d/2.

Content Level » Research

Keywords » Code - Error-correcting Code - Information - Shannon - algorithms - coding theory - complexity theory - concatenated codes - decoding - decoding algorithms - encoding - error-detecting codes - information theory - list decoding - reed-solomon codes

Related subjects » Computational Science & Engineering - Information Systems and Applications - Security and Cryptology - Theoretical Computer Science

Table of contents / Preface 

Popular Content within this publication 

 

Articles

Read this Book on Springerlink

Services for this book

New Book Alert

Get alerted on new Springer publications in the subject area of Data Structures, Cryptology and Information Theory.