Finite State Machine – Designing FSM for x/3

state-machines

I was asked to design a FSM for outputting x/3 without the remainder.

This should be implemented using a synchronous system defined as follows:

input: on each clock cycle t, one bit x[t]

output: on each clock cycle t, one bit y[t]

functionality:

let x be a number represented by concatenation of the input bits where x[t] is the LSB

let y be a number represented by concatenation of the output bits where y[t] is the LSB

so y is the result of x/3 (the floor function with x/3 as argument)

e.g.:

t 1 2 3 4

x[t] 1 0 1 0

y[t] 0 0 1 1

I am including two attempts, yet neither is actually yielding the correct result but rather the remainder (i.e. x mod 3), right? They were both intended to yield x/3 and yet it seems they both yield the remainder instead.

Best Answer

I think you already did pretty much the right thing. The table looks like this:

$$\begin{array}{r|cc} & \textrm{bits:}\\ & 0 & \quad1\\ \hline \textrm{states:}\quad0 & 0:`0\textrm' & \quad1:`0\textrm'\\ 1 & 2:`0\textrm' & \quad 0:`1\textrm'\\ 2 & 1:`1\textrm' & \quad 2:`1\textrm' \end{array}$$

You enter (start) at state 0 and then index into the table as bits arrive. So the state diagram looks like:

I've added the "emit" parts, as this is what is needed for you to get the quotient. (Obviously, the remainder is the state itself.) You will need some method of accumulating bits that are emitted (shift register, for example.)

Here are the results for all four-bit input values:

$$\begin{array}{r|cc} \textrm{input} & \textrm{emitted output} & \textrm{remainder (state)}\\ \hline 0000 & 0000 & 0\\ 0001 & 0000 & 1\\ 0010 & 0000 & 2\\ 0011 & 0001 & 0\\ 0100 & 0001 & 1\\ 0101 & 0001 & 2\\ 0110 & 0010 & 0\\ 0111 & 0010 & 1\\ 1000 & 0010 & 2\\ 1001 & 0011 & 0\\ 1010 & 0011 & 1\\ 1011 & 0011 & 2\\ 1100 & 0100 & 0\\ 1101 & 0100 & 1\\ 1110 & 0100 & 2\\ 1111 & 0101 & 0 \end{array}$$

Related Solutions

Finite State Machine for Synchronous Circuit

Assuming:

Q0 is the output of the DFF on the left,
Q1 is the output of the DFF on the right,
Q0+ = Q0* = Q0 next,
Q1+ = Q1* = Q1 next

We can derive expressions for the values Q0*, Q1*, F and G from observations of the circuit.

F = Q0 (connected to output of Q0 DFF)
G = Q1 (connected to output of Q1 DFF)
Q1* = Q0 (connected to output of Q0 DFF)
Q0* = ~Q1 (connected to inverted output of Q1 DFF)

You may notice that all of the above equations only depend on the Q0 and Q1 state registers. This means this is a Moore FSM since the output depends only on the present state. We can build the entire truth table from just the Q0 and Q1 states on the left side:

Truth Table

Q1 Q0 | Q1* Q0* G F
-------------------
0  0  | 0   1   0 0
0  1  | 1   1   0 1
1  0  | 0   0   1 0
1  1  | 1   0   1 1

Electronic – Finite State Machine

An FSM typically has 2 always blocks: 1 sequential (with a clock), 1 combinational (no clock). Assuming you have a clock and an asynchronous reset (untested):

module FSM(D1,D2, NextState, clk, rst);
input D1,D2,clk,rst;
output [1:0] NextState;
reg [1:0] CurrentState;
reg [1:0] NextStateOut;
parameter S0=2'b00, S1=2'b10, S2=2'b11, S3=2'b01;

always @(posedge clk or posedge rst) begin
    if (rst) begin
        CurrentState <= S0;
    end else begin
        CurrentState <= NextStateOut;
    end
end

always @*
 begin
 case(CurrentState)
 S0:
 begin
    if(D1==1'b0 && D2==1'b0)
        NextStateOut =S0;
    if(D1==1'b1 && D2==1'b0)
    begin
        NextStateOut =S1;              
    end
end
S1:
begin
    if(D1==1'b0 && D2==1'b0)
    begin
        NextStateOut =S0;          
    end
    if(D1==1'b1 && D2==1'b0)
        NextStateOut =S1;
    if(D1==1'b1 && D2==1'b1)
    begin
        NextStateOut =S2;                  
    end
end
S2:
begin
    if(D1==1'b1 && D2==1'b0)
    begin
        NextStateOut =S1;      
    end
    if(D1==1'b1 && D2==1'b1)
        NextStateOut =S2;
    if(D1==1'b0 && D2==1'b1)
    begin
        NextStateOut =S3;                  
    end
end
S3:
begin
    if(D1==1'b1 && D2==1'b1)
    begin
        NextStateOut =S2;
                end
    if(D1==1'b0 && D2==1'b1)
        NextStateOut =S2;
    if(D1==1'b0 && D2==1'b0)
    begin
        NextStateOut =S0;           
    end
end
endcase
end

assign  NextState= NextStateOut;

endmodule

Some modifications:

Combo always block uses @*
Use blocking assignments (=) in combo block
Use S0 parameter instead of 2'b00 in last assignment.

Best Answer

Related Solutions

Finite State Machine for Synchronous Circuit

Electronic – Finite State Machine

Related Topic