A state assignment algorithm for two-level logic implementation based on a simulated annealing algorithm is proposed. To save CPU time an efficient cost estimation method is devised without losing much estimation accuracy. The experimental results based on 40 benchmark example finite state machines show that the number of cubes and area obtained by the proposed approach is approximately 10% less than that of NOVA [1] within a comparable CPU time. For a large example, it could reduce the number of product terms by more than 40%.