5

Given a black box with N binary inputs and specification of the output for every one of the 2**N possible input states (but no pre-knowledge of the logic in the box) I need software tools to design the minimal gate logic in the box. What method or software can anyone suggest, and can it handle problems with N=256 ?

cuddlyable3
  • 468
  • 2
  • 10
  • 1
    Like an automatic Karnaugh map simplifier? http://k-map.sourceforge.net/ – Mister Mystère Apr 14 '15 at 22:28
  • @Mister Mystère the code that you linked has a pretty (educational) GUI and makes a sum-of-products expression for up to N=5 maximum. I don't actually need the GUI, map or interactive speed, nor do I have don't-care states in my specification. – cuddlyable3 Apr 16 '15 at 20:44
  • It looks like it's open source, you can look at the algorithm. With any luck only the GUI is limited in the number of states. Otherwise, have you looked online for arbitrarily big karnough tables solvers? – Mister Mystère Apr 16 '15 at 23:28
  • @Mister Mystère A Karnaugh map (call it a karnough[_sic_] table if you will) is useful for spotting patterns by subjective inspection; it is likable for education and its 2-D nature limits its use to a small number of variables. My specification states every one of 2**N products with none remaining to exploit as "don't care". I think it obvious that for N=256 it is no help trying to look at a map sized 3.4E38 x 3.4E38. – cuddlyable3 Apr 19 '15 at 09:56
  • Why would you need so many variables? What are the requirements exactly (number of variables, duration of solution...)? This would be better suited to the mathematics stackexchange, but going down the Karnaugh map solver gets you this infinite variables solver: http://www.codeproject.com/Articles/649849/A-Cplusplus-Karnaugh-Map-Minimizer-Infinite-Variab. Maybe the algorithm can be tweaked so that 256 variables can be handled by the PC (RAM will certainly be the main issue). Also, you should probably drop the sarcasm with people who are trying to help you. – Mister Mystère Apr 20 '15 at 00:14
  • I design hardware to extract the RC4 stream cipher key bits from 256 captured key stream bits. Brute force search is impractical even for off-line cryptanalysis but an eventual FPGA implementation may succeed. I shall study A. Asem's C++ code that you linked with a view to mapping variables to hard disk storage. Thank you for politeness. http://en.wikipedia.org/wiki/RC4 – cuddlyable3 Apr 21 '15 at 02:47
  • [Espresso heuristic logic minimizer](http://en.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer) may be of interest. – Tut May 04 '15 at 13:25

4 Answers4

2

For implementation of a complex boolean function it is normally done either by putting in an FPGA in which case the FPGA software will do the minimization (not necessarily into gates but more likely into LUTs) or you can directly put the table into a memory (FLASH, RAM whatever is appropriate for the speed you need).

For the memory implementation the binary input signals form the address inputs into the memory.

In modern logic you will rarely find a large number of gates used in an implementation of a logic function, a table look up approach is much more commonly used (FPGA or discrete).

Kevin White
  • 32,097
  • 1
  • 47
  • 74
1

I see two (similar) paths:

  • use an FPGA programming tool, like Xilinx ISE or Vivado (WebPack is free for both), entering your initial expression in Verilog (for example) and seeing its optimized version as RTL schematics after structural synthesis (first step of compilation, optimization must be enabled).

    http://www.xilinx.com/support/download.html

  • use a less complex tool, like the Atmel SPLC/CPLD tools, ProChip Designer or WinCUPL, typing your initial expression to be next optimized during compilation.

    http://www.atmel.com/products/other/spld-cpld/?tab=tools

In any case, you need to be a little bit familiar with the tool you choose, at least to create a fiction/dummy project with source file(s) and configure it correctly.

asndre
  • 1,597
  • 10
  • 17
1

What you require is Espresso heuristic logic minimizer

radically different approach to this issue is followed in the ESPRESSO algorithm, developed by Brayton e.a. at the University of California, Berkeley.[7] Rather than expanding a logic function into minterms, the program manipulates "cubes", representing the product terms in the ON-, DC- and OFF-covers iteratively. Although the minimization result is not guaranteed to be the global minimum, in practice this is very closely approximated, while the solution is always free from redundancy. Compared to the other methods, this one is essentially more efficient, reducing memory usage and computation time by several orders of magnitude. Its name reflects the way of instantly making a cup of fresh coffee. There is hardly any restriction to the number of variables, output functions and product terms of a combinational function block. In general, e.g. tens of variables with tens of output functions are readily dealt with.

Logic Friday (an application that uses Espresso) is 16x16 only so if you want to go to 256 have a look over the source at http://embedded.eecs.berkeley.edu/pubs/downloads/espresso/index.htm

0

In use many years ago a manual technique existed called "The Algorthmic State Machine Method",(ASM) Dr. D.H. Green of the Univesity of Manchester Institute of Science and Technology authored a book on it. Not sure if the book is still in print, I doubt it.

The technique was based on designing finite state machines but an intrinsic part of that was the design of combinational (or combinatorial) logic functions that drive output functions, and the inputs to the flipflops.

So the technique included a manual reduction/simplification method for reducing logic circuits. I recall at University we had to write a computer program to achieve the same result. Sorry, I no longer have that program!

Automated techniques: what you're looking for is what is known as a synthesis tool, which can take a text based description of the behaviour and generate a logic circuit from it.

One of the first (and expensive) tools was from a company called Synopsys, I think it was called Synopsys Design Compiler. We used to use this on Sun workstations many years ago.

When you synthesize logic from a text behavioural description (languages: VHDL, Verilog) you have various parameters you can control which influence the synthesis processs.

You can specify performance constraints and have the software create a logic circuit design which is designed for high speed and use more logic gates as a result, or you can have the synthesis software produce a design with as few a logic gates as possible, which usually result in a slower design.

The professional tools such as Synopsys took in libraries of logic gates from the large ASIC manufacturers with performance data included. Invaribly, you will find that the synthesis tool is targetting a particular logic technology when it creates its output design. In the case of ASIC vendors, the output will often be simple logic gates, in the case of FPGA vendors, the output of the synthesis tool is quite different as FPGA architectures are considerably different.

So you really want to seek out : 1) A software implementation of the ASM method, or write a program to do it 2) Synthesis software for programmable logic devices, but consider what I said, the output won't necessarily be a simple logic gate implementation (using AND, OR, NAND, NOR, NOT, XOR gates) and will be dependent on the target technology: CPLD, FPGA, ASIC and what logic functions these technologies from the vendors support.

Dean
  • 838
  • 4
  • 7