Monday Feb. 2
I. Introduction
1. Basic problem of digital transmission
2. Shannon's general framework
(source channel separation)
3. Three important channel models
(BSC, BEC, AWGNC)
4. Two simple transmission techniques
for the BSC channel
(uncoded, repetition coding)
5. Shannon's channel coding theorem
for the BSC (unfinished)
Wednesday Feb. 4
Finish proof of Shannon's channel
coding theorem for the BSC
6. The (7, 4) Hamming code
(syndrome decoding, bit error probability)
Friday Feb. 13
7. Minimum distance of a code
(definition, minimum distance of (7, 4)
Hamming code is 3, relationship
between minimum distance and error
correcting capabilities, bounded
distance decoding)
II. Finite Fields
1. Groups:definition, division
algorithm, the additive and the
multiplicative group of integers
mod p, abelian and non-abelian
groups, the order of a group
and of a group element, subgroups,
Monday Feb. 16
coset decomposition, Lagrange's theorem,
2. Basic Definition and Examples of a Field
definition, GF(p)
3. Polynomials and the Euclidean Algorithm
polynomials over a field, division
algorithm, reducible and irreducible
polynomials, gcd and lcm of polynomials
Wednesday Feb. 18
Euclidean algorithm and its consequences,
unique factorization of polynomials,
roots of polynomials,
4. More (on) Finite Fields
construction of extension fields by
means of polynomials, the fields GF(p^m)
5. The Structure of Finite Fields
characteristic of a finite field,
simplifications in the arithmetic over
field with characteristic p,
Monday Feb. 23
III. Block Codes
1. Basic Definitions and Properties
linear, nonlinear, rate, generator
matrix, equivalent codes, minimum
distance, minimum weight, Singleton
Bound, maximum distance separable, dual
code, parity check matrix, syndrome
decoding
Wednesday Feb. 25
2. Some (Good) Codes
2.1 Hamming Codes
Monday March 23
2.2 Hadamard Codes
2.3 The [24, 12, 8] Golay Code
2.4 Reed-Solomon and BCH Codes
Wednesday March 25
3. New Codes from Old Codes
extending, puncturing, shortening,
the (u, u+v) construction
4. Bounds on Codes
Hamming, Gilbert-Varshamov, Singleton,
Plotkin, the greedy algorithm for
nonlinear and linear codes
Monday March 9
3.5 Decoding of RS and BCH Codes
1. The Fourier Transform over Finite Fields
defintion, basic properties,
conjugacy constraints
Wednesday March 11
more on conjugacy constraints
2. A Spectral Defintion of RS and BCH Codes
definitions, examples,
3. A Brief Description of the Peterson-
Gorenstein-Zierler Decoder
Monday March 23
3. A Brief Description of the Peterson-
Gorenstein-Zierler Decoder
4. Linear Complexity and Linear
Feedback Shift Registers (Massey's View)
basic definitions and notation, equivalent
coditions for a LFSR to generate a
sequence, pasting together LFSRs,
Wednesday March 25
Massey's length condition,
Massey's algorithm, condition
for uniqueness
Monday March 30
Berlekamp-Massey Algorithm
derivation and examples
Wednesday April 1
IV. Convolutional Codes
1. Basic Definitions and Examples
definition of convolutional
encoder and codes, notion
of equivalence, equivalent
encoders, polynomial, systematic
catastrophic encoders
Monday April 6
2. State Diagram, Trellis Diagram
and Viterbi Decoder
basic definitions and examples,
derivation of the Viterbi algorithm
Wednesday April 8
example of the Viterbi algorithm
for Hamming metric, general
formulation, example of AWGN channel,
decoding complexity, block codes
versus convolutional codes
Monday April 13
3. Bahl algorithm
4. The Path Enumerator Function
Mason's rule, direct solution
Monday April 20
5. The Smith Normal Form
6. Encoder Inverse
7. (Non)Catastrophic Encoders
8. Minimal Encoders
Wednesday April 22
V. 1. The Effect of Turbo Codes
on Figure 1
2. Turbo Codes as Described
by Berrou, Glavieux and
Thitimajshima
structure, decoding, extrinsic
versus intrinsic information,
Monday April 27
Hagenauers example of decoding
a simple product code, log-likelihood
algebra,
3. Bits and pieces
parallel, serial, product codes,
Stephan ten Brink's turbo demapping,
Hagenauer's turbo equalization,
trellis termination
Wednesday April 29
4. Code performance
bounds based on weight enumerator
functions, Benedetto's turbo
code ensemble, recursive versus non-
recursive, Craig's formula,
directions for improved bounds
Monday May 4
5. Low Density Parity Check Codes/
Expander Codes
Wednesday May 6
6. Geometric Interpretation
of the Turbo Decoding Algorithm
Thursday May 21
7. Codes on graphs
[Scott Rickard and Ying Zhu]
Friday May 22
8. Turbo Codes for higher spectral efficieny
[Boonchai Sriponpaew, Peng Yin, and Julio I. Concha]
9. Turbo Vector Quantization
[Xin Li and Xin Wang]
Last modified: May 6 1998