[sdiy] complex logic problem

[ASSI]

On Mittwoch, 23. August 2006 22:11, Tavys Ashcroft wrote:
> I'm working on a sequencer design that is probably going to require
> at least a small microcontroller or FPGA to take care of some logic. 
> But before I go that route, I want to lay out a big old truth table
> and see if I can reduce my logic needs down to a realistic number of
> gates.  Perhaps I can get away with using a handfull of CMOS chips.

When you say "logic for a sequencer", do you mean the complete state 
machine or just the state transition logic?  If you've already fixed 
the state encoding, the minimization of the transition logic is 
comparatively easy, but may not produce the solution you wish for.

> Is there any software out there that would automate this process, or
> at least assist?

Any of the free FPGA/PLD development allows to optimize combinatorial 
logic, the closest to the thruth table approach would probably be ABEL 
or similar languages developed for relatively small PLD.  The results 
naturally map less well to CMOS chips than the target architecture of 
the respective system, but at least you get a rough idea of how many 
gates you'd really need (or just skip the CMOS chips and go to CPLD 
directly).

> I'm hoping to just fill out a giant truth table and 
> have software give me possible combinations of gates that would
> create the result I'm looking for.  Does such a thing exist?

That would be quite a feat for any nontrivial logic function. The 
optimal synthesis problem is NP complete and there are many seemingly 
simple functions that have exponential complexity with the number of 
inputs.  There are some academic synthesis programs, but I don't 
remember any of them specifically targeting CMOS series chips - all 
that I've seen targeted LUT-based ASIC or FPGA architectures.

> If not, could somebody point me to a good primer for doing this
> by hand?

Small combinatorial functions (up to 5 inputs) can be optimized by 
Karnaugh-Veitch maps, you should find plenty of descriptions and even 
some Java applets on the web.  Larger functions are tractable via the 
Quine-McCluskey algorithm, there is at least one online optimizer using 
this algorithm - search for the phrase "Gateway to Logic".  Synthesis 
today uses so-called binary decision diagrams (BDD, not BBD :-), again 
there's plenty of info to be found on the web.  Optimiziation of the 
state machine itself involves chosing a suitable coding (one-hot, 
binary, Gray, etc.), which directly relates to the minimum number of 
registers (flip-flops) you need.  One-hot encoding (that is one FF for 
each state) are good for minimization of the transistion logic and are 
easily understood intuitively, especially if the state graph is sparse 
and each state has only a few incoming and exiting transitions.  Beware 
that one-hot state machines are "unsafe", you should dedicate extra 
logic that resets the state machine when more than one state is "hot".  
There is much less info available on optimization of state machines, 
but the JHDL package at http://www.jhdl.org has an FSM generator module 
that might just do what you want (or not, I've never tried the 
software).


Achim.
-- 
+<[Q+ Matrix-12 WAVE#46 Neuron microQkb Andromeda XTk sonic heaven]>+

Wavetables for the Terratec KOMPLEXER:
http://Stromeko.Synth.net/Downloads.html#KomplexerWaves