针对混合极性RM(Reed-Muller)电路逻辑综合中的极性转换和极性优化问题,提出了基于对偶逻辑的极性转换和极性优化方法.从理论上证明了所提出方法的正确性,并用实验验证了其有效性和可行性.所提出方法有助于将较成熟的MPRM(Mixed-Polarit...针对混合极性RM(Reed-Muller)电路逻辑综合中的极性转换和极性优化问题,提出了基于对偶逻辑的极性转换和极性优化方法.从理论上证明了所提出方法的正确性,并用实验验证了其有效性和可行性.所提出方法有助于将较成熟的MPRM(Mixed-Polarity RM)极性转换和极性优化方法应用于MPDRM(Mixed-Polarity Dual form of RM).对15个基于XOR的MCNC电路进行逻辑综合然后映射到FPGA(Field Programmable Gate Array)的实验结果表明,从平均结果来看,与逻辑综合工具Espresso以及ABC的结果相比,混合极性RM电路能够获得面积和延时的优势,并且MPDRM电路极性优化结果能够得到最为优化的FPGA实现.展开更多
This paper discusses the definitions and properties of two kinds of fundamental symmetric functions, which are based on AND-OR-NOT algebraic system and AND-Exclusive OR algebraic system, respectively. Based upon it, s...This paper discusses the definitions and properties of two kinds of fundamental symmetric functions, which are based on AND-OR-NOT algebraic system and AND-Exclusive OR algebraic system, respectively. Based upon it, some mapping transformation methods between two kinds of expansion coefficients of an arbitrary symmetric, function in the complete set of two fundamental symmetric functions.展开更多
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 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.展开更多
Reed-Muller logic is becoming increasingly attractive. However, its synthesis and optimization are difficult especially for mixed polarity Reed-Muller logic. In this paper, a function is expressed into a truth vector....Reed-Muller logic is becoming increasingly attractive. However, its synthesis and optimization are difficult especially for mixed polarity Reed-Muller logic. In this paper, a function is expressed into a truth vector. Product shrinkage, general sum shrinkage （GSS）, elimination and extraction operators are proposed to shrink the truth vector. A novel algorithm is presented to derive a compact Multi-level Mixed Polarity Reed-Muller Form （MMPRMF） starting from a given fixed polarity truth vector. The results show that a significant area improvement can be made compared with published results.展开更多
The power and area optimization of Reed-Muller （RM） circuits has been widely concerned. However, almost none of the exiting power and area optimization approaches can obtain all the Pareto optimal solutions of the o...The power and area optimization of Reed-Muller （RM） circuits has been widely concerned. However, almost none of the exiting power and area optimization approaches can obtain all the Pareto optimal solutions of the original problem and are efficient enough. Moreover, they have not considered the don＇t care terms, which makes the circuit performance unable to be further optimized. In this paper, we propose a power and area optimization approach of mixed polarity RM expression （MPRM） for incompletely specified Boolean functions based on Non-Dominated Sorting Genetic Algorithm II （NSGA-II）. Firstly, the incompletely specified Boolean function is transformed into zero polarity incompletely specified MPRM （ISMPRM） by using a novel ISMPRM acquisition algorithm. Secondly, the polarity and allocation of don＇t care terms of ISMPRM is encoded as chromosome. Lastly, the Pareto optimal solutions are obtained by using NSGA-II, in which MPRM corresponding to the given chromosome is obtained by using a chromosome conversion algorithm. The results on incompletely specified Boolean functions and MCNC benchmark circuits show that a significant power and area improvement can be made compared with the existing power and area optimization approaches of RM circuits.展开更多
文摘针对混合极性RM(Reed-Muller)电路逻辑综合中的极性转换和极性优化问题,提出了基于对偶逻辑的极性转换和极性优化方法.从理论上证明了所提出方法的正确性,并用实验验证了其有效性和可行性.所提出方法有助于将较成熟的MPRM(Mixed-Polarity RM)极性转换和极性优化方法应用于MPDRM(Mixed-Polarity Dual form of RM).对15个基于XOR的MCNC电路进行逻辑综合然后映射到FPGA(Field Programmable Gate Array)的实验结果表明,从平均结果来看,与逻辑综合工具Espresso以及ABC的结果相比,混合极性RM电路能够获得面积和延时的优势,并且MPDRM电路极性优化结果能够得到最为优化的FPGA实现.
文摘This paper discusses the definitions and properties of two kinds of fundamental symmetric functions, which are based on AND-OR-NOT algebraic system and AND-Exclusive OR algebraic system, respectively. Based upon it, some mapping transformation methods between two kinds of expansion coefficients of an arbitrary symmetric, function in the complete set of two fundamental symmetric functions.
基金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)+1 种基金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.
文摘Reed-Muller logic is becoming increasingly attractive. However, its synthesis and optimization are difficult especially for mixed polarity Reed-Muller logic. In this paper, a function is expressed into a truth vector. Product shrinkage, general sum shrinkage （GSS）, elimination and extraction operators are proposed to shrink the truth vector. A novel algorithm is presented to derive a compact Multi-level Mixed Polarity Reed-Muller Form （MMPRMF） starting from a given fixed polarity truth vector. The results show that a significant area improvement can be made compared with published results.
基金This work is supported by the National Natural Science Foundation of China under Grant Nos. 60973106, 61370059, 61232009, and 81571142, Beijing Natural Science Foundation under Grant No. 4152030, the Fundamental Research Funds for the Central Universities of China under Grant Nos. YWF-15-CJSYS-085 and YWF-14-JSJXY-14, the Fund of the State Key Laboratory of Computer Architecture of China under Grant No. CARCH201507, the Open Project Program of National Engineering Research Center for Science and Technology Resources Sharing Service （Beihang University）, and the Fund of the State Key Laboratory of Software Development Environment of China under Grant No. SKLSDE-2016ZX-15.
文摘The power and area optimization of Reed-Muller （RM） circuits has been widely concerned. However, almost none of the exiting power and area optimization approaches can obtain all the Pareto optimal solutions of the original problem and are efficient enough. Moreover, they have not considered the don＇t care terms, which makes the circuit performance unable to be further optimized. In this paper, we propose a power and area optimization approach of mixed polarity RM expression （MPRM） for incompletely specified Boolean functions based on Non-Dominated Sorting Genetic Algorithm II （NSGA-II）. Firstly, the incompletely specified Boolean function is transformed into zero polarity incompletely specified MPRM （ISMPRM） by using a novel ISMPRM acquisition algorithm. Secondly, the polarity and allocation of don＇t care terms of ISMPRM is encoded as chromosome. Lastly, the Pareto optimal solutions are obtained by using NSGA-II, in which MPRM corresponding to the given chromosome is obtained by using a chromosome conversion algorithm. The results on incompletely specified Boolean functions and MCNC benchmark circuits show that a significant power and area improvement can be made compared with the existing power and area optimization approaches of RM circuits.
