Today, let’s look into one of the interesting design puzzles in digital design that I have come across. And how to design the micro-architecture to solve it.

Problem Statement

You are serially receiving a number of no fixed length, and on any given clock cycle, you have to indicate whether the number received so far is divisible by N , where N is any natural number which is constant. Assumption here is that MSB is received first.

Initial thoughts

• For any natural number N as divisor, remainders possible ranges from 0 to N-1 .
• For any number M < N , remainder = M .
• If M is divisible by N , then remainder = 0.
• 0 is divisible with any N > 0 .

Break it down…

From the initial thoughts, we can say that the system we design may compute M \text{ modulo } N at any given time and look for remainder 0 to indicate that the number is divisible by N . The system should be in one of the N states at any given point of time because remainders range from 0 to N-1 . Paraphrasing in the words of digital designer, We are looking at an FSM with N states to solve the problem.

Design it!

FSM got to have N states, where each state corresponds to remainder for M \text{ modulo } N in that clock cycle.

For the sake of simplicity, let’s consider the case for divisibility by 5 , and let’s see how to design a Moore FSM for it.

Let’s first put down states for each of the remainders [0, 4] and how these states are reached for values of M < 5 i.e., M \in [0, 4] :

Initial Draft

R0 is the remainder 0 state where the system starts operation and generates output = 1 . We have to now fill in the incomplete transitions at different states. For e.g., at R3 , the number received so far is same as the remainder i.e., 3 . Receiving ‘0’ next should make the number received = \text{ } '110' \text{ or } 6 with remainder = 1 .

Adding Transition for 6 or ‘110’

Similarly, complete all missing transitions and add outputs to each state:

Completed FSM

Aaaaaand that completes the puzzle! You can now extend this concept to divisibility by any number.

This is Moore machine. Can you design the same FSM in mealy? Leaving this to you…

Support

Leave a comment or visit support for any queries/feedback regarding the content of this blog.

If you liked Chipmunk , do follow us here.

Bonus

Check out another interesting digital arithmetic problem here !