EEL 6550 Error Control Coding

Dr. John M. Shea

• Announcements
  • Suggested topics for the individual presentations have been posted.
  • Please read the Syllabus.
  • Office hours will be: 3 PM -- 4 PM on Mondays and 4 PM -- 5 PM on Wednesdays, or by appointment. If you want an appointment, please check my schedule and send me an email with a proposed appointment time that does not conflict with my busy times.
• Lecture Notes
• Lecture 7
  • Groups and Rings
• Lecture 8
  • Fields and Vector Spaces
• Lecture 9
  • Vector Spaces, Dual Spaces, Matrix Operations
• Lecture 14, February 8
  • ML Decoding with Standard Array, Error-Correcting Capability of Binary Linear Block Codes
• Lecture 33, April 7
  • Trellis diagram from Viterbi example
• Assignments
  • Homework Project 1 is due by Friday, March 7. Note that you do not have to use PARI for homeworks 4 and 5.
• Handouts, etc.
  • Syllabus
  • Intro to conditional probability and application to communication systems
  • PARI/GP is available for most platforms from the Main PARI/GP web site. Please download an appropriate version if you are not on the DSP subgroup. On the DSP subgroup, the Solaris version of PARI/GP can be executed from /home/users/jshea/bin/gp
  • Very Brief intro to Galois Fields in MATLAB
• Literature
  Here is some relevant literature on error-control coding. Some represent important topics that are covered (at least in part) in class. Others represent recent contributions.
  • A good survey on error-control coding is given in "Applications of Error Control Coding," by D. J. Costello, Jr., et al., in Information Theory: 50 Years of Discovery, edited by S. Verdu and S. McLaughlin.
  • The BCJR decoding algorithm that we will discuss in class is from L. R. Bahl, J. Cocke, F. Jelinek, and J. Raviv, "Optimal decoding of linear codes for minimizing symbol error rates," IEEE Trans. Inform. Theory, vol. IT-20, pp. 284-287, Mar. 1974.
  • An alternative (subopimtal but somewhat lower complexity) approach to soft-decision decoding of convolutional codes is given by the soft-output Viterbi algorithm: J. Hagenauer and P. Hoeher, "A Viterbi algorithm with soft outputs and its applications," in Proc. 1989 IEEE Global Communications Conf. (Dalla,s, TX, Nov., 1989), pp. 47.1.1-47.1.7.
  • Another suboptimal approach to soft-decision decoding is to use the max-log-MAP approximation in the BCJR decoding algorithm: P. Robertson, E. Villebrun, and P. Hoeher, "A comparison of optimal and sub-optimal MAP decoding algorithms operating in the log domain", in Proc. 1996 IEEE Int. Conf. on Communications (Seattle, WA), June 1995, vol. 2, pp. 1009-1013.
  • In fact, it has been shown that the SOVA and max-log-MAP/BCJR are equivalent: M. P. C. Fossorier, F. Burkert, S. Lin, and J. Hagenauer, "On the equivalence between SOVA and max-log-MAP decodings," IEEE Communications Letters, vol. 2, pp. 137-139, May 1998.
  • This paper gives a good overview of soft-decision decoding of block and convolutional codes: J. Hagenauer, E. Offer, and L. Papke, "Iterative decoding of binary block and convolutional codes," IEEE Trans. Inform. Theory, vol.~42, pp.~429--445, Mar. 1996.
  • Two of the best introductions to turbo codes are by William Ryan in an unpublished manuscript entitled A Turbo Code Tutorial and in a chapter of the Wiley Encyclopedia of Telecommunications entitled Concatenated Convolutional Codes and Iterative Decoding.
  • Sklar also published an introduction to turbo concepts in B. Sklar, "A primer on turbo code concepts", IEEE Communications Magazine, vol. 35, pp. 94-102, Dec. 1997.
  • Parallel concatenated turbo codes were developed by Berrou, Glavieux, and Thitimajshima in "Near Shannon limit error-correcting coding and decoding: turbo codes (1)", in Proc. 1993 IEEE Int. Conf. on Communications, vol. 2, pp. 23-26, May 1993.
  • Some of the first works to well explain the performance of turbo codes are S. Benedetto and G. Montorsi, "Unveiling turbo codes: Some results on parallel concatenated coding schemes," IEEE Trans. Inform. Theory, vol. 42, pp. 409-428, Mar. 1996
  and L. C. Perez, J. Seghers, and D. J. Costello, Jr., "A distance spectrum interpretation of turbo codes," IEEE Trans. Inform. Theory, vol. 42, pp. 1698--1709, Nov. 1996.
  • An alternative type of turbo code based on serial concatenation is proposed in S. Benedetto, D. Divsalar, G. Montorsi, and F. Pollara, "Serial concatenation of interleaved codes: Performance analysis, design, and iterative decoding," IEEE Trans. Inform. Theory, vol. 44, pp. 909-926, May 1998.
  • Finding weight spectrum needed to estimate the error floors for turbo codes can be simplified using the approach in O. Takeshita, M. P. C. Fossorier, and D. J. Costello, Jr., "A new technique for computing the weight spectrum of turbo-codes," IEEE Communications Letters, vol. 3, pp. 251-253, Aug. 1999.
  • Here is the paper I used as reference when creating the notes for the transition matrix approach to finding the weight spectrum of convolutional codes: J. K. Wolf and A. J. Viterbi, "On the weight distribution of linear block codes formed from convolutional codes," IEEE Trans. Commun., vol. 44, pp. 1049-1051, Sept. 1996.
  • J. Hagenauer, "Rate-compatible punctured convolutional codes and their applications," IEEE Trans. Commun., vol. 36, pp. 389-400, Apr. 1988.
  • When block codes do not have a nice structure that permits the application of low-complexity replication decoding or other graph-based soft-decision decoding, Chase decoding represents an alternative: D. Chase, "A class of algorithms for decoding block codes with channel measurement information", IEEE Trans. Inform. Theory, vol. IT-18, pp. 170--182, Jan. 1972.
  • Here is an Introduction to Hidden Markov Models that may be helpful. In particular, it talks about the Baum-Welch algorithm, which is a generalized form of the BCJR algorithm.
• Other Useful Links
• Viterbi Decoder JAVA Applet