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.


Publié dans:
Proceedings of the 47th International Symposium on Multiple-Valued Logic (ISMVL), 272-276
Présenté à:
IEEE 47th International Symposium on Multiple-Valued Logic (ISMVL), Novi Sad, Serbia, 22-24 May 2017
Année
May 24 2017
Publisher:
IEEE
Mots-clefs:
Note:
ERC Cybercare 669354 / SNF MAJesty 200021-169084
Laboratoires:


Note: Le statut de ce fichier est: Seulement EPFL


 Notice créée le 2018-01-09, modifiée le 2019-08-12

n/a:
Télécharger le document
PDF

Évaluer ce document:

Rate this document:
1
2
3
 
(Pas encore évalué)