The Mathematics of Coding Theory

Contents......Page 3
1.1 Set.s and functions......Page 9
1.2 Counting
......Page 13
1.3 Preliminary ideas of  probability
......Page 16
1.4 More formal view of probability
......Page 21
1.5 Random variables, expected values, variance
......Page 28
1.7 Law of Large Numbers
......Page 35
2.1 Uncertainty, acquisition of information
......Page 41
2.2 Definition of entropy
......Page 45
3.1 Noiseless coding
......Page 52
3.2 Kraft and McMillan inequalities
......Page 56
3.3 Noiseless coding theorem
......Page 59
3.4 Huffman encoding
......Page 62
4.1 Noisy channels 
......Page 69
4.2 Example: parity checks
......Page 71
4.3 Decoding from a noisy channel
......Page 74
4.4 Channel capacity
......Page 75
4.5 Noisy coding theorem
......Page 79
5.1 The finite field with 2 elements
......Page 90
5.2 Polynomials over GF(2)
......Page 91
5.3 Cyclic redundancy checks (CRCs)
......Page 94
5.4 What errors does a CRC catch?
......Page 96
6.1 The reduction algorithm
......Page 101
6.2 Divisibility
......Page 104
6.3 Factorization into primes
......Page 107
6.4 A failure of unique factorization
......Page 111
6.5 The Euclidean Algorithm
......Page 113
6.6 Equivalence relations
......Page 116
6.7 The integers modulo m
......Page 119
6.8 The finite field Z/p for p prime
......Page 123
6.9 Fermat's Little Theorem......Page 125
6.10 Euler's theorem
......Page 126
6.11 Facts about primitive roots
......Page 128
6.12 Euler's criterion
......Page 129
6.13 Fast modular exponentiation
......Page 130
6.14 Sun-Ze's theorem
......Page 132
6.15 
Euler's phi-function......Page 136
7.1 Permutations of sets
......Page 142
7.2 Shuffles
......Page 147
7.3 Block interleavers
......Page 149
8.1 Groups
......Page 153
8.2 Subgroups
......Page 155
8.3 Lagrange's Theorem
......Page 156
8.4 Index of a subgroup
......Page 158
8.5 Laws of exponents
......Page 159
8.6 Cyclic subgroups, orders, exponents
......Page 161
8.7 Euler's Theorem
......Page 162
8.8 Exponents of groups
......Page 163
8.9 Group homomorphisms
......Page 164
8.10 Finite cyclic groups
......Page 166
8.11 Roots, powers
......Page 169
9.1 Rings
......Page 175
9.2 Ring homomorphisms
......Page 179
9.3 Fields
......Page 183
10.1 Polynomials
......Page 186
10.2 Divisibility......Page 189
10.3 Factoring and irreducibility......Page 192
10.4 Euclidean algorithm for polynomials......Page 195
10.5 Unique factorization of polynomials......Page 197
11.1 Making fields......Page 200
11.2 Examples of field extensions......Page 203
11.5 Multiplicative inverses mod P......Page 205
12.1 An ugly example
......Page 208
12.2 A better approach......Page 211
12.3 An inequality from the other side
......Page 212
12.4 The Hamming binary [7,4] code......Page 213
12.5 Some linear algebra......Page 216
12.6 Row reduction: a review......Page 219
12.7 Linear codes......Page 226
12.8 Dual codes, syndrome decoding......Page 230
13.1 Hamming (sphere-packing) bound
......Page 236
13.2 Gilbert-Varshamov bound......Page 238
13.3 Singleton bound......Page 240
14.1 Minimum distances in linear codes
......Page 242
14.2 Cyclic codes
......Page 243
15.1 Primitive elements in finite fields
......Page 248
15.2 Characteristics of fields
......Page 249
15.3 Multiple factors in polynomials
......Page 251
15.4 Cyclotomic polynomials
......Page 254
15.5 Primitive elements in finite fields: proofs
......Page 259
15.6 Primitive roots in Z/p
......Page 260
15.7 Primitive roots in Z/pe
......Page 261
15.8 Counting primitive roots
......Page 264
15.9 Non-existence of primitive roots
......Page 265
15.10 An algorithm to find primitive roots
......Page 266
16.1 Definition of primitive polynomials......Page 268
16.2 Examples mod 2......Page 269
16.3 Testing for primitivity......Page 272
16.4 Periods of LFSRs......Page 275
16.5 Two-bit errors in CRCs......Page 280
17 RS and BCH Codes......Page 284
17.1 Vandermonde determinants......Page 285
17.2 Variant check matrices for cyclic codes......Page 288
17.3 Reed-Solomon codes......Page 290
17.4 Hamming codes......Page 293
17.5 BCH codes......Page 295
18.1 Mirage codes
......Page 305
18.2 Concatenated codes
......Page 309
18.3 Justesen codes
......Page 311
18.4 Some explicit irreducible polynomials
......Page 314
19.1 Ideals in commutative rings......Page 317
19.2 Ring homomorphisms
......Page 321
19.3 Quotient rings......Page 325
19.5 Field extensions......Page 326
19.6 The Frobenius automorphism......Page 329
19.7 Counting irreducibles......Page 337
19.8 Counting primitives......Page 339
20.1 Plane curves
......Page 343
20.2 Singularities of curves
......Page 347
20.3 Projective plane curves
......Page 350
20.5 Genus, divisors, linear systems
......Page 356
20.6 Geometric Goppa codes
......Page 361
20.7 The Tsfasman-Vladut-Zink-Ihara bound
......Page 362
Appendix: Stirling's Formula......Page 364
A.1 Basics
......Page 368
A.2 Dimension
......Page 371
A.3 Homomorphisms and duals
......Page 373
A.4 Scalar products
......Page 380
A.5 Vandermonde determinants
......Page 382
Appendix: Polynomials......Page 386
Bibliography......Page 392
1.01 - 1.40
......Page 394
1.53 - 6.11
......Page 395
6.13 - 6.71
......Page 396
6.75 - 11.05
......Page 397
11.06 - 16.13
......Page 398
16.16 - 18.06
......Page 399
19.03 - 20.06
......Page 400
Index......Page 401