On the Complexity of Mod-2 Sum PLA’s

Tsutomu Sasao, Philipp Besslich

Research output: Contribution to journalArticle

121 Citations (Scopus)

Abstract

We consider the realization of logic functions by using PLA’s with an Exclusive-OR (Exor) array, where a function is represented by mod-2 (EXOR) sum-of-products (ESOP’s), and both true and complemented variables are used. First, we propose a new PLA structure using an EXOR array. Second, we derive upper bounds on the number of products of this type of PLA, which are useful for estimating the size of a PLA as well as for assessing the minimality of the solutions obtained by heuristic ESOP minimization algorithms. Computer simulation using randomly generated functions shows that PLA’s with EXORarray require, on the average, fewer products than conventional PLA’s. For symmetric functions, we conjecture that the PLA’s with an EXORarray require at most as many products as the conventional PLA’s. The proposed PLA’s can be made easily testable by adding a small amount of hardware.

Original languageEnglish
Pages (from-to)262-266
Number of pages5
JournalIEEE Transactions on Computers
Volume39
Issue number2
DOIs
Publication statusPublished - 1 Jan 1990

Keywords

  • Complexity
  • Exclusive-OR sumof-products
  • easily testable circuits
  • functions
  • logic minimization
  • programmable logic array
  • symmetric

Fingerprint Dive into the research topics of 'On the Complexity of Mod-2 Sum PLA’s'. Together they form a unique fingerprint.

  • Cite this