Browse Prior Art Database

THE SYNTHESIS OF THREE-LEVEL LOGIC NETWORKS

IP.com Disclosure Number: IPCOM000149494D
Original Publication Date: 1966-May-31
Included in the Prior Art Database: 2007-Apr-01
Document File: 40 page(s) / 2M

Publishing Venue

Software Patent Institute

Related People

Grasselli, Antonio: AUTHOR [+3]

Abstract

PRINCETON UNIVERSITY Department of Electrical Engineering

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

Page 1 of 40

PRINCETON UNIVERSITY

Department of Electrical Engineering

Digital Systems Laboratory Technical Report Number 49

(May 1966')

THE SYNTHESIS OF THREE-LEVEL

LOGIC NETWORKS

Antonio Grasselli and James F. Gimpel

    This work was supported i n part by the Bell Telephone Laboratories, Murray H i l l , New Jersey. One of the authors (Antonio Grasselli) was also supported by a Fullbright travel grant of the United States Department of State.

[This page contains 1 picture or other non-text object]

Page 2 of 40

THE SYNTHESIS OF THREE-LEVEL

LOGIC NETWORKS

Antonio Grasselli and James F. Gimpel

AB STRAC T

    
This paper describes an exact method for obtaining minimum-cost three-level networks composed of AND and OR gates and to the authors' knowledge this is the first time this has been done. A s one may expect, the amount of computation required to obtain an absolutely least-cost solution becomes unmanageably large for problems of prac- tical interest. The method presented, however, readily lends itself to heuristic simplifications; several simplify- ing modifications are suggested.

Introduction

      The optimal synthesis of logic networks using AND gates and OR gates (see Fig. 1) is a fundamental but, as yet, unsolved problem in logical design. Various departures from this basic problem are made
but by far the most common is to restrict the number of levels. If the number of levels is limited to two, the Quine-McCluskey algorithm is an effective synthesis procedure.* In this paper we w i l l extend the number of permitted levels to three and examine the consequences of trying to obtain a reasonable algorithm for finding minimum gate networks.

      The authors are unaware of any precise treatment of this problem
in the literature. Several papers have dealt with finding minimum-
literal three-level and multi-level expressions [3-81. In general, however, these expressions do not correspond to minimum-gate networks. A completely

*Familiarity with two-level minimization w i l l be assumed throughout.

[This page contains 1 picture or other non-text object]

Page 3 of 40

Figure 1.

The symbols for (a) an AND gate and (b) an OR gate

[This page contains 1 picture or other non-text object]

Page 4 of 40

different approach t o multi-level synthesis of logic networks was sup- plied by Akers [9]. H i s technique, however, was developed as a toal.to assist a human designer rather than as an exact or mechanical method.

Basic Concepts

       In this paper we w i l l consider only single-output loop-free networks composed of AND gates and OR gates. We assume that the output gate is an
OR gate; that this assumption represents no loss of generality can be seen from conventional duality arguments. We w i l l also assume that the inputs
to a network can appear i n both complemented and uncomplemented form
(i.
e . , double rail) .

       There are two commonly-used means for evaluatin...