Please wait a minute...

Frontiers of Computer Science

Front. Comput. Sci.    2017, Vol. 11 Issue (4) : 728-742     DOI: 10.1007/s11704-016-5259-2
RESEARCH ARTICLE |
An efficient and fast polarity optimization approach for mixed polarity Reed-Muller logic circuits
Zhenxue HE1,2, Limin XIAO1,2(), Fei GU2, Tongsheng XIA3, Shubin SU2,5, Zhisheng HUO1,2, Rong ZHANG3, Longbing ZHANG4, Li RUAN1,2, Xiang WANG3()
1. State Key Laboratory of Software Development Environment, Beihang University, Beijing 100191, China
2. School of Computer Science and Engineering, Beihang University, Beijing 100191, China
3. School of Electronic and Information Engineering, Beihang University, Beijing 100191, China
4. State Key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China
5. 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 Authors: 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:  
http://journal.hep.com.cn/fcs/EN/10.1007/s11704-016-5259-2
http://journal.hep.com.cn/fcs/EN/Y2017/V11/I4/728
Service
E-mail this article
E-mail Alert
RSS
Articles by authors
Zhenxue HE
Limin XIAO
Fei GU
Tongsheng XIA
Shubin SU
Zhisheng HUO
Rong ZHANG
Longbing ZHANG
Li RUAN
Xiang WANG
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
doi: 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
doi: 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
doi: 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
doi: 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
doi: 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
doi: 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
doi: 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
doi: 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
doi: 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
doi: 10.1145/233539.233540
19 YangM, LaiJ M. Optimisation of mixed polarity Reed-Muller functions. Journal of Software, 2013, 8(11): 2770–2774
doi: 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
doi: 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
doi: 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
doi: 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
doi: 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
doi: 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
doi: 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
doi: 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
doi: 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
doi: 10.1109/TSMCB.2006.880136
[1] FCS-0728-15259-LMX_suppl_1 Download
Related articles from Frontiers Journals
[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