A New Technique for Efficient Compression of Information

Award Information
Agency: Department of Defense
Branch: Missile Defense Agency
Contract: DASG60-01-P-0048
Agency Tracking Number: 01-0155
Amount: $64,929.00
Phase: Phase I
Program: SBIR
Awards Year: 2001
Solitcitation Year: N/A
Solitcitation Topic Code: N/A
Solitcitation Number: N/A
Small Business Information
GRAMMATECH, INC.
317 N. Aurora Street, Ithaca, NY, 14850
Duns: 603978321
Hubzone Owned: N
Woman Owned: N
Socially and Economically Disadvantaged: N
Principal Investigator
 Paul Anderson
 Senior Software Engineer
 (607) 273-7340
 paul@grammatech.com
Business Contact
 Ray Teitelbaum
Title: Chairman
Phone: (607) 273-7340
Email: tt@grammatech.com
Research Institution
N/A
Abstract
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.

* information listed above is at the time of submission.

Agency Micro-sites

US Flag An Official Website of the United States Government