Classifying Functions with Exact Synthesis

Due to recent advances, constraint solvers have become efficient tools for synthesizing optimum Boolean circuits. We take advantage of this by showing how SAT based exact synthesis may be used as a method for finding minimum length Boolean chains. As opposed to other exact synthesis methods, ours may be easily parallelized, which we use to obtain a speedup of approximately 48 times. By combining our method with NPN canonization, we find for the first time the minimum length chains for all 4- and 5-input functions in terms of 3-input Boolean operators. Finally, we propose a hardware acceleration method for NPN canonization. It can be used to speed up NPN canonization in existing algorithms, and we believe it will allow us to find all 6-input NPN classes as well.


Published in:
Proceedings of the 47th International Symposium on Multiple-Valued Logic (ISMVL), 272-276
Presented at:
IEEE 47th International Symposium on Multiple-Valued Logic (ISMVL), Novi Sad, Serbia, 22-24 May 2017
Year:
2017
Publisher:
IEEE
Keywords:
Laboratories:


Note: The status of this file is: EPFL only


 Record created 2018-01-09, last modified 2018-03-17

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)