Math 432 Daily Schedule

Meeting Date Topic
1 Wed, Jan 17, 2001 Introduction
1.1 Basic problem
1.2 Three simple codes
2 Fri, Jan 19, 2001 1.3 Channel models
1.4 Encoders, error processors, decoders
1.5 Specific cases
Exercises: 4, 5, 6
3 Mon, Jan 22, 2001 2.1 Block codes
2.2 Weight and distance
2.3 Error processing
4 Wed, Jan 24, 2001 2.4 Error detection: necessary and sufficient conditions
2.5 Error correction: necessary and sufficient conditions
2.6 Mixed strategies
5 Fri, Jan 26, 2001 2.7 Probability of errors
2.8 Probability of correct transmission
2.9 Examples
2.10 Shannon's Theorem
Exercises: 1, 2, 4, 6, 7, 9, 10, 13, 14, 15
6 Mon, Jan 29, 2001 3.1 Arithmetic in B
3.2 Arithmetic in B^n
3.3 Fields: a definition
3.4 Vector space operations
7 Wed, Jan 31, 2001 3.5 Binary linear codes
3.6 Encoders and linearity
3.7 The generator matrix
8 Fri, Feb 2, 2001 3.8 The columns of the generator matrix
3.9 Codes and generator matrices
9 Mon, Feb 5, 2001 3.10 Code word checking
3.11 Relationship between generator and check matrices
3.12 Existence of generator and check matrices
3.13 Rank of the check matrix
Exercises: 6, 7, 10, 12, 16, 19, 21, 22, 23
10 Wed, Feb 7, 2001 4.1 Constructing the standard array
4.2 Row and column differences in a standard array
4.3 Occurrence of words in a standard array
4.4 Another view of Theorem 4.3
11 Fri, Feb 9, 2001 4.5 Cosets
4.6 Error words
4.7 Correction to closest code word
4.8 Information from the standard array
12 Mon, Feb 12, 2001 4.9 Cosets of a code and its check matrix
4.10 Syndromes of received words and error words
4.11 Condition for single error correction
4.12 Check matrix and minimum distance
Exercises: 1, 2, 4, 5, 6, 8
13 Wed, Feb 14, 2001 5.1 The binary Hamming codes
5.2 Parameters of the Hamming codes
5.3 Comparing Ham(3) and TPC
14 Fri, Feb 16, 2001 5.4 Perfect codes
5.5 Length of Hamming codes
5.6 A closer look at Ham(3)
5.7 Symmetries of the Hamming code
Exercises: 1, 2, 4, 5, 6
15 Mon, Feb 19, 2001 6.1 Constructing codes for correcting multiple errors
6.2 Correcting error bursts
6.3 Finding new codes
6.4 Four-bit strings
6.5 The integers modulo 16
6.6 Polynomials with binary coefficients
16 Wed, Feb 21, 2001 6.7 The structure of B[x]/f(x)
6.8 The field of order 16
Exercises: 4, 5, 6, 7, 8, 9, 10, 11
17 Fri, Feb 23, 2001 7.1 An example
7.2 Euclidean domains
7.3 Greatest common divisor
7.4 GCD in terms of a and b
18 Mon, Feb 26, 2001 7.5 The four-column array for Euclid's algorithm
7.6 A worked example
7.7 A formal definition of Euclid's algorithm
7.8 More on Euclid's algorithm
Exercises: 1, 2, 3, 4, 8, 9
19 Wed, Feb 28, 2001 8.1 Invertible elements
8.2 More on GCDs
8.3 Invertibility and ||x||
8.4 Relative primeness
20 Fri, Mar 2, 2001 8.5 The "1-trick"
8.6 Irreducibility
8.7 The key property of irreducible elements
8.8 LCM of relatively prime elements
Exercises: 1, 2, 3, 7, 8, 9, 10, 11, 12, 13
21 Mon, Mar 5, 2001 9.1 The factor ring
9.2 The uniqueness assumption
9.3 D/a is a commutative ring
22 Wed, Mar 7, 2001 9.4 Remainder functions
9.5 Class representatives
9.6 Interchangeability of remainders
23 Fri, Mar 9, 2001 9.7 Condition for a field
9.8 Proof of the condition
9.9 Finding inverses
9.10 Available field sizes
9.11 GF(16) again
Exercises: 7, 8, 9, 10, 11, 12, 13
24 Mon, Mar 12, 2001 10.1 The prime field and the characteristic
10.2 Sizes of finite fields
10.3 A property of X(F)
10.4 Fermat's little theorem
25 Wed, Mar 14, 2001 10.5 Integer multiples
10.6 Some arithmetic
10.7 Constructing the prime field
10.8 Isomorphisms and automorphisms
10.9 Completing Theorem 10.1
10.10 Completing Theorem 10.2
26 Fri, Mar 16, 2001 10.11 Use of linear algebra
10.12 Uniqueness of the prime field
10.13 A result on binomial coefficents
10.14 The Frobenius automorphism
10.15 Termat's little theorem
Exercises: 1, 2, 3, 4, 5, 6, 7, 8
SPRING BREAK
27 Mon, Mar 26, 2001 11.1 More on polynomials
11.2 Evaluating polynomials
11.3 The formal derivative
11.4 Horner's scheme
11.5 The minimal polynomial of b
28 Wed, Mar 28, 2001 11.6 Properties of the minimal polynomial
11.7 Fields with p^n elements
11.8 The splitting field
11.9 An existence theorem
11.10 Herstein's alternative
11.11 Subfields of all orders
Exercises 1, 2, 3, 4, 5, 6, 7, 8
29 Fri, Mar 30, 2001 12.1 Primitive elements
12.2 Existence of primitive elements: preliminaries
12.3 Elements of large order
12.4 Existence of primitive element: proof
30 Mon, Apr 2, 2001 12.5 Discrete logarithms and addition
12.6 Primitive polynomials
12.7 Isomorphisms of fields of same order
12.8 Factorization of x^q - x
Exercises 1, 2, 3, 4, 5, 6, 7, 8
31 Wed, Apr 4, 2001 13.1 Introduction
13.2 Vandermonde matrices
13.3 Extending a Hamming check matrix
13.4 Verification
32 Fri, Apr 6, 2001 13.5 Further extensions
13.6 Using BCH(4, 3) as an example
13.7 List of code words
13.8 The reduced check matrix
33 Mon, Apr 9, 2001 13.9 Some questions
13.10 The check matrix and error patterns
Exercises: 1, 2, 3
14.1 Code polynomials
34 Wed, Apr 11, 2001 14.2 The generator polynomial
14.3 Rank and generator polynomial of BCH codes
14.4 Multiplicative encoding
35 Fri, Apr 13, 2001 14.5 A generator matrix for BCH(k, t)
14.6 The check polynomial
14.7 Multiplicative decoding for BCH(k, t)
36 Mon, Apr 16, 2001 14.8 Systematic encoding for BCH(k, t)
Exercises 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
15.1 Determining the error word
15.2 The syndromes of a received word
37 Wed, Apr 18, 2001 15.3 Syndromes and syndrome vectors
15.4 The case s = 2
15.5 Summary of the method
38 Fri, Apr 20, 2001 15.6 The syndrome polynomial
15.7 A geometric progression
15.8 Formula for syndrome polynomial
39 Mon, Apr 23, 2001 15.9 Introduction to the fundamental equation
15.10 The numerators
15.11 The fundamental equation
15.12 Proving the fundamental equation
Exercises: 1, 2, 3, 4, 5, 6, 7
40 Wed, Apr 25, 2001 16.1 The fundamental equation again
16.2 The BCH algorithm
16.3 Termination of the algorithm
41 Fri, Apr 27, 2001 16.4 Failure modes
16.5 The polynomials calculated by the algorithm
16.6 Uniqueness of the error locator and evaluator
42 Mon, Apr 30, 2001 16.7 Properties of Euclid's algorithm
16.8 Relating l°, u°, w° to l, u, w
Exercises: 1, 2, 4, 5, 6