access icon free Cube-Based Synthesis of ESOPs for Large Functions

This study focuses on low-complexity synthesis of Exclusive-or sum-of-products expansions (ESOPs). A scalable cube-based method, which only uses iterative executions of cube intersection and subcover minimization for cube set expressions, is presented to obtain quasi-optimal ESOPs for completely specified multi-output functions. For deriving canonical Reed-Muller (RM) forms, four conversion rules of cubes are proposed to achieve fast conversion between a canonical form and an Exclusiveor sum-of-products (ESOP) or between different canonical forms. Numerical examples are given to verify the correctness of cube-based minimization and conversion methods. The proposed methods have been implemented in C language and tested on a large set of MCNC benchmark functions (ranging from 5 to 201 inputs). Experimental results show that, compared with existing methods, ours can reduce the number of cubes by 27% and save the CPU time by 74% on average in the final solution of minimization, and consume less time as well during the conversion process. As a whole, our methods are efficient in terms of both memory space and CPU time and can be able to deal with very large functions.

Inspec keywords: minimisation; computational complexity; Boolean functions; C language

Other keywords: canonical Reed-Muller forms; conversion process; C language; multioutput functions; conversion rules; quasioptimal ESOPs; conversion methods; low-complexity synthesis; cube-based synthesis; CPU time; canonical form; cube intersection; MCNC benchmark functions; cube set expressions; exclusive-or sum-of-products expansions; subcover minimization

Subjects: Combinatorial mathematics; Optimisation techniques; Computational complexity; Algebra; High level languages

http://iet.metastore.ingenta.com/content/journals/10.1049/cje.2018.01.006
Loading

Related content

content/journals/10.1049/cje.2018.01.006
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading