FSM state minimization with ISE?

Hi Mike,
what do you mean with winner? Lowest overall FF count?
Sure, but there was never a doubt about it.
The question was if a state minimzation can be performed with ISE 
regardless of the encoding style.

The Quartus results are quite interesting.
In pseudo_states.pdf we can see the states before(!) minimization. From 
the autogenerated diagram it's kind of hard to see that the states build 
a decision tree. (Well... tools :-) )
It's funny to see that S7 and S11 are in double circles unlike the other 
  States above S6.
The only difference between the double circled states and the single 
circled states is, that Y remains constantly '0'.

The ptd-fsm checks a serial bitstream X for non-BCD tetrades with LSB 
first (at S0) and MSB last (at S(>6)), setting the output Y at that moment.
Now what happens in the QUARTUS created FSM when it should branch to S7 
or S11. Does it remain in S3 or S5 for 2 clock cycles? How?
Or has it really kicked away these states, thus running out of 
synchronization with the data stream. (I doubt, but who knows.)
May be it goes over states S8 or S12 and does a tricky output decoding.

At least it does some minimization, even if it wasn't expected that way.
Thank you for presenting these results.

Best regards
   Eilert



Mike Treseler schrieb:
> backhus wrote:
> 
>> Mike, interesting result from Quartus. At least it seems to do some 
>> optimization.
> 
> It may be of academic interest,
> but binary encoding is the clear winner here,
> as it usually is in small cases.
> Even in large cases the difference is
> mostly one of speed, not area.
> 
>> Is there anything in the synthesis report that gives information about 
>> what exactly was done to the FSM?
> 
> looks like it pitched 7 and 11:
> http://home.comcast.net/~mike_treseler/pseudo.pdf
> http://home.comcast.net/~mike_treseler/pseudo_states.pdf
> 
>       -- Mike Treseler

backhus wrote:
> Hi Mike,
> what do you mean with winner? Lowest overall FF count?
> Sure, but there was never a doubt about it.
> The question was if a state minimzation can be performed with ISE
> regardless of the encoding style.
>
> The Quartus results are quite interesting.
> In pseudo_states.pdf we can see the states before(!) minimization. From
> the autogenerated diagram it's kind of hard to see that the states build
> a decision tree. (Well... tools :-) )
> It's funny to see that S7 and S11 are in double circles unlike the other
>   States above S6.
> The only difference between the double circled states and the single
> circled states is, that Y remains constantly '0'.
>
> The ptd-fsm checks a serial bitstream X for non-BCD tetrades with LSB
> first (at S0) and MSB last (at S(>6)), setting the output Y at that moment.
> Now what happens in the QUARTUS created FSM when it should branch to S7
> or S11. Does it remain in S3 or S5 for 2 clock cycles? How?
> Or has it really kicked away these states, thus running out of
> synchronization with the data stream. (I doubt, but who knows.)
> May be it goes over states S8 or S12 and does a tricky output decoding.
>
> At least it does some minimization, even if it wasn't expected that way.
> Thank you for presenting these results.
>
> Best regards
>    Eilert
>
>
>
> Mike Treseler schrieb:
> > backhus wrote:
> >
> >> Mike, interesting result from Quartus. At least it seems to do some
> >> optimization.
> >
> > It may be of academic interest,
> > but binary encoding is the clear winner here,
> > as it usually is in small cases.
> > Even in large cases the difference is
> > mostly one of speed, not area.
> >
> >> Is there anything in the synthesis report that gives information about
> >> what exactly was done to the FSM?
> >
> > looks like it pitched 7 and 11:
> > http://home.comcast.net/~mike_treseler/pseudo.pdf
> > http://home.comcast.net/~mike_treseler/pseudo_states.pdf
> >
> >       -- Mike Treseler

Hi All,
  First, apologies to Eilert and Mike:

  Eilert, I posted in haste on Tuesday, not giving full consideration
to your original post, thought you were the student, not the
instructor, and so the unfortunate RTM comment. Mike, I tried this out
at home yesterday on my laptop, and "auto" used to produce one-hots in
ISE 6.1, so you were right then.

  Tommy, when I said "LUT usage increase", I was (wrongly) comparing
apples to oranges, i.e., ISE to Quartus. ISE 8.1 gave 10 LUTs (auto,
with sequential binary coding) where Quartus gave 13 LUTs.

Trying to contribute a little more:

Today I tried ISE with "compact" encoding, and it produced a solution
w/ 4 FFs, and 6 LUTs.

Finally, I tried the "hand" reduction myself. Not using pen/paper, but
with an editor, eye-balling for equivalent states, and replacing all
equivalent states with the lowest numbered state in an eqiv group. It
takes more than one pass, and I ended up with a different final number
than the 7 states that Eilert posted (Eilert, since this is a class
exercise, I'll send you the final result direct). Putting the final
reduced state machine through ISE w/ compact encoding resulted in: 3
FFs, 3 LUTs. (I think XST gave the same speed estimate for both the 4
FF and the 3 FF solution, and I am not going go further and try hand
placing and routing)

This simple example is a very good demonstration that state reduction
can produce dramatic resource reduction: 4 FFs => 3 FFs, 6 LUTs => 3
LUTs. I don't get excited about anything less than a factor of 2
lately, but the LUT results clearly indicate that this can be a very
valuable feature for a synthesis tool, in spite of the difficulty
reconciling functional sim with post synth sim...after all, the states
can remain hidden. It's certainly an easy process algorithmically,
given a canonical represention of each state...

So I've reversed my opinion, because I'm often wrong, and remain,
Just John
(aka John Smith (Not to be confused with a certain noisy Viking))

Hi Tommy,
your solution is perfectly correct!
While the example comes from the script and has 6 states in the end, my 
(then absent) mind was fixed to the laboratory assignment, which is 
slightly different and has the mentioned 7 States.

Sorry for causing confusion.

Best Regards
   Eilert

Hi John,
you are the second that comes up with a 6 state solution. That made me 
doubt about my posted code, so I fed it into DesignCompiler and got the 
same result. I nearly went mad, looking for the mistake when I finally 
took a look in the mirror, and there it was! :-)

I have to apologize.

Tommys solution (and yours probably too) is correct. I confused the 
script exercise (which I posted) with the slightly different lab 
exercise. The lab exercise reduces to 7 States.

The solution to the posted script exercise is in the script anyway 
(That's why we have created a different version for the lab), and  the 
VHDL version has already been posted by Tommy.

If you want to send me your results use this link to get my real 
email-adress:

http://www.i3m.hs-bremen.de/internet/contacts/

After all it was a nice brain teaser, wasn't it?
It's correct that more than one pass is needed to do a complete 
minimization. And now that you have posted some results about saved 
resources everyone should ask why these algorithms are not available in 
ISE XST. (I already opened a webcast, since none of the XILINX guys in 
this Newsgroup wrote any statement)

Best Regards
   Eilert




> Finally, I tried the "hand" reduction myself. Not using pen/paper, but
> with an editor, eye-balling for equivalent states, and replacing all
> equivalent states with the lowest numbered state in an eqiv group. It
> takes more than one pass, and I ended up with a different final number
> than the 7 states that Eilert posted (Eilert, since this is a class
> exercise, I'll send you the final result direct). Putting the final
> reduced state machine through ISE w/ compact encoding resulted in: 3
> FFs, 3 LUTs. (I think XST gave the same speed estimate for both the 4
> FF and the 3 FF solution, and I am not going go further and try hand
> placing and routing)
> 
> This simple example is a very good demonstration that state reduction
> can produce dramatic resource reduction: 4 FFs => 3 FFs, 6 LUTs => 3
> LUTs. I don't get excited about anything less than a factor of 2
> lately, but the LUT results clearly indicate that this can be a very
> valuable feature for a synthesis tool, in spite of the difficulty
> reconciling functional sim with post synth sim...after all, the states
> can remain hidden. It's certainly an easy process algorithmically,
> given a canonical represention of each state...
> 
> So I've reversed my opinion, because I'm often wrong, and remain,
> Just John
> (aka John Smith (Not to be confused with a certain noisy Viking))
> 

backhus wrote:
> what do you mean with winner? Lowest overall FF count?

Sorry. I thought you meant converting a graph
to a netlist and minimizing the logic, maybe like this:

http://www.ece.utexas.edu/~adnan/syn-03/SIS_paper.pdf

> The question was if a state minimzation can be performed with ISE 
> regardless of the encoding style.

Minimizing an arbitrary digraph is a hard problem,
so I'm not surprised the tools punt it.

> The Quartus results are quite interesting.
> In pseudo_states.pdf we can see the states before(!) minimization.

Yes, it drew them for me without even
being asked.

> The only difference between the double circled states and the single 
> circled states is, that Y remains constantly '0'.

That makes some sense, as zero outputs
require no state decodes for d-flop synthesis.

> The ptd-fsm checks a serial bitstream X for non-BCD tetrades with LSB 
> first (at S0) and MSB last (at S(>6)), setting the output Y at that moment.
> Now what happens in the QUARTUS created FSM when it should branch to S7 
> or S11. Does it remain in S3 or S5 for 2 clock cycles? 

Run a sim on the netlist.
I expect that it is functionally equivalent.

> Thank you for presenting these results.

You are welcome.

     -- Mike Treseler

Hi everybody,
XILINX answered my webcast:

"I've spoken to our XST expert and he informed me that FSM minimization
isn't a feature of XST. If you have two states that are totally
identical then the tool will optimise them, otherwise the FSM will be
encoded with the encoding algorithm specified within the process
properties. "

Bad news for this topic.
I'm going to check out Precision Synthesis RTL on this.

Best regards
   Eilert