Cube-Based Synthesis of ESOPs for Large Functions  

作　　者：ZHANG Qiaowen WANG Pengjun HU Jiang ZHANG Huihong 

机构地区：[1]Institute of Circuits and Systems, Ningbo University [2]Ningbo Key Laboratory of Digital Signal Processing, Zhejiang Wanli University

出　　处：《Chinese Journal of Electronics》2018年第3期527-534,共8页电子学报（英文版）

基　　金：the Natural Science Foundation of Zhejiang Province(No.LY14F040002,No.16F010005);the National Natural Science Foundation of China(No.61474068,No.61234002);the Natural Science Foundation of Ningbo City(No.2013A610006,No.2013A610008);the K.C.Wong Magna Fund in Ningbo University

摘　　要：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.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.

关 键 词：Logic synthesis Exclusive-or sum-of-products（ESOP） Canonical forms Large functions 

分 类 号：TM13[电气工程—电工理论与新技术]