PLADE: a two-stage PLA decomposition

Author

Ciesielski, Maciej J. ; Yang, Saeyang

Author_Institution

Dept. of Electr. & Comput. Eng., Massachusetts Univ., Amherst, MA, USA

Volume

11

Issue

8

fYear

1992

fDate

8/1/1992 12:00:00 AM

Firstpage

943

Lastpage

954

Abstract

An efficient method for PLA decomposition, in which a single two-level Boolean function (PLA) is decomposed into two stages of cascaded PLAs such that the total area of all PLAs is smaller than that of the original PLA, is presented. The first stage may contain an arbitrary number of PLAs (generalized decoders), and the second stage contains a single PLA. Primary inputs are partitioned into disjoint sets of input variables and represented as multiple-valued variables so as to minimize the total PLA area. Two efficient algorithms for assignment of input variables to individual decoders are presented, one based on an integer programming technique and the other on graph partitioning. The constrained input encoding of the second-stage PLA is performed by an efficient procedure based on graph coloring and partitioning theory

Keywords

Boolean functions; graph colouring; integer programming; logic CAD; logic arrays; PLADE; cascaded PLAs; constrained input encoding; generalized decoders; graph coloring; graph partitioning; integer programming; multiple-valued variables; programmable logic array; two-level Boolean function; two-stage PLA decomposition; Boolean functions; Circuits; Decoding; Encoding; Input variables; Minimization; Optimization methods; Partitioning algorithms; Programmable logic arrays; Routing;

fLanguage

English

Journal_Title

Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on

Publisher

ieee

ISSN

0278-0070

Type

jour

DOI

10.1109/43.149766

Filename

149766