In this paper we address the problem of state encoding for synchronous finite state machines. The primary goal is the reduction of switching activity in the state register. At the beginning the state transition graph is transformed into an undirected graph where the edges are labeled with the state transition probabilities. Next a maximum spanning tree of the undirected graph is constructed, and we formulate the state encoding problem as an embedding of the spanning tree into a Boolean hypercube of unknown dimension. At this point a modification of Prim's maximum spanning tree algorithm is presented to limit the dimension of the hypercube for area constraints. Then we propose a polynomial time embedding heuristic, which removes the restriction of previous works, where the number of state bits used for encoding of a k-state FSM was generally limited to log2(k). Next a more sophisticated embedding algorithm is presented, which takes into account the state transition probabilities not covered by the spanning tree. The resulting encodings of both algorithms often exhibit a lower switching activity and power dissipation in comparison with a known heuristic for low power state encoding.