Ant Colony Heuristic Algorithm For Multi-Level Synthesis of Multiple-Valued Logic Functions

A number of successful implementation of Multiple-Valued Logic (MVL) circuits using Very Large Scale Integration (VLSI) technology has been reported in the literature. The Ant Colony (ACO) optimization algorithm is a meta-heuristic that mimics the antsʹ behavior in finding the shortest path to reach food sources. We have previously introduced ACO-based heuristic for synthesis of two-level MVL functions. In this paper, we introduce a hybrid ACO-Direct Cover (DC) technique for synthesis of multi-level MVL functions. In this technique, we use ants to decompose the given MVL function into a number of levels and synthesize each sub-function using a DC-based technique. A benchmark set consisting of 50000 randomly generated 2-varaible 4-valued functions is used to compare the results obtained using the proposed approach with those obtained using existing techniques. It is shown that on average the proposed hybrid technique produces more efficient realizations in terms of the chip area consumed in synthesizing a given MVL function.