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.

Leave a Reply

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