Finite State Machine Design For Sequence Detector

    FSM DESIGN MADE SIMPLE             

       Hie, its been a long time since i updated my blog as i was busy with other projects. In last one month i have received many requests to provide the more details on FSM coding so here is it for you.Today i am going to explain how to create a simple FSM using verilog with an example of sequence detector. FSM is a simple system by itself and its designed to perform certain functions. Take for example traffic light controller ,lift operation, etc.
         

                   Every FSM has fixed states through which it has to pass. For a traffic light the initial state might be "red light on" followed by "saffron on" then "green on". In every state the FSM does some operation and after its completed is moves ahead to the next state. So to design a FSM we have to first define the number states of possible states the system must have. Once number of states are identified we have to specify the task to be done in every state. The last step is to define condition for transition from one state to next. A diagram which shows all the details of FSM is called the state diagram which shows all the states and also shows the condition for transition from present to next state.

Link for the coupons : Here

     Note: every FSM must and should have a reset state. This is because there are possibilities that our system can go to an unknown state which is not defined by us. This can completely make the system remain in that state forever. To avoid such situations "reset " is used to bring back the FSM to a known state.

Steps to build FSM:

1. Identify number of states 
2. Define task to be performed in every state
3. condition for tradition from one state to next
4. Draw a state diagram for the complete system

Consider we have a FSM which must detect the number "0111" which is a sequence. For this problem statement let us try and build a FSM following the steps given above.

Number of states: 

• Reset State
• State 1- detect  "0"
• State 2- detect  "01"
• State 3- detect  "011"
• State 4- detect  "0111"

Draw a state diagram showing states and transition between states as shown below:

            Best practice to build any complex FSM is to first draw the state diagram on paper and then convert it to an equivalent verilog code. Conversion from state diagram to code is quite a simple process , most of the time must be spent in drawing the state diagram correctly rest of the job is not that complicated. Figure below shows to write a code for any FSM in general. Code fragment must look like the one shown below.

Code fragment for any FSM:

module();

//declare all inputs and outputs

-

-

//use two registers , one to hold current state and one for next state

reg [N-1:0]current_state,next_state; 

-where N is number of states.

//declare all states 

-

-

-

-

// define state and state transition here using case statement

-Here we have to mention the transition of states. for example, if the current state is "state0" and if reset if "0" then the next state has to be "state1" and at any state if reset is "1" the next state will be "reset". when FSM is in the last states it goes again back to the first states and the process repeats.

// use control signal to indicate correct results

-In our example of sequence detector when the FSM is in the "state0111" it implies that the sequence is detected so to indicate this we need a signal which will set when state is "0111". 

Conversion from state diagram to Verilog code:

`timescale 1ns / 1ps

////////////////////////////////////////////////////////////////////////////////

// Engineer: Somshekhar R Puranmath

// Design Name:   sequence_0111

// Project Name:  sequence_counter_0111

////////////////////////////////////////////////////////////////////////////////

module sequence_0111(clock, reset, in_bit, out_bit

    );

//declare all inputs and outputs

  input clock, reset, in_bit;

  output out_bit;

  // use registers to hold current and next states

  reg [2:0] state_reg, next_state;

  // State declaration

  parameter    reset_state  =  3'b000;

  parameter    read_zero =   3'b001;

  parameter    read_0_one =   3'b010;

  parameter    read_zero_one_one = 3'b011;

  parameter    read_zero_one_one_one= 3'b100;

  

  // state register , for every clock cycle the FSM  state registers are updated

  always @ (posedge clock or posedge reset)

     if (reset == 1) 

        state_reg <= reset_state; 

     else  

        state_reg <= next_state;

  // next-state logic, transistion from current to next state

always @ (state_reg or in_bit) 

    case (state_reg)

        reset_state: 

              if (in_bit == 0) 

                  next_state = read_zero; 

              else if (in_bit == 1) 

                  next_state = reset_state;

              else next_state = reset_state;

        read_zero: 

              if (in_bit == 0) 

                  next_state = read_zero; 

              else if (in_bit == 1) 

                  next_state = read_0_one;

              else next_state = reset_state;

        read_0_one: 

              if (in_bit == 0) 

                  next_state = read_zero; 

              else if (in_bit == 1) 

                  next_state =  read_zero_one_one;

              else next_state = reset_state;

 read_zero_one_one: 

            if (in_bit == 0) 

                next_state = read_zero;

            else if (in_bit == 1) 

                next_state = read_zero_one_one_one;

            else  next_state = reset_state;

      read_zero_one_one_one: 

            if (in_bit == 0) 

                next_state = read_zero; 

            else if (in_bit == 1) 

                next_state = reset_state;

            else next_state = reset_state;

        default: next_state = reset_state;

  endcase

assign out_bit = (state_reg == read_zero_one_one_one)? 1 : 0; // control signal to indicate sequence //is detected 

endmodule

Test bench for sequence detector:

`timescale 1ns / 1ps

////////////////////////////////////////////////////////////////////////////////

// Engineer: Somshekhar R Puranmath

// Design Name:   sequence_0111

// Project Name:  sequence_counter_0111

////////////////////////////////////////////////////////////////////////////////

module test_ma_sequence;

// Inputs

reg clock;

reg reset;

reg in_bit;

// Outputs

wire out_bit;

// Instantiate the Unit Under Test (UUT)

sequence_0111 uut (

.clock(clock), 

.reset(reset), 

.in_bit(in_bit), 

.out_bit(out_bit)

);

initial begin

// Initialize Inputs

clock = 0;

reset = 0;

in_bit = 0;

// Wait 100 ns for global reset to finish

#10;

reset = 1;

in_bit = 0;

#10;

reset = 0;

in_bit = 0;

#10;

        

 reset = 0;

in_bit = 1;

#10;

reset = 0;

in_bit = 1;

#10;

reset = 0;

in_bit = 1;

#10;

Click Here for reference Book : MUST READ BOOK

// Add stimulus here

reset = 1;

in_bit = 1;

#10;

reset = 0;

in_bit = 0;

#10;

reset = 0;

in_bit = 1;

#10;

reset = 0;

in_bit = 1;

#10;

reset = 0;

in_bit = 1;

#10;

end

 always begin #5 clock=~clock; end    

endmodule

Simulation Results:

RTL schematic:

Do write back to me for more details on FSM coding at verilogblog@gmail.com.. have a nice day

Please Note : Our course is now listed for Udemy training by Industry and leading companies use our courses  :
Analog Design- Intuitive Approach
Rc Circuits Analysis With LT Spice
Basics of Mosfet - Simplified View
Please use these links or share with someone who might be interested.
Note : Author discounts are already applied to these links. 

VHDL to VIRILOG and VERILOG to VHDL

Hello everyone,
Here is a tool which can be used to convert verilog to vhdl and vice-versa. I had tried a lot searching for a free tool online  and finally found this one which is cool to use and easy to operate. You can click on the link below and use it.

I have tried converting few simple VHDL programs to verilog and it works fine.

Here are some snapshots of one such program with steps for conversion:
step 1: run the software

step 2: Click on the tab  " VHDL TO VERILOG"  and also specify the destination directory where you want to save your files

step 3: Click on the tab "translate" and check the results in verilog

Step 4 : verify results

Link for the coupons : Here

Click here to download Tool

Use password as : XHDL65@tech

Do write back to me if it was helpful
  

Please Note : Our course is now listed for Udemy training by Industry and leading companies use our courses  :
Analog Design- Intuitive Approach
Rc Circuits Analysis With LT Spice
Basics of Mosfet - Simplified View
Please use these links or share with someone who might be interested.
Note : Author discounts are already applied to these links. 

verilog code for Booth Multiplier

Refer to "HDL progamming using Verilog and Vhdl " by botros for booth multiplier logic.
or watch this video




CODE:

module booth (X, Y, Z,en);
       input signed [15:0] X, Y;
 input en;
       output signed [31:0] Z;
       reg signed [31:0] Z;
       reg [1:0] temp;
       integer i;
       reg E1;
       reg [15:0] Y1;
       always @ (X, Y,en)
       begin
       Z = 32'd0;
       E1 = 1'd0;
       for (i = 0; i < 16; i = i + 1)
       begin
       temp = {X[i], E1};
     
           //The above statement is catenation
     
       Y1 = - Y;
     
           //Y1 is the 2’ complement of Y
     
       case (temp)
       2'd2 : Z [31 : 15] = Z [31 : 15] + Y1;
       2'd1 : Z [31 : 15] = Z [31 : 15] + Y;
       default : begin end
       endcase
       Z = Z >> 1;
       /*The above statement is a logical shift of one position to
           the right*/
     
       Z[31] = Z[30];
       /*The above two statements perform arithmetic shift where
       the sign of the number is preserved after the shift. */
     
       E1 = X[i];
           end
       if (Y == 16'd32)
     
       /*If Y = 1000; then according to our code,
       Y1 = 1000 (-8 not 8, because Y1 is 4 bits only).
       The statement sum = - sum adjusts the answer.*/
     
           begin
               Z = - Z;
           end
     
       end
     
       endmodule

Please Note : Our course is now listed for Udemy training by Industry and leading companies use our courses  :
Analog Design- Intuitive Approach
Rc Circuits Analysis With LT Spice
Basics of Mosfet - Simplified View
Please use these links or share with someone who might be interested.
Note : Author discounts are already applied to these links. 

Reading Image File using HDL

Storing image file onto FPGA has two main steps

1. Converting image file format to co-efficient file format(COE format)
2. Storing the COE image file using BRAM(block ram IP core)

1. Converting image to COE format:

In this tutorial we will try and convert JPEG image to COE format using a matlab code. It can also be used for file formats  as bmp, gif, and tif too. Locate the image to be converted in the working directory and run the program given below. After successful execution the program will ask for the location of the image to be converted following which the converted image file will be stored in the same working directory. Copy this .COE file and don't make any alteration to it.  (Here make sure that the image file if of size 240x160)

This format is a RAW image file which saves the values of the pixel in an array(1 Dimension). First two lines of this file are used to indicate the data type(hex/binary/octal etc) and second line marks the beginning of  the pixel values. 

2. Storing COE file in BRAM IP core

Create a new project in Xilinx and in the new source file wizard click on IP(core generator and architecture) . Name this file as "mymemory" and click next

Select Block Memory Generator v2.8 in the submenu RAMs & ROMs under the Memories & Storage Select Next, then Finish.

The .coe file produced by  will contain 240×160 = 38,400 bytes. Following the procedure described we can use the Core Generator to create a read only block memory component "mymemory" of size 240x160, which is 8 bits wide with a depth of 38400 .

Click on Load Int File and click on Browse. Place the COE file generated in the location where the browsers points to. It will be in the "ipcore_dir" folder of your project.

Once the file is loaded we have an option to view the contents of your COE file . To view your coe file click on "show" . Verify if the width and the depth of your image file matches with the one which you have provided for the IP core. Once verified click next and generate. It might take time for the IP BRAM to get generated after which it will appear as a module in your project directory. After successful creation of IP BRAM and COE files your image is now ready to be operated on. You can perform all types of image processing algorithms like smoothing,edge detection , noise reduction etc. Try all these steps and check if you got it right. queries are welcome . Thank you

Link for the coupons : Here

Frequency dividing circuit with minimum hardware

Link for the coupons : Here

       

Most the FPGA boards these days come to high frequency oscillators in orders of 50Mhz/100Mhz and the circuits which we have to drive using FPGA work on lower clock rates. So clock division is the need for such applications.  Though Xilinx provides DCM IP cores for clock division, they are board specific and appear as a black box. With the counters explained below you can customize your code and synthesize it as per your requirement which are independent of the board you use.

Divide by 2 counter :

Its one of the simplest and most used counter which requires only one D-Flip Flop. We have to first design a D-FF and connect the Q-bar output to the D input to get division by 2. Waveform based simulation can be used to verify your design. You can notice that the o/p will have 50% duty cycle too.

Given below are the code with RTL schematic created using PlanAhead tool. You can verify the code for and the RTL.

RTL/CODE:

Simulation results:

Divide by 3 counter :

For divide by 3 counter we have to desin two modules
1. mod 3 counter
2.Dff

Dff code has to be modified in this case as the FF has to be transparent to D only on the negative edge of the clock..
With slight modification for the D-FF code we can create the DFF for neg- edge.  We have to use a OR gate to get the final o/p. The RTL gives the clear design for divide by 3 counter.

RTL/CODE:

simulation results :

Divide by 4 counter :

If you notice , the design for divide by 4 is similar to the divide by 2. Here we have two divide by 2 counters in cascade. This situation makes our efforts easy as we don't have to rewrite the code for div4 counter. All we have to do is to instantiate the div2 counter twice and connect them is cascade as shown. Here there is no need of any other logical gates like in case of Div3 counter. Refer to the code and RTL for div3 counter as shown below. Individual reset are used for the DFF and they must be set in order. First the D-FF X1(rst1) must be reset(high) and then turned low. Next you have to reset the D-FF X2 high followed by low.

RTL/CODE:

simulation results :

Once the deign for divide by 4 is complete you can extend the same concept for all mulitple of 4 division like 4,8, 12 etc. Only modification you require is the number of D-FF stages. For divide by 8 counter you need  3 D-FF in cascade and for 12 you will need 4 and so on... Below are the design for 8 and 12 counters . Try and design it with the same codes and instantiate them accordingly.

Divide by 6 counter :

Not much complex , just 3 D-FF and cascading them gives us divide by 6 counter. Coding is quite simpler as compared to divide by 3 counter. Try and code it yourself if you get stuck , you can refer my code below with RTL schematic.












RTL/CODE:

Simulation results:

We will update the remaining counters as and when the design is ready. Thank you . Keep reading .

Full Adder using generate statement

                 

Link for the coupons : Here

Generate statement in verilog comes in handy when we have to instantiate a sub circuit multiple times. Consider for example you have a 32 bit adder which has 32 full adder circuits and we have to call the FA module 32 times to design a 32 bit adder. This is where the "generat" statement will be of great help. Here we will try to design a 32 bit adder using full adders and by using generate statement try to instantiate this module 32 times as per our design.
                    If we need a variable in our design in order to hold temporary values we have "genvar" key word for declaration.

given below is the code for 32 bit adder using generate statement:


Code:




Test fixture:


Simulation results:

RTL

                         















Once you have simulated the code and synthesied it. Eloborate the RTL by double clicking on the FA module and you can notice that there will be exactly 32 FA module generated.

Design and implementation of 16 Bit Vedic Arithmetic Unit

        Hello guys , i have recently worked on vedic multipliers and have referred few papers too to implement it. I want to make this project open to everyone so that you can build your own Vedic multipliers and compare the results.Previously i have written about 2x2 bit Vedic multipliers  which you can refer back again. We will start by designing a 2x2 multipliers and will develop a 16x16 multipliers. Once we are done with this we will proceed to build a MAC unit. A complete module which has 16x16 multiplier/MAC/ADD-SUB will be our end design

2X2 multiplier:

Design:

Figure illustrates the steps to to multiply two 2 bit numbers (design detail). Converting the above figure to a hardware equivalent we have 3 and gates which will act as 2 bit multipliers and two half adders to add the products to get the final product. Here is the hardware detail of the multiplier 

 Where "a" and "b" are two numbers to be multiplied and "q" is the product. With this design we are now ready to code this in verilog easily using and gates and HA(half adders). To make the design more modular we try to write  code for HA first and then instantiate it to have the final product. 

Code:

4X4 multiplier:

Design:

Using 4 such 2x2 multipliers and 3 adders we can built 4x4 bit multipliers as shown in the design. Proper instantiating of the 2x2 multipliers and adders. We have to first write code for 4bit and 6 bit adders. Its your choice to choose your adders. If in case you want to have better performance you can replace these normal adders with CSA or compressors. For a simpler design we have used the "+" operator which is supported by the XST synthesis tool which by default selects a low hardware adder. This architecture follows wallace tree which reduces the addition levels from 3 to just 2 stages as shown. Arrangement of the adders and the addition is explained from the figure shown below:

  

Code:

Link for the coupons : Here

8X8 multiplier:
Design:

similar to the previous design of 4x4 multiplier , we need 4 such  4x4 multipliers to develop 8x8 multipliers. Here we need to first design 8bit and 12 bit adders and by proper instantiating of the module and connections as shown in the figure we have designed a 8x8 bit multiplier. At this point of time its necessary for you to even verify the  RTL code and check if the hardware is as per your design. PlanAhead tool by xilinx gives better view of the hardware design with design elaborate option(will explain this in my next posts). Refer the addition tree diagram to know the process for 8x8 multiplier:

Code:


16x16 multiplier:
Design:

Follow the same steps as in case of previous multipliers and develop 16x16 multipliers. Refer the adder tree diagram below :

code:

Here is the test bench for 16x16 vedic multipliers :



Simulation results:

RTL:

MAC design:

TO being with MAC design we have to first design a accumulator which adds two number . One of which is the output of the previous stage and the other is the output from the multiplier module. Figure below shows the implementation  design for mac.

It can be seen from the block diagram that the accumulator module has one input( we have designed this module be be synchronous so we have used Clock as second input). Few more control signals are required to clear(clr) the ACC unit and enable signal(en) to  initiate the process of accumulation. We replace the MUL unit shown in the diagram above with out 16x16 multiplier module. Here is the code for MAC unit

code:


Simulation results :

This module cane be further devloped to convert the top module into ALU by designing your own adder/substractor and making this as the top module. please let me know if there is anything you did not understand. We are happy to help. Thank you.










Note: Replace the modules with name  "add_N_bit" with a N bit adder. You can use your own adder in place of this module like csa/cla etc. If speed is not of major concern for your design use the "+" operator to create the adder modules.

RTL:

Referece Papers:


Paper 1

Paper 2


contact: verilogblog@gmail.com