FSM - finite state machine

[elecs_gene]

hi guys,
could u please help me in developing the state machine for detecting multiples of 5..that is output is 1 if any multiple of 5 is detected..the input comes serially..after the each input,you have to store it in some sort of infinite register and check for multiple of 5..

mukund

 

[Davood Amerion]

can you explain about input words format . is it integer, binary, bcd, 2 digit, n digit?

 

[elecs_gene]

the input is binary..the actual problem is that multiples of 5 don't follow a pattern such as---101 for 5,1010 for 10,1111 for 15 etc....that is the problem..

with regards

 

[jearome]

I think you should use division operation

 

[elecs_gene]

hi
if u say u have to use division,how can u implement it using an fsm??moreover,it should be good enough to detect any multiple of 5..

regards

 

[tkbits]

If your input is bit serial with MSB first, then you can check if the current bit string you have received is divisible by 5.

I don't know how you can check the divisibility using only the bit pattern. If you add a subtraction unit and a register, the state machine will be simple. You will need a separate condition to indicate when you have reached the end of the number.

 

[noloser]

is it die die must be model in FSM? this shall be much easier if you model in behaviour mode. just capture the serial input, convert it to integer and check for the value mod 5 equal to 0 will do the work.

 

[OvErFlO]

I think that the better solution is an infinity ROM... if you can't find periodicity in the number multiply of 5.

in the second use a Divider unit... but if you need speed it isn't a better solution...

 

[Hero]

Yes

I think that ROM is better solution than FSM or arithmetical unit. You need to generate appropriate ROM table and directly detect multiples of five. For 8-bit input data you need only 256 bytes of memory. Connect input data bus to ROM address bus and use ROM output bus for detection.

 

[verilog_coder]

I have one scheme in mind.it is something like it. You need to have your own buffer to compare the incoming stream . I am assuming the stream is coming with lsb arriving first. now initially store the value 5 in your buffer say temp buffer.

if temp buffer is equal to stream buffer.
{
set divide by 5 output high.
increase temp buffer by 5.
}
else if{
stream buffer value is greater than temp buffer
{
increase temp buffer by 5.
set divide by 5 output low.
}
else
{
temp buffer retains its value.
set divide by 5 output low.
}

 

[nand_gates]

Here goes the solution!
The idea here is we need to convert the infinite bin no. to BCD we should only
look for BCD LSB if it is 0 or 5 the no. is divisible by 5!
Rest the code will explain!
Hope this helps

module div5(
// Outputs
y,
// Inputs
clk, reset_n, d
);
input clk, reset_n;
input d;
output y;

reg [3:0] q_reg;
reg [3:0] q_reg_nx;

assign y = (q_reg == 5) || (q_reg == 0);

always @(posedge clk or negedge reset_n)
if (!reset_n)
q_reg <= 0;
else
q_reg <= q_reg_nx;

always @(d or q_reg) begin //shift and decimal adjust the lsb
q_reg_nx = {q_reg[2:0], d};
if (q_reg_nx > 9 || q_reg[3])
q_reg_nx = {q_reg[2:0], d} + 6;
end
endmodule // div5

 

[tkbits]

Why bother with converting to BCD?

If you divide by 5, a remainder of 0 means the number is divisible by 5.

 

[nand_gates]

HI tkbits
Please check the problem definition first!
It says the number is in infinite shift register into which we are shifting the data in bits!

 

[tkbits]

The LSD of a BCD number is the remainder of a divide by 10 operation.

So just divide by 5 and check for the remainder of 0.

 

[benzwishc]

XOR operation by"101" or its multiply

 

[agilbert]

Because I can't find anything on the internet... This is a FSM that does it.

 

[permute]

this is a pretty classic interview question.

The solution is simple:
you have 5 states -- a%5 = 0, a%5 = 1, ...

state 0: (implies a%5 = 0, a divisible by 5). 2a would be divisible by 5, so transition to self. 2a+1 would have a remainder of 1, transition to 1.
1: 2a would have a remainder of 2. 2a+1 would have a remainder of 3
2: 2a would have a remainder of 4, 2a+1 would have a remainder of 0
3: 2a would have a remainder of 1, 2a+1 would have a remainder of 2
4: 2a would have a remainder of 3, 2a+1 would have a remainder of 4

the "shift in 0 from lsb" would give 2a. "shift in 1" gives 2a+1.

five is typically used because it is non-trivial (like 2^n), but not laborious like higher numbers.