How would one go about building a sequential circuit that produces an output of 1 if the input sequence of binary bits is divisible by 5? I've been racking my brain at this for a while but can't figure it out. For the longest time I was thinking of just looking at the last 4 bits and see if they equal decimal 5 or 0 but then I realized that wouldn't work at all. Something like: 001110000000 is 896 in decimal so no go there. My circuit should also be able to handle any number of input bits. Can anyone give me some tips on how to approach this?
Some hints to point you in the right direction (since this is clearly coursework):
0to the end of a binary number has the effect of multiplying it by 2. Adding a
1multiplies it by 2, then adds 1.
For a number
xto be divisible by 5,
x % 5 = 0(where
%is the modulus operator).
(x * 2) % 5and
(x * 2 + 1) % 5would look like for the five cases
x % 5 = 0,
x % 5 = 1…
x % 5 = 4. Draw these out as a state diagram. Now implement it in hardware.
What you are looking at is a modulo operation, which is the remainder after division. There are hardware algorithms for this but fast ones are not all that simple.
If you calculate x % 10 you will get a number from 0 to 9 for the modulo. If the modulo is 0 you know it is divisible by 5 or 10, if it is 5 you know it is divisible only by 5.
The simplest (and the least efficient for large numbers) way of doing division is by repeated subtraction. If you subtract 10 (0x0A) from your unknown number until the result is less than 0x0A you have the modulo. For division you would keep track of the number of times you subtracted 0x0A, but in this case you don't need to keep track, since you are only interested in the remainder, not the quotient.
You can use the Google calculator to play with this, simply by typing this into the search window:
896 % 10
for your example.. giving a result of 6.
This is just to expand on duskwuf answer, to make it a little bit clearer, without giving it all away.
The idea is that you can shift the number bit by bit, starting with the most significant bit, and every time you shift in, you can be in one of five states (one for every possible modulo 0~4), and after shifting in all the bits, the state in which you are in determines if it is divisible by 5.
The hints are about figuring out what the state diagram is, every time you shift in a new bit.
For example, you start at state 0, and you are going to start shifting in your example number
Your states would go as follows:
Number: 001110000000 State : 001324312431
After shifting in the last bit, the state becomes 1 (as in modulo 5 being 1), so the number is not divisible by 5.
The rules to determine the state diagram are based on the fact that every time you shift a bit in, you are multiplying by 2 and adding either 0 or 1, depending on the new bit being shifted in. The next state only depends on the previous state and the new bit, so the hardware is very simple. The disadvantage is that you need as many clock cycles as input bits. But since no restrictions have been specified, there is no problem.
You may need to add a bit counter and/or some kind of synchronization signal.