cancel
Showing results for 
Show  only  | Search instead for 
Did you mean: 
xuantran
Contributor
Contributor
659 Views
Registered: ‎04-11-2019

State machine implementation

I am learning FPGA.

When I design a FSM, I see the difference of the number of clocks required to complete a task when changing the number of states. A FSM which has less states requires less clock cycles to finish the task.

I wonder if there are differences of the number of resources required when a tool synthesizes these FSMs.

0 Kudos
12 Replies
dpaul24
Scholar
Scholar
646 Views
Registered: ‎08-07-2014

@xuantran ,

Yes the state encodings will take a few more resources and introduces latency due to state transitions and then doing the task. But think about code readability, debugging and maintainability also. I would recommend a SM based design.

btw - how many states does your design have?

 

------------FPGA enthusiast------------
Consider giving "Kudos" if you like my answer. Please mark my post "Accept as solution" if my answer has solved your problem

0 Kudos
xuantran
Contributor
Contributor
633 Views
Registered: ‎04-11-2019

@dpaul24 

Thanks for your reply!

I am a beginner.

I play only with a 4-5 states.

I am eager to learn how to write good Verilog code and design an efficient FSM.

0 Kudos
dpaul24
Scholar
Scholar
629 Views
Registered: ‎08-07-2014

@xuantran 

play only with a 4-5 states

That will only use up 2 or 3 flops for state encoding, that is really nothing.

regarding latency, it really matters how many times the design is iterating withing the states and which outputs are available at which state.

I am eager to learn how to write good Verilog code and design an efficient FSM.

Do not worry much about latency now, it is much more important to have the functionality and have a synthesizable state machine. Later you can analyze you SM during simulation and see if states can be reduced. It is ok if you do not have the efficient RTL SM code right from the 1st go.

------------FPGA enthusiast------------
Consider giving "Kudos" if you like my answer. Please mark my post "Accept as solution" if my answer has solved your problem

xuantran
Contributor
Contributor
615 Views
Registered: ‎04-11-2019

@dpaul24  Thanks!

xuantran
Contributor
Contributor
514 Views
Registered: ‎04-11-2019

I have a FSM to convert a binary number to BCD.

module double_dabble
		# ( parameter BIN_WIDTH = 32,
			parameter BCD_DIGIT = 8
		)
		(	input 					clk_in,
			input 					rst_in,
			input					start,
			input [BIN_WIDTH-1:0]	bin_in,
			output reg[(BCD_DIGIT*4)-1:0] bcd_out
		);
		
		parameter IDLE 		= 3'b001;
		parameter CONVERT 	= 3'b010;
		parameter DONE 		= 3'b100;
		
		// The vector that contains the input binarnext value being shifted
		reg [BIN_WIDTH-1:0]	bin_shift;
		
		// The vector that contains the output BCD
		reg [(BCD_DIGIT*4)-1:0] bcd_shift;
		
		// This vector that keeps track the shift operator
		reg [7:0] shift_index = 'b0;
		
		reg [2:0] state, next;
		integer k;
		
		// Define the next state and output combinational circuits
		always @(state, start, bin_in)
		begin
			next = 4'bx;	//@loop back: next = state
			bcd_out = 'b0;
			case(state)
			IDLE: 
					begin
						if (start == 1'b1)
						begin							
							bin_shift = bin_in;
							next = CONVERT;
						end				
						else
							next = IDLE;	// @loop back
					end
			CONVERT:
					begin
						bcd_shift = bcd_shift << 1;								
						bcd_shift[0] = bin_shift[BIN_WIDTH-1];								
						bin_shift = bin_shift << 1;								
						
						if (shift_index == BIN_WIDTH-1)
						begin
							shift_index = 8'b0;
							next = DONE;
						end
						else
						begin
							shift_index = shift_index + 8'b1;
							for (k = 0; k < BCD_DIGIT; k = k+1)
								if (bcd_shift[(4*k)+:4] > 4'b0100)
									bcd_shift[(4*k)+:4] = bcd_shift[(4*k)+:4] + 4'b0011;
							next = CONVERT; // @loop back
						end
					end
			DONE: 	begin
						bcd_out = bcd_shift;
						bcd_shift = 'b0;													
						next = IDLE;
					end
					
			default: begin
						next = 'bx;
						bcd_out = 'bx;
					 end
			endcase
		end		
		
		// Define the sequential block		
		always @(posedge clk_in)
			if (rst_in == 1'b1)	state <= IDLE;
			else 			state <= next;
		
endmodule

CONVERT state loops back to convert a binary input.

shift_index is expected to increase from 0 to 31.

However, it only gets to 2 when simulating.

sim_4_2.png

 

Any ideas? I am grateful for any explanation.

0 Kudos
markcurry
Scholar
Scholar
492 Views
Registered: ‎09-16-2009

Well, for starters "shift_index" will form a latch since it's entire state space is not explicitly decoded.  Fix that first.  Hint, assign "shift_index" a default value at the beginning of your combinational procedural clause.

Regards,

Mark

 

0 Kudos
xuantran
Contributor
Contributor
455 Views
Registered: ‎04-11-2019

@markcurryThanks for your reply!

Nevertheless, I don't get it. Could you please clarify it?

0 Kudos
markcurry
Scholar
Scholar
431 Views
Registered: ‎09-16-2009

Is this homework?  We'll still help if it is, but it would be preferred to know this up front.

Ask yourself what value do you expect "shift_index" to take when "state" is IDLE?  What does the code do in this case?

Regards,

Mark

xuantran
Contributor
Contributor
388 Views
Registered: ‎04-11-2019

@markcurry

Thanks for your hint.

Now I get what you meant by "assign "shift_index" a default value at the beginning of your combinational procedural clause."

 

However, the problem isn't solved yet.

I don't understand why they are stuck.

The following FSM works well. The CONVERT state is split into two states: SHIFT and ADD.

 

module double_dabble
		# ( parameter BIN_WIDTH = 32,
			parameter BCD_DIGIT = 8
		)
		(	input 					clk_in,
			input 					rst_in,
			input					start,
			input [BIN_WIDTH-1:0]	bin_in,
			output reg[(BCD_DIGIT*4)-1:0] bcd_out
		);
		
		parameter IDLE 	= 4'b0001;
		parameter SHIFT = 4'b0010;
		parameter ADD 	= 4'b0100;
		parameter DONE 	= 4'b1000;
		
		// The vector that contains the input binarnext value being shifted
		reg [BIN_WIDTH-1:0]	bin_shift;
		
		// The vector that contains the output BCD
		reg [(BCD_DIGIT*4)-1:0] bcd_shift;
		
		// This vector that keeps track the shift operator
		reg [7:0] shift_index = 8'b0;
		
		reg [3:0] state, next;
		integer k;
		
		// Define the next state and output combinational circuits
		always @(state, start, bin_in)
		begin
			next = 4'bx;	//@loop back: next = state
			bcd_out = 'b0;
			case(state)
			IDLE: 
					begin
						if (start == 1'b1)
						begin							
							bin_shift = bin_in;
							next = SHIFT;
						end				
						else
							next = IDLE;	// @loop back
					end
			SHIFT:
					begin
						// Always shift the BCD vector until all bits are through
						// Shift the most significant bit of bin_shift into bcd_shift
						bcd_shift = bcd_shift << 1;								
						bcd_shift[0] = bin_shift[BIN_WIDTH-1];												
						bin_shift = bin_shift << 1;	
						
						if (shift_index == BIN_WIDTH-1)
						begin
							shift_index = 8'b0;
							next = DONE;
						end
						else
						begin
							shift_index = shift_index + 8'b1;
							next = ADD;
						end
					end
			
			ADD:	begin
						/* Check every BCD digit if its value is greater than 4.
						   If so, add 3 to its value. Otherwise, do nothing.
						*/
						for (k = 0; k < BCD_DIGIT; k = k+1)
							if (bcd_shift[(4*k)+:4] > 4'b0100)
								bcd_shift[(4*k)+:4] = bcd_shift[(4*k)+:4] + 4'b0011;
														
						next = SHIFT;
					end
			
			DONE: 	begin
						bcd_out = bcd_shift;
						bcd_shift = 'b0;													
						next = IDLE;
					end
					
			default: begin
						next = 'bx;
						bcd_out = 'bx;
					 end
			endcase
		end		
		
		// Define the sequential block		
		always @(posedge clk_in)
			if (rst_in == 1'b1)	state <= IDLE;
			else 			state <= next;
		
endmodule

 

sim_3_1.png

0 Kudos
markcurry
Scholar
Scholar
378 Views
Registered: ‎09-16-2009

You still have the latch problem on your combinational clause. For every variable in your combinational clause - one must have a decode for every sub-clause and/or sub-state.  If one doesn't then you are implying memory (no decode in some clause, means keep same value = memory or a latch in this case).

The easiest way to make sure you have (at least) a default decoding for every variable is to assign (without qualification) every variable at the beginning of your clause.

So for me quick reading your clause, I see you're assigning the following variables: next, bcd_out, bin_shift, bcd_shift, shift_index.

But at the top of that clause you're only assigning default decodes for the first two variables.  Add default decodings for the others as well:

always @(state, start, bin_in)
begin
  next = 4'bx;	//@loop back: next = state
  bcd_out = 'b0;
  bin_shift = something;
  bcd_shift = something;
  shift_index = something;

 

Then below, you can over write these default values as needed.  But you must have a default.

Regards,

Mark

xuantran
Contributor
Contributor
216 Views
Registered: ‎04-11-2019

@markcurry  Thanks so much for your help!

 

  1. SHIFT and ADD
  • As far as I understand, because bcd_shift, bin_shift and shift_index in this case don't have defaults values, there are inferring latches to store their previous values. So, this FSM works.
  • With default values, the FSM doesn't work as I expected.

       ----> The FSM without the default values isn't correct

 

     2. The following FSM works as my expectation. However, I am not sure about its correctness.

        Is it possible to put shifting and adding operation (shift_index, bin_shift and bcd_shift) into a sequential logic?

 

module double_dabble
		# ( parameter BIN_WIDTH = 32,
			parameter BCD_DIGIT = 8
		)
		(	input 					clk_in,
			input 					rst_in,
			input					start,
			input [BIN_WIDTH-1:0]	bin_in,
			output reg[(BCD_DIGIT*4)-1:0] bcd_out
		);
		
		localparam IDLE 	= 4'b0001;
		localparam SHIFT 	= 4'b0010;
		localparam ADD 		= 4'b0100;
		localparam DONE		= 4'b1000;
		
		// The vector that contains the input binarnext value being shifted
		reg [BIN_WIDTH-1:0]	bin_shift;
		
		// The vector that contains the output BCD
		reg [(BCD_DIGIT*4)-1:0] bcd_shift;
		
		// This vector that keeps track the shift operator
		reg [7:0] shift_index = 8'b0;
		
		reg [3:0] state, next;
		integer k;
		
		// Define the next state and output combinational circuits
		always @(state, start, shift_index, bcd_shift)
		begin
			next = 4'bx;	//@loop back: next = state
			bcd_out = 'b0;
			case(state)
			IDLE: 	
					if (start == 1'b1)				
						next = SHIFT;
					else		
						next = IDLE;	// @loop back
			SHIFT:	
					if (shift_index == BIN_WIDTH-1)						
						next = DONE;
					else						
						next = ADD;
			ADD:	next = SHIFT;
			DONE: 	begin
						bcd_out = bcd_shift;					
						next = IDLE;
					end
					
			default: begin
						next = 'bx;
						bcd_out = 'bx;
					 end
			endcase
		end		
		
		// Define the sequential block		
		always @(posedge clk_in)
			if (rst_in == 1'b1)	state <= IDLE;
			else 				state <= next;
		
		// Shifting and adding operation of the input value and BCD digits	
		always @(posedge clk_in)
			if (rst_in == 1'b1)
			begin
				bin_shift <= 'b0;
				bcd_shift <= 'b0;
				shift_index <= 8'b0;
			end	
			else
				case (state)
				IDLE : 	
						begin
							if (start == 1'b1)
								bin_shift <= bin_in;
								shift_index <= 8'b0;
								bcd_shift <= 'b0;
						end
				SHIFT :	
						begin																		
							bcd_shift <= bcd_shift << 1;								
							bcd_shift[0] <= bin_shift[BIN_WIDTH-1];												
							bin_shift <= bin_shift << 1;
															
							if (shift_index ==  BIN_WIDTH-1)
								shift_index <= 8'b0;
							else								
								shift_index <= shift_index + 1;
						end
				ADD:
							for (k = 0; k < BCD_DIGIT; k = k+1)
								if (bcd_shift[(4*k)+:4] > 4'b0100)
									bcd_shift[(4*k)+:4] <= bcd_shift[(4*k)+:4] + 4'b0011;	
				default : 	
							begin							
								bcd_shift <= 'bx;
								bin_shift <= 'bx;
								shift_index <= 8'bx;
							end
				endcase

endmodule

 

 

 

        3. CONVERT

           I still don't get why the following FSM is stuck.

 

// Define the next state and output combinational circuits
		always @(state, start, bin_in)
		begin
			next = 4'bx;	//@loop back: next = state
			bcd_out = 'b0;
			case(state)
			IDLE: 
					begin
						if (start == 1'b1)
						begin							
							bin_shift = bin_in;
							next = CONVERT;
						end				
						else
							next = IDLE;	// @loop back
					end
			CONVERT:
					begin
						bcd_shift = bcd_shift << 1;								
						bcd_shift[0] = bin_shift[BIN_WIDTH-1];								
						bin_shift = bin_shift << 1;								
						
						if (shift_index == BIN_WIDTH-1)
						begin
							shift_index = 8'b0;
							next = DONE;
						end
						else
						begin
							shift_index = shift_index + 8'b1;
							for (k = 0; k < BCD_DIGIT; k = k+1)
								if (bcd_shift[(4*k)+:4] > 4'b0100)
									bcd_shift[(4*k)+:4] = bcd_shift[(4*k)+:4] + 4'b0011;
							next = CONVERT; // @loop back
						end
					end
			DONE: 	begin
						bcd_out = bcd_shift;
						bcd_shift = 'b0;													
						next = IDLE;
					end
					
			default: begin
						next = 'bx;
						bcd_out = 'bx;
					 end
			endcase
		end		

 

 

0 Kudos
xuantran
Contributor
Contributor
265 Views
Registered: ‎04-11-2019

@markcurry  Thanks so much for your help!

1. SHIFT and ADD:

  • As far as I understand, there are inferring latches for variables shift_index, bin_shift, bcd_shift because they don't have default values or are not defined in every states.
  • When adding default values for these variables. FSM doesn't work as expected. ---> I see the problem.
  • FSM without default values or not being defined in every state isn't correct.

2. I build a new FSM as follows. I'd appreciate your feedback.

   Is it possible to put shift_index, bin_shift and bcd_shift in a sequential logic block?

 

module double_dabble
		# ( parameter BIN_WIDTH = 32,
			parameter BCD_DIGIT = 8
		)
		(	input 					clk_in,
			input 					rst_in,
			input					start,
			input [BIN_WIDTH-1:0]	bin_in,
			output reg[(BCD_DIGIT*4)-1:0] bcd_out
		);
		
		localparam IDLE 	= 4'b0001;
		localparam SHIFT 	= 4'b0010;
		localparam ADD 		= 4'b0100;
		localparam DONE		= 4'b1000;
		
		// The vector that contains the input binarnext value being shifted
		reg [BIN_WIDTH-1:0]	bin_shift;
		
		// The vector that contains the output BCD
		reg [(BCD_DIGIT*4)-1:0] bcd_shift;
		
		// This vector that keeps track the shift operator
		reg [7:0] shift_index = 8'b0;
		
		reg [3:0] state, next;
		integer k;
		
		// Define the next state and output combinational circuits
		always @(state, start, shift_index, bcd_shift)
		begin
			next = 4'bx;	//@loop back: next = state
			bcd_out = 'b0;
			case(state)
			IDLE: 	
					if (start == 1'b1)				
						next = SHIFT;
					else		
						next = IDLE;	// @loop back
			SHIFT:	
					if (shift_index == BIN_WIDTH-1)						
						next = DONE;
					else						
						next = ADD;
			ADD:	next = SHIFT;
			DONE: 	begin
						bcd_out = bcd_shift;					
						next = IDLE;
					end
					
			default: begin
						next = 'bx;
						bcd_out = 'bx;
					 end
			endcase
		end		
		
		// Define the sequential block		
		always @(posedge clk_in)
			if (rst_in == 1'b1)	state <= IDLE;
			else 				state <= next;
		
		// Shifting and adding operation of the input value and BCD digits	
		always @(posedge clk_in)
			if (rst_in == 1'b1)
			begin
				bin_shift <= 'b0;
				bcd_shift <= 'b0;
				shift_index <= 8'b0;
			end	
			else
				case (state)
				IDLE : 	
						begin
							if (start == 1'b1)
								bin_shift <= bin_in;
								shift_index <= 8'b0;
								bcd_shift <= 'b0;
						end
				SHIFT :	
						begin																		
							bcd_shift <= bcd_shift << 1;								
							bcd_shift[0] <= bin_shift[BIN_WIDTH-1];												
							bin_shift <= bin_shift << 1;
															
							if (shift_index ==  BIN_WIDTH-1)
								shift_index <= 8'b0;
							else								
								shift_index <= shift_index + 1;
						end
				ADD:
							for (k = 0; k < BCD_DIGIT; k = k+1)
								if (bcd_shift[(4*k)+:4] > 4'b0100)
									bcd_shift[(4*k)+:4] <= bcd_shift[(4*k)+:4] + 4'b0011;	
				default : 	
							begin							
								bcd_shift <= 'bx;
								bin_shift <= 'bx;
								shift_index <= 8'bx;
							end
				endcase

endmodule

 

3. CONVERT

   I still don't get why it gets stuck.

   Is there any way to shift and increase value in a combinational logic? or is it impossible?

// Define the next state and output combinational circuits
		always @(state, start, bin_in)
		begin
			next = 4'bx;	//@loop back: next = state
			bcd_out = 'b0;
			case(state)
			IDLE: 
					begin
						if (start == 1'b1)
						begin							
							bin_shift = bin_in;
							next = CONVERT;
						end				
						else
							next = IDLE;	// @loop back
					end
			CONVERT:
					begin
						bcd_shift = bcd_shift << 1;								
						bcd_shift[0] = bin_shift[BIN_WIDTH-1];								
						bin_shift = bin_shift << 1;								
						
						if (shift_index == BIN_WIDTH-1)
						begin
							shift_index = 8'b0;
							next = DONE;
						end
						else
						begin
							shift_index = shift_index + 8'b1;
							for (k = 0; k < BCD_DIGIT; k = k+1)
								if (bcd_shift[(4*k)+:4] > 4'b0100)
									bcd_shift[(4*k)+:4] = bcd_shift[(4*k)+:4] + 4'b0011;
							next = CONVERT; // @loop back
						end
					end
			DONE: 	begin
						bcd_out = bcd_shift;
						bcd_shift = 'b0;													
						next = IDLE;
					end
					
			default: begin
						next = 'bx;
						bcd_out = 'bx;
					 end
			endcase
		end

 

0 Kudos