State Machine

Project 12: Serial Adder

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 the Xilinx® ISE WebPACK™ 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 circuit using ISim.
  • 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.

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.
  4. Now let's consider the case when one of the inputs (A, 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. 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 \oplus B$. 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.
    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
    					

  • Other product and company names mentioned herein are trademarks or trade names of their respective companies. © 2014 Digilent Inc. All rights reserved.