TUTORIALS

Tutorial 3: The rise, fall and rise again of sequential decoding algorithms

Sequential decoding was invented by Wozencraft in 1957 as an efficient technique to decode convolutional codes. In the following years, subsequent research brought more refined algorithms (such as the Stack and Fano algorithms) and importantly proved that sequential decoding, with the proper choice of parameters, can be used to achieve error free communication over discrete memoryless channels with bounded average complexity as long as the data rates remain below the cutoff rate of the channel considered (R0 or RCOMP ). However, in 1993, Turbo Codes proved that rates R0 < R < C can be achieved through interleaver gains and iterative decoding, which presented a setback for sequential decoding algorithms. Recent applications, such as maximum likelihood detection and decoding in multiple-input multiple-output (MIMO) and intersymbol interference (ISI) channels, revived the interest in sequential decoding algorithms.
Sequential decoding offers an alternative and, sometimes, complementary method to iterative decoding over such channels, which gives different performance/complexity tradeoffs.
In this tutorial, we survey the different sequential decoding algorithms and their applications in the last 50 years. We detail the functionality of these algorithms through a unified framework and we highlight the difference between several sequential decoding algorithms. This framework also connects sequential decoding to other closest lattice point search (CLPS) algorithms, such as sphere decoding and branch and bound algorithms, allowing, thus, cross-fertilization between those research areas. We examine the role of preprocessing and show the importance of minimum mean square error decision feedback equalization (MMSE-DFE) frontend filtering. We also discuss results on average and maximum complexity analysis of sequential decoding algorithms in various scenarios. We conclude by presenting some analytical and numerical results of recent applications of sequential decoding in various AWGN, MIMO and ISI channels and give an outlook on future research and applications of sequential decoding.

Presenter: Mohamed Oussama Damen, University of Waterloo

Mohamed Oussama Damen (S’97-M’00-SM’04) received a B.Sc. degree in mathematics from the University of Paris VII in 1995, an M.Sc. degree in digital communications systems from the Ecole Nationale Superieure des Telecommunications (ENST) de Paris, France, in 1996 and a Ph.D. degree in electronics and communications from the ENST, Paris, France, in October 1999. He has done post-doctoral research at the ENST, Paris, France, from November 1999 to August 2000, and at the Electrical and Computer Engineering department of the University of Minnesota from September 2000 to March 2001. From March 2001 to June 2004, he worked the Electrical and Computer Engineering department of the University of Alberta, where he is now working as a senior research associate of Alberta Informatics Circle of Research Excellence (ICORE). In June 2004, he joined the Electrical and Computer Engineering department at the University of Waterloo, Ontario, where he is now working as an Assistant Professor and holds the NSERC/NORTEL Associate Research Chair in Advanced Telecommunications.
He is a co-author of more than 60 papers in international journals and conferences, and two US patent applications. His current research interests are in the areas of communication theory, coding theory, and information theory, with a special emphasis on coding for multiple-input multiple-output (MIMO) channels, cooperative diversity and sub-optimal detection and decoding.

back