Minimization for ternary fixed polarity Reed-Muller expressions based on ternary quantum shuffled frog leaping algorithm

Logic minimization is one of the most crucial steps in combinational logic synthesis. The minimization for ternary fixed polarity Reed-Muller (FPRM) expressions aims to find a polarity that produces a ternary FPRM expression with as few operation terms as possible. However, the size of the ternary FPRM optimization space is much larger than that of binary FPRM optimization space, and the minimization for ternary FPRM expressions is a computationally hard problem. In this paper, we first propose a ternary quantum shuffled frog leaping algorithm (TQSFL) to solve the three-valued combinatorial optimization problem. The TQSFL divides frog individuals into three subpopulations: a subpopulation with a global updating strategy, a subpopulation with a local updating strategy, and a subpopulation with a random updating strategy, and performs local depth search on the three subpopulations based on the proposed ternary quantum rotation gate, ternary quantum correction mechanism, and ternary quantum crossover operator. Moreover, based on the TQSFL, we propose a minimization algorithm (MA) for ternary FPRM expressions, which searches for a polarity that produces a ternary FPRM expression with as few operation terms as possible by using the TQSFL. Experimental results demonstrated the effectiveness of the MA in minimizing ternary FPRM expressions. (C) 2021 Elsevier B.V. All rights reserved.

Automated summary

This paper introduces a ternary quantum shuffled frog leaping algorithm (TQSFL) and a minimization algorithm (MA) for ternary FPRM expressions. Experimental results demonstrate the effectiveness of MA in minimizing ternary FPRM expressions.