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.