Browse Prior Art Database

Logic Simplification

IP.com Disclosure Number: IPCOM000045737D
Original Publication Date: 1983-Apr-01
Included in the Prior Art Database: 2005-Feb-07
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Roth, JP: AUTHOR

Abstract

In several steps in the process of the design of logic - notably optimization, timing verification, redesign - it is desired to simplify the logic, whether in terms of circuit count (optimization) or reducing the number of levels (timing verification). Procedures have been given (3) for most of the algorithms required; here, a final simple method called dynamic partitioning is added which renders the overall process computationally feasible for automatic simplification. The starting point here is an already existing logic design, not a high-level definition, although the latter could easily be transformed thereinto by means of a hardware compiler, such as RTRAN (3, p. 98).

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

Logic Simplification

In several steps in the process of the design of logic - notably optimization, timing verification, redesign - it is desired to simplify the logic, whether in terms of circuit count (optimization) or reducing the number of levels (timing verification). Procedures have been given (3) for most of the algorithms required; here, a final simple method called dynamic partitioning is added which renders the overall process computationally feasible for automatic simplification. The starting point here is an already existing logic design, not a high-level definition, although the latter could easily be transformed thereinto by means of a hardware compiler, such as RTRAN (3, p. 98).

Logic simplification has a hoary tradition (3), going back at least to Boole and continuing to today: (1) In timing verification one is given a completed logic design, in some technology, and it is desired to ascertain all chains (paths) whose delays are excessive as compared with the delays as associated by the clocks (synchronous machine assumed) ; after finding the longest critical chains, the design is returned to the originator(s) who redesign the logic so that it is faster, i.e., in general has fewer levels. (2) In redesign for optimization, one is given a design and wishes to reduce its cost or circuit-count or the number of chips on which it will fit. (3) In production of a design from some high-level description, like PL/R (3, p. 96) it is sometimes desired to reduce the low-level realization as in (2). (4) This would also reduce the cost of testing since the number of failures would in general be reduced; optimization would also tend to enhance reliability by reducing circuit count.

The simplification method. Assume that one is given a regular logic design (3, p. 88). The steps are as follows: (1) The first step is PT (pronounced pi-star) , to transform the function of each primary output and (output) register to a 2- level representation of its primary inputs and (input) registers, or in terms, as outlined below, of other internal variables selected to improve the effectiveness of the process.

One of the shortcomings, as described in (3, pp. 82f), with PT was that the 2- level representations programmed logic arrays (PLAs) it Produced, equivalent to the original design, may be very excessively large; this is controlled in this algorithm in step (2). As an indication of the reduc...