大函数ISFPRM面积优化方法

doi:10.3969/j.issn.0372-2112.2018.05.012

电子学报 ›› 2018, Vol. 46 ›› Issue (5): 1101-1106.DOI: 10.3969/j.issn.0372-2112.2018.05.012

大函数ISFPRM面积优化方法

瞿婷, 王伦耀, 罗文强, 夏银水

宁波大学信息科学与工程学院, 浙江宁波 315211

收稿日期:2017-03-27 修回日期:2017-07-06 出版日期:2018-05-25
- 作者简介:
- 瞿婷女,1992年生于贵州铜仁,现为宁波大学硕士研究生.主要的研究方向为RM逻辑的混合极性综合.E-mail:quting_qt@163.com;王伦耀 男,1972年生于浙江宁波,博士,教授.主要的研究方向为Reed-Muller逻辑以及基于Reed-Muller逻辑与传统布尔逻辑的双逻辑综合与优化.E-mail:wanglunyao@nbu.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61471211）; 国家自然科学基金重点项目 (No.61131001）

A Novel Method For Large ISPFRM Function Optimization

QU Ting, WANG Lun-yao, LUO Wen-qiang, XIA Yin-shui

School of Information Science and Engineering, Ningbo University, Ningbo, Zhejiang 315211, China

Received:2017-03-27 Revised:2017-07-06 Online:2018-05-25 Published:2018-05-25

摘要/Abstract

摘要： 针对以往在ISFPRM优化过程中只能处理小规模电路的不足，提出了一种新的乘积项十进制表示和处理方法来实现大电路ISFPRM面积优化.具体包括：ISFPRM多位变量的十进制数表示，基于二进制插值的极性转换方法，以及基于整数的位运算遗传算法实现ISFPRM面积优化.提出的算法能有效地避免以往算法在处理输入较多的函数时效率低下甚至无法工作的情况，算法的性能用MCNC标准电路作为测试.实验结果表明，提出的算法可以处理输入变量个数为199个的大电路，算法的速度对待处理电路的变量数不敏感特点，引入不确定项后，电路面积优化明显.

关键词: 不完全确定RM电路, 二进制插值, 位运算, GA算法

Abstract: In view of the problems of the published methods of the ISPFRM functions optimization which couldn't deal with large functions,a novel method for large ISPFRM function optimization was proposed which consists of the representation of product term in integer form,the polarity conversion method using the binary interpolation,and the circuit area optimization of ISFPRM using the bit-wise operation and the genetic algorithm.The proposed algorithm could deal with those functions with large inputs effectively,and has been implemented in C and tested under MCNC benchmarks.The experimental results show that it can deal with the large function with 199 inputs,and the speed of the algorithm is not sensitive to the functions' polarity.After the introduction of DC terms,the circuit area is further optimized.

Key words: ISFPRM(Incompletely Specified Fixed Polarity Reed-Muller), binary interpolation, bit operation, genetic algorithm

中图分类号:

TP391.72

瞿婷, 王伦耀, 罗文强, 夏银水. 大函数ISFPRM面积优化方法[J]. 电子学报, 2018, 46(5): 1101-1106.

QU Ting, WANG Lun-yao, LUO Wen-qiang, XIA Yin-shui. A Novel Method For Large ISPFRM Function Optimization[J]. Acta Electronica Sinica, 2018, 46(5): 1101-1106.

参考文献

[1] Khan M H A.An ASIC architecture for generating optimum mixed polarity Reed-Muller expression[J].Engineering Letters,2006,13(3):236-243.
[2] Jankovic D,Stankovic R S,Moraga C.Optimization of polynomial expressions by using the extended dualpolarity[J].IEEE Transactions on Computers,2009,58(12):1710-1725.
[3] 王伦耀,夏银水,陈偕雄.逻辑函数的双逻辑综合与优化[J].计算机辅助设计与图形学学报,2012,24(7):961-967. Wang Lunyao,Xia Yinshui,Chen Xiexiong.Logic synthesis and optimization based on dual logic[J].Journal of Computer-Aided Design & Computer Graphics,2012,24(7):961-967.(in Chinese)
[4] M Amy,D Maslov,M Mosca,M Roetteler.A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits[J].IEEE Transactions on Computer-Aided Design ofIntegrated Circuits and Systems,2012,32(6):818-830.
[5] A Rafiev,A Mokhov,FP Burns,JP Murphy,A Koelmans.Mixed radix reed-muller expansions[J].IEEE Transactions on Computers,2012,61(8):1189-1202.
[6] Saeed S M,Sinanoglu O,Almukhaizim S.Predictive techniques for projecting test data volume compression[J].IEEE Transactions on very Large scale Integration Systems,2013,21(9):1762-1766.
[7] L Amarú,PE Gaillardon,GD Micheli.A circuit synthesis flow for controllable-polarity transistors[J].IEEE Transactions on Nanotechnology,2014,13(6):1074-1083.
[8] 王玉花,王伦耀,夏银水.基于不相交项并行列表技术的FPRM实现[J].电子与信息学报,2014,36(9):2258-2264. Wang Yuhua,Wang Lunyao,Xia Yinshui.FPRM conversion using parallel tabular technique with disjointed products[J].Journal of Electronics & Information Technology,2014,36(9):2258-2264.(in Chinese)
[9] Al Jassani B A,Urquhart N,Almaini A E A.Manipulation and optimisation techniques for Boolean logic[J].IET Computers & Digital Techniques,2010,4(3):227-239.
[10] 卜登立,江建慧.基于对偶逻辑的混合极性RM电路极性转换和优化方法[J].电子学报,2015,43(1):79-85. Bu Dengli1,Jiang Jianhui.Dual logic based polarity conversion and optimization of mixed polarity RM circuits[J].Acta Electronica Sinica,2015,43(1):79-85.(in Chinese)
[11] L Xiao,Z He,L Ruan,R Zhang.Optimization of best polarity searching for mixed polarity reed-muller logic circuit[A].Publishing House of System-on-chip Conference[C].Beijing:2015.275-280.
[12] 汪鹏君,汪迪生,蒋志迪,张会红.基于PSGA算法的ISFPRM电路面积与功耗优化[J].电子学报,2013,41(8):1542-1548. Wang Pengjun,Wang Disheng,Jiang Zhidi,Zhang Huihong.Area and power optimization of ISFPRM circuits based on PSGA algorithm[J].Acta Electronica Sinica,2013,41(8):1542-1548.(in Chinese)
[13] D Debnath,T Sasao.Exact minimization of FPRM for incompletely specified functions by using MTBDDs[J].IEICE Transactions on Fundamentals of Electronics,Communications and Computer Science,2005,88(12):3332-3341.
[14] M K Habib.A new approach to generate fixed-polarity Reed Muller expansions for completely and incompletely specified functions[J].International Journal of Electronics,2002,89(11):845-876.

大函数ISFPRM面积优化方法

A Novel Method For Large ISPFRM Function Optimization

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics