Computer Engineering Cider Seminars

Using EXOR gates in logic synthesis reduces the hardware costs in many cases. Additionally EXOR based circuits often have nice testability properties. In contrast to AND/OR minimization — that in the meantime is well understood — in AND/EXOR minimization several restricted classes are considered. These subclasses are of interest, since the minimization of general Exclusive Sum of Product Expressions (ESOPs) turned out to be computationally very hard, i.e. all programs presented so far have long run times and often fail to determine the optimal result.
As one alternative Pseudo Kronecker Expressions (PSDKROs) have been proposed, since they are an interesting compromise: the resulting 2-level forms are of moderate size, i.e. close to ESOPs, and additionally the minimization process can be handled within reasonable time bounds
But the size of PSDKROs depends on a chosen order in which the variables are considered. Especially for ordering problems Evolutionary Algorithms (EAs) have shown to give very good results and a large set of operators is available. In this talk an EA is presented for determining a good decomposition order for PSDKROs. Experimental results are given to demonstrate the efficiency of the approach.

Alexander Finder studied computer science at the University of Bremen, Germany, where he received his Diploma in 2009. Since then, he is with Rolf Drechsler in the Group for Computer Architecture at the University of Bremen pursuing the PhD. His research interests include debugging, formal methods and logic synthesis.