Help with state machine

[Leep]

I've written a FSM to take a 14-bit binary number (decimal 0-9999) and convert it to 16-bit BCD using the following algorithm:

1. Shift the binary number left one bit.
2. If 14 shifts have taken place, stop.
3. If the binary value in any of the BCD columns (units, tens, hundreds, thousands) is 5 or greater, add 3 to that value in that BCD column.
4. Go to 1.

I have 3 states (RESET, SHIFT, IDLE) and a 0-13 counter. Setting reset high puts the FSM into RESET mode which initializes things and puts it in SHIFT mode where it stays in state SHIFT for 14 cycles (controlled by the counter) and performs the algorithm each time, then enters IDLE mode.

The problem I'm having is that it seems like it's incrementing the counter and changing the output fields (thousands, hundreds, tens, and units) one more time after entering IDLE. I'm sure this isn't literally the case, but I'm at a loss for what's going on.

I'm outputing the tens and units values to the right two seven-segment displays and for debug I'm outputting the current state and the counter to the left two seven-segment displays. Here's the sequence I get after hitting reset (I slowed the FSM clock WAY down to about 2Hz, to see the display changing):

0000 <-- state == 0, counter == 0
2000 <-- state == 2, counter == 0
2101 <-- state == 2, counter == 1
2202 <-- state == 2, counter == 2
2304 <-- state == 2, counter == 3
240c <-- state == 2, counter == 4
251c <-- state == 2, counter == 5
263c <-- state == 2, counter == 6
27ab <-- state == 2, counter == 7
2889 <-- state == 2, counter == 8
2912 <-- state == 2, counter == 9
2a24 <-- state == 2, counter == 10
2b4c <-- state == 2, counter == 11
2ccc <-- state == 2, counter == 12
2d99 <-- state == 2, counter == 13, tens and units both have 9, which is correct at this point.
1e33 <-- state == 1, counter == 14 (????), tens and units have changed (????)

The last values (state == 1, counter == 14, tens = 3, units = 3) stay until reset is hit again.

When I run this in the simulator (with the full speed clock, I just changed clk_slow in the two always blocks to clk) I get:

(sorry for the small image, I couldn't figure out how to get it bigger in-line... click it to see full size)

which seems to be the correct results (thousands, hundreds, tens and units are all 9), not what I get when I synthesize it and run it on the Nexys 3.

Here's my code:

module seven_seg_test
  (
    input  wire       clk,
    input  wire       reset,
    output wire [3:0] an,   // enable, 1-out-of-4 asserted low
    output wire [7:0] sseg  // led segments
  );

  parameter STATE_SIZE = 2;
  parameter RESET = 2'b00, IDLE = 2'b01, SHIFT = 2'b10;
  parameter CLOCK_SIZE = 26;

  reg  [STATE_SIZE-1:0] state, next_state;
  reg [13:0] decimal;
  reg  [3:0] thousands, hundreds, tens, units;
  reg  [3:0] bits_to_go;
  reg  [CLOCK_SIZE-1:0] counter;

  wire [7:0] led3, led2, led1, led0;
  wire clk_slow;
  
  hex_to_sseg sseg_unit_0
  (
    .hex(units),
    .dp(1'b1),
    .sseg(led0)
  );
  hex_to_sseg sseg_unit_1
  (
    .hex(tens),
    .dp(1'b1),
    .sseg(led1)
  );
  hex_to_sseg sseg_unit_2
  (
    .hex(bits_to_go),
    .dp(1'b1),
    .sseg(led2)
  );
  hex_to_sseg sseg_unit_3
  (
    .hex({2'b0, state}),
    .dp(1'b1),
    .sseg(led3)
  );

  disp_mux disp_unit
  (
    .clk(clk),
    .reset(1'b0),
    .in0(led0),
    .in1(led1),
    .in2(led2),
    .in3(led3),
    .an(an),
    .sseg(sseg)
  );

  assign clk_slow = counter[CLOCK_SIZE-1];

  always @(posedge clk)
  begin
    counter <= counter + 1'b1;
  end

  always @(posedge clk_slow, posedge reset)
  begin
    if(reset)
    begin
      state = RESET;
    end else begin
      state = next_state;
    end
  end

  always @(posedge clk_slow)
  begin
    case (state)
      RESET:
        begin
          {thousands, hundreds, tens, units} = 16'b0;
          decimal = 14'd9999;
          bits_to_go = 1'b0;
          next_state = SHIFT;
        end
      SHIFT:
        begin
          {thousands, hundreds, tens, units, decimal} = {thousands[2:0], hundreds, tens, units, decimal, 1'b0};
          bits_to_go = bits_to_go + 1'b1;
          if(bits_to_go != 4'd13 && units >= 5) units = units + 2'd3;
          if(bits_to_go != 4'd13 && tens >= 5) tens = tens + 2'd3;
          if(bits_to_go != 4'd13 && hundreds >= 5) hundreds = hundreds + 2'd3;
          if(bits_to_go != 4'd13 && thousands >= 5) thousands = thousands + 2'd3;
          if(bits_to_go == 4'd13)
          begin
            next_state = IDLE;
          end
        end
      default:
        begin
        end
    endcase
  end
  
endmodule

What am I doing wrong? Am I approaching the FSM wrong? Am I thinking too much like "programming" and not "describing hardware"? I'm still very new to all this, so any advice at all will be welcomed!

-----
Leep

 

[FvM]

Your FSM design uses double registering of state variable, assignments of next_state and state are both under always @(clk). To make things worse, both are using blocking assignments, thus causing unpredictable results with multiple always blocks.

Please refer to a FSM template from literature, or use a single clock edge sensitive always block and assign variable state directly, without a next_state. Except for special purposes, assignments in a synchronous always block should be non-blocking.

 

[Leep]

@FSM, thanks for the advice. I got the template from various examples I found Googling... I might have "Frankenstein'ed" them into the monster I have now. I'll rework the FSM to directly assign to state without using next_state (I feel more comfortable doing it that way anyway). As for blocking assignments, with the logic I have to implement in the SHIFT state (assign thousands, hundreds, tens, and units, then check each and add 3 more if they're >= 5), how could I design it to use non-blocking assignments? Or could I just use non-blocking assignment for the state <= (bits_to_go == 1'b0 ? IDLE : SHIFT) in the SHIFT state and the other assignments be blocking?

I understand blocking and non-blocking assignments, at least how they function, but I'm still a bit (a lot) confused on where/when/why I would use one over the other. Obviously if I have assignments that I have to check the value of right after the assignment (if(units >= 5) ...) the assignment has to be blocking. Non-blocking assignments get their right-side "evaluated" (sorry for using a software term) at the end of the always block essentially if I understand correctly. Any checking of the left hand value, even after the non-blocking assignment, would get the original value, not the assigned value. Is this correct?

-----
Leep

 

[FvM]

Any checking of the left hand value, even after the non-blocking assignment, would get the original value, not the assigned value. Is this correct?

Yes. Of course, this requires to change the way of coding some details and may be unusual for a software guy at first sight. But it's the "natural" coding style describing registered hardware. Using blocking assignments e.g. for bits_to_go enforces usage of additional logic cells to calculate intermediate logic terms that may fit into the logic of registered LEs otherwise. If bits_to_go would be used as intermediate variable only, a blocking assingment may be reasonable, but it's a registered variable at the same time.

P.S.:

Or could I just use non-blocking assignment for the state <= (bits_to_go == 1'b0 ? IDLE : SHIFT) in the SHIFT state and the other assignments be blocking?

I see some arguments for using blocking assignments with the number fields. The only strict rule is to use only one assignment type for each variable. I mentioned the blocking assigment point, because it brings up special issue of execution order of always blocks in your original design, where variables with blocking assignments are read in a second edge sensitive always block.

 

[Leep]

Ok, I did some more research and settled on the FSMD "template" used in the book FPGA Prototyping By Verilog Examples by Pong P. Chu (I highly recommend this book to anyone learning FPGA design; there is a VHDL version as well). It uses current and next registers for everything, which I wanted to avoid at first, but now that I've rewritten my binary-to-BCD converter that way I think I like it. It keeps the current and the next values of everything very clear. It actually helped me get my brain wrapped around the "cyclical" nature of a FSM.

Here's the code as it is now (still lots to play with it, like making the number to convert be a input instead of hard coded). It works, and I even added some debouncing of the reset button. I was getting odd results occasionally that I suspected were due to the button bouncing... they went away when I added the debouncing code, and since my purpose of this is to continuously refresh four seven-segment displays, a ~42 ms pause after reset is no big deal. Eventually this will receive the binary number and a load flag as input and the button won't come into play (at least not in THIS circuit, maybe in the test circuit that tests this one).

`timescale 1ns / 1ps
module seven_seg_test
  (
    input  wire       clk,
    input  wire       reset,
    output wire [3:0] an,   // enable, 1-out-of-4 asserted low
    output wire [7:0] sseg  // led segments
  );

  parameter [1:0] RESET = 2'b00,
                  IDLE  = 2'b01,
                  SHIFT = 2'b10;
  //parameter CLOCK_SIZE = 26;
  reg  [1:0] state_reg,     state_next;
  reg [13:0] decimal_reg,   decimal_next;
  reg  [3:0] thousands_reg, thousands_next,
             hundreds_reg,  hundreds_next,
             tens_reg,      tens_next,
             units_reg,     units_next;
  reg  [3:0] counter_reg,   counter_next;
  reg [21:0] reset_reg,     reset_next;
  //reg  [CLOCK_SIZE-1:0] counter;

  wire [7:0] led3, led2, led1, led0;
  //wire clk_slow;
  
  hex_to_sseg sseg_unit_0
  (
    .hex(units_reg),
    .dp(1'b1),
    .sseg(led0)
  );
  hex_to_sseg sseg_unit_1
  (
    .hex(tens_reg),
    .dp(1'b1),
    .sseg(led1)
  );
  hex_to_sseg sseg_unit_2
  (
    .hex(hundreds_reg),
    .dp(1'b1),
    .sseg(led2)
  );
  hex_to_sseg sseg_unit_3
  (
    .hex(thousands_reg),
    .dp(1'b1),
    .sseg(led3)
  );

  disp_mux disp_unit
  (
    .clk(clk),
    .reset(1'b0),
    .in0(led0),
    .in1(led1),
    .in2(led2),
    .in3(led3),
    .an(an),
    .sseg(sseg)
  );

  //assign clk_slow = counter[CLOCK_SIZE-1];

  //always @(posedge clk)
  //begin
  //  counter <= counter + 1'b1;
  //end

  always @(posedge clk/*_slow*/, posedge reset)
  begin
    if(reset)
      begin
        state_reg = RESET;
        decimal_reg = 14'd9999;
        {thousands_reg, hundreds_reg, tens_reg, units_reg} = 16'b0;
        counter_reg = 4'd14;
        reset_reg = 22'b1111111111111111111111; // @100MHz 1 clock cycle = 10ns, (2^22)*10ns == ~42ms
      end
    else
      begin
        state_reg = state_next;
        decimal_reg = decimal_next;
        {thousands_reg, hundreds_reg, tens_reg, units_reg} = {thousands_next, hundreds_next, tens_next, units_next};
        counter_reg = counter_next;
        reset_reg = reset_next;
      end
  end
  
  always @*
  begin
    state_next = state_reg;
    decimal_next = decimal_reg;
    {thousands_next, hundreds_next, tens_next, units_next} = {thousands_reg, hundreds_reg, tens_reg, units_reg};
    counter_next = counter_reg;
    reset_next = reset_reg;
    case (state_reg)
      RESET:
        begin
          // debounce by pausing long enough to let the bouncing settle
          reset_next = reset_next - 1'b1;
          if(reset_next == 1'b0) state_next = SHIFT;
        end
      SHIFT:
        begin
          {thousands_next, hundreds_next, tens_next, units_next, decimal_next} = {thousands_reg[2:0], hundreds_reg, tens_reg, units_reg, decimal_reg, 1'b0};
          counter_next = counter_reg - 1'b1;
          if(counter_next != 4'b0 && units_next >= 5) units_next = units_next + 2'd3;
          if(counter_next != 4'b0 && tens_next >= 5) tens_next = tens_next + 2'd3;
          if(counter_next != 4'b0 && hundreds_next >= 5) hundreds_next = hundreds_next + 2'd3;
          if(counter_next != 4'b0 && thousands_next >= 5) thousands_next = thousands_next + 2'd3;
          if(counter_next == 4'b0) state_next = IDLE;
        end
      default:
        begin
          state_next = IDLE;
        end
    endcase
  end
  
endmodule

@FvM, this has been an excellent learning experience for me. I feel I have a much better understanding of how to code a FSM (FSMD as it's called in the book I mentioned... Finite State Machine with (implicit) Data path). There are so many "little parts" (in the software world I think I'd refer to them as "framework") I need to learn before I can progress onto bigger things. Thanks for your previous advice, and I welcome any comments you (or anyone) have on the current code. :-D

 

[FvM]

I'm mostly using VHDL rather than Verilog, but the basic questions in FSM coding and general synchronous design are the same.

You are now referring to a classical FSM template. It's good to practically evaluate it's properties, I think.

I tend to use a shortcut without the xxx_next variables and the combinational always @* block (respectively process in VHDL). State variable and other registered variables are directly assigned in the state case construct. If designed properly, it should end up in (almost) the same gate level netlist.

In my view, the single always block FSM offers both writing convenience and good readability.