Browse Prior Art Database

Logic Reduction for a Hardware Simulator

IP.com Disclosure Number: IPCOM000036479D
Original Publication Date: 1989-Oct-01
Included in the Prior Art Database: 2005-Jan-29
Document File: 3 page(s) / 53K

Publishing Venue

IBM

Related People

Sweet, CP: AUTHOR

Abstract

This disclosure presents an algorithm that given an arbitrary AO (AND- OR) block will construct an equivalent logic network subject to the following constraints: 1) The network must consist of a minimal set of logic blocks. 2) Each logic block must have 4 inputs (unused inputs are connected to a constant 0 or constant 1). 3) Any boolean function is acceptable for a logic block.

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 53% of the total text.

Page 1 of 3

Logic Reduction for a Hardware Simulator

This disclosure presents an algorithm that given an arbitrary AO (AND- OR) block will construct an equivalent logic network subject to the following constraints: 1) The network must consist of a minimal set of logic blocks. 2) Each logic block must have 4 inputs (unused inputs are connected to a constant 0 or constant 1). 3) Any boolean function is acceptable for a logic block.

Although this disclosure describes an alternative representation for AO logic blocks, the procedure is also applicable to OA, AOI and OAI blocks.

Before proceeding with the algorithm, let us make an observation. If any of the AND groups in the AO block have 4 or more inputs, they can be replaced with a cascade of 4-input AND gates. For example, if a group has 5 inputs, the first 4 can be fed to an AND gate and the output of the AND gate fed to the group in the AO block. Note that this group now has 2 inputs, the output of the AND gate and the original fifth input. This simplifies the algorithm because after this replacement the maximum number of inputs to an AO group is 3.

Next, we dispense with some trivial cases before presenting the general algorithm. 1) If all groups have 1 input, the AO block is equivalent to a chain of (1 or more) 4-input OR blocks. 2) If there are exactly 3 groups and 1 group has 2 inputs (a and b) and the second group has 1 input (c) and the last group has 1 input (d), then the AO block is equivalent to a 4 input block with function F = c d (a&b). 3) If there are exactly 2 groups and the first group has 1 input (a) and the other group has 3 inputs (b, c and d), then the AO block is equivalent to a 4-input block with function G = a (b&c&d). 4) If there are exactly 2 groups each of which has 2 inputs, the block is already in minimal form.

The algorithm to construct minimal logic for a general AO block is now described. 1) Add cascades of AND gates (as required) to limit the number of inputs to an AO group to a maximum of three. 2) If none of the AO groups has two...