Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

- Community Forums
- :
- Forums
- :
- Vivado RTL Development
- :
- Implementation
- :
- State machine implementation

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

xuantran

Contributor

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

04-14-2021 05:52 AM

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.

12 Replies

dpaul24

Scholar

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

04-14-2021 06:17 AM - edited 04-14-2021 06:19 AM

646 Views

Registered:
08-07-2014

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

xuantran

Contributor

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

04-14-2021 06:26 AM

633 Views

Registered:
04-11-2019

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.

dpaul24

Scholar

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

04-14-2021 06:29 AM - edited 04-14-2021 06:32 AM

629 Views

Registered:
08-07-2014

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

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

xuantran

Contributor

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

04-14-2021 06:37 AM

615 Views

Registered:
04-11-2019

@dpaul24 Thanks!

xuantran

Contributor

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

04-15-2021 10:43 AM

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.

Any ideas? I am grateful for any explanation.

markcurry

Scholar

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

04-15-2021 01:39 PM

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

xuantran

Contributor

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

04-16-2021 12:33 AM

455 Views

Registered:
04-11-2019

@markcurryThanks for your reply!

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

markcurry

Scholar

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

04-16-2021 09:13 AM

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

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

04-16-2021 03:05 PM

388 Views

Registered:
04-11-2019

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

markcurry

Scholar

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

04-16-2021 03:21 PM

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

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

04-17-2021 01:34 PM - edited 04-17-2021 01:42 PM

216 Views

Registered:
04-11-2019

@markcurry Thanks so much for your help!

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

xuantran

Contributor

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

04-18-2021 02:01 AM

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