Analyze and Design Sequential circuit#

Sensitivity List#

1. Once using sensitivity list (posedge, negedge), then all signal must use sensitivity list.
2. assign use <=. (In sequential circuit always @(posedge clk), rather than use =. (in combinational circuit always @*)

	<=	=
Using timing	Sequential circuit	Combinational circuit
Meaning	Use old value	Use new value
Example

3. Results of operators (at the left side of assignment) inside always block must be declared as register, for example:

// Code A
reg z;
wire c;
always @* begin
    z = x || y
    c = x || y // wrong code
end
        
// Code B
wire z;
assign z = x && y // z is not a reg here

4. There are two types of coding:

// Style 1 : Combinational circuit and sequential circuit are seperate
reg [3:0] count1, next_count1;
always @(posedge clk) // Sequnetial part
    count1 <= next_count1;
always @* begin // Combinational part
    if (reset) 
        next_count1 = 0;
    else 
        next_count1 = (count1 == 4) ? 0 : count1 + 1;
end
assign enable1 = (count1 == 4);

// Style 2 : Combinational circuit and sequential curcuit are together
reg [3:0] count2;
always @(posedge clk) begin
    if (reset) 
        count2 <= 0;
    else 
        count2 <= (count2 == 4) ? 0 : count2 + 1;
end
assign enable2 = (count2 == 4);

Finite-State Machine (FSM)#

• Sychronous sequential circuit (a.k.a. clocked sequential circuit) is a kind of Finite-State Machine.
• Current state at time $t$ is stored in a set of flip-flops.
• (input, current state) => (output, next state) next state at time $t+1$ is a boolean function of the present state and input.

Different types of output function decides different types of circuit.

Mealy machine (circuit)#

Info:

The output is a function of both present state and input.

And here is an example state diagram:

digraph mealy{
    layout = circo
    node [shape = circle];
    s1 -> s1 [label = "1/1"];
    s1 -> s2 [label = "0/1"];
    s0 -> s1 [label = "1/0"];
    s0 -> s2 [label = "0/0"];
}

Moore machine (circuit)#

Info:

The output is a function of present state only.

And here is an example state diagram:

digraph moore{
    layout = circo
    node [shape = circle];
    k [shape = point];
    s0 [label = "s0\n 00"];
    s1 [label = "s1\n 01"];
    s2 [label = "s2\n 11"];
    k -> s0 ;
    s1 -> s1 [label = "1"];
    s1 -> s2 [label = "0"];
    s0 -> s1 [label = "1"];
    s0 -> s2 [label = "0"];
}

Analysis#

Illustration#

Ok, lets start analyzing. First, take a look at this example: First, look at the combinational part, we can obtain:

process:

Also, we have known that in a D flip-flop, $Q(t+1) = D$. So we will get:

Hence, we can get:

After this process, we want to record the status as truth table,so we define a status table. There are two ways to represent: After this, we can use a state diagram to represent the transition. Info:

State diagram#

• circle : a state
• directed line : transition between the states
• On the edge, it is either output (Moore) or input/output(Mealy).

digraph state_diagram{
    node [shape = circle];
    layout = circo;
    00 -> 00 [label = "0/0"];
    10 -> 10 [label = "1/0"];
    00 -> 01 [label = "1/0"];
    01 -> 00 [label = "0/1"];
    01 -> 11 [label = "1/0"];
    11 -> 00 [label = "0/1"];
    11 -> 10 [label = "1/0"];
    10 -> 00[label = "0/1"];
    
}

Now, we can have the step to analyze a sequential circuit:

Lets look at another example.

Example_01 Analyze with DFF#

Look at this circuit, we can get:

Example_02 Analyze with JKFF#

We can find these equations:

We then apply the characteristic equation $Q(t+1)=JQ'(t)+K'Q(t)$:

Complete the state table and diagram:

Example_03 Analyze with TFF#

By observation, we can get:

Then by the characteristic equation $Q(t+1)=T \oplus Q$:

Complete the state table and diagram:

Design#

Illustration#

There is a procedure to produce a sequential circuit: Info:

1. Determine a state diagram or state table.

2. State reduction if necessary.

3. Assign binary values to the states. obtain binary-coded state table

4. Choose the type of flip-flops. derive the simplified flip-flop input equations and output equations

5. Obtain the logic diagram.

Without further ado, lets look at a example.

Example_01 String Detector#

Success:

Illustration#

Construct a recognizer that takes one bit at a time and generates an output $Z=1$ when and only when the sequence $\{1101\}$ is detected at the input.

Input#

The input $X$ is the continous signal that you need to detect.

Output#

The output $Z$ is $1$ if there is a sequence $\{1101\}$ and $0$ otherwise.

Here is an example:

Lets define four states:

• $A$ : there is no any char correspond to $1101$.
• $B$ : so far, we have $1$.
• $C$ : so far, we have $11$.
• $D$ : so far, we have $110$.

We can design like this:

First, we can construct the straight way to output $1$.

digraph design{
    layout = circo
    node [shape = circle]
    
    A -> B [label = "1/0"];
    B -> C [label = "1/0"];
    C -> D [label = "0/0"];
    D -> B [label = "1/1"];
}

Now, consider those fail condition.

digraph design{
    layout = circo
    node [shape = circle]
    
    A -> B [label = "1/0"];
    A -> A [label = "0/0", color = red];
    B -> C [label = "1/0"];
    B -> A [label = "0/0", color = red];
    C -> D [label = "0/0"];
    C -> C [label = "1/0", color = red];
    D -> B [label = "1/1"];
    D -> A [label = "0/0", color = red];
}

Then we have the state diagram! Here is the corresponding state table:

For futher implementation, we need to use binary code to encode those states.

Remember that different binary code assignments may result in different final circuit with different time complexities.

Now, for example, we encode these four states like this, and thus we have:

digraph design{
    layout = circo
    node [shape = circle]
    A [label = "00"];
    B [label = "01"];
    C [label = "11"];
    D [label = "10"];
    A -> B [label = "1/0"];
    A -> A [label = "0/0"];
    B -> C [label = "1/0"];
    B -> A [label = "0/0"];
    C -> D [label = "0/0"];
    C -> C [label = "1/0"];
    D -> B [label = "1/1"];
    D -> A [label = "0/0"];
}

Now, we are going to implement with D filp-flop. We use $ab$ to represent the current state (If State is $01$, then $a = 0, b = 1$). First, we need to write out the logic equations. details:

By using K-map: We can have reduced SOP form.

Then by a little reduction on $a(t+1)$, we can have:

Since we want to use D flip-flop, we can use its characteristic equation $Q(t+1)=D$ to create the storage part.

Hence, we can get the circuit.

Example_02 Vending Machine#

Success:

Illustration#

There are two kinds of coins, one is nickel and one is dime, the relationship is 1 dime = 2 nickels.

Now, design a circuit to determine whether to output a merchandise which price is 3 nickels.

Input#

There are three types of input:

• $N$ (Nickel) : insert a nickel.
• $D$ (Dime) : insert a dime.
• $Reset$ : back to the initial condition.

Output#

There is one output:

• $Open$ : 0 is not and 1 is output the merchandise.

First, we can obseve that there are only 5 possible sequence to activate open:

digraph vending{
    rankdir = LR
    node [shape = circle]
    k [shape = point]
    k -> s0 [label = "Reset"];
    s0 -> s1 [label = "N"];
    s0 -> s2 [label = "D"];
    s1 -> s3 [label = "N"];
    s1 -> s4 [label = "D"];
    s3 -> s7 [label = "N"];
    s3 -> s8 [label = "D"];
    s2 -> s5 [label = "N"];
    s2 -> s6 [label = "D"];
    s7, s8, s4, s5, s6 [color = "red"]
}

Those states with red color means $Open$ should output 1, otherwise should output 0.

By State reduction (let every state be the current dollor), we can obtain the state diagram like this:

digraph state{
    rankdir = LR
    node [shape = circle];
    k [shape = point];
    0 [label = "0 Nickel"];
    1 [label = "1 Nickel"];
    2 [label = "2 Nickel"];
    3 [label = "3 Nickel\n [open]", color = "red"];
    k -> 0 [label = "Reset"];
    0 -> 0 [label = "D'N'"];
    0 -> 1 [label = "N"];
    0 -> 2 [label = "D"];
    1 -> 1 [label = "D'N'"];
    1 -> 2 [label = "N"];
    1 -> 3 [label = "D"];
    2 -> 3 [label = "D, N"];
    2 -> 2 [label = "D'N'"];
    3 -> 0 [label = "*"]
}

We can encode as follow and get the state table:

Next, obtain the state equations: details:

By K-Map: We can have the SOP form:

Using D flip-flop, we can have the characteristic equation $$ \begin{align} D_a &= ab’+Na’+Da’b\ D_b &= DN’b’+D’a’b+Nab’\ Open &= ab \end{align}

\begin{align} J_A &= BX’\ K_A &= BX \ J_B &= X \ K_B &= (A \oplus X)’ \ \end{align}

\begin{align} T_{A2} &= A_1A_0 \ T_{A1} &= A_0 \ T_{A0} &= 1 \ \end{align}

Two states of a FSM are equivalent if \the outputs produced for each possible input value are identical\and the next states for each possible input value are the same or equivalent