as a school assignment we were given simple graph of FSM and the task is to design digital circuit described by this graph. Everything is fine I just followed my notes. While encoding the states I used codin we have been taught, but the problem is I cannot find this algorithm anywhere.

enter image description here

On left is transfer table - from state 1 go to state 2 when receiving signal A. On right is the encoded table. The column W is sum of appearances of each state in transfer table - state 2 appears 3 times, state 3 once etc.

The coding is defined in way that state with biggest W has least ones in codes - state 2 is encoded with 3 zeros, state 1 is encoded with 2 ones. Does anybody know name of this coding? It's not one-hot, neither it's binary encoding.


1 Answer 1


The states, when arranged in decreasing frequency, may be numbered according to a monotonic Gray Code.

Although note that this montonic Gray code itself does not stipulate anything about the successive values representing a frequency of occurrence. It's just the name for sequences of increasing or decreasing weight, where weight is defined as the number of digits which are 1.

  • \$\begingroup\$ Out of curiosity, do you happen to know why a state machine would be encoded in this fashion? I'm trying to think of a reason but coming up blank. \$\endgroup\$
    – Tim
    Apr 10, 2013 at 23:24
  • 1
    \$\begingroup\$ @Tim - The states with the most transfer terms would take the most product terms in the sum of products logic equations. If you implement the logic of the transition equations by writing them for the 1 bits in the states then you can see that minimizing the number of product terms for each '1' state bit reduces the amount of logic to realize the circuit design. \$\endgroup\$ Apr 11, 2013 at 4:45
  • \$\begingroup\$ @MichaelKaras I.e. finish the homework. :) \$\endgroup\$
    – Kaz
    Apr 11, 2013 at 4:47
  • \$\begingroup\$ @Kaz - It's not Tim's homework. He just asked a question which I tried to answer in a concise manner to explain why one would use the technique mentioned by the question author. \$\endgroup\$ Apr 11, 2013 at 4:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.