Lattice-based computation of Boolean functions

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.

References

1. C. E. Shannon, "A Symbolic Analysis of Relay and Switching Circuits," Transactions of the AIEE, vol. 57, pp. 713--723, 1938.
2. M. L. Fredman and L. Khachiyan, "On the Complexity of Dualization of Monotone Disjunctive Normal Forms," Journal of Algorithms, vol. 21, no. 3, pp. 618--628, 1996.
3. T. Ibaraki and T. Kameda, "A Theory of Coteries: Mutual Exclusion in Distributed Systems," IEEE Transactions on Parallel and Distributed Systems, vol. 4, no. 7, pp. 779--794, 1993.
4. E. M. Sentovich et al., "SIS: A System for Sequential Circuit Synthesis," Tech. Rep., 1992.
5. M. Altun, M. Riedel, and C. Neuhauser, "Nanoscale Digital Computation through Percolation," in DAC'09, pp. 615--616.
6. T. Eiter, K. Makino, and G. Gottlob, "Computational Aspects of Monotone Dualization: A Brief Survey," Discrete Applied Mathematics, vol. 156, no. 11, pp. 1952--2005, 2008.

Index Terms

• Hardware

  • Emerging technologies