A New Heuristic Tool for Designing Multiple-Valued Logic Systems

In this paper, a brand new heuristic optimization algorithm for multiple-valued logic (MVL) functions and the performance of the implementation will be introduced. In logic synthesis, optimization procedure is a fundamental process in order to design more efficient systems. The proposed algorithm, called MVL-MIN, utilizes Cube Algebra operators. MVL-MIN computes the prime cubes that cover a target cube at a time, instead of extracting all the primes for a given MVL function. MVL-MIN consists of five major procedures, called (a) checking, (b) expansion, (c) elimination, (d) nondisjoint sharp, and (e) prime determination. In order to find a near-minimal cover, three different prime determination functions are developed. The implementation based on the new algorithm is compared with MVSIS. For testing, three sets of test bench are prepared. Each set includes 5 MVL functions. Test results proved that MVL-MIN is able to solve all test files within a fixed allocation of computer resources while MVSIS could not. MVL-MIN achieved 1.9x to 9.7x speedup over MVSIS. In terms of cover size, since current MVL-MIN implementation cannot recognize redundant cubes, MVSIS computed more concise covers for all test benches than MVL-MIN.

Automated summary

This paper introduces a brand new heuristic optimization algorithm called MVL-MIN for multiple-valued logic functions and compares its performance with MVSIS. Test results show that MVL-MIN is able to solve problems by efficiently utilizing computer resources and achieves significant speedup compared to MVSIS. However, MVSIS still produces more concise covers in terms of cover size due to the inability of MVL-MIN to recognize redundant cubes.