Continue to Site

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
 

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

    V

    Points: 2
    Helpful Answer Positive Rating
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
 

I think you should use division operation
 

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
 

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.
 

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.
 

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...
 

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.
 

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.
}
 

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
Why bother with converting to BCD?

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

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!
 

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.
 

XOR operation by"101" or its multiply
 

Because I can't find anything on the internet... This is a FSM that does it.
div5.jpg
 
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

Back
Top