| Title | Lattice-Based Boolean Diagrams: Canonical, Order-Independent Graphical Representations of Boolean Functions |
| Author | Ahmed Nassar, *Fadi J. Kurdahi (University of California, Irvine, U.S.A.) |
| Page | pp. 468 - 473 |
| Keyword | Boolean functions, Graph representations, decision diagrams |
| Abstract | This paper presents lattice-based Boolean diagrams (LBBDs), a graphical representation of Boolean functions that is not derived from binary decision diagrams (BDDs), as well as symbolic manipulation algorithms. It also identifies a class of Boolean functions where LBBDs are demonstrably more efficient to construct, and reason with, when compared to BDDs. The case studies include ITC99 and MCNC benchmarks, randomly generated cube covers or sum-of-products (SOP) formulas as well as multi-level Boolean formulas. Finally, LBBDs proved to be instrumental to the efficient runtime verification of software over distributed multiprocessor systems. |
| Title | BDD Minimization for Approximate Computing |
| Author | *Mathias Soeken, Daniel Große, Arun Chandrasekharan, Rolf Drechsler (University of Bremen, Germany) |
| Page | pp. 474 - 479 |
| Keyword | BDDs, Approximate computing, Algorithms, Optimization |
| Abstract | We present Approximate BDD Minimization (ABM) as a problem that has application in approximate computing. Given a BDD representation of a multi-output Boolean function, ABM asks whether there exists another function that has a smaller BDD representation but meets a threshold with respect to an error metric. We present operators to derive approximated functions and present algorithms to exactly compute the error metrics directly on the BDD representation. An experimental evaluation demonstrates the applicability of the proposed approaches. |
| Title | MajorSat: A SAT Solver to Majority Logic |
| Author | Yu-Min Chou (National Tsing Hua University, Taiwan), Yung-Chih Chen (Yuan Ze University, Taiwan), Chun-Yao Wang, *Ching-Yi Huang (National Tsing Hua University, Taiwan) |
| Page | pp. 480 - 485 |
| Keyword | Satisfiability, Majority |
| Abstract | A majority function can be represented as sum-of-product (SOP) form or product-of-sum (POS) form. However, a Boolean expression including majority functions could be more compact compared to SOP or POS forms. Hence, majority logic provides a new viewpoint for manipulating the Boolean logic. Recently, majority logic attracts more attentions than before and some synthesis algorithms and axiomatic system for majority logic have been proposed. On the other hand, solvers for satisfiability (SAT) problem have a tremendous progress in the past decades. The format of instances for the SAT solvers is the Conjunctive Normal Form (CNF). For the instances that are not expressed as CNF, we have to transform them into CNF before running the SAT-solving process. However, for the instances including majority functions, this transformation might be not scalable and time-consuming due to the exponential growth in the number of clauses in the resultant CNF. As a result, this paper presents a new SAT solver—MajorSat, which is for solving a SAT instance containing majority functions without any transformation. Some techniques for speeding up the solver are also proposed. Besides, we also propose a transformation method that can generate the characteristic function of a majority logic gate. The experimental results show that the MajorSat solver can efficiently solve random instances containing majority functions that CNF SAT solvers, like MiniSat or Lingeling, cannot. |
| Title | Fast Synthesis of Threshold Logic Networks with Optimization |
| Author | *Yung-Chih Chen, Runyi Wang, Yan-Ping Chang (Yuan Ze University, Taiwan) |
| Page | pp. 486 - 491 |
| Keyword | Threshold logic, logic synthesis, logic optimization |
| Abstract | Threshold logic, a more compact Boolean representation compared to conventional logic gate representation, re-attracted substantial attention from researchers due to the advances of threshold logic implementations with novel nanoscale devices. For the compact representation to be promising, a fast and effective method for transforming a conventional Boolean logic network into a threshold logic network is necessary. This paper presents such a synthesis method for threshold logic based on logic optimization. First, a Boolean logic network is mapped into a threshold logic network by one-to-one mapping. Then, a method is used to optimize the threshold logic network based on eight transformations for reducing gate count. Unlike the previous methods, the proposed method does not require threshold function identification, and thus is much more efficient. The experimental results show that the proposed method is three orders of magnitude faster than a widely used synthesis method. Additionally, the proposed method has a better synthesis quality with an average saving of 28% threshold gates. |
| Title | Polysynchronous Stochastic Circuits |
| Author | *M. Hassan Najafi, David J. Lilja, Marc Riedel, Kia Bazargan (University of Minnesota, U.S.A.) |
| Page | pp. 492 - 498 |
| Keyword | Polysynchronous circuits, asynchronous circuits, multi-clock circuits, stochastic computing, clock distribution network |
| Abstract | Clock distribution networks (CDNs) are costly in high-performance ASICs. This paper proposes a new approach: splitting clock domains at a very fine level, down to the level of a handful of gates. Each domain is synchronized with an inexpensive clock signal, generated locally. This is possible by adopting the paradigm of stochastic computation, where signal values are encoded as random bit streams. The design method is illustrated with the synthesis of circuits for applications in signal and image processing. |