2005 Viterbi Lecture

Jacob Ziv

WHAT IS HIDDEN IN AN INDIVIDUAL SEQUENCE ?

UNIVERSAL DATA-COMPRESSION REVISITED

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.
Jacob Ziv – A brief 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.
Honors
  • Herman Gross Professor of Communications
  • Technion Distinguished Professor, 1982.
  • Fellow, IEEE
  • Member of the Israel Academy of Sciences, 1982;
  • Foreign Associate Member of the US National Academy of Engineering, 1988.
  • The IEEE Information Theory Society held the IEEE International Workshop on Information Theory in Haifa on the occasion of Jacob Ziv’s 65th birthday,
  • Foreign member of the American Academy of Arts and Science, 1998 Member of the American Philosophical Society, (2003)
  • Foreign member of the American Philosophical Society, 2003
  • Member of the European Academy of Sciences and Arts 2004
  • Foreign Associate Member of the US National Academy of Science 2004
Awards
  1. “The Rate Distortion Function for Source Coding, with Side-Information at the Detector” – see paper No. 33. Received the IEEE Information Theory Group Best Paper Award for the year 1976.
  2. “A Universal Algorithm for Sequential Data-Compression” – see paper No. 36. Received the IEEE Information Theory Group Best Paper Award for the year 1977.
  3. Israel Prize in Exact Sciences (Engineering and Technology) 1993.
  4. Marconi International Award 1995
  5. IEEE Richard W. Hamming Medal 1995.
  6. IEEE Information Theory Society Shannon Award for 1997.
  7. ACM 1997 Paris Kanellakis Theory and Practice Award.
  8. 1998 Eduard Rhein Prize for Basic Research
  9. 2002 Rothschild Prize for Technological Sciences

Published on June 26th, 2017

Last updated on April 7th, 2021