Automatic synthesis of multiple constant multiplication circuits using genetic algorithms

摘要

In multiple constant multiplication (MCM) computational complexity can be reduced by substitution of multiplications for shifts and additions. This circuit structure can be represented as a directed acyclic graph (DAG). However, synthesis of MCM so as to minimize computational complexity is known as an NP complete problem. Therefore, an effective tool for optimization of circuit synthesis is needed. In this paper, we propose an automatic synthesis method of MCM circuits by GA. The novel idea is that the chromosome to represent DAG is composed of stack type operators. As the chromosome is formed with a sequence of simple symbols, the similar method to a conventional GA can be employed.