Coding theory: a first course

Cover......Page 1
Half-title......Page 3
Title......Page 5
Copyright......Page 6
Dedication......Page 7
Contents......Page 9
Preface......Page 13
1 Introduction......Page 15
Exercises......Page 18
2.1 Communication channels......Page 19
2.3 Hamming distance......Page 22
2.4 Nearest neighbour/minimum distance decoding......Page 24
2.5 Distance of a code......Page 25
Exercises......Page 28
3.1 Fields......Page 31
3.2 Polynomial rings......Page 36
3.3 Structure of finite fields......Page 40
3.4 Minimal polynomials......Page 44
Exercises......Page 50
4.1 Vector spaces over finite fields......Page 53
4.2 Linear codes......Page 59
4.3 Hamming weight......Page 60
4.4 Bases for linear codes......Page 62
4.5 Generator matrix and parity-check matrix......Page 66
4.6 Equivalence of linear codes......Page 70
4.7 Encoding with a linear code......Page 71
4.8.1 Cosets......Page 73
4.8.2 Nearest neighbour decoding for linear codes......Page 75
4.8.3 Syndrome decoding......Page 76
Exercises......Page 80
5.1 The main coding theory problem......Page 89
5.2.1 Sphere-covering bound......Page 94
5.2.2 Gilbert–Varshamov bound......Page 96
5.3 Hamming bound and perfect codes......Page 97
5.3.1 Binary Hamming codes......Page 98
Decoding with a binary Hamming code......Page 99
5.3.2 q-ary Hamming codes......Page 101
5.3.3 Golay codes......Page 102
Binary Golay codes......Page 103
Ternary Golay codes......Page 105
5.4 Singleton bound and MDS codes......Page 106
5.5 Plotkin bound......Page 109
5.6 Nonlinear codes......Page 110
5.6.2 Nordstrom–Robinson code......Page 112
5.6.4 Kerdock codes......Page 113
5.7 Griesmer bound......Page 114
5.8 Linear programming bound......Page 116
Exercises......Page 120
6.1 Propagation rules......Page 127
6.2 Reed–Muller codes......Page 132
6.3 Subfield codes......Page 135
Exercises......Page 140
7.1 Definitions......Page 147
7.2 Generator polynomials......Page 150
7.3 Generator and parity-check matrices......Page 155
7.4 Decoding of cyclic codes......Page 159
Decoding algorithm for cyclic codes......Page 162
Decoding algorithm for cyclic burst-error-correcting codes......Page 165
7.5 Burst-error-correcting codes......Page 164
Exercises......Page 167
8.1.1 Definitions......Page 173
8.1.2 Parameters of BCH codes......Page 175
8.1.3 Decoding of BCH codes......Page 182
8.2 Reed–Solomon codes......Page 185
8.3 Quadratic-residue codes......Page 189
Exercises......Page 197
9.1 Generalized Reed–Solomon codes......Page 203
9.2 Alternant codes......Page 206
9.3 Goppa codes......Page 210
9.4 Sudan decoding for generalized RS codes......Page 216
9.4.1 Generation of the (P, k, t)-polynomial......Page 217
9.4.2 Factorization of the (P, k, t)-polynomial......Page 219
Factoring algorithm......Page 222
Exercises......Page 223
References......Page 229
Bibliography......Page 231
Index......Page 233