Assuming incoming bit stream is one bit per cycle, design a circuit that detects whether the integer number formed by the bit stream is a multiple of 5.

The idea is to have an FSM consisting of 5 states, S0, S1, S2, S3, S4. Each state represents divided by 5 remainder in previous cycle. If FSM stays at S0, then it means the number could be divided by 5 in previous cycle; otherwise, the number was not a multiple of 5.

MSB Appears in Bit Stream First

One case would be MSB appearing in the bit stream first. 

For example, if the sequence is 1 -> 0 -> 1 -> 0, then in the 4th cycle, the integer number is ‘b1010 or ‘d10. In the 5th cycle, the FSM should stay at S0, i.e., it was a multiple of 5.

The state transition can be described in the formula below:

State_next = (State x 2 + in) % 5

Since MSB appears first, the remainder of previous cycle should be doubled in current cycle, in order to calculate the new remainder, and the input of the current cycle represents either a 0 or 1.

The diagram below shows the FSM and the state transition.

LSB Appears in Bit Stream First

The other case would be LSB appearing in the bit stream first.

Take the same example, if the sequence is 1 -> 0 -> 1 -> 0, then in the 4th cycle, the integer number is ‘b0101 or ‘d5. In the next cycle, the FSM should stay at S0 as well.

Since LSB presents first, the remainder from previous cycle should not be doubled in current cycle, and the input = 1 in current cycle represents 1, 2, 4, 8, 16, 32, 64, 128, etc., depending on when it appears in the sequence.

Notice that,

1    % 5 = 1 (SS1)
2    % 5 = 2 (SS2)
4    % 5 = 4 (SS4)
8    % 5 = 3 (SS3)
16   % 5 = 1 (SS1)
32   % 5 = 2 (SS2)
64   % 5 = 4 (SS4)
128 % 5 = 3 (SS3)

This implies that we should keep a sub-FSM with 4 states, SS1, SS2, SS3, SS4, tracking the result of new input modulo of 5. The sub-FSM traverses from SS1, to SS2, SS4 and SS3, then goes back to SS1.

The state transition can be described in the formula below:

State_next = (State + in * sub-state) % 5

The diagram below shows the FSM and the state transition from S0 and S1. You can derive the state transition from other states.

6 Comments

  1. Can you please explain the state transition of sub-FSM, based on what conditions it goes to another state?

    Many Thanks

    1. In the sub-FSM,
      . There is a pattern of remainders generating {1 -> 2 -> 4-> 3} -> {1 -> 2 -> 4 -> 3}
      . This looks cyclic. So, you could run this sub-FSM without really implementing any divider logic.
      . As soon as the input pattern is initiated into the design, we could start running this sub-FSM unconditionally.

      In the main FSM,
      . If input = 1, you use this sub-FSM remainder to calculate actual remainder.
      . Else, there is no change in actual remainder.

    2. The sub-FSM will always go to the next state because it is to track the weight of the coming input

    3. The sub-FSM will always go the the next state for tracking the weight of the coming input.

  2. The sub-FSM will always go the the next state for tracking the weight of the coming input.

  3. sub-fsm has unconditional state transfer..will move to the next state on every clock ..since the modulu with 5 follows a cyclic pattern

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.