# Project 11: Building a Serial Adder Using a State Machine

## Introduction

In this project, we 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, we 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.

Before you begin, you should:

- Have Vivado installed.
- Have your FPGA board set up.
- Be able to describe digital circuits using logic operators.
- Be able to write a test bench and simulate circuits using Vivado's simulator.
- Be able to describe sequential circuits using an always block.

After you're done, you should:

- Be able to use the state diagram to describe the functionality of a digital system.
- Be able to describe the state diagram in Verilog.

## Inventory

- Digilent Nexys A7 or Basys 3 FPGA Board
- Vivado Installation

## Step 1: Describe the Serial Adder Using the State Diagram

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

2. 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 will define that both outputs will be initialized to be 0, as shown in Fig. 1 below.

*Figure 1. Defining output initialization.*

3. Now, we will try to see where we will 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 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.

*Figure 2. Self loop diagram.*

Figure 3. New state diagram.

5. Now, 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.Figure 4. Transition from S0 to S2.

6. 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.Figure 5. State diagram repeating previous steps.

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

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 S4.8. As we have one more state from last step, we need to consider all of the input patterns starting from S4. You can do it on your own and check your result with the one shown in Fig. 7 below.

*Figure 7. State diagram starting from S4.*

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

*Figure 8. State machine.*

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.

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

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

2. 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, we 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;

3. We need to declare internal signals for the next state and the present state. In this example, we only have four states. As we 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;

4. Now we 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

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

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

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