[Home | Cryptography Course Outline]

Coding Theory Course
Duration: 35 1-hour lectures (12 weeks, 3hrs/week)
(1 lecture for midterm makes total 36)

Text: Hoffman, D.G., et al. 1991. Coding Theory: The Essentials. Marcel Dekker Inc: New York.
(comments: undergraduate level, covers most coding theory topics at an appropriate level, does not cover algebra in enough detail)
Library Reserve Text (referenced): Roman, Steven. 1992. Coding and Information Theory. Springer-Verlag: New York.
(comments: graduate level, covers many topics not covered in the course, has better detail on some topics needed for course)
Library Reserve Text (unreferenced): Lidl, R., Niederreiter, H. 1983. Finite Fields. Addison-Wesley: Reading/Mass.
(comments: does not cover some topics for coding theory, good algebra reference, not directly referenced for lectures, but would make a good resource)

Resources:

  • CO 331
  • The Error Correcting Codes Page
  • CIRC
  • CD encoding
  • Google Web Directory on Coding Theory
  • Coding Theory Texts (select a few to put on reserve in library as alternatives)

    Lecture 1: Overview and Introduction to Coding Theory
    Text: 1.1
    Reserve Text: Introduction (pages 1 - 8)

  • course overview
  • basic communications model
  • history of coding theory field
  • discuss "big picture", goals for encoding, decoding
    (e.g. fast with little storage for both parties, good error correcting capability, consideration for encryption, compression)

    Lecture 2: Basic Concepts
    Text: 1.2 - 1.5
    Reserve Text: 2.1, 3.3

  • simple replication code
  • ISBN numbers (sum of digits mod 11 is always zero)
  • basic defintions (e.g. alphabet, word, code, block code)
  • q-symmetric channels.
  • Information rate and distance of a code.

    Lecture 3: Decoding Strategies
    Text: 1.6 - 1.10
    Reserve Text: 4.1, 4.2

  • Incomplete Maximum Likelihood Decoding (IMLD).
  • Complete Maximum Likelihood Decoding (CMLD).
  • Minimum Error probability Decoding (MED)
  • comparison of different methods

    Lecture 4: Error Correcting Capabilities
    Text: 1.11 - 1.12, 3.1
    Reserve Text: 4.1, 4.2, and pages 136, 139, 175

  • Error correcting and detecting capabilities of a code.
  • sphere packing problem, bound

    Lecture 5: Algebraic Background
    Text: Section 5.1
    Reserve Text: Appendix A1, 7.1

  • groups (basic definitions)
  • rings (basic defintions)
  • fields (basic definitions)

    Lecture 6: Introduction to Finite Fields
    Text: Section 5.1
    Reserve Text: 7.1, Appendix A1

  • Definition of finite fields
  • Existence of finite fields of prime order p (the integers modulo p).
  • The characteristic of a finite field.

    Lecture 7: Introduction to Finite Fields II
    Text: Section 5.1
    Reserve Text: 7.1, Appendix A1

  • Consideration of a finite field as a vector space over Zp.
  • Every finite field has order p^n, for some prime p and positive integer n.

    Lecture 8: Polynomials over Finite Fields
    Text: Section 5.1
    Reserve Text: 7.2, Appendix A1, A4

  • Polynomial rings
  • irreducible polynomials
  • construction of irreducible polynomials

    Lecture 9: Construction of Finite Fields
    Text: Section 5.1
    Reserve Text: 7.1, Appendix A1

  • Construction of finite fields of order p^n
  • Examples of finite fields and construction

    Lecture 10: Properties of Finite Fields
    Text: Section 5.1
    Reserve Text: 7.1, 7.3, Appendix A1

  • Freshman's dream: (a + b)k = ak + bk
  • Orders of non-zero field elements
  • Definition of a primitive element (aka generator)
  • Proof that every finite field has a primitive element

    Lecture 11: Finite Field Related Examples
    Text: Section 5.1
    Reserve Text: 7.1, 7.3, Appendix A1

  • example of finding primitive element
  • other examples as appropriate/as requested

    Lecture 12: Linear Codes
    Text: Chapter 2
    Reserve Text: 5.1, 5.2

  • Definition of a linear (n,k)-code over a finite field F
  • Weight and rate of a linear code
  • Encoding rules for linear codes
  • Example

    Lecture 13: Properties of Linear Codes
    Text: Section 2.6, 2.8
    Reserve Text: 5.1, and pages 143-144

  • Generator matrix of a linear code
  • Number of linear codes
  • Systematic codes
  • Equivalent codes

    Lecture 14: The Dual Code
    Text: section 2.7
    Reserve Text: 5.1

  • dual code of a linear code
  • Parity-check matrix of a linear code

    Lecture 15: Perfect Codes
    Text: Sections 3.1 - 3.3
    Reserve Text: 5.1, 6.1 and pages 138, 150, 154

  • Deducing the distance of a linear code from a parity-check matrix.
  • Perfect codes
  • Hamming codes of order r over GF(q)

    Lecture 16: Hamming Codes
    Text: Sections 3.1 - 3.3
    Reserve Text: 6.1

  • Distance and dimension of a Hamming code
  • Classification of binary perfect codes
  • Hamming codes are perfect

    Lecture 17: Decoding Linear Codes, Analysing Algorithms
    Text: 2.10 - 2.12
    Reserve Text: 5.1, 5.3

  • Decoding algorithm for single-error correcting codes
  • running time of an algorithm, space usage, big-O notation

    Lecture 18: Decoding Linear Codes with Analysis
    Text: Sections 2.10 - 2.12
    Reserve Text: 5.1, 5.3, Appendix A1

  • Standard array decoding for a linear code
  • Analysis of space and runtime
  • definition of cosets, coset leaders
  • Syndrome decoding
  • Analysis of space and runtime

    Lecture 19: Extended Binary Golay Code
    Text: Sections 3.5 - 3.7
    Reserve Text: page 151

  • Binary Golay Code, another perfect code
  • Extended Binary Golay Code
  • decoding the Golay Code

    Lecture 20: Algebraic Background for Cyclic Codes
    Text: --
    Reserve Text: Appendix A1

  • Ideals of a ring
  • An algebraic characterization of cyclic subspaces of Vn(F)
  • R=F[x]/(x^n-1) is a principal ideal ring

    Lecture 21: Algebraic Background for Cyclic Codes II
    Text: --
    Reserve Text: Appendix A1

  • Definition of the generator polynomial of an ideal.
  • 1-1 correspondence between monic divisors of x^n-1 and ideals of R
  • connection to cyclic codes

    Lecture 22: Cyclic Codes
    Text: Sections 4.1 - 4.2
    Reserve Text: 7.3, 7.4

  • The dimension of the cyclic code C generated by a degree (n-k) monic divisor g(x) of x^n-1 is k.
  • A generator matrix G for C.
  • Encoding of message a(x) with respect to G corresponds to polynomial multiplication of a(x) and g(x)

    Lecture 23: Dual Code for Cyclic Codes
    Text: Section 4.5
    Reserve Text: 7.4

  • dual code of a cylic code is also cyclic.
  • generator polynomial for the dual code of a cylic code
  • parity check polynomial (x^n-1)/g(x)
  • Examples

    Lecture 24: Burst Error Correcting
    Text: Section 7.1
    Reserve Text: 7.5

  • definition of a cyclic burst error
  • cyclic burst error correcting capability of a code
  • error trapping decoding algorithm

    Lecture 25: Interleaving
    Text: Section 7.2
    Reserve Text: 7.5

  • definition/method
  • purpose (increase cyclic burst error correcting capability)
  • examples to prove purpose is fufilled

    Lecture 26: Erasures
    Text: Section 6.6
    Reserve Text: --

  • erasure correction ability
  • cyclic codes and burst erasures

    Lecture 27: Minimal Polynomials
    Text: Section 5.2
    Reserve Text: 7.2, Appendix A1, A4

  • Definition of the minimal polynomial of a field element.
  • Basic properties of minimal polynomials.

    Lecture 28: Minimal Polynomials CONT'D
    Text: 5.2
    Reserve Text: 7.2, Appendix A1, A4

  • Conjugates over GF(q) of an element of GF(q^m).
  • A formula for computing minimal polynomials.

    Lecture 29: Cyclotomic Cosets
    Text: --
    Reserve Text: 7.3

  • Cyclotomic cosets of q modulo n
  • Using cyclotomic cosets to derive the factorization pattern of x^n-1 over GF(q)

    Lecture 30: BCH Codes
    Text: 5.4
    Reserve Text: 8.1

  • Definition of a BCH code
  • Construction with design distance d
  • Determinant of a Vandermonde matrix
  • Proof of the BCH bound

    Lecture 31: BCH Decoding Algorithm
    Text: 5.5
    Reserve Text: 8.1

  • decoding algorithm
  • examples

    Lecture 32: Reed-Solomon Codes
    Text: Chapter 6
    Reserve Text: 8.2

  • definitions, subset of BCH codes, specified RS(n, k) with s-bit symbols
  • t error correcting capability where 2t = n - k
  • decoding algorithm

    Lecture 33: Application of Reed-Solomon Codes
    Text: Section 7.3, Appendix C
    Reserve Text: --

  • CD encoding using Cross Interleaved Reed-Solomon Code (CIRC)
  • uses 2 Reed-Solomon codes with interleaving
  • burst error correcting capability (corrects error bursts up to 3,500 bits (2.4 mm in length) and compensates for error bursts up to 12,000 bits (8.5 mm) such as caused by minor scratches)
  • webpage about CIRC
  • webpage about CD encoding

    Lecture 34: Final Exam Review

  • topics from midterm with which students had trouble
  • topics important for final exam
  • student requests

    Lecture 35: Overflow/Holiday Allowance

  • to be used during the term for a missed lecture
  • or for a topic that required an extra lecture to cover