Math 342 - Algebra and Coding Theory.

• Chapter 11:
• BCH codes
  
• Practice problems: 11.1, 11.3, 11.4, 11.6.

• Chapter 14: The main linear coding theory problem
• The two forms of the problem.
  
• d=3 case, Hamming codes.
  
• Projective space and the problem of finding linearly independent points.
  

• Chapter 8:
• Hamming codes, both binary and p-ary.
  
• Decoding with Hamming codes. 
• How to determine the minimal distance of a code from the columns of H.
  
• Omitted: Shortened and extended Hamming codes.
  

• Chapter 12:
• Division algorithm for polynomials. g.c.d of two polynomials
  
• Factorization of polynomials.
  
• Polynomials modulo f(x), operations modulo f(x), inverses modulo f(x).
  
• Cyclic codes codes. How to determine all cyclic codes for a given p and n. The matrices G and H for a cyclic code.
  

• Cryptography: (The RSA paper above, or Chapter 16.)
  
• Symmetric key algorithms (affine enciphering/deciphering functions)
• Asymmetric key algorithms: RSA algorithm.
• Digital signatures with RSA algorithm.
• Number theory results related to RSA: Fermat's little theorem, discrete logarithm, Euler's phi function.
  

• Omitted: Diffie-Hellman and McEliece algorithms.

Practice problems from the textbook:

• Chapter 8: 8.1, 8.3, 8.5, 8.6, 8.11. (Notation: the Hamming code Ham(r,p) has parameters  n=(p^r-1)/(p-1) and k=n-r. The code is also called a [n,k]-Hamming code.)
• Chapter 12: 12.1, 12.4, 12.5, 12.7, 12.8, 12.9, 12.10, 12.11, 12.12, 12.13, 12.15, 12.18. (Almost all problems are related to factorization of polynomials, especially the polynomial x^n-1.)
• Chapter 16: 16.1, 16.2, 16.3.

• Chapter 1:
• What is a (n,M,d) q-ary code?
• Hamming distance.
  
• Error detection and correction algorithms.
• How many errors can a code detect/correct?
• Omitted: Error probabilities.
  

• Chapter 2:
• What is a good code?
• Definition of A_q(n,d).
• Simple known values of A_q(n,d).
  
• Equivalence of codes.
• A_2(n,d) = A_2(n+1,d+1) when d is odd.
• Binomial coefficients.
• Spheres, number of elements in a sphere.
• The sphere packing bound and perfect codes.
• Omitted: Balanced block designs.

• Chapter 3:
• Integers: division, principal remainder, Euclidean algorithm, gcd.
  
• Z_m with addition and multiplication operations.
• Division in Z_m, fields Z_p.
  
• The ISBN code.
• Omitted: definition of an abstract field, Galois fields GF(q) other than Z_p.

• Chapter 4:
• The vector space Z_p^n=V(n,p).
• Subspaces of V(n,p).
• Span and linear independence.
• Basis of a subspace.
• Omitted: the axioms of a vector space.

• Chapter 5:
• Linear codes
• Minimal distance of a linear code
• Generator matrix
• How to bring a generator matrix to the standard form
• Omitted: Equivalence of linear codes

• Chapter 6:
• Encoding using a matrix multiplication
• Decoding using the standard array
• Omitted: Error probabilities

• Chapter 7:
• Dot product and orthogonality
• The matrix H and syndrome decoding
• Omitted: Incomplete decoding

---

Practice problems from the textbook:

• Chapter 1: 1.5
• Chapter 2: 2.1, 2.2, 2.3, 2.4, 2.6, 2.8, 2.9, 2.10, 2.16, 2.17, 2.19.
• Chapter 3: 3.1, 3.2, 3.4, 3.6, 3.7, 3.9, 3.12, 3.13.
• Chapter 4: 4.1, 4.3.
• Chapter 5: 5.2, 5.3, 5.4, 5.5, 5.6, 5.7, 5.8, 5.9. (Also, row reduction and bringing a matrix to standard form.)
  
• Chapter 6: 6.1. (Also, matrix multiplication and how to construct the standard array.)
  
• Chapter 7: 7.2, 7.3, 7.4, 7.5, 7.6, 7.11.