EDOA: an efficient delay optimization approach for mixed-polarity Reed-Muller logic circuits under the unit delay model  

作　　者：Zhenxue HE Limin XIAO Fei GU Li RUAN Zhisheng HUO Mingzhe LI Mingfa ZHU Longbing ZHANG Rui LIU Xiang WANG 

机构地区：[1]College of Information Science and Technology, Hebei Agricultural University, Baoding 071001, China [2]State Key Laboratory of Software Development Environment, Beihang University, Beijing 100083, China [3]School of Computer Science and Engineering, Beihang University, Beijing 100083, China [4]School of Electronic and Information Engineering, Beihang University, Beijing 100083, China [5]State Key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China [6]National Engineering Research Center for Science & Technology Resources Sharing Service, Beijing 100083, China

出　　处：《Frontiers of Computer Science》2019年第5期1102-1115,共14页中国计算机科学前沿（英文版）

基　　金：This work was supported by the National Natural Science Foundation of China (Grant Nos. 61370059 and 61232009);Beijing Natural Science Foundation (4152030), Fundamental Research Funds for the Central Universities (YWF-15-GJSYS-085, YWF-14-JSJXY-14);Open Project Program of National Engineering Research Center for Science & Technology Resources Sharing Service (Beihang University), the fund of the State Key Laboratory of Computer Architecture (CARCH201507);the fund of the State Key Laboratory of Software Development Environment (SKLSDE-2016ZX-13).

摘　　要：Delay optimization has recently attracted signif-icant attention. However, few studies have focused on the delay optimization of mixed-polarity Reed-Muller (MPRM) logic circuits. In this paper, we propose an efficient delay op-timization approach (EDOA) for MPRM logic circuits under the unit delay model, which can derive an optimal MPRM logic circuit with minimum delay. First, the simplest MPRM expression with the fewest number of product terms is ob-tained using a novel Reed-Muller expression simplification approach (RMESA) considering don't-care terms. Second, a minimum delay decomposition approach based on a Huffman tree construction algorithm is utilized on the simplest MPRM expression. Experimental results on MCNC benchmark cir-cuits demonstrate that compared to the Berkeley SIS 1.2 and ABC, the EDOA can significantly reduce delay for most cir-cuits. Furthermore, for a few circuits, while reducing delay, the EDOA incurs an area penalty.

关 键 词：DELAY optimization mixed-polarity Reed-Muller LOGIC circuits UNIT DELAY model don't-care terms 

分 类 号：TP[自动化与计算机技术]