[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)