Accession Number : ADA243740

Title :   Global Optimization of Digital Circuits.

Descriptive Note : Master's thesis,

Corporate Author : AIR FORCE INST OF TECH WRIGHT-PATTERSON AFB OH SCHOOL OF ENGINEERING

Personal Author(s) : Flandera, Richard

Report Date : DEC 1991

Pagination or Media Count : 296

Abstract : This thesis was divided into two tasks. The first task involved developing a parser which could translate a behavioral specification in Very High-Speed Integrated Circuits (VHSIC) Hardware Description Language (VHDL) into the format used by an existing digital circuit optimization tool, BOolean Reasoning In Scheme (BORIS). Since this toll is written in Scheme, a dialect of Lisp, the parser was also written in Scheme. The parser was implemented is Artez's modification of Earley's Algorithm. Additionally, a VHDL tokenizer was implemented in Scheme and a portion of the VHDL grammar was converted into the format which the parser uses. The second task was the incorporation of intermediate functions into BORIS. The existing BORIS contains a recursive optimization system that optimizes digital circuits by using circuit outputs as inputs into other circuits. Intermediate functions provide a greater selection of functions to be used as circuits inputs. Using both intermediate functions and output functions, the costs of the circuits in the test set were reduced by 43%. This is a 10% reduction when compared to the existing recursive optimization system. Incorporating intermediate functions into BORIS required the development of an intermediate-function generator and a set of control methods to keep the computation time from increasing exponentially.

Descriptors :   ALGORITHMS, BEHAVIOR, BOOLEAN ALGEBRA, CIRCUITS, COMPUTATIONS, CONTROL, COSTS, DIGITAL SYSTEMS, FUNCTIONS, HIGH RATE, INTEGRATED CIRCUITS, LANGUAGE, OPTIMIZATION, OUTPUT, PARSERS, REASONING, RECURSIVE FUNCTIONS, SPECIFICATIONS, TEST SETS, THESES, TIME, TOOLS.

Subject Categories : Electrical and Electronic Equipment
      Electricity and Magnetism
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE