| 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 |
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.)