Serial Adders

Introduction to State Machines

8565

Introduction

In this tutorial, you are going to design a serial adder. A serial adder is a circuit that performs binary addition bit by bit (i.e., instead of presenting both operands at the inputs of an adder at the same time, the operands are fed into the serial adder bit by bit and it generates the answer on the fly). To design such a circuit, you are going to use the state diagram as the mode of describing the behavior of the circuit, and then translate the state diagram into Verilog code.

Step 1: Describe the Serial Adder Using the State Diagram

Define Inputs and Outputs

Before designing the state diagram, we always need to define the inputs and outputs first. In this case, we have two data inputs named A and B. Both of them are 1-bit wires. As with the adder we described in the arithmetic circuit, we have a data output F and another output called Cout (Carry Out). We also need a clock signal (named clk here) to provide the timing reference for both the inputs and the outputs and a reset signal (named rst) to bring the circuit into initial state.

Design State Diagram

Every state diagram starts from an initial state. So we will draw a circle to represent the initial state and we will name it S0. When rst is asserted, the circuit should reset to this initial state S0, and we define that both outputs will be initialized to be 0, as shown in Fig. 1 below.

Now, we will try to see where to go from the initial state when inputs come. Let’s consider the case when neither A or B are asserted. If A is 0, and B is 0, the result of the current bit will be 0 with no carry generated. And it is exactly the initial state. So we just need to draw an arrow from S0 to S0 (self loop) and label it $\overline A \cdot \overline B$ , as shown in Fig. 2 below.

Let’s consider the case when one of the inputs A and B is asserted. The result of the current bit should be 1 with no carry out generated. Circuits will certainly be in a different state than the initial state S0. So we will create another state by drawing another circle and labeling it S1. The condition that the circuit will go from S0 to S1 is that one of A and B is 1. We can draw an arrow from S0 to S1 and label it A and B, respectively. When the circuit arrives at state S1, output F should be driven high and Cout remains low. Thus, we label $F=1$ and $Cout=0$ beside state S1. The new state diagram is shown below in Fig. 3.

Starting from initial state, we have one case left that we have not yet considered both A and B are asserted. In this case, the output F is 0 and a carry will be generated. This is certainly another state that is different from either S0 or S1. So we will need to create another state and label it S2. The transition from S0 to S2 should be described as an arrow starting with S0 and ending at S2 with a label $A \cdot B$ as shown in Fig. 4 below.

Now we have three states in the state diagram S0, S1, S2 and we have considered all of the transitions starting from S0. So Let’s start from state S1 and repeat the previous three steps. You can do it on your own and check your new state diagram with Fig. 5 shown below.

We have covered all of the transitions starting from S0 and S1. Now assume that we start from S2. Repeat the steps and check your new state diagram with the one shown in Fig. 6 below.

If you did this correctly, you will notice that when you are in S2, and both A and B are asserted, you need to add the carry generated by the previous bit together with current A and B together, resulting in $F=1$ and $Cout=1$ . This is a state that is different from S0, S1 and S2. So we have the fourth state in the state machine and we will label it S3.

As we have one more state from last step, we need to consider all of the input patterns starting from S3. You can do it on your own and check your result with the one shown in Fig. 7 below.

Step 2: Code a State Machine in Verilog

A state machine is composed of three parts: next state decoding logic, state registers, and output logic, as shown in Fig. 8 below.

The next state logic is a combinational block that implements the state transition logic. In other words, it generates the state code for the next state based on the present state and inputs. The state register updates the current state with the next state logic, calculated by the next state logic at every rising edge of the clock. The output logic is another combinational logic block that asserts the output based on the present state. So we can code the state machine in sections: a combinational block for next state logic, a sequential block for state register, and finally another combinational block for output logic.

Declare Inputs and Outputs

The first step to describe any circuit is the inputs and outputs description. In this serial adder, we have A, B, clk, and rst as inputs and F, Cout as outputs. Feel free to try this on your own first and then check the example code by clicking show/hide code.

`timescale 1ns / 1ps
module SA(
    input A,
    input B,
    output F,
    output Cout,
    input clk,
    input rst
    );

Define States

Instead of using numbers to directly represent states, it is always good practice to define state codes as constant variables so that you can change the state encoding easily in the future. In Verilog, you will use the localparam statement to define constant variables.

// Define State Codes
localparam S0 = 2'b00;
localparam S1 = 2'b01;
localparam S2 = 2'b10;
localparam S3 = 2'b11;

Internal Signals for Current State and Next State

You need to declare internal signals for the next state and the present state. In this example, you only have four states. As you defined the state code to be 2 bits, our next state and present state signals should be two-bits wide.

reg [1:0] pState, nState;

Describe State Diagram in Verilog

Now you need to code the next state logic. As it is a combinational block, we need to put all of the inputs to this block into the brackets after always @. The block will drive the next state signal (nState) based on the present state (pState) signals and inputs (A and B). In state diagrams, we describe state transitions by an arrow starting from present state and pointing to the next state with a label showing input conditions for state transition. It is pretty straightforward to use case statement to describe the state transitions.

// Combinational Logic: Next State Logic
always @ (pState, A, B)
begin
    case (pState)
        S0:begin
            if (A == 1'b0 && B == 1'b0)
                nState = S0;
            else if (A == 1'b1 && B == 1'b1)
                nState = S2;
            else
                nState = S1;
            end
        S1:
            if (A == 1'b0 && B == 1'b0)
                nState = S0;
            else if (A == 1'b1 && B == 1'b1)
                nState = S2;
            else
                nState = S1;
        S2:
            if (A == 1'b0 && B == 1'b0)
                nState = S1;
            else if (A == 1'b1 && B == 1'b1)
                nState = S3;
            else
                nState = S2;
        S3:
            if (A == 1'b0 && B == 1'b0)
                nState = S1	;
            else if (A == 1'b1 && B == 1'b1)
                nState = S3;
            else
                nState = S2;
        default:
            nState = S0;
    endcase
end

The state registers are just D flip-flops with reset signals. The code is as follows:

// State Registers
always @ (posedge(clk), posedge(rst))
begin
    if (rst == 1'b1)
        pState <= S0;
    else
        pState <= nState;
end

Finally, the output logic drives the outputs based on present state and Mealy inputs. In our case, we do not have Mealy inputs. You can use the case statement similar to the next state logic to code the output logic here. In this example, the assign statement is used to show that various syntaxes can be used to describe combinational circuits.

// Output Logic
assign F = (pState == S1 || pState == S3) ? 1'b1 : 1'b0;
assign Cout = (pState == S2 || pState == S3) ? 1'b1 : 1'b0;

By putting all of those pieces shown above together, the file should look like this:

`timescale 1ns / 1ps
module SA(
    input A,
    input B,
    output F,
    output Cout,
    input clk,
    input rst
    );

// Define State Codes
localparam S0 = 2'b00;
localparam S1 = 2'b01;
localparam S2 = 2'b10;
localparam S3 = 2'b11;

reg [1:0] pState, nState;

// Combinational Logic: Next State Logic
always @ (pState, A, B)
begin
    case (pState)
        S0:begin
            if (A == 1'b0 && B == 1'b0)
                nState = S0;
            else if (A == 1'b1 && B == 1'b1)
                nState = S2;
            else
                nState = S1;
            end
        S1:
            if (A == 1'b0 && B == 1'b0)
                nState = S0;
            else if (A == 1'b1 && B == 1'b1)
                nState = S2;
            else
                nState = S1;
        S2:
            if (A == 1'b0 && B == 1'b0)
                nState = S1;
            else if (A == 1'b1 && B == 1'b1)
                nState = S3;
            else
                nState = S2;
        S3:
            if (A == 1'b0 && B == 1'b0)
                nState = S1	;
            else if (A == 1'b1 && B == 1'b1)
                nState = S3;
            else
                nState = S2;
        default:
            nState = S0;
    endcase
end

// State Registers
always @ (posedge(clk), posedge(rst))
begin
    if (rst == 1'b1)
        pState <= S0;
    else
        pState <= nState;
end

// Output Logic
assign F = (pState == S1 || pState == S3) ? 1'b1 : 1'b0;
assign Cout = (pState == S2 || pState == S3) ? 1'b1 : 1'b0;

endmodule