EVOLUTIONARY TECHNIQUES IN SYNTHESIS OF MULTIPLE-VALUED LOGIC FUNCTIONS

The radix (R) used in Multiple-Valued Logic (MVL) circuits goes beyond the binary case (R = 2). MVLRead Only Memory (ROM), Random Access Memory (RAM), and Digital Signal Processing (DSP) systems have been successfully implemented using Complementary Metal Oxide Semiconductor (CMOS) Technology. The complexity of exact synthesis of MVL circuits is prohibitively large. This is because of the enormous solution search space. The Direct Cover (DC) algorithm is a well-known heuristic for synthesis of MVL functions. The algorithm selects the next minterm to be covered and the appropriate implicant to cover it in an iterative manner using a set of synthesis criteria. Evolutionary algorithms, such as Genetic Algorithms (GAs) and Ant Colony (ACO) have also been successfully used in synthesis of MVL functions. In this paper, we introduce and compare synthesis of MVL functions using the GAs and ACO with the corresponding synthesis using the conventional DC algorithm. Our comparison is based on synthesizing a benchmark consisting of 50000 randomly generated 2-variable 4-valued randomly generated functions. The obtained results showed that the average number of product terms (PTs) needed to synthesize a given MVL function using evolutionary techniques outperforms those obtained using conventional DC heuristics. Among the two techniques it is shown that the technique based on the ACO achieves the best results.