Universal Source Coding
This part of the course will introduce the student to Source Coding, a sub-area of Information Theory, and particularly to universal data compression, which greatly benefits from techniques of analysis of algorithms.
1) Source coding fundamentals
a. Information sources
b. Modeling and coding
c. Source codes
and coding theorem
2) Basic coding techniques
a. Huffman codes
b. Ideal code length and arithmetic coding
3) Universal coding
a. Universal modeling and coding, model classes
b. Redundancy in various settings
c. Lower bounds on redundancy
primitive universal codes
4) The Lempel-Ziv algorithm
a. Description of LZ'77 and LZ'78
b. Universality of LZ’78
l T. M. Cover and J. A. Thomas, Elements of Information Theory. NY: John Wiley & Sons, Inc., 1991.
l L. D. Davisson, “Universal noiseless coding,” IEEE Trans. Inform. Theory, vol. IT-19, pp. 783–795, Nov. 1973.
l J. Rissanen and G. G. Langdon, Jr., “Universal modeling and coding,” IEEE Trans. Inform. Theory, vol. IT-27, pp. 12–23, Jan. 1981.
l A. Barron, J. Rissanen, B. Yu, “The minimum description length principle in coding and modeling,” IEEE Trans. Inform. Theory, vol. IT-44, pp. 2743–2760, Oct. 1998.
l N. Merhav and M. Feder, “Universal prediction,” IEEE Trans. Inform. Theory, vol. IT-44, pp. 2124–2147, Oct. 1998.
l J. Ziv and A. Lempel, “A universal algorithm for sequential data compression,” IEEE Trans. Inform. Theory, vol. IT-23, pp. 337–343, May 1977.
l J. Ziv and A. Lempel, “Compression of individual sequences via variable rate coding,” IEEE Trans. Inform. Theory, vol. IT-24, pp. 530–536, Sept. 1978.