QUANTUM-INSPIRED EVOLUTIONARY DESIGN OF SYNCHRONOUS FINITE STATE MACHINES: PART I

Synchronous finite state machines are very important for digital sequential designs. Among other important aspects, they represent a powerful way for synchronizing hardware components so that these components may cooperate adequately in the fulfillment of the main objective of the hardware design. In this paper, we propose an evolutionary methodology based on the principles of quantum computing to synthesize finite state machines. First, we optimally solve the state assignment NP-completeproblem, which is inherent for designing any synchronous finite slate machines. This is motivated by the fact that with an optimal state assignment, one can physically implement the state machine in question using a minimal hardware area and response time. Second, with the optimal state assignment provided, we propose to use the same evolutionary methodology to yield an optimal evolutionary hardware that implements the state machine control component. The evolved hardware requires a minimal hardware area and imposes a minimal propagation delay on the machine output signals. This work is divided in a two-part paper: the assignment problem is deployed in this first part while the generation of the control logic in Part II [1] of the paper.