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

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

References

[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

[3] WangP J, WangZ H, XuR. Conversion algorithm for MPRM expansion. Journals of Semiconductors, 2014, 35(3): 150–155

[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

[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

[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

[10] WangL, Almaini A E A. Exact minimisation of large multiple output FPRM functions. Computers and Digital Techniques, 2002, 149(5): 203–212

[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

[12] PurwarS. An efficient method of computing generalized Reed-Muller expansions from binary decision diagram. IEEE Transactions on Computers, 1991, 40(11): 1298–1301

[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

[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

[19] YangM, LaiJ M. Optimisation of mixed polarity Reed-Muller functions. Journal of Software, 2013, 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

[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

[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

[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

[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

[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

[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

[29] AlmainiA E A, Mckenzie L. Tabular techniques for generating Kronecker expansions. Computers and Digital Techniques, 1996, 143(4): 205–212

[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

[32] WangX, LuY, ZhangY. Power optimization in logic synthesis for mixed polarity Reed-Muller logic circuits. The Computer Journal, 2015, 58(6): 1307–1313

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg