Given a desired truth table, this program exhaustively searches through combinations of NAND gates to find ways to produce this truth table. I'm sure e.g. VHDL synthesizers have better implementations of this; on my 300MHz laptop, this takes about 2 seconds to run through all the 5-gate circuits, which involves examining 549 067 candidate circuits, and 75 seconds to run through all the 6-gate circuits. (I'm still running through all the 7-gate circuits as I write this.) It took some work to get even to this level of performance, but it still runs through a lot of redundant work --- circuits that can't possibly work, multiple permutations of the same circuit.
/* * search through combinations of NAND gates for a combinatorial * circuit producing a particular truth table * * BUGS: * - produces suboptimal output (3 gates) for circuits with always-0 * or always-1 output, and also (2 gates) for circuits whose output is * simply one of their inputs, other than the last input. */ #include <assert.h> #include <setjmp.h> #include <stdlib.h> #include <stdio.h> #include <string.h> typedef struct { int ninputs, ngates; /* number of circuit inputs and number of gates */ int input[1][2]; /* not really [1]... really [ngates+ninputs] */ /* each input[a][b] contains input #b for gate #a. gates < ninputs are dummy gates * whose output is a circuit input. */ } circuit; circuit *newcircuit(int ninputs, int ngates) { circuit *cp = malloc(sizeof(*cp) + (ninputs + ngates - 1) * 2 * sizeof(int)); if (!cp) return 0; cp->ninputs = ninputs; cp->ngates = ngates; return cp; } int evalcircuit(circuit *cp, int *inputs) { int noutputs = cp->ninputs + cp->ngates; int outputs[noutputs]; /* gcc extension to C: variable-size arrays */ int ii; for (ii = 0; ii < cp->ninputs; ii++) outputs[ii] = inputs[ii]; for (ii = cp->ninputs; ii < noutputs; ii++) outputs[ii] = !(outputs[cp->input[ii][0]] && outputs[cp->input[ii][1]]); return outputs[noutputs - 1]; } char varname(int ii) { return 'A' + ii; } int gate_output_used_more_than_once(circuit *cp, int gatenum) { int ii, jj; int uses = 0; for (ii = cp->ninputs; ii < cp->ninputs + cp->ngates; ii++) { for (jj = 0; jj < 2; jj++) if (cp->input[ii][jj] == gatenum) uses++; } return (uses > 1); } void print_gate_expression_or_var(circuit *cp, int gatenum); void print_gate_expression(circuit *cp, int gatenum) { printf("-("); print_gate_expression_or_var(cp, cp->input[gatenum][0]); printf("*"); print_gate_expression_or_var(cp, cp->input[gatenum][1]); printf(")"); } void print_gate_expression_or_var(circuit *cp, int gatenum) { if (gatenum < cp->ninputs || gate_output_used_more_than_once(cp, gatenum)) { printf("%c", varname(gatenum)); } else { print_gate_expression(cp, gatenum); } } void nicely_print_circuit(circuit *cp) { int ii; int output = cp->ninputs + cp->ngates - 1; for (ii = cp->ninputs; ii <= output; ii++) if (ii == output || gate_output_used_more_than_once(cp, ii)) { printf("%c = ", varname(ii)); print_gate_expression(cp, ii); printf("\n"); } } void printcircuit(circuit *cp) { int ii; for (ii = cp->ninputs; ii < cp->ninputs + cp->ngates; ii++) printf("%c = -(%c*%c)\n", varname(ii), varname(cp->input[ii][0]), varname(cp->input[ii][1])); } void printentry(void *cd, circuit *cp, int *inputs, int output) { int ii; for (ii = 0; ii != cp->ninputs; ii++) printf("%d ", inputs[ii]); printf("-> %d\n", output); } void printentry_brief(void *cd, circuit *cp, int *inputs, int output) { printf("%d", output); } void enumtable(circuit *cp, void *client_data, void (*cb)(void *client_data, circuit *cp, int *inputs, int output) ) { int inputs[cp->ninputs]; int ii; for (ii = 0; ii < cp->ninputs; ii++) inputs[ii] = 0; nextline: for (;;) { (*cb)(client_data, cp, inputs, evalcircuit(cp, inputs)); for (ii = cp->ninputs - 1; ii >= 0; ii--) if (!inputs[ii]) { for (; ii < cp->ninputs; ii++) inputs[ii] = !inputs[ii]; goto nextline; /* we just horked ii */ } return; } } void reset_circuit(circuit *cp) { int ii; for (ii = 0; ii < cp->ngates; ii++) { cp->input[cp->ninputs + ii][0] = 0; cp->input[cp->ninputs + ii][1] = 0; } } /* go to the lexically next valid circuit and return 1, * or return 0 if that's not possible. */ int increment_circuit(circuit *cp) { /* in valid circuits, each input[ii][x] < ii, and of course >= 0. */ /* We also enforce the condition that input[ii][1] <= input[ii][0], * because NAND is commutative; considering both -(B*A) and -(A*B) * doesn't help. */ int ii; int min; for (ii = cp->ninputs + cp->ngates - 1; ii >= cp->ninputs; ii--) { min = ii - 1; if (cp->input[ii][0] < min) min = cp->input[ii][0]; if (cp->input[ii][1] != min) { cp->input[ii][1]++; zero_lower_order_gates: for (ii++; ii < cp->ninputs + cp->ngates; ii++) { cp->input[ii][0] = 0; cp->input[ii][1] = 0; } return 1; } if (cp->input[ii][0] != ii - 1) { cp->input[ii][0]++; cp->input[ii][1] = 0; goto zero_lower_order_gates; } } return 0; } /* it isn't *really* necessary to put this in a struct. Maybe I've been programming Python too much... */ typedef struct { int counter; char *pattern; jmp_buf mismatch; } search_result; search_result the_search_result; void match(void *client_data, circuit *cp, int *inputs, int output) { search_result *sr = client_data; char pattern_element = sr->pattern[sr->counter]; sr->counter++; if (pattern_element == 'x') return; /* don't care */ if (output != pattern_element - '0') longjmp(sr->mismatch, -1); } int test_circuit(circuit *cp, char *pattern) { search_result *sr = &the_search_result; sr->counter = 0; sr->pattern = pattern; if (setjmp(sr->mismatch) == 0) { enumtable(cp, sr, &match); } else { return 0; /* found a mismatch */ } return 1; } int inputs_for_pattern(char *pattern) { char *s; int len; int log2 = 0; for (s = pattern; *s; s++) if ((*s != '0') && (*s != '1') && (*s != 'x')) return 0; len = s - pattern; while (len > 1) { if (len & 1) return 0; log2 ++; len >>= 1; } return log2; } int max_gates_for_inputs(int inputs) { /* this function may not be useful to implement, as the program takes too long to run in practice for more than a few gates. */ return 100; } int main(int argc, char **argv) { circuit *cp = 0; int ninputs, ngates, maxgates, done; if (argc != 2) { fprintf(stderr, "%s: Usage: %s pattern\n" "pattern is a pattern of 0's, 1's, and x's.\n", argv[0], argv[0]); return 1; } if (!(ninputs = inputs_for_pattern(argv[1]))) { fprintf(stderr, "%s: Don't understand pattern '%s' of length %d.\n" "Pattern lengths should be powers of 2; they " "consist of 0's, 1's, and x's.\n", argv[0], argv[1], strlen(argv[1])); return 2; } { int ii; printf("Inputs: "); for (ii = 0; ii < ninputs; ii++) printf("%c ", varname(ii)); printf("\n"); } maxgates = max_gates_for_inputs(ninputs); done = 0; for (ngates = 0; ngates <= maxgates; ngates++) { printf("Trying with %d gates...\n", ngates); free(cp); cp = newcircuit(ninputs, ngates); if (!cp) { /* out of memory, probably; how likely is that?! */ fprintf(stderr, "For %d inputs and %d gates", ninputs, ngates); perror("newcircuit"); return 3; } reset_circuit(cp); do { if (test_circuit(cp, argv[1])) { nicely_print_circuit(cp); enumtable(cp, 0, &printentry); done = 1; } } while (increment_circuit(cp)); if (done) return 0; /* no need to try more complex circuits... */ } assert(0); /* should never happen */ } -- <[EMAIL PROTECTED]> Kragen Sitaker <http://www.pobox.com/~kragen/> Edsger Wybe Dijkstra died in August of 2002. The world has lost a great man. See http://advogato.org/person/raph/diary.html?start=252 and http://www.kode-fu.com/geek/2002_08_04_archive.shtml for details.