Bitwise encoding of finite state machines
Jose Carlos Monteiro, James H. Kukula, Srinivas Devadas, Horácio C. Neto · 2002
We propose an innovative method of encoding the states of finite state machines. Our approach consists of iteratively defining the code word, one bit at a time. In each iteration the input state machine is decomposed into two submachines, with the first submachine having only two states. One bit is therefore sufficient to encode this submachine and it can be assigned arbitrarily as the particular value it assumes for each state is of minimal influence in terms of the machine implementation. The process is repeated again having as input the second submachine, until all the bits are encoded. We provide experimental results which indicate that our method of iteratively defining one bit at a time can generally achieve superior results to existing sequential state assignment methods which try to solve large problems heuristically.>