An efficient and fast polarity optimization approach for mixed polarity Reed-Muller logic circuits

doi:10.1007/s11704-016-5259-2

Front. Comput. Sci.

2017, Vol. 11

Issue (4) : 728-742 https://doi.org/10.1007/s11704-016-5259-2

RESEARCH ARTICLE

An efficient and fast polarity optimization approach for mixed polarity Reed-Muller logic circuits

Zhenxue HE^1,², Limin XIAO^1,²(

), Fei GU², Tongsheng XIA³, Shubin SU^2,⁵, Zhisheng HUO^1,², Rong ZHANG³, Longbing ZHANG⁴, Li RUAN^1,², Xiang WANG³(

)

¹. State Key Laboratory of Software Development Environment, Beihang University, Beijing 100191, China
². School of Computer Science and Engineering, Beihang University, Beijing 100191, China
³. School of Electronic and Information Engineering, Beihang University, Beijing 100191, China
⁴. State Key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China
⁵. National Engineering Research Center for Science & Technology Resources Sharing Service, Beijing 100191, China

Download: PDF(709 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

Although the genetic algorithm has been widely used in the polarity optimization of mixed polarity Reed- Muller (MPRM) logic circuits, few studies have taken into account the polarity conversion sequence. In order to improve the efficiency of polarity optimization of MPRM logic circuits, we propose an efficient and fast polarity optimization approach (FPOA) considering the polarity conversion sequence. The main idea behind the FPOA is that, firstly, the best polarity conversion sequence of the polarity set waiting for evaluation is obtained by using the proposed hybrid genetic algorithm (HGA); secondly, each of polarity in the polarity set is converted according to the best polarity conversion sequence obtained by HGA. Our proposed FPOA is implemented in C and a comparative analysis has been presented for MCNC benchmark circuits. The experimental results show that for the circuits with more variables, the FPOA is highly effective in improving the efficiency of polarity optimization of MPRM logic circuits compared with the traditional polarity optimization approach which neglects the polarity conversion sequence and the improved polarity optimization approach with heuristic technique.

Keywords genetic algorithm polarity optimization mixed polarity Reed-Muller polarity conversion sequence hybrid genetic algorithm

Corresponding Author(s): Limin XIAO,Xiang WANG

Just Accepted Date: 14 April 2016 Online First Date: 17 March 2017 Issue Date: 26 July 2017

Cite this article:

Zhenxue HE,Limin XIAO,Fei GU, et al. An efficient and fast polarity optimization approach for mixed polarity Reed-Muller logic circuits[J]. Front. Comput. Sci., 2017, 11(4): 728-742.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-016-5259-2
https://academic.hep.com.cn/fcs/EN/Y2017/V11/I4/728

1	LiangH, XiaY S, QianL B, Huang C L. Low power 3-input AND/XOR gate design. Journal of Computer-Aided Design & Computer Graphics, 2015, 27(5): 940–945
2	WangX, LuY, ZhangY. Probabilistic modeling during power estimation for mixed polarity Reed-Muller logic circuits. In: Proceedings of IEEE International Conference on Green Computing and Communications. 2013, 1414–1418 https://doi.org/10.1109/greencom-ithings-cpscom.2013.247
3	WangP J, WangZ H, XuR. Conversion algorithm for MPRM expansion. Journals of Semiconductors, 2014, 35(3): 150–155 https://doi.org/10.1088/1674-4926/35/3/035007
4	BuD L, JiangJ H. An efficient optimization algorithm for multi-output MPRM circuits with very large number of input variables. In: Proceedings of the 7th IEEE Joint International Information Technology and Artificial Intelligence Conference. 2014, 228–232 https://doi.org/10.1109/itaic.2014.7065040
5	GeethaV, Devarajan N, NeelakantanP N . OR-Bridging fault analysis and diagnosis for exclusive-OR sum of products Reed-Muller canonical circuits. Journal of Computer Science, 2011, 7(5): 744–748 https://doi.org/10.3844/jcssp.2011.744.748
6	YuH Z, JiangZ D, WangP J. GA-DTPSO algorithm and its application in area optimization of mixed polarity XNOR/OR circuits. Journal of Computer-Aided Design & Computer Graphics, 2015, 27(5): 946–952
7	LiX W, XiaY S, WangL Y. An improved tabular-technique for mixpolarity. Journal of Ningbo University (NSEE), 2015, 28(1): 42–46
8	LiH, WangP J, DaiJ. Area minimization of MPRM circuits. In: Proceedings of the 8th International Conference on ASIC. 2009, 521–524
9	AlmainiA E A, McKenzie L. Tabular techniques for generating kronecker expansions. IEE Proceedings — Computers and Digital Techniques, 1996, 143(4): 205–212 https://doi.org/10.1049/ip-cdt:19960564
10	WangL, Almaini A E A. Exact minimisation of large multiple output FPRM functions. Computers and Digital Techniques, 2002, 149(5): 203–212 https://doi.org/10.1049/ip-cdt:20020674
11	BeckerB, Drechsler R. OFDD based minimization of fixed polarity Reed-Muller expressions using hybrid genetic algorithms. In: Proceedings of the IEEE International Conference on Computer Design: VLSI in Computers and Processors. 1994, 106–110 https://doi.org/10.1109/iccd.1994.331866
12	PurwarS. An efficient method of computing generalized Reed-Muller expansions from binary decision diagram. IEEE Transactions on Computers, 1991, 40(11): 1298–1301 https://doi.org/10.1109/12.102837
13	SunF, WangP J, YuH Z. Ternary FPRM circuit area optimization based on genetic algorithm. Journal of Shandong University (Natural Science), 2013, 48(5): 51–56
14	BuD L, JiangJ H. Dual logic based polarity conversion and optimization of mixed polarity RM circuits. Acta Electronica Sinica, 2015, 43(1): 79–85
15	MudaliarD N, ModiN K. Unraveling travelling salesman problem by genetic algorithm using m-crossover operator. In: Proceedings of the International Conference on Signal Processing, Image Processing and Pattern Recognition (ICSIPR). 2013, 127–130 https://doi.org/10.1109/icsipr.2013.6497974
16	ThomsonP, MillerJ F. Optimisation techniques based on the use of genetic algorithms (Gas) for logic implementation on FPGAs. In: Proceedings of IEE Colloquium on Software Support and CAD Techniques for FPGAs. 1994
17	DrechslerR, BeckerB, GockelN. A genetic algorithm for the construction of small and highly testable OKFDD-circuits. In: Proceedings of the 1st Annual Conference on Genetic Programming. 1996, 473–478
18	CongJ, DingY Z. Combinational logic synthesis for LUT based field programmable gate arrays.ACM Transactions on Design Automation of Electronic Systems, 1996, 1(2): 145–204 https://doi.org/10.1145/233539.233540
19	YangM, LaiJ M. Optimisation of mixed polarity Reed-Muller functions. Journal of Software, 2013, 8(11): 2770–2774 https://doi.org/10.4304/jsw.8.11.2770-2774
20	WangP J, LiH, WangZ H. MPRM expressions minimization based on simulated annealing genetic algorithm. In: Proceedings of the International Conference on Intelligent Systems and Knowledge Engineering (ISKE). 2010, 261–265 https://doi.org/10.1109/iske.2010.5680868
21	JassaniA, Urquhart N, AlmainiA E A . Minimization of incompletely specified mixed polarity Reed-Muller functions using genetic algorithm. In: Proceedings of the 3rd International Conference on Signals, Circuits and Systems. 2009, 1–6 https://doi.org/10.1109/icscs.2009.5412318
22	YangM, XuH Y, AlmainiA E A . Optimization of mixed polarity Reed-Muller functions using genetic algorithm. In: Proceedings of the 3rd International Conference on Computer Research and Development (ICCRD). 2011, 293–296 https://doi.org/10.1109/iccrd.2011.5764198
23	SunF, WangP J, YuH Z. Best polarity searching for ternary FPRM logic circuit area based on whole annealing genetic algorithm. In: Proceedings of the 10th IEEE International Conference on ASIC (ASICON). 2013, 1–4
24	DrechslerR, BeckerB, DrechslerN. Genetic algorithm for minimisation of fixed polarity Reed-Muller expressions. Computers and Digital Techniques, 2000, 147(5): 349–353 https://doi.org/10.1049/ip-cdt:20000743
25	WuW J, WangP J, ZhangX Y.Notice of retraction search for the best polarity of fixed polarity Reed-Muller expression base on QGA. In: Proceedings of the 11th IEEE International Conference on Communication Technology. 2008, 343–346
26	DaiJ, ZhangH H. A novel quantum genetic algorithm for area optimization of FPRM circuits. In: Proceedings of the 3rd International Symposium on Intelligent Information Technology Application. 2009, 408–411 https://doi.org/10.1109/iita.2009.454
27	WangP J, LiH, WangZ H. MPRM expressions minimization based on simulated annealing genetic algorithm. In: Proceedings of the International Conference on Intelligent Systems and Knowledge Engineering. 2010, 261–265 https://doi.org/10.1109/iske.2010.5680868
28	ChaudhuryS, Chattopadhyay S. Output phase assignment for area and power optimization in multi-level multi-output combinational logic circuits. In: Proceedings of the Annual IEEE India Conference. 2006, 1–4 https://doi.org/10.1109/INDCON.2006.302786
29	AlmainiA E A, Mckenzie L. Tabular techniques for generating Kronecker expansions. Computers and Digital Techniques, 1996, 143(4): 205–212 https://doi.org/10.1049/ip-cdt:19960564
30	ZhangH H, WangP J, GuX S. Best polarity searching of FPRM circuits with heuristic technique. Journal of Circuits and Systems, 2009, 14(6): 24–28
31	NguyenH D, Yoshihara I, YamamoriK , YasunagaM. Implementation of an effective hybrid GA for large-scale traveling salesman problems. IEEE Transactions on Systems, Man, and Cybernetics, 2007, 37(1): 92–99 https://doi.org/10.1109/TSMCB.2006.880136
32	WangX, LuY, ZhangY. Power optimization in logic synthesis for mixed polarity Reed-Muller logic circuits. The Computer Journal, 2015, 58(6): 1307–1313 https://doi.org/10.1093/comjnl/bxu072

[1]

FCS-0728-15259-LMX_suppl_1

Download

[1]	Sedigheh KHOSHNEVIS, Fereidoon SHAMS. Automating identification of services and their variability for product lines using NSGA-II[J]. Front. Comput. Sci., 2017, 11(3): 444-464.
[2]	Chenchen SUN,Derong SHEN,Yue KOU,Tiezheng NIE,Ge YU. A genetic algorithm based entity resolution approach with active learning[J]. Front. Comput. Sci., 2017, 11(1): 147-159.
[3]	Lamia SADEG-BELKACEM,Zineb HABBAS,Wassila AGGOUNE-MTALAA. Adaptive genetic algorithms guided by decomposition for PCSPs: application to frequency assignment problems[J]. Front. Comput. Sci., 2016, 10(6): 1012-1025.
[4]	Xiangxiang ZENG,Sisi YUAN,Xianxian HUANG,Quan ZOU. Identification of cytokine via an improved genetic algorithm[J]. Front. Comput. Sci., 2015, 9(4): 643-651.
[5]	Priyanka CHAWLA,Inderveer CHANA,Ajay RANA. A novel strategy for automatic test data generation using soft computing technique[J]. Front. Comput. Sci., 2015, 9(3): 346-363.
[6]	Dunwei GONG, Yan ZHANG. Generating test data for both path coverage and fault detection using genetic algorithms[J]. Front Comput Sci, 2013, 7(6): 822-837.
[7]	Dion DETTERER, Paul KWAN, Cedric GONDRO. A co-evolving memetic wrapper for prediction of patient outcomes in TCM informatics[J]. Front Comput Sci, 2012, 6(5): 621-629.
[8]	Bo YUAN, Wenhuang LIU. Measure oriented training: a targeted approach to imbalanced classification problems[J]. Front Comput Sci, 2012, 6(5): 489-497.
[9]	Kenli LI, Zhao TONG, Dan LIU, Teklay TESFAZGHI, Xiangke LIAO. A PTS-PGATS based approach for data-intensive scheduling in data grids[J]. Front Comput Sci Chin, 2011, 5(4): 513-525.
[10]	Dabin ZHANG, Lean YU, Shouyang WANG, Yingwen SONG. A novel PPGA-based clustering analysis method for business cycle indicator selection[J]. Front Comput Sci Chin, 2009, 3(2): 217-225.

Viewed

Full text

Abstract

Cited

Shared

Discussed