DocumentCode :
523993
Title :
Lattice-based computation of boolean functions
Author :
Altun, Mustafa ; Riedel, Marc D.
Author_Institution :
Dept. of Electr. & Comput. Eng., Univ. of Minnesota, Minneapolis, MN, USA
fYear :
2010
fDate :
13-18 June 2010
Firstpage :
609
Lastpage :
612
Abstract :
This paper studies the implementation of Boolean functions with lattices of two-dimensional switches. Each switch is controlled by a Boolean literal. If the literal is 1, the switch is connected to its four neighbours; else it is not connected. Boolean functions are implemented in terms of connectivity across the lattice: a Boolean function evaluates to 1 iff there exists a top-to-bottom path. The paper addresses the following synthesis problem: how should we map literals to switches in a lattice in order to implement a given target Boolean function? We seek to minimize the number of switches. Also, we aim for an efficient algorithm - one that does not exhaustively enumerate paths. We exploit the concept of lattice and Boolean function duality. We demonstrate a synthesis method that produces lattices with a number of switches that grows linearly with the number of product terms in the function. Our algorithm runs in time that grows polynomially.
Keywords :
Boolean functions; computational complexity; Boolean functions; Boolean literal; efficient algorithm; lattice based computation; Boolean functions; Circuit synthesis; Cities and towns; Computational modeling; Lattices; Network synthesis; Permission; Polynomials; Switches; Switching circuits; Boolean Functions; Lattice Duality; Lattices; Switching Circuits;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Design Automation Conference (DAC), 2010 47th ACM/IEEE
Conference_Location :
Anaheim, CA
ISSN :
0738-100X
Print_ISBN :
978-1-4244-6677-1
Type :
conf
Filename :
5523551
Link To Document :
بازگشت