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 ?
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 appropriate).
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 commonly used (FPGA or discrete).
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).
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.
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.
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. 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
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.