Browse Prior Art Database

Automatic Conversion of Computer Logic to Make it Inverter Free

IP.com Disclosure Number: IPCOM000089830D
Original Publication Date: 1977-Dec-01
Included in the Prior Art Database: 2005-Mar-05
Document File: 5 page(s) / 60K

Publishing Venue

IBM

Related People

Russo, RL: AUTHOR [+2]

Abstract

This article presents a procedure for generating an inverter-free logic design from one containing inverters and for counting the extra circuits required.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 44% of the total text.

Page 1 of 5

Automatic Conversion of Computer Logic to Make it Inverter Free

This article presents a procedure for generating an inverter-free logic design from one containing inverters and for counting the extra circuits required.

The basic concept behind the valid removal of inverters is De Morgan's theorem: f = (AB + CD + .....)' = ((a'+B') (C'+D') ...). This theorem is illustrated in
Fig. 1.

Thus, assuming that complemented versions of the signals feeding the logic structure L are available somewhere in the design, f can be generated by another logic structure whose block count is equal to the count of the blocks in L. For ease of understanding, this transformation is shown for two levels of logic, rather than for the general case of n levels, but the theorem is extendable to the n-level case.

It is also assumed that complemented versions of signals are available at the output of storage elements and at primary inputs.

ANDs and ORs are used to explain the concept. The question is whether a block will be required in its original form (e.g., AND) only, its new form (e.g.. OR) only, or in both forms (e.g., AND and OR), in which case one additional block will be required. In this latter case the block in question is "duplicated".

The simple example of Fig. 2 shows one case where a block is to be duplicated. To remove the inverter, block 1 of Fig. 2 is duplicated, as shown in Fig. 3.

Using this example, the concept of retaining (in the inverter-free logic) the original signals is introduced, indicated by marking a net with an "0", and generating new signals required by marking nets with an "N". The Vertex Generating Program (VGP) is first run on the example (procedure described later) to obtain the vertex graph structure shown in Fig. 4, which illustrates the condition after the VGP has been executed. The new structure with inverter block 2 of Fig. 4 removed is shown in Fig. 5.

A procedure is now described for processing a logic graph to determine the inverter-free graph, and the blocks which must be duplicated. The procedure is explained with reference to Figs. 6 through 10.

A1. Run ALMS/360 VGP (1) (2) using primary inputs, primary outputs, storage elements and inverter blocks as initiates. Use mode 5 (redundant) in order to generate the cones of influence (shown as the symbol

(Image Omitted)

in the examples). The cone of influence of an initiate contains the blocks which control that initiate and lie "between" that initiate and other initiates.

1

Page 2 of 5

A2. Label all vertices initiated by inverters as I vertices. Label all vertices initiated by SE (storage elements) or non-inverter initiated PO (primary outputs) as NI vertices.

A3. Levelize the vertex graph by putting all the output nets of NI vertices at the left side of a left-to-right organized levelized structure. Put all I vertices fed only by left side nets in level 1. Put all I vertices fed by level 1 or by level 1 and left side nets in level 2, and so on. Each I vertex in the gra...