This paper reports an efficient state encoding scheme for synthesis of large FSMs with enhanced BIST quality. A metric, referred to as degree-of-freedom (DOF) [5] in FSM states has been employed to quantify the BIST quality. Analysis of DOF enables efficient encoding of FSM states and gives solution to the problem of handling unreachable/ hard-to-exit/ hardto- reach state codes of an FSM. The synthesis of a large FSM is realized through decomposition. DOF analysis for the individual component sub-FSM states is done to reduce the complexity of synthesis. A scheme is proposed for encoding the sub-FSM states that significantly improves testability of the synthesized resultant FSM, displaying the terminal behavior as the original FSM.