List Decoding of Error-Correcting Codes: Winning Thesis of the 2002 ACM Doctoral Dissertation Competition

Front Cover
Springer Science & Business Media, Nov 29, 2004 - Computers - 350 pages
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.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

I
1
III
4
IV
7
V
8
VI
9
VII
10
IX
13
XI
15
CXIV
169
CXV
171
CXVI
174
CXVII
177
CXVIII
178
CXIX
179
CXX
180
CXXI
184

XIV
17
XVI
18
XVII
20
XX
21
XXI
22
XXIII
23
XXIV
24
XXVI
26
XXVII
28
XXVIII
29
XXX
33
XXXII
34
XXXIII
35
XXXIV
37
XXXV
39
XXXVI
41
XXXVII
43
XXXVIII
45
XXXIX
46
XL
47
XLI
48
XLII
50
XLIV
55
XLV
56
XLVI
60
XLVIII
62
L
63
LI
64
LII
67
LIII
68
LIV
71
LVI
72
LVII
76
LIX
79
LXI
80
LXII
81
LXIV
85
LXV
88
LXVI
89
LXVII
90
LXVIII
91
LXIX
95
LXXI
96
LXXII
97
LXXIII
98
LXXV
100
LXXVI
102
LXXVII
103
LXXVIII
105
LXXIX
108
LXXX
111
LXXXI
113
LXXXII
114
LXXXIII
117
LXXXIV
121
LXXXVI
122
LXXXVII
126
LXXXVIII
129
LXXXIX
132
XC
134
XCI
136
XCII
137
XCIII
138
XCIV
141
XCV
142
XCVI
146
XCVIII
148
XCIX
149
C
151
CI
152
CIII
153
CV
154
CVI
155
CVII
156
CIX
159
CX
160
CXI
161
CXII
162
CXIII
165
CXXII
186
CXXIII
187
CXXV
188
CXXVI
192
CXXVII
195
CXXVIII
198
CXXIX
199
CXXX
202
CXXXI
205
CXXXII
206
CXXXIII
208
CXXXIV
210
CXXXV
213
CXXXVI
215
CXXXVIII
216
CXXXIX
218
CXL
221
CXLI
225
CXLII
227
CXLIII
228
CXLV
231
CXLVI
234
CXLVII
235
CXLVIII
236
CXLIX
239
CL
242
CLI
243
CLII
244
CLIII
245
CLIV
249
CLV
251
CLVII
252
CLVIII
253
CLIX
254
CLXI
256
CLXII
257
CLXIII
258
CLXIV
259
CLXV
262
CLXVI
265
CLXIX
266
CLXX
268
CLXXI
270
CLXXII
272
CLXXIV
275
CLXXV
276
CLXXVI
277
CLXXVII
279
CLXXVIII
284
CLXXIX
285
CLXXX
286
CLXXXI
288
CLXXXII
289
CLXXXIV
291
CLXXXV
294
CLXXXVI
297
CLXXXVII
298
CLXXXVIII
299
CLXXXIX
300
CXC
302
CXCI
304
CXCII
308
CXCIII
309
CXCIV
310
CXCV
311
CXCVI
313
CXCVII
315
CXCIX
318
CC
320
CCI
324
CCIII
325
CCV
329
CCVII
330
CCIX
331
CCX
333
CCXII
336
CCXIII
348
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information