Technology for finite-state machine (FSM) encoding during design synthesis for a circuit is disclosed. The encoding of the FSM may include determining values of a multi-bit state register that are to represent particular states of the FSM. These values may be determined based on possible states of the FSM, possible transitions between the states, probabilities of particular transitions occurring, amounts of false switching associated with particular transitions, area estimates for logic respectively associated with states of the FSM, and/or the like. The values may also be determined based on power considerations, such as estimated power consumption for the circuit. The design synthesis may include generation of a structural description of the encoded FSM.