one-hot encoding and fale-safe condition.

Discussion in 'VHDL' started by Mohammed A khader, Jan 24, 2005.

  1. Hi all,

    I am designing a fsm which has more then 8 states.I would like to have
    a one-hot machine but at the same time it should have the fail-safe
    condition that is if accidentally fsm goes into illegal state(i:e Two
    or more FFs are high) then it should be forced back to initial state.
    That is having WHEN others => next_state <=Inital_state clause as
    the last statement.

    But if I implement that then the function for next state becomes as
    many states as my fsm is having.

    Do we have any technique to detect an illegal state while making the
    fsm as one-hot.

    Thanks in Advance.
     
    Mohammed A khader, Jan 24, 2005
    #1
    1. Advertising

  2. Mohammed A khader wrote:

    > I am designing a fsm which has more then 8 states.I would like to have
    > a one-hot machine but at the same time it should have the fail-safe
    > condition that is if accidentally fsm goes into illegal state(i:e Two
    > or more FFs are high) then it should be forced back to initial state.


    The basis for one-hot encoding is that it might save some gates.
    However when you add the fail-safe requirement to a one-hot
    machine, this savings (if there really is any) goes out the window.

    Another twist that synthesis may optimize out the "WHEN others" logic
    in any case.

    Consider binary encoding.

    -- Mike Treseler
     
    Mike Treseler, Jan 24, 2005
    #2
    1. Advertising

  3. Never do anything like adding fail-save conditions for a state machine.
    You just waste your time.

    Intel, AMD never do it. Professtionals never do it. Why? If your logic
    is correct, you don't have to worry about any unsafe conditions.

    Weng
     
    Weng Tianxiang, Jan 24, 2005
    #3
  4. Mohammed  A khader

    jtw Guest

    If your inputs and your clock are correct, you never have to worry....

    Now try real life, with clocks that may get turned on and off. Add
    excessive jitter. Any stray 'event' that causes the state machine to enter
    the 'twilight zone.'

    Don't bet that the big guys don't do it when the circumstances demand
    automatic recovery from an errant condition.

    Jason

    "Weng Tianxiang" <> wrote in message
    news:...
    > Never do anything like adding fail-save conditions for a state machine.
    > You just waste your time.
    >
    > Intel, AMD never do it. Professtionals never do it. Why? If your logic
    > is correct, you don't have to worry about any unsafe conditions.
    >
    > Weng
     
    jtw, Jan 25, 2005
    #4
  5. Mohammed A khader wrote:
    > But if I implement that then the function for next state becomes as
    > many states as my fsm is having.


    Actually, with one hot I would expect the others branch to contain way more
    states than your fsm. Not that this matters of course, since your compiler
    should handle that for you. What exactly are your reasons for wanting a
    one-hot fsm?

    > Do we have any technique to detect an illegal state while making the
    > fsm as one-hot.


    I'd leave that to the compiler; in general they're a lot better at reducing
    logic than you or I.

    Regards,

    Pieter Hulshoff
     
    Pieter Hulshoff, Jan 25, 2005
    #5
  6. Mike Treseler worte:
    >The basis for one-hot encoding is that it might save some gates.
    >However when you add the fail-safe requirement to a one-hot
    >machine, this savings (if there really is any) goes out the window.


    >Another twist that synthesis may optimize out the "WHEN others" logic
    >in any case.
    >Consider binary encoding.


    Thank you very much Mike. I have considered your suggestion but now I
    have much similar problem to ask in in Binary Encoding..
    Following is the excerpt from the synopsys
    documentation...................

    " Designers using VHDL often create an enumerated type for their FSM,
    as shown in
    the following example:

    type state_type is (IDLE, S1, S2, S3,S4);
    signal state, next_state : state_type;
    begin
    process (state, NEXT)
    begin
    next_state <= state;
    case state is
    when IDLE =>
    if (NEXT) then
    next_state <= S1;
    end if;
    when S1 =>
    if (NEXT) then
    next_state <= S2;
    end if;
    when S2 =>
    if (NEXT) then
    next_state <= S3;
    end if;
    when S3 =>
    if (NEXT) then
    next_state <= S4;
    end if;
    when S4 =>
    if (NEXT) then
    next_state <= IDLE;
    end if;
    end case;
    end process;

    In this example, the behavior for each of the enumerated states is
    described.
    However, when this code is synthesized to hardware, there will be three
    remaining states in which the FSM can potentially get stuck. Using
    "when
    others" is not sufficient by itself to prevent problems in this
    situation,
    because no other enumerated states exist for this type. Consequently
    dummy
    states must be created to make the FSM fail-safe.

    Dummy States Example

    type state_type is (IDLE, S1, S2, S3, S4, S5_dummy, S6_dummy,
    S7_dummy);
    signal state, next_state : state_type;
    begin
    process (state, NEXT)
    begin
    next_state <= state;
    case state is
    when IDLE =>
    if (NEXT) then
    next_state <= S1;
    end if;
    when S1 =>
    if (NEXT) then
    next_state <= S2;
    end if;
    when S2 =>
    if (NEXT) then
    next_state <= S3;
    end if;
    when S3 =>
    if (NEXT) then
    next_state <= S4;
    end if;
    when S4 =>
    if (NEXT) then
    next_state <= IDLE;
    end if;
    when others =>
    next_state <= "IDLE";
    end case;
    end process;

    Design Compiler will report that these dummy states are unreachable
    because
    there are no transitions into them, but the transition logic from the
    dummy
    states back to the useful states will still be synthesized.
    Fortunately, Design
    Compiler doesn't automatically remove the unreachable dummy states.
    However,
    when an FSM optimization command such as fsm_enable_state_minimization
    is used,
    these unreachable states are optimized away. Therefore, to build a
    fail-safe
    FSM, do not use the FSM optimization capability."

    Now I would like to ask that if a design has 17 legal states then do
    I have to follow the same guidelines and create additional 15 dummy
    states to accomplish fail-safe requirments. Or do we have any other
    better technique for this.

    Thanks..
    -- Mohammed A khader.
     
    Mohammed A khader, Jan 25, 2005
    #6
  7. Mohammed A khader wrote:

    > Thank you very much Mike. I have considered your suggestion but now I
    > have much similar problem to ask in in Binary Encoding..


    Binary encoding gives you an inherent transition to
    to state zero from any undefined state for little
    or no cost. This is not fail-safe, but it is
    simple and I expect that doing any more is not
    worth the effort.

    Real trouble in large designs is more likely
    from missing or inadequate synchronization,
    than it is from cosmic rays.

    -- Mike Treseler
     
    Mike Treseler, Jan 25, 2005
    #7
  8. Clyde R. Shappee wrote:

    > Pieter Hulshoff wrote:
    >
    >> Mohammed A khader wrote:
    >>
    >>> But if I implement that then the function for next state becomes as
    >>> many states as my fsm is having.

    >>
    >>
    >>
    >> Actually, with one hot I would expect the others branch to contain way
    >> more
    >> states than your fsm. Not that this matters of course, since your
    >> compiler
    >> should handle that for you. What exactly are your reasons for wanting a
    >> one-hot fsm?
    >>
    >>
    >>> Do we have any technique to detect an illegal state while making the
    >>> fsm as one-hot.

    >>
    >>
    >>
    >> I'd leave that to the compiler; in general they're a lot better at
    >> reducing
    >> logic than you or I.
    >>
    >> Regards,
    >>
    >> Pieter Hulshoff
    >>

    > As mentioned earlier many compilers optimise out the when others choice.
    >
    > If one really wants one hot, it is really easy to guard against a
    > failure. If the machine fails the next state logic will transisition
    > to all state bits as a zero. So, I always code the others case and one
    > I call "hung" to transition from an all zero case to whatever state I
    > want the machine to recover to.


    This is not sufficient. Noise and/or timing issues are just as likely to
    result in a 2-or-more-hot state as in the 0-hot state you are covering.
    See
    <http://groups.google.ca/groups?hl=en&lr=&selm=3FC2E205.A635F699%40no.spam>
    where this has been covered previously.
    --
    Tim Hubberstey, P.Eng. . . . . . Hardware/Software Consulting Engineer
    Marmot Engineering . . . . . . . VHDL, ASICs, FPGAs, embedded systems
    Vancouver, BC, Canada . . . . . . . . . . . http://www.marmot-eng.com
     
    Tim Hubberstey, Jan 29, 2005
    #8
  9. Pieter Hulshoff wrote:
    > Mohammed A khader wrote:
    >
    >>But if I implement that then the function for next state becomes as
    >>many states as my fsm is having.

    >
    >
    > Actually, with one hot I would expect the others branch to contain way more
    > states than your fsm. Not that this matters of course, since your compiler
    > should handle that for you. What exactly are your reasons for wanting a
    > one-hot fsm?
    >
    >
    >>Do we have any technique to detect an illegal state while making the
    >>fsm as one-hot.

    >
    >
    > I'd leave that to the compiler; in general they're a lot better at reducing
    > logic than you or I.
    >
    > Regards,
    >
    > Pieter Hulshoff
    >

    As mentioned earlier many compilers optimise out the when others choice.

    If one really wants one hot, it is really easy to guard against a
    failure. If the machine fails the next state logic will transisition
    to all state bits as a zero. So, I always code the others case and one
    I call "hung" to transition from an all zero case to whatever state I
    want the machine to recover to.

    (Rove the under score to get a real address.)

    Clyde
     
    Clyde R. Shappee, Jan 30, 2005
    #9
  10. Tim Hubberstey wrote:
    > Clyde R. Shappee wrote:
    >
    >> Pieter Hulshoff wrote:
    >>
    >>> Mohammed A khader wrote:
    >>>
    >>>> But if I implement that then the function for next state becomes as
    >>>> many states as my fsm is having.
    >>>
    >>>
    >>>
    >>>
    >>> Actually, with one hot I would expect the others branch to contain
    >>> way more
    >>> states than your fsm. Not that this matters of course, since your
    >>> compiler
    >>> should handle that for you. What exactly are your reasons for wanting a
    >>> one-hot fsm?
    >>>
    >>>
    >>>> Do we have any technique to detect an illegal state while making the
    >>>> fsm as one-hot.
    >>>
    >>>
    >>>
    >>>
    >>> I'd leave that to the compiler; in general they're a lot better at
    >>> reducing
    >>> logic than you or I.
    >>>
    >>> Regards,
    >>>
    >>> Pieter Hulshoff
    >>>

    >> As mentioned earlier many compilers optimise out the when others choice.
    >>
    >> If one really wants one hot, it is really easy to guard against a
    >> failure. If the machine fails the next state logic will transisition
    >> to all state bits as a zero. So, I always code the others case and
    >> one I call "hung" to transition from an all zero case to whatever
    >> state I want the machine to recover to.

    >
    >
    > This is not sufficient. Noise and/or timing issues are just as likely to
    > result in a 2-or-more-hot state as in the 0-hot state you are covering.
    > See
    > <http://groups.google.ca/groups?hl=en&lr=&selm=3FC2E205.A635F699%40no.spam>
    > where this has been covered previously.

    A two or more hot state will then transisiton to the all zeros case, and
    as I propose, the machine would recover. It just takes two illegal
    states before the machine recovers. Maybe not what you desire, but it
    recovers.

    Clyde
     
    Clyde R. Shappee, Jan 30, 2005
    #10
  11. Clyde R. Shappee wrote:
    >
    > Tim Hubberstey wrote:
    >
    >> Clyde R. Shappee wrote:
    >>>
    >>> If one really wants one hot, it is really easy to guard against a
    >>> failure. If the machine fails the next state logic will
    >>> transisition to all state bits as a zero. So, I always code the
    >>> others case and one I call "hung" to transition from an all zero case
    >>> to whatever state I want the machine to recover to.

    >>
    >> This is not sufficient. Noise and/or timing issues are just as likely
    >> to result in a 2-or-more-hot state as in the 0-hot state you are
    >> covering. See
    >> <http://groups.google.ca/groups?hl=en&lr=&selm=3FC2E205.A635F699%40no.spam>
    >> where this has been covered previously.

    >
    > A two or more hot state will then transisiton to the all zeros case, and
    > as I propose, the machine would recover. It just takes two illegal
    > states before the machine recovers. Maybe not what you desire, but it
    > recovers.


    No, that's not guaranteed. The reason for using one-hot is that state
    "decoding" consists of sampling the output of a single state FF. This
    means the state machine does not consider the output of any other state
    FFs except for the current state FF when making a transition. The result
    is that if 2 state FFs are set, the machine will transition to 2
    (probably different) next states simultaneously.

    As a very simple example, consider this example code:

    type state_vector is (state1,state2,state3,state4);
    ....
    case state_vector is
    when state1 => state_vector <= state2;
    when state2 => state_vector <= state3;
    when state3 => state_vector <= state4;
    when state4 => state_vector <= state1;
    end case;

    Without any safety logic, this translates to the following logic (use
    fixed-space font to view):

    +- state1 +- state2 +- state3 +- state4
    | | | |
    +---[d FF1 q]-+-[d FF2 q]-+-[d FF3 q]-+-[d FF4 q]-+-+
    | |
    +---------------------------------------------------+

    It is obvious from looking at this that if a two-hot situation arises,
    the machine will always have 2 FFs set from then on. In the more general
    case, a machine will probably converge to having only 1 FF hot but this
    is by no means guaranteed, will take an indeterminate number of clocks,
    and the resulting parallel states will wreak who knows what kind of
    havoc on the rest of the circuit before converging.
    --
    Tim Hubberstey, P.Eng. . . . . . Hardware/Software Consulting Engineer
    Marmot Engineering . . . . . . . VHDL, ASICs, FPGAs, embedded systems
    Vancouver, BC, Canada . . . . . . . . . . . http://www.marmot-eng.com
     
    Tim Hubberstey, Feb 1, 2005
    #11
  12. Tim Hubberstey wrote :
    >No, that's not guaranteed. The reason for using one-hot is t­hat

    state
    >"decoding" consists of sampling the output of a single state­ FF.
    >This means the state machine does not consider the output of any

    ­other state
    >FFs except for the current state FF when making a transition­. The

    result
    >is that if 2 state FFs are set, the machine will transition ­to 2
    >(probably different) next states simultaneously.


    Yes, I completely agree with this. The rate of comversion to legal
    state will be more unpredictable if it has more states.For example
    consider a state machine with 40 states . Due to noise if state 3
    and state 12 are set as high , then in next clock cycle state 4 and
    state 13 will be high and then state 5 and state 14 and so on ...

    But can we have some extra logic to detect if more then 1 bit is
    high. Is it possible to read the State FFs and check whether more then
    1 bit is high with some combinational logic and give this output as
    the input to the one-hot fsm. That is state machine would have one
    more extra input signal to resolve the next state. Has anybody tried as
    the combinational logic which I am refering here.Is it practically
    feasibly to do like this.

    Mohammed A khader.
     
    Mohammed A khader, Feb 1, 2005
    #12
  13. Tim Hubberstey wrote:

    > As a very simple example, consider this example code:
    >
    > type state_vector is (state1,state2,state3,state4);
    > ...
    > case state_vector is
    > when state1 => state_vector <= state2;
    > when state2 => state_vector <= state3;
    > when state3 => state_vector <= state4;
    > when state4 => state_vector <= state1;
    > end case;
    >
    > Without any safety logic, this translates to the following logic (use
    > fixed-space font to view):
    >
    > +- state1 +- state2 +- state3 +- state4
    > | | | |
    > +---[d FF1 q]-+-[d FF2 q]-+-[d FF3 q]-+-[d FF4 q]-+-+
    > | |
    > +---------------------------------------------------+


    Well said.
    If this example were redone with binary encoding, illegal
    states would return to zero.

    -- Mike Treseler
     
    Mike Treseler, Feb 1, 2005
    #13
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. mobi999
    Replies:
    0
    Views:
    761
    mobi999
    Jun 9, 2007
  2. Sandy Miller

    Java EE Developer-HOT HOT OPENINGS

    Sandy Miller, Jan 8, 2008, in forum: Java
    Replies:
    0
    Views:
    374
    Sandy Miller
    Jan 8, 2008
  3. Sandy Miller
    Replies:
    0
    Views:
    347
    Sandy Miller
    Jan 17, 2008
  4. Sandy Miller
    Replies:
    0
    Views:
    541
    Sandy Miller
    Jan 28, 2008
  5. Sandy Miller
    Replies:
    0
    Views:
    391
    Sandy Miller
    Feb 1, 2008
Loading...

Share This Page