2016 - 2017

0512-4163-01
  Introduction to Error Correction Codes                                                               
FACULTY OF ENGINEERING
Prof. Simon LitsynComputer and Software Engineering106Sun1400-1700 Sem  2
 
 
University credit hours:  4.0

Course description
Credit Points: 3.5
Prerequisites: Digital Communications (Concurrent)
Block codes, linearity, generator matrix, check matrix. Errors and erasures decoding. Hamming bound, Singleton bound, covering radius, Reed-Muller codes, Griesmer bound, Hamming codes. Monomial equivalence. Product codes, generalized Hamming weight. Singleton bound over a general alphabet, MDS codes, equivalence. Cyclic codes, interleaved codes, the Meggitt decoder and error trapping. Computation in finite fields. BCH codes, Reed-Solomon codes, concatenation, BCH boud, error location polynomial and the PGZ decoder, fast decoders for BCH codes.
 
Week 1: Model of communication system. Models of errors. Codes. Encoding and decoding. Hamming distance. Minimum distance of codes. Maximum likelihood and minimum distance decoding. Error-correcting capability.
 
Week 2: Hamming bound on the minimum distance. Perfect codes. Linear codes. Generator matrix. Parity-check matrix. Finding the minimum distance from parity-check matrix.
Week 3: Standard array. Cosets. Syndrome decoding.
Week 4: Repetition codes. Parity-check codes. Hamming codes. Simplex codes. Reed-Muller codes. Golay codes. Operations on codes – shortening, lengthening, puncturing. Bounds on codes’ parameters (Plotkin bound, Singleton bound, Griesmer bound).
Week 5: Dual codes. Distance distributions. The Mac-Williams threorem. Computation of decoding and detection error probabilities.
Week 6: Cyclic codes. Generator polynomial. Check polynomial. Encoding using registers with feedback. Meggit’s decoder.
Week 7: Introduction to groups and finite fields. Implementation of operations in fields.
Week 8: Hamming codes in the cyclic form. Two-error correcting BCH codes.
Week 9: BCH and Reed-Solomon codes.
Week 10: Decoding BCH codes using Peterson-Gorenstein-Zierler algorithm.
Week 11: Decoding BCH codes using Berlekamp-Welch algorithm.
Week 12: Decoding Reed-Solomon codes.
Week 13: Product codes. Concatenated codes. Reed-Muller codes.
Week 14: Low-density parity check codes.
 

accessibility declaration


tel aviv university