Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronics Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

FSM - finite state machine

Status
Not open for further replies.

elecs_gene

Member level 2
Joined
Dec 20, 2005
Messages
52
Helped
3
Reputation
6
Reaction score
1
Trophy points
1,288
Activity points
1,797
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

Advanced Member level 2
Joined
Mar 1, 2005
Messages
584
Helped
116
Reputation
232
Reaction score
24
Trophy points
1,298
Location
Persia
Activity points
6,351
can you explain about input words format . is it integer, binary, bcd, 2 digit, n digit?
 

    V

    Points: 2
    Helpful Answer Positive Rating

elecs_gene

Member level 2
Joined
Dec 20, 2005
Messages
52
Helped
3
Reputation
6
Reaction score
1
Trophy points
1,288
Activity points
1,797
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

Junior Member level 3
Joined
Sep 1, 2005
Messages
26
Helped
0
Reputation
0
Reaction score
0
Trophy points
1,281
Activity points
1,460
I think you should use division operation
 

elecs_gene

Member level 2
Joined
Dec 20, 2005
Messages
52
Helped
3
Reputation
6
Reaction score
1
Trophy points
1,288
Activity points
1,797
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

Full Member level 5
Joined
Dec 4, 2004
Messages
242
Helped
39
Reputation
78
Reaction score
2
Trophy points
1,298
Activity points
2,209
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

Junior Member level 1
Joined
Jan 21, 2006
Messages
17
Helped
0
Reputation
0
Reaction score
0
Trophy points
1,281
Location
Singapore
Activity points
1,455
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

Full Member level 3
Joined
Dec 7, 2001
Messages
178
Helped
7
Reputation
14
Reaction score
3
Trophy points
1,298
Activity points
1,356
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

Full Member level 2
Joined
Mar 6, 2002
Messages
145
Helped
4
Reputation
8
Reaction score
2
Trophy points
1,298
Activity points
1,608
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

Member level 3
Joined
Jan 4, 2006
Messages
55
Helped
4
Reputation
8
Reaction score
2
Trophy points
1,288
Location
Pakistan
Activity points
1,725
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

Advanced Member level 3
Joined
Jul 19, 2004
Messages
892
Helped
175
Reputation
350
Reaction score
51
Trophy points
1,308
Activity points
6,838
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
 

    elecs_gene

    Points: 2
    Helpful Answer Positive Rating

tkbits

Full Member level 5
Joined
Dec 4, 2004
Messages
242
Helped
39
Reputation
78
Reaction score
2
Trophy points
1,298
Activity points
2,209
Why bother with converting to BCD?

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

nand_gates

Advanced Member level 3
Joined
Jul 19, 2004
Messages
892
Helped
175
Reputation
350
Reaction score
51
Trophy points
1,308
Activity points
6,838
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

Full Member level 5
Joined
Dec 4, 2004
Messages
242
Helped
39
Reputation
78
Reaction score
2
Trophy points
1,298
Activity points
2,209
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

Junior Member level 1
Joined
Dec 16, 2005
Messages
16
Helped
2
Reputation
4
Reaction score
1
Trophy points
1,283
Activity points
1,400
XOR operation by"101" or its multiply
 

agilbert

Newbie level 1
Joined
Oct 14, 2011
Messages
1
Helped
1
Reputation
2
Reaction score
1
Trophy points
1,283
Activity points
1,284
Because I can't find anything on the internet... This is a FSM that does it.
div5.jpg
 

permute

Advanced Member level 3
Joined
Jul 16, 2010
Messages
923
Helped
295
Reputation
590
Reaction score
268
Trophy points
1,343
Activity points
8,543
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.
 
Status
Not open for further replies.

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Top