2005 Viterbi Lecture

Ming Hsieh Department of Electrical Engineering

Title
“What is Hidden in an Individual Sequence? Universal Data-Compression Revisited”

Jacob Ziv
Distinguished Professor Emeritus
Technion – Israel Institute of Technology

Abstract

We consider the case where consecutive blocks of N letters of a semi-infinite, finite-alphabet individual sequence X are being compressed into binary sequences by some one-to-one mapping.

No a-priori information about X is available at the encoder, which must therefore adopt a universal data-compression algorithm.

It is known that if the universal LZ77 data compression algorithm is successively applied to N-blocks, then the best error-free compression, H(X), for the particular individual sequence X is achieved as N tends to infinity.

We discuss the best possible compression H(X,N) that may be achieved by ANY universal data compression algorithm for finite N-blocks, and demonstrate that context tree coding essentially achieves the optimal H(X,N).

Possible extentions to cases were some distortion is allowed and were side-information is available at the decoder are introduced.

Biography

Jacob Ziv was born in Tiberias, Israel, on November 27, 1931. He received the B.Sc., Dip. Eng., and M.Sc. degrees, all in Electrical Engineering, from the Technion—Israel Institute of Technology, Haifa, Israel, in 1954, 1955 and 1957, respectively, and the Sc.D. degree from the Massachusetts Institute of Technology, Cambridge, U.S.A., in 1962.

From 1955 to 1959, he was a Senior Research Engineer at the Scientific Department, Israel Ministry of Defense, where he engaged in research and development of communication systems. From 1961 to 1962, while studying for his doctorate at M.I.T., he joined the Applied Science Division of Melpar, Inc., Watertown, MA, where he was a Senior Research Engineer doing research in communication theory. In 1962 he returned to the Scientific Department, Israel Ministry of Defense, as Head of the Communications Division and also served as an Adjunct of the Faculty of Electrical Engineering, Technion—Israel Institute of Technology. From 1968 to 1970 he was a Member of the Technical Staff of Bell Laboratories, Inc., Murray Hill, NJ. He joined the Technion full time in 1970 where he is now the is Herman Gross Professor of Electrical Engineering and a Technion Distinguished Professor.

He was Dean of the Faculty of Electrical Engineering from 1974 to 1976 and Vice President for Academic Affairs from 1978 to 1982.

From 1977 to 1978, 1983 to 1984, and 1991 to 1992 he was on Sabbatical leave at the Information Research Department, Bell Laboratories, Murray Hill, NJ, USA. He was the Chairman of the Israeli Universities Planning and Grants Committee from 1985 to 1991. (The Planning and Grant Committee is the interphase between The Government of Israel and the Universities; it prepares the budget, presents it to the government and allocates it to the Universities; it is in charge of development and means and practices in the Universities.)

He is a Member of the Israel National Academy of Sciences and Humanities and has served as its President from 1996 till 2005.

His research interests include data-compression, information theory and statistical communication.