Lossless Source Coding Algorithms

2013 ISIT Plenary Lecture
Lossless Source Coding Algorithms
Frans M.J. Willems
Eindhoven University of Technology



We focus on source coding algorithms for binary sources. First we discuss the i.i.d. case. We start with the well-known Huffman (fixed-to-variable length) and Tunstall (variable-to-fixed length) constructions. Then we consider enumerative variants of these methods. We conclude the first part by discussing universal (enumerative) methods for i.i.d. sources. In the second part of the lecture we first demonstrate how arithmetic coding follows from enumerative principles. Then we investigate lossless coding for tree sources. Using arithmetic coding we can handle these sources, also in the universal case (context-tree weighting). Finally we move to stationary ergodic sources. We show, using a result by Kac (1947), that a simple method based on coding repetition times achieves entropy. We conclude the lecture by discussing some extensions and open problems.


Frans M.J. Willems was born in Stein, The Netherlands, on June 26, 1954. He received the M.Sc. degree in electrical engineering from Eindhoven University of Technology, Eindhoven, The Netherlands, and the Ph.D. degree from the Catholic University of Louvain, Louvain, Belgium, in 1979 and 1982 respectively. From 1979 to 1982 he was a research assistant at the Catholic University of Louvain. Since 1982, he is a staff member at the Electrical Engineering Department of Eindhoven University of Technology. His research contributions are in the areas of multi-user information theory and noiseless source coding. Dr. Willems received the Marconi Young Scientist Award in 1982. From 1988 to 1990, he served as Associate Editor for Shannon Theory for the IEEE Transactions on Information Theory. He is co-recipient of the 1996 IEEE Information Theory Society Paper Award. From 1998 to 2000 he was a member of the Board of Governors of the IEEE Information Theory Society. Since 1999 he is connected to Philips Research Laboratories as an advisor. From 2001 to 2004 he served as an Associate Editor for Information Theory for the European Transactions on Telecommunications. Dr. Willems is a Fellow of the IEEE since 2005.