Logic Minimization and Testability of 2-SPP Networks
- 17 June 2008
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 27 (7) , 1190-1202
Abstract
The 2-SPP networks are three-level EXOR-AND-OR forms, with EXOR gates being restricted to fan-in 2. This paper presents a heuristic algorithm for the synthesis of these networks in a form that is fully testable in the stuck-at fault model (SAFM). The algorithm extends the EXPAND-IRREDUNDANT-REDUCE paradigm of ESPRESSO in heuristic mode, and it iterates local minimization and reshape of a solution until no further improvement can be achieved. This heuristic could escape from local minima using a LAST_GASP-like procedure. Moreover, the testability of 2-SPP networks under the SAFM is studied, and the notion of EXOR-irredundancy is introduced to prove that the computed 2-SPP networks are fully testable under the SAFM. Finally, this paper reports a large set of experiments showing high-quality results with affordable run times, handling also examples whose exact solutions could not be computed.Keywords
This publication has 21 references indexed in Scilit:
- Efficient Minimization of Fully Testable 2-SPP Networks2006
- Synthesis of spp three-level logic networks using affine spacesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2003
- A fast algorithm for or-and-or synthesisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2003
- Multiple-valued minimization to optimize PLAs with output EXOR gates2003
- A heuristic algorithm to design AND-OR-EXOR three-level networks2002
- On a new Boolean function with applicationsIEEE Transactions on Computers, 1999
- EXMIN2: a simplification algorithm for exclusive-OR-sum-of-products expressions for multiple-valued-input two-valued-output functionsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1993
- Zero-suppressed BDDs for set manipulation in combinatorial problems1993
- Design automation tools for efficient implementation of logic functions by decompositionIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1989
- Multiple-Valued Minimization for PLA OptimizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987