|
|
Searching the best polarity for fixed polarity Reed-Muller
circuits based on delay model |
WANG Peng-jun1, WANG Zhen-hai1, CHEN Yao-wu2, LI Hui1 |
1. Institute of Circuits and Systems, Ningbo University, Ningbo 315211, China;
2. Institute of Advanced Digital Technologies and Instrumentation, Zhejiang University, Hangzhou 310027, China |
|
|
Abstract To optimize delay of fixed polarity Reed-Muller (FPRM) circuits, a polarity searching algorithm was proposed for medium-scale ones to obtain the best polarity based on delay model. Within the frame of the proposed algorithm, FPRM expression of someone polarity was simplified by an algebraic method, the delay of corresponding estimated by Huffman-Like algorithm, and polarity conversion technique was used to search the best polarity exhaustively according to the characteristics of medium-scale integrated circuits. It was testified by 15 programmable logic array (PLA) formatted MCNC Benchmark circuits, and shows that it gains the average savage of 24.3% and 25% compared with two counterpart optimization algorithms on FPRM expression, and delay savage of 22.2% compared with optimization by sequential interactive system (SIS).
|
Published: 01 February 2013
|
|
固定极性Reed-Muller电路最佳延时极性搜索
为优化固定极性Reed-Muller(FPRM)电路延时,提出一种适合中小规模FPRM电路的最佳延时极性搜索算法.该算法利用代数法化简某一极性下的FPRM表达式,利用类Huffman算法估计该FPRM电路延时,根据中小规模集成电路的特点结合极性转换技术穷尽搜索延时最优的FPRM极性.对15个可编程逻辑阵列(PLA)格式MCNC Benchmark电路进行测试,结果表明:与其他2种FPRM表达式优化算法相比,与项数分别平均减少了24.3%和25%|与时序交互系统(SIS)优化后的电路相比,延时平均节省了22.2%.
|
|
[1] KAR R, MAHESHWARI V, MAQBOOL M, et al. A closed form delay evaluation approach using Burrs distribution function for high speed on-chip RC interconnects [C]∥ Proceedings of IEEE International Advance Computing Conference. Patiala: IEEE, 2010: 129-133.
[2] CORTADELLA J. Timing-driven logic bi-decomposition [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2003, 22(6): 675-685.
[3] SRIVASTAVA A, CHEN C, SARRAFZADEH M. Timing driven gate duplication in technology independent phase [J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2001, E84-A(11): 2673-2680.
[4] MICHELI G D. Synthesis and optimization of digital circuits [M]. New York: McGraw-Hill Higher Education, 1994: 343-439.
[5] JASSANI B A Al, URQUHART N, ALMAINI A E A. Manipulation and optimisation techniques for Boolean logic [J]. IET Computers and Digital Techniques, 2010, 4(3): 227-239.
[6] RAHAMAN H, DAS D K, BHATTACHARYA B B. Testable design of AND-EXOR logic networks with universal test sets [J]. Computers and Electrical Engineering, 2009, 35(5): 644-658.
[7] 汪鹏君,李辉,吴文晋,等.量子遗传算法在多输出Reed-Muller逻辑电路最佳极性搜索中的应用[J].电子学报,2010, 38(5): 1058-1063
WANG Peng-jun, LI Hui, WU Wen-jin, et al. Application of quantum genetic algorithm in searching for best polarity of multi output Reed-Muller logic circuits [J]. Acta Electronica Sinica, 2010, 38(5): 1058-1063.
[8] DAI Jing, ZHANG Hui-hong. A novel quantum genetic algorithm for area optimization of FPRM circuits [C]∥ Proceedings of International Symposium on Intelligent Information Technology Application. NanChang: IEEE, 2009: 408-411.
[9] WANG Peng-jun, LU Jin-gang, CHEN Ken, et al. Low power polarity conversion based on the whole annealing genetic algorithm [J]. Journal of Semiconductors, 2008, 29(2): 298-303.
[10] FUJITA M, MURGAI R. Delay estimation and optimization of logic circuits: a survey [C]∥ Proceedings of the Asia and South Pacific Design Automation Conference. Chiba: IEEE, 1997: 25-30.
[11] YANG Meng, WANG Ling-li, TONG Jia-rong, et al. Techniques for dual forms of Reed-Muller expansion conversion [J]. Integration, the VLSI Journal, 2008, 41(1): 113-122.
[12] YANG H, TAN E C. Optimization of multi-output fixed-polarity Reed-Muller circuits using the genetic algorithm [J]. International Journal of Electronics, 1999, 86(6): 663-670. |
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|