Algorithms for Computing the Maximum Number of Prime Implicants of Symmetric Boolean Functions

Yoshihide IGARASHI  

IEICE TRANSACTIONS (1976-1990)   Vol.E63   No.10   pp.693-699
Publication Date: 1980/10/25
Online ISSN: 
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Computers

Full Text: PDF>>
Buy this Article

A fast algorithm for computing the maximum number of prime implicants of n-variable symmetric Boolean function is described. A dynamic programming technique is used in the algorithm. The total logarithmic computing time cost and the total uniform computing time cost by a random access machine are O (n4) and O (n3), respectively. The algorithm can be implemented faster by a parallel computer. The corresponding computing time costs by a parallel computer with O (n) processors are O (n3) and O (n2), respectively.