Lab 3 Finite State Machine
===
> Required time : 12 hour

[TOC]

---

## Q1 Sequential Circuit
In assignment 4, we have already introduced how DFF worked and how to design a DFF using two latches.

Now, let's introduce an alternative way to model DFF.

The following code is an example.

always@(posedge clk) begin
    if (!rst) begin
        q <= 1'b0;
    end else begin
        q <= d;
    end
end

We summarize some points here:
- `posedge clk`: only trigger this always block when `clk` is on positvie edges.
- `q <= next_q`: <font color=#bf2222>In `DFF` always block, you have to use `<=` instead of `=`.</font> However, you have to use `=` in other always blocks which are not triggered by `clk`.

- It is common practice to have no more than **<font color=#bf22222>one</font>** DFF block in a module.

- In DFF, `rst` signal is usually used to reset a flip flop. <font color=#bf2222>If we don't mention in this lab, the default reset values in DFF are `0`.</font>

- In this lab, reset the DFF, <font color=#bf2222>when `rst = 1'b0`</font>.

- In a `DFF` always block, signals will be updated **<font color=#bf2222>simultaneously</font>**. for example:

always@(posedge clk) begin
    if(!rst) begin ... 
    end else begin
        q1 <= q1 + 1;
        q2 <= q1;
    end
end

Then the signals will be:

clk: 1, 2, 3, 4, 5, 6,
-----------------------------
q1 : 1, 2, 3, 4, 5, 6 ...
q2 : 0, 1, 2, 3, 4, 5 ...

(suppose the default value of {q1,q2} are {1,0})

The DFF always block upates `q2` according to previous value of `q1`, not the current `q1`.

- Please refer to [FSM](https://hackmd.io/ntyIA5KbSIK3eJTqGSwDYA) for more details.

---

In this question, you have to convert the following code by replacing `DFF` module with `DFF` always block.

module q1_init(clk, rst, in1, in2, out1, out2);
    input clk, rst, in1, in2;
    output out1, out2;

    wire next_out1, next_out2;

    DFF dff1(.clk(clk), .rst(rst), .d(next_out1), .q(out1));
    DFF dff2(.clk(clk), .rst(rst), .d(next_out2), .q(out2));

    assign next_out1 = in1 & in2;
    assign next_out2 = in1 | in2;


endmodule 

module Flip_Flop (clk, rst, d, q);
    input clk, d;
    output q;
    wire n_clk, _q, temp;

    not no (n_clk, clk);
    Latch Master ( .clk (n_clk), .d (d), .q (_q) );
    Latch Slave  ( .clk (clk), .d (_q), .q (temp) );

    assign q = (!rst) ? 1'b0 : temp;
    
endmodule

module Latch (clk, d, q);
    input clk;
    input d;
    output q;
    // our design
    wire not_d, not_q, a1, a2;

    not n1 (not_d, d);
    nand na1 (a1, d, clk);
    nand na2 (a2, not_d, clk);
    nand na3 (q, a1, not_q);
    nand na4 (not_q, a2, q);
endmodule

module q1(clk, rst, in1, in2, out1, out2);
    input clk, rst, in1, in2;
    output out1, out2;
    
    // ...
    
    // DFF
    always@(posedge clk) begin
        if (!rst) begin
            out1 <= ...;
            out2 <= ...;
        end else begin
            //...;
            //...;
        end
    end
    
    // datapath
    assign next_out1 = ...;
    assign next_out2 = ...;


endmodule

---
## Q2 Fibonacci Sequence
Fibonacci sequence is defined as:

$F_{0}=0$
$F_{1}=1$
$F_{n}=F_{n-1}+F_{n-2}$,, $n \geq 2$

Please design a circuit to calculate fibonacci sequence and reset `f` to `32'b1` when `rst = 1'b0`.

module q2(clk, rst, f);
    input clk, rst;
    output [31:0] f;
    // ...

    // DFF
    always@(posedge clk) begin
        if (!rst) begin
            f    <= 1'b1;
            fn_1 <= ...;
        end else begin
            // hint: definition
            f    <= ...; 
            fn_1 <= ...;
        end
    end

endmodule


---
## Q3 Separation of Computation from Sequential DFF Block (<font color=#bf2222>**Important!!!**</font>)

Due to the constraints of DFF, we do not suggest to do any computation in a DFF always block. It may easily cause unexpected delay and glitch.

As a result, we have to separate the combinational logic (computation) from the sequential DFF block.

In this question, you have to divide Q2 into a combinational logic block and a DFF block.

module q3(clk, rst, f);
    input clk, rst;
    output [31:0] f;
    
    // ...

    // DFF 
    always@(posedge clk) begin
        if (!rst) begin
            f    <= ...;
            fn_1 <= ...;
        end else begin
            f    <= next_f;
            fn_1 <= next_fn_1;
        end
    end
    
    // datapath
    assign next_f = ...;
    assign next_fn_1 = ...;

endmodule

---
## Q4 State Transition

In sequential circuits, states help us divide a job into small pieces.

For example, we can do part A in state 1 and do part B in state 2 ...

There are some reasons why we divide a job.

One of the reasons is that a job is so complicated that it cannot be finished in a clock cycle, so we devide the job into pieces and do them in multiple clock cycles.

Another one is dependency. Sometimes, the signals are not independent, they depends on previous values or other signals( e.g. input signals). As a result, we do certain computation(or action) in the first cycle, and do another one in the second cycle.

Condition is also a reason. State transition can decide the next computation (or action), according to the input signals (or previous values).

---
### Part 1 Moore Machine
In this question, you are asked to design a circuit that follows the given state transition diagram (It's a moore machine).

Reset the state to `S0` when `rst = 1'b0`

The output signal `out` is the current state:

S0: 2'd0;
S1: 2'd1;
S2: 2'd2;
S3: 2'd3;


`define S0 2'd0
`define S1 2'd1
`define S2 2'd2
`define S3 2'd3

module q4_1(clk, rst, in, out);
    input clk, rst, in;
    output [1:0] out;
    //...
    
    // DFF
    always@(posedge clk) begin
        if (!rst) begin
            state <= `S0;
        end else begin
            state <= next_state;
        end
    end
    
    // datapath
    always@(*) begin
        case(state)
        `S0: begin
            next_state = (in == 1'b1) ? `S0 : `S1;
        end
        
        // ...
        endcase
    end

    // datapath
    always@(*) begin
        case(state)
        `S0: begin
            out = ...;
        end
        // ...
        endcase
    end

endmodule

---

### Part 2 Mealy Machine
Enhance the circuit (`q4_1`) with the following functions.

Reset `ans = 32'd0` when `rst = 1'b0`.

> The output signal out is the current state. (same as q4_1)

{state, in}
{S0, 0} : ans = ans + 32'd10;
{S0, 1} : ans = ans - 32'd10;
{S1, 0} : ans = ans + 32'd87;
{S1, 1} : ans = ans + 32'd88;
{S2, 0} : ans = 32'd0;
{S2, 1} : ans = 32'd5;
{S3, 0}: ans = ans * 5;
{S3, 1}: ans = ans * 10;

`define S0 2'd0
`define S1 2'd1
`define S2 2'd2
`define S3 2'd3

module q4_2(clk, rst, in, out, ans);
    input clk, rst, in;
    output [1:0] out;
    output [31:0] ans;

    //...

    // DFF
    always@(posedge clk) begin
        if (!rst) begin
            state <= `S0;
            ans   <= 32'd0;
        end else begin
            state <= next_state;
            ans   <= next_ans;
        end
    end
    // datapath 
    ...

    // datapath
    always@(*) begin
        case(...)
        ...: begin
            next_ans = ...;
        end
        ...
        endcase
    end

endmodule

Please answer the following questions in your report.

1. The difference between moore and mealy machine.
2. The reason why part1 is a moore machine.
3. The reason why part2 is a mealy machine.

---
## Q5 Sequence Detector

Please design a circuit to detect the sequence `1101`. A sequence detector produces `out = 1` if the consecutive input signals are `1101`; otherwise, `out = 0`.For example,

example 1
-----------|.....|-------|.....|-------
in : 0,0,0,1,1,0,1,1,0,0,1,1,0,1,0,0...
out: 0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0...
.................^.............^.........


example 2
-----|.....|.....|-------------
in : 1,1,0,1,1,0,1,0,0,0,1,0,0...
out: 0,0,0,1,0,0,1,0,0,0,0,0,0...
...........^.....^...............


1. Draw the state transition diagram on your report.
2. Design the circuit based on the state transition diagram.

> Hint: It is a Mealy Machine.

module q5(clk, rst, in, out);
    input clk, rst, in;
    output out;
    
    // DFF
    always@(posedge clk) begin ...
    
    // datapath 
    // ...

endmodule

:::danger
6/1 Hint 2
Note that this state transition diagram is not complete. You have to finish it by yourselves.
:::

## Q6 Sequence Detector 2
A sequential circuit has two inputs, `a` and `b`, and an output `z`. Its function is to compare the input sequences on the two inputs. If `a = b` during any four consecutive clock cycles, the circuit produces `out = 1`; otherwise, `out = 0`. For example,

------|.....|---|.........|-----
a : 0,1,1,0,1,1,1,0,0,0,1,1,0 ...
b : 1,1,1,0,1,0,1,0,0,0,1,1,1 ...
out:0,0,0,0,1,0,0,0,0,1,1,1,0 ...
............^.........^ ^ ^......

module q6(clk, rst, a, b, out);
    input clk, rst, a, b;
    output out;
    
    // DFF
    always@(posedge clk) begin ...
    
    // datapath 
    //...

endmodule

---
## Assignment Rule

1. Deadline: <font color=#bf2222>**6/6**</font>

2. Submit your code to ILMS. Please upload the questions separately. <font color=#bf2222>**Do not** zip them</font>.

3. The file content tree should look like:
- q1.v
- q2.v
- q3.v
- q4_1.v
- q4_2.v
- q5.v
- q6.v
- lab3_StudentID<font color=#bf2222>**.pdf**</font> (ex. `lab1_105066666.pdf`)

**<font color=#bf2222>wrong filename = no point.</font>**
**<font color=#bf2222>wrong module name = no point.</font>**

4. Answer the question in Q4 and draw the state transition diagramin of Q5 in your report.
- Up to 3 pages.

5. We will judge your code by our testbenches (not released testbenches).