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
d. Entropy
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
d. Some
primitive universal codes
4)
The Lempel-Ziv
algorithm
a. Description
of LZ'77 and LZ'78
b. Universality of LZ’78
A link to an expanded version of this course will be available here and here .
Other references:
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.