Gate Level model of a Finite state machine

[Inderkal]

Does anybody have any ideas about implementing a gate level model of a
finite state machine? Any kind of info will do. I just want to get
started.

 

[rickman]

Does anybody have any ideas about implementing a gate level model of a
finite state machine? Any kind of info will do. I just want to get
started.

While working with one-hot encoded state machines, I realized that the
input function for each state register was a simple two level sum of
products.

Your state diagram will have arrows representing the transitions between
states. A condition is associated with each transition. If you express
each transition as a product (AND) of the state and the condition you
can then sum (OR) the resulting products to form the input function to
the state register.

This can be generalized to different encoding schemes by using a full
decode for the state input. The resulting sum will be used to form the
next state value. All of these values may be further summed (ORed) to
form the complete state=>next-state function for the machine. This
generalize method also works for the one-hot encoding, but since all
state values assert a single bit in the state variable, it can be done
with the simpler method above.

--

Rick "rickman" Collins

(e-mail address removed)
Ignore the reply address. To email me use the above address with the XY
removed.

Arius - A Signal Processing Solutions Company
Specializing in DSP and FPGA design URL http://www.arius.com
4 King Ave 301-682-7772 Voice
Frederick, MD 21701-3110 301-682-7666 FAX

 

[Weng Tianxiang]

Rick,
If at State1 and NextState jumps to State2, you don't mention to clear
State1 register. Am I right or it isn't needed?

Weng

 

[rickman]

Rick,
If at State1 and NextState jumps to State2, you don't mention to clear
State1 register. Am I right or it isn't needed?

You cover that by specifying that state1 is continued while there is no
active condition that *leaves* state1.

-foo -bar
+----+ +----+
| | | |
V | foo V | bar
+--> state1 ----------> state2 ---+
| |
+---------------------------------+

So the equation for next_state1 will be:

next_state1 <= state1 & -foo + state2 & bar;

next_state2 <= state2 & -bar + state1 & foo;

If you have more than one exit from a state, the condition for staying
in the state is the product of all the negated exit conditions.
statefoo * -bar * -foo * -others

So just treat staying in a state as another transition.

--

Rick "rickman" Collins

(e-mail address removed)
Ignore the reply address. To email me use the above address with the XY
removed.

Arius - A Signal Processing Solutions Company
Specializing in DSP and FPGA design URL http://www.arius.com
4 King Ave 301-682-7772 Voice
Frederick, MD 21701-3110 301-682-7666 FAX

 

[Paul Uiterlinden]

Does anybody have any ideas about implementing a gate level model of a

Gate level model? You mean RTL model? Or do you really want to design at
gate level?

finite state machine? Any kind of info will do. I just want to get
started.

Vending machine, trafic light controller, elevator controller. Use your
imagination.

Paul.

 

[Inderkal]

Hi Paul,
I implemented a RTL model for a reed solomon encoder using a state
machine for my controller. Now I am bringing everything down to gate
level. The architecture was no problem. but I do not know how to start
with the controller.

 

[Mike Treseler]

Now I am bringing everything down to gate
level. The architecture was no problem. but I do not know how to start
with the controller.

Consider using synthesis to make a gate level netlist.

-- Mike Treseler

 

[Weng Tianxiang]

Rick,
I learn what you say from some textbooks, what you say is right.

I want to know if you are a professional compiler designer? i.e. if
what you say is what really most market predominant ASIC compiler
providers do with the above equations?

Weng

 

[rickman]

Rick,
I learn what you say from some textbooks, what you say is right.

I want to know if you are a professional compiler designer? i.e. if
what you say is what really most market predominant ASIC compiler
providers do with the above equations?

No, I don't write compilers. I use compilers. I don't know how
compilers work on the inside and I try not to need to. I much prefer to
write my code to limit what the compiler can do and force a given
implementation. Writing your equations the way I describe allows you to
contol the mapping of the equation to hardware if you need to.

--

Rick "rickman" Collins

(e-mail address removed)
Ignore the reply address. To email me use the above address with the XY
removed.

Arius - A Signal Processing Solutions Company
Specializing in DSP and FPGA design URL http://www.arius.com
4 King Ave 301-682-7772 Voice
Frederick, MD 21701-3110 301-682-7666 FAX