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
Solicitation Year: N/A
Solicitation Topic Code: N/A
Solicitation Number: N/A
Small Business Information
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
Business Contact
 Ray Teitelbaum
Title: Chairman
Phone: (607) 273-7340
Email: tt@grammatech.com
Research Institution
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

SBA logo
Department of Agriculture logo
Department of Commerce logo
Department of Defense logo
Department of Education logo
Department of Energy logo
Department of Health and Human Services logo
Department of Homeland Security logo
Department of Transportation logo
Environmental Protection Agency logo
National Aeronautics and Space Administration logo
National Science Foundation logo
US Flag An Official Website of the United States Government