Combinational Circuit Synthesis with Time and Component Bounds

Author

Chen, Shyh-Ching ; Kuck, David J

Author_Institution

Burroughs Corporation, Great Valley Laboratory

Issue

8

fYear

1977

Firstpage

712

Lastpage

726

Abstract

New results are given concerning the design of combinational logic circuits. We give time and component bounds for combinational circuits specified in several ways. For any sequential machine defined by linear recurrence relations, we discuss an algorithm for the synthesis of equivalent combinational logic. The procedure includes upper bounds on the time and components involved. We also discuss the transformation of nonlinear recurrences into combinational circuits. Examples are given using gates as well as IC´s as components. These include binary addition, multiplication, and ones´ position counting. The time and component bounds our procedure yields compare favorably with traditional results.

Keywords

Binary addition, binary multiplication, circuit synthesis, combinational circuits, component bounds, sequential circuits, time bounds.; Adders; Algorithm design and analysis; Circuit synthesis; Combinational circuits; Integrated circuit packaging; Integrated circuit synthesis; Laboratories; Logic design; Sequential circuits; Upper bound; Binary addition, binary multiplication, circuit synthesis, combinational circuits, component bounds, sequential circuits, time bounds.;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/TC.1977.1674909

Filename

1674909