Ben Gurion University of the Negev

Department of Mathematics

---

CODING THEORY

Course number: 201-14501; Spring Semester 2015

Instructor: Prof. Ido Efrat

• Office: Mathematics Building, Room 106
• Office hours: TBA
• Tel.: (08) 6461627
• E-mail: efrat@math.bgu.ac.il

Exercises:

Exercise no. 1

Exercise no. 2

Exercise no. 3

Exercise no. 4

Exercise no. 5

Exercise no. 6

Exercise no. 7

Exercise no. 8

Exercise no. 9

Exercise no. 10

Exams:

Moed A

Course plan:

1. Introduction
   
   • The main problem of coding theory
   • Hamming distance
   • The minimal distance of a code
   • Optimal codes
   • Constructions of codes from existing codes
   
   
2. Bounds on codes
   
   • The Singleton bound
   • The sphere packing bound
   • The Gilbert-Varshamov bound
   • The Plotkin bound
   
   
3. Finite fields
   
   • The characteristic
   • Existence and uniqueness
   • Primitive roots
   • The Frobenius automorphism
   
   
4. Linear codes
   
   • Dimension
   • Generating Matrices
   • Dual codes
   • Parity check matrices and syndroms
   • Decimal codes and the ISBN code
   • Coding and decoding procedures
   • Reed-Muller codes
   
   
5. Perfect codes
   
   • Hamming codes
   • Football pools
   • The binary Golay code
   • The trenary Golay code
   • Connections with sporadic groups and Platonic solids
   
   
6. Cyclic codes
   
   • Ideals in polynomial rings
   • The generating polynomial
   • Check polynomials
   • The Hamming codes as cyclic codes
   • BCH codes
   • Reed-Solomon codes
   
   
7. Sphere packing
   
   • The problem in dimensions 2 and 3
   • Kepler's problem
   • Connections with codes
   • The Leech lattice
   • Kissing numbers
   
   
8. Asymptotic bounds on sizes of codes
   
   • The code domain, Manin's theorem
   • Assymptotic sphere-packing, Gilbert-Varshamov, Singleton and Plotkin bounds
   
   
9. Introduction to information theory (if time allows)
   
   • Entropy
   • Capacity
   • Shannon's theorems (without proofs)

   ---

   Recommanded Bibliography:

   • R. Hill, A first Course in Coding theory, Clarendon Press, Oxford 1986
     
   • W.C. Huffman and V. Pless, Fundamentals of error-correcting codes, Cambridge University Press, 2003.
     
   • J.H. Van Lint, Introduction to Coding Theory, Springer, Berlin-Heidelberg-New York 1999
     
   • G.A. Jones and J.M. Jones, Information and Coding Theory, Springer 2000

   ---

   Some links:

   • Morse code alphabet
   • A Morse Code translator and player
   • The NATO (Phonetic) code
   • A QR code generator
   • A biography of Richard Hamming
   • The 36-Cube

   ---