Gate Level model of a Finite state machine

I

Inderkal

Guest
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.
 
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
 
Inderkal wrote:
Does anybody have any ideas about implementing a gate level model of a
Click to expand...
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.
Click to expand...
Vending machine, trafic light controller, elevator controller. Use your
imagination.

Paul.
 
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.
 
Inderkal wrote:
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.
Click to expand...
Consider using synthesis to make a gate level netlist.

-- Mike Treseler
 
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
 
Weng Tianxiang wrote:
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?
Click to expand...
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

rick.collins@XYarius.com
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
 
Inderkal wrote:
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.
Click to expand...
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

rick.collins@XYarius.com
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 wrote:
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?
Click to expand...
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

rick.collins@XYarius.com
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
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top