One-hot encoding mystery

[Tickstart]

I am really confused right now. I've checked the numbers and I can't figure out what's wrong.

Let me fill you in. I was brushing up on my skills, trying to design a very simple FSM. It is meant to detect the rising edge of a signal, for instance when I've divided the clock in the FPGA a few times but don't want a process to execute during the whole 'high'-state of the divided clock but only on its rise.

 

I start out with the state diagram, which contains three states. I opted for a Moore-machine, just for practice. See pic below.

 

Next, I chose to use 1-hot encoding, again for practice. States are enumerated as; S0 = 001, S1 = 010, S2 = 100. I is input, Q is output, S+ is the next state encodings.

 

Then I calculate the next state bits, S+:es, and the output equations from the table above. (There is a misspelling here, "S3+" is supposed to be S2+, since that's what the K-map is calculating).

 

What?? Why does nothing depend on S2?? Where has this state gone?! What am I doing wrong?

[D@n]

@Tickstart,

Sure it's legal: replace S0+ and S1+ above with their respective formulas and you then have a formula for S2+ that doesn't depend upon S0+ or S1+.  Further, since S2 is dependent upon S0 and S1 only, that formula should require only S0, S1, and I. 

Dan

[Piasa]

VHDL uses the sensitivity list as a hint for the simulator.  VHDL-2008 adds a wildcard feature for the sensitivity list.  Verilog is a bit different as it uses the sensitivity list to determine if something infers clocked logic and if there is async set/reset.  Verilog-2001 added a @(*) for combinatorial always blocks.  SystemVerilog adds always_comb and always_ff to ensure the inferred logic matches the intended type.

@Trickstart:  In your post, the simulation will not use the I input in the "diagram" process.  If the value of I changes and the value of state does not change, the value of next_state will not change -- in simulation.  The synthesis tools will ignore the sensitivity list and provide a "simulation mismatch" warning.  I generally search synthesis logs for "simulation mismatch" as a result.

There is a slightly newer/better template that places the reset condition at the end of the process, either inside the if (rising_edge(clk)) statement, or after for async resets.  This allows the data path logic -- which might not need a reset -- to be in the same process as the control logic that does need a reset.  The issue with the traditional approach is that signals are left out of the reset case.  This causes reset to become an input to the logic driving that register.  FPGA vendors often advise only resetting control logic as well, which can lead to developers placing related logic in several different processes.  (this is similar to an older design style where every register was in its own process -- as if it were a schematic element.)

The three-process style is not common anymore, nor are two-process state machines.  More devs do what @D@n describes as the single process style is less verbose and has less micro-management and also simulates faster.  IMO, this is a failing of both VHDL and Verilog as the single process FSM is more prone to major logic errors -- things that can only be caught with really good simulation.  2-3 process versions are much more likely to produce logic errors that also generate synthesis warnings.  The single process style also has issues when you need combinatorial logic to be based on FSM transitions on the same cycle.  This occurs when a process interacts with a process in another module, in some cases.  Mostly fifo empty/full.

There are actually a lot of nifty ways to represent FSMs and to write them.  The main issue is checking to see if the tools actually do what you want.

 

In terms of encodings, one-hot is just one case.  Really, none of the encoding types is the best, and tools don't normally support anything but the basics.  four-hot, for example, might make more sense for an FPGA that uses LUTs as you can have a small encoding with efficient, but not instant decoding.  Likewise, a factor approach with a "state-group" selector and a "state within state group" might be better.  Even a 1-hot + state group (now more state bits than states) could lead to higher performance when lots of logic is based on logic being in any of a group of states.

 

--edit: for the 1-hot.  The logic is "if input is 0, transition to state 0 else if state isn't state0 transition to 2 else transition to 1."  In this case, you know that being in state2 is equivalent to not being in state0 and not being in state1.

[hamster]

19 minutes ago, Tickstart said:

Should I add "process(clk, ..... and rising_edge(clk) to every process? Does that make a difference? I don't really understand the importance of the sensitivity list, it doesn't seem to matter what I put there anyway.

The "sensitivity list" is the list of signals that will cause the body of the process to be evaluated when their values change.

It can be also thought of the list of all asynchronous inputs and any clock signals used in the process.

For hardware, usually the synthesis tool will generate the correct hardware anyway, regardless of any errors or omissions. For simulation they need to have all the required signals, as otherwise they body of the process won't be evaluated when it should be.

For clocked processes, it should usually just be the clock signal and any async reset signal (which shouldn't really be used in FPGAs anyway!)

For unclocked processes (asynchronous logic), it should be any signal that is used within the process.

A template for a clocked process is this:

process_name: process(clk, async_reset) 
  begin
    if async_reset = '1' then
       x  <= whatever_the_reset_state_is;
    elsif rising_edge(clk) then
       -- all your usual stuff 
       if a = '1' then
         x <= b AND c;
       end if;
    end if;
  end process;

In this case, if  a = '1', b ='1' and then c changes the output x doesn't change - it only changes when the clk rises or if reset is asserted, which is why a,b and c are not needed on the sensitivity list.

A template for an unclocked ("async") process is this:

process_name: process(a,b,c) 
  begin
    if a = '1' then
      x <= b AND c;
    end if;
  end process;

if a = '1' and b = 'a' the process needs to be evaluated every time 'c' changes, so 'c' has to be on the sensitivity list. Likewise the output might change if a or b changes value, depending on the values of the other inputs, so they have to be there too.

Having additional signals that aren't needed to the sensitivity list doesn't break anything, but it can waste time in simulation as the process triggers but nothing changes.

You can do other things like "wait until rising_edge(clk);", which avoids the "if rising_edge() then" and nesting, but that is not "the done thing", and considered being a bit of a smarty-pants.

[D@n]

@Tickstart,

I'm going to bow out at that question--I'm not familiar enough with VHDL to answer.  Perhaps @hamster can come back and answer better than I.

Dan

[Tickstart]

Should I add "process(clk, ..... and rising_edge(clk) to every process? Does that make a difference? I don't really understand the importance of the sensitivity list, it doesn't seem to matter what I put there anyway.

[D@n]

@Tickstart,

Yes, latches are bad.  Only transition your logic on the positive edge of the clock and you'll avoid latches.

I may be strange in how I do state machines.  I tend not to do them via a combinatorial process calculating the next step.  Rather, I've been known to calculate the next state directly within my clocked process.  It might not match the text book, but it's just as legal and I find it's easier to read.

Dan

[Tickstart]

I find when writing state machines like this Vivado has to infer latches from time to time, which is bad I think. I don't know if it's a flaw with the code or if I just need to initialize variables somewhere..

[Tickstart]

entity edge_detector is
	port (clk, I : in STD_LOGIC;
    	  Q : out STD_LOGIC);
end entity edge_detector;

architecture of edge_detector is

type state_type is (S0, S1, S2);
signal state, next_state : state_type;

begin

diagram: process(state)
		 begin
         	case state is
            	when S0		=> if I = '1' then
                				  next_state <= S1;
                               end if;
                when S1		=> if I = '1' then
                				  next_state <= S2;
                               else
                               	  next_state <= S0;
                   			   end if;
                when others => if I = '0' then
                				  next_state <= S0;
                               end if;
                end case;
          end process;
          
output:process(state)
		begin
        	case state is
            	when S1		=> Q <= '1';
                when others => Q <= '0';
            end case;
        end process;
        
transition:process(clk)
			begin
            	if rising_edge(clk)
                	state <= next_state;
                end if;
            end process;

That's the sort of VHDL FMS I've learnt from my text book. The author is close to 90 years old so I don't know how modern this approach is. I just wrote it here, not in Vivado so I haven't checked the syntax 100%. Does this do what I originally intended?

[Tickstart]

Yeah I don't know either. One-hot has never really worked for me, I don't even think it's that convenient. It's supposed to be faster in some cases, but screw it.

[D@n]

@Tickstart,

S2+ = I && (!S0)

This all makes sense, so ... the logic you are creating may just be due to the nature of the problem you've chosen.

I remember the last time I tried doing a one-hot encoding, it didn't make sense in the end since I still needed complex combinations of the state wires to determine the output.

Dan

[Tickstart]

@D@n,

Makes sense. So what did I do wrong? Is 1-hot incompatible with this problem or what? I still need those three states right?

[Tickstart]

@D@n,

Yes that's true. Is that legal though? I thought you derived the next state from current states, not other next states. Or are you making a different point? (: 

[D@n]

@Tickstart,

What do you get if you take (!S0+)&&(!S1+)?  You should get S2+.

Dan

[Tickstart]

@D@n,

You mean S2+? Cause in that case no, it isn't..? It's linearly independent of S1 and S0.

[Tickstart]

*wait, gimme a minute

[D@n]

@Tickstart,

You realize that S2 = (!S0)&&(!S1), right?  S2 therefore is a completely superfluous and un-necessary bit.  You knew this already, though, since you were building a "one-hot" encoding that used more bits than ceiling(log_2(# of states)).

Dan

[Tickstart]

Hey Dan, nice to see you again. You mean what works, my pseudocode? (:

 

What about my original problem, I still can't figure out why I seem to have one loose end, that pesky S2 state bit leading nowhere  :s

[D@n]

@Tickstart,

Yeah, that works.  Your "edge" logic will look like "(!last_pseudo_clock)&&(this_pseudo_clock)".  You're likely going to run one clock behind the rising edge, but you'll probably find this close enough.

Dan

[Tickstart]

Thanks Ham, I know about the "keep everything in one clock domain", that's probably the most important thing I've learnt from this forum and I was not planning on treason. Isn't it ok to create an artificial clock, for example dividing the real clock 16 times, running that signal through my currently non-existent edge-detector, and then checking that resulting signal on the edge of the real clock in a process? I.e, pseudocode:

-- pretend this is vhdl or something

slow_clk = divide(real_clk); -- the real clock goes into this black box also of course

edge = edge_detect(slow_clk); -- the real clock goes into this black box also of course

process(clk)
  begin
  	if rising_edge(clk)
  		if edge = '1' then
  			stuff;
end everything;

 

[hamster]

I know I am completely off topic, and being no help at all, but....

IMO an FSM is the wrong tool for the job, and that why it seems odd.

This is a pretty standard "build an FSM" assignment, but it involves creating a state machine where none is really needed. All you need to know is the state of the input during the previous clock cycle.

if rising_edge(clk) then
  if my_signal_last = '0' and my_signal = '1' then
    my_signal_rising_edge <= '1';
  else
    my_signal_rising_edge <= '0';
  end if;
  my_signal_last <= my_signal;
end if;

or

  -- concurrently detect the rising edge of my_signal. 
  -- It will be asserted when my_signal transitions from 
  -- zero to one.
  --
  -- You better make sure that my_signal is synchronised 
  -- to the clock for this to work correctly!
  --
  my_signal_rising_edge <= my_signal and not my_signal_last;
                         
process(clk)
  begin
    if rising_edge(clk) then 
      my_signal_last <= my_signal;
    end if;
  end if;

And as for "dividing the clock a few times", I shudder a little. Far better to keep everything in one clock domain,

  signal clock_enable_shift_register := std_logic_vector(7 downto 0) := "10000000";

generate_clock_enable_process: process(clk) 
  begin
    if rising_edge(clk) then
      clock_enable <= clock_enable_shift_register(0);
      clock_enable_shift_register <=clock_enable_shift_register(0) & clock_enable_shift_register(clock_enable_shift_register'high downto 1);                   end if;
  end process;
  
do_stuff_slowly_process: process(clk)
  begin
    if rising_edge(clk) then
      if clock_enable = '1' then
         ... do stuff once in a while
      end if
    end if;
  end process;

 

[Tickstart]

Is my assumption about the illegal states/don't-cares wrong (see the scribbled out crossed out areas in the K-map)? Shall I be explicit and state S2+ = I • (not S0) • (S2 ⊕ S1) instead of S2+ = I • (not S0)?

*edit: But that doesn't make any sense since then the only signal dependent on S2 would be S2+, circular logic which is completely unnecessary. Yeah, I have no clue.