A New Technique for Efficient Compression of Information

We propose the commercial development of a new data structure thatwill be a plug-compatible replacement for binary-decision diagrams(BDDs). BDDs have proven to be extremely useful across a wide rangeof software applications. For example, they are essential in manyhardware design automation tasks, including analysis, optimization andverification. They are also useful in applications such as datacompression, spectral analysis and signal processing, and many others.The improved data structure --- Context-Free Language Ordered binaryDecision Diagrams (CFLOBDDs) --- can lead to data structures that areexponentially smaller than BDDs. CFLOBDDs have the potential topermit hardware analysis and verification to be done much faster, andto allow much larger problems to be tackled than has previously beenpossible. The proposed product will be marketed as a softwarecomponent to producers of CAD software, where their use will allowtheir customers to develop higher-quality digital electroniccomponents at lower cost.The proposed software has applications in at least the following areas: digital circuit design, analysis and verification; spectral analysis and digital signal processing; data compression and transmission in compressed form; genetic-programming problems;and many other kinds of software applications.