We propose Finite State Machine (FSM) re-engineering, a performance enhancement framework for FSM synthesis and optimization. It starts with the traditional FSM synthesis procedure, then proceeds to re-construct a functionally equivalent but topologically different FSM based on the optimization objective, and concludes with another round of FSM synthesis on the re-constructed FSM. This approach explores a larger solution space that consists of a set of FSMs functionally equivalent to the original one, making it possible to obtain better solutions than in the original FSM. Guided by the result from the rst round of synthesis, the solution space exploration process can be rapid and cost-ef cient. We apply this framework to FSM state encoding for power minimization and area minimization. The FSM is rst minimized and encoded using existing state encoding algorithms. Then we develop both a heuristic algorithm and a genetic algorithm to re-construct the FSM. Finally, the FSM is reencoded by the same encoding algorithms. To demonstrate the effectiveness of this framework, we conduct experiments on MCNC91 sequential circuit benchmarks. The circuits are read in and synthesized in SIS environment. After FSM re-engineering are performed, we measure the power, area and delay in the newly synthesized circuits. In the powerdriven synthesis, we observe an average 5.5% of total power reduction with 1.3% area increase and 1.3% delay increase. This results are in general better than other low power state encoding techniques on comparable cases. In the area-driven synthesis, we observe an average 2.7% area reduction, 1.8% delay reduction, and 0.4% power increase. Finally, we use integer linear programming to obtain the optimal low power state encoding for benchmarks of small size. We nd that the optimal solutions in the re- engineered FSMs are 1% to 8% better than the optimal solutions in the original FSMs in terms of power minimization.