A First Course in Coding Theory

✍ Scribed by Raymond Hill

• Tongue: English
• Leaves: 263
• Category: Library

✦ Synopsis

Algebraic coding theory is a new and rapidly developing subject, popular for its many practical applications and for its fascinatingly rich mathematical structure. This book provides an elementary yet rigorous introduction to the theory of error-correcting codes. Based on courses given by the author over several years to advanced undergraduates and first-year graduated students, this guide includes a large number of exercises, all with solutions, making the book highly suitable for individual study.

✦ Table of Contents

Notation
1. Introduction to error-correcting codes
Introduction to error-correcting codes
The transmission of photographs from deep-space
Exercises 1
2. The main coding theory problem
The main coding theory problem
Equivalence of codes
Binomial coefficients
Perfect codes
Balanced block designs
Concluding remarks on Chapter 2
Exercises 2
3. An introduction to finite fields
An introduction to finite fields
The ISBN code
Exercises 3
4. Vector spaces over finite fields
Vector spaces over finite fields
Exercises 4
5. Introduction to linear codes
Introduction to linear codes
Equivalence of linear codes
Exercises 5
6. Encoding and decoding with a linear code
Encoding with a linear code
Decoding with a linear code
Probability of error correction
Symbol error rate
Probability of error detection
Concluding remark on Chapter 6
Exercises 6
7. The dual code, the parity-check matrix, and syndrome decoding
The dual code and the parity-check matrix
Syndrome decoding
Incomplete decoding
Exercises 7
8. The Hamming codes
The Hamming codes
Decoding with a binary Hamming code
Extended binary Hamming codes
A fundamental theorem
q-ary Hamming codes
Decoding with a q-ary Hamming code
Shortening a code
Concluding remarks on Chapter 8
Exercises 8
9. Perfect codes
Perfect codes
The binary Golay [23, 12, 7]-code
The ternary Golay [11, 6, 5]-code
Are there any more perfect codes?
t-designs
Remaining problems on perfect codes
Concluding remarks
Exercises 9
10. Codes and Latin squares
Latin squares
Mutually orthogonal Latin squares
Optimal single-error-correcting codes of length 4
Sets of t mutually orthogonal Latin squares
Exercises 10
11. A double-error correcting decimal code and an introduction to BCH codes
A double-error correcting decimal code and an introduction to BCH codes
Some preliminary results from linear algebra
A double-error-correcting modulus 11 code
A class of BCH codes
Outline of the error-correction procedure (assuming ≤ t errors)
Concluding remarks
Exercises 11
12. Cyclic codes
Cyclic codes
Polynomials
The division algorithm for polynomials
The ring of polynomials modulo f(x)
The finite fields GF(p^h), h > 1
Back to cyclic codes
The check polynomial and the parity-check matrix of a cyclic code
The binary Golay code
The ternary Golay code
Hamming codes as cyclic codes
Concluding remarks on Chapter 12
Exercises 12
13. Weight enumerators
Weight enumerators
Probability of undetected errors
Exercises 13
14. The main linear coding theory problem
The main linear coding theory problem
The MLCT problem for d = 3 (or Hamming codes revisited)
The projective geometry PG(r - 1, q)
The MLCT problem for d = 4
The determination of max₃(3, q)
The determination of max₃(4, q) for q odd
The values of B_q(n, 4), for n ≤ q² + 1
Remarks on max₃(r, q) for r ≥ 5
Concluding remarks on Chapter 14
Exercises 14
15. MDS codes
MDS codes
The known results concerning Conjecture 15.2
Concluding remarks on Chapter 15
Exercises 15
16. Concluding remarks, related topics, and further reading
Concluding remarks, related topics, and further reading
Burst error-correcting codes
Convolutional codes
Cryptographic codes
Variable-length source codes
Exercises 16
Solutions to exercises
Chapter 1
Chapter 2
Chapter 3
Chapter 4
Chapter 5
Chapter 6
Chapter 7
Chapter 8
Chapter 9
Chapter 10
Chapter 11
Chapter 12
Chapter 13
Chapter 14
Chapter 15
Chapter 16
Bibliography
Index