Colloquium Speaker

Speaker:John Kieffer
Department of Electrical & Computer Engineering
University of Minnesota Twin Cities Campus
Topic:Data Compression Using Binary Decision Diagrams
Date:Thursday, November 4, 1999
Time:9:30 AM
Place:Gould-Simpson, Room 701

Refreshments will be served in the 7th-floor lobby of Gould-Simpson at 9 :15 AM


Reduced ordered binary decision diagrams (ROBDD's) are used to represent Boolean functions and have applications in computer-aided design, circuit verification, and coding theory. In this expository talk, a novel application of ROBDD's to data compression is presented. One can think of the entries of a binary sequence of length 2^k as the values of a Boolean function of k variables, which one then represents as a ROBDD. (This representation is unique and there are public domain software packages on the Web for computing it.) The given binary sequence is then losslessly compressed by a coding of this ROBDD representation. The technique is illustrated by example. The talk concludes with a discussion of the redundancy of the ROBDD-based compression algorithm. (This work was done jointly with Philippe Flajolet and En-hui Yang.)