Introduction to Coding Theory

Front Cover
Cambridge University Press, Feb 23, 2006 - Computers - 566 pages
0 Reviews
Error-correcting codes constitute one of the key ingredients in achieving the high degree of reliability required in modern data transmission and storage systems. This book introduces the reader to the theoretical foundations of error-correcting codes, with an emphasis on Reed-Solomon codes and their derivative codes. After reviewing linear codes and finite fields, Ron Roth describes Reed-Solomon codes and various decoding algorithms. Cyclic codes are presented, as are MDS codes, graph codes, and codes in the Lee metric. Concatenated, trellis, and convolutional codes are also discussed in detail.
 

What people are saying - Write a review

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

Contents

Introduction
1
12 Channel coding
3
13 Block codes
5
14 Decoding
7
15 Levels of error handling
11
Problems
17
Notes
22
Linear Codes
26
List Decoding of ReedSolomon Codes
266
91 List decoding
267
92 Bivariate polynomials
268
93 GRS decoding through bivariate polynomials
269
94 Sudans algorithm
271
95 The GuruswamiSudan algorithm
276
96 List decoding of alternant codes
280
97 Finding linear bivariate factors
284

22 Encoding of linear codes
28
23 Paritycheck matrix
29
24 Decoding of linear codes
32
Problems
36
Notes
47
Introduction to Finite Fields
50
32 Polynomials
51
33 Extension fields
56
34 Roots of polynomials
59
35 Primitive elements
60
36 Field characteristic
62
37 Splitting field
64
double errorcorrecting codes
66
Problems
70
Notes
90
Bounds on the Parameters of Codes
93
41 The Singleton bound
94
42 The spherepacking bound
95
43 The GilbertVarshamov bound
97
44 MacWilliams identities
99
45 Asymptotic bounds
104
46 Converse Coding Theorem
110
47 Coding Theorem
115
Problems
119
Notes
136
ReedSolomon and Related Codes
147
51 Generalized ReedSolomon codes
148
52 Conventional ReedSolomon codes
151
53 Encoding of RS codes
152
54 Concatenated codes
154
55 Alternant codes
157
56 BCH codes
162
Problems
163
Notes
177
Decoding of ReedSolomon Codes
183
62 Syndrome computation
184
63 Key equation of GRS decoding
185
64 Solving the key equation by Euclids algorithm
191
65 Finding the error values
194
66 Summary of the GRS decoding algorithm
195
67 The BerlekampMassey algorithm
197
Problems
204
Notes
215
Structure of Finite Fields
218
72 Enumeration of irreducible polynomials
224
73 Isomorphism of finite fields
227
75 Cyclotomic cosets
229
Problems
232
Notes
240
Cyclic Codes
242
82 Generator polynomial and check polynomial
244
83 Roots of a cyclic code
247
84 BCH codes as cyclic codes
250
85 The BCH bound
253
Problems
256
Notes
265
98 Bounds on the decoding radius
289
Problems
291
Notes
295
Codes in the Lee Metric
298
102 Newtons identities
300
103 Leemetric alternant codes and GRS codes
302
104 Decoding alternant codes in the Lee metric
306
105 Decoding GRS codes in the Lee metric
312
106 Berlekamp codes
314
107 Bounds for codes in the Lee metric
316
Problems
321
Notes
327
MDS Codes
333
112 GRS codes and their extensions
335
113 Bounds on the length of linear MDS codes
338
114 GRS codes and the MDS conjecture
342
115 Uniqueness of certain MDS codes
347
Problems
351
Notes
361
Concatenated Codes
365
121 Definition revisited
366
122 Decoding of concatenated codes
367
123 The Zyablov bound
371
124 Justesen codes
374
125 Concatenated codes that attain capacity
378
Problems
381
Notes
392
Graph Codes
395
131 Basic concepts from graph theory
396
132 Regular graphs
401
133 Graph expansion
402
134 Expanders from codes
406
135 Ramanujan graphs
409
136 Codes from expanders
411
137 Iterative decoding of graph codes
414
138 Graph codes in concatenated schemes
420
Problems
426
Notes
445
Trellis and Convolutional Codes
452
141 Labeled directed graphs
453
142 Trellis codes
460
143 Decoding of trellis codes
466
144 Linear finitestate machines
471
145 Convolutional codes
477
146 Encoding of convolutional codes
479
147 Decoding of convolutional codes
485
148 Noncatastrophic generator matrices
495
Problems
501
Notes
518
Basics in Modern Algebra
521
Problems
522
Bibliography
527
List of Symbols
553
Index
559
Copyright

Common terms and phrases

Popular passages

Page 529 - Near Optimum Error Correcting Coding and Decoding: Turbo-Codes,
Page 533 - P. Delsarte, Four fundamental parameters of a code and their combinatorial significance, Info.

About the author (2006)

Ron M. Roth is Professor of Computer Science at the Technion, Israel Institute of Technology.

Bibliographic information