Reverse engineering logic equations from truth tables

From: Marko Mäkelä (marko.makela_at_hut.fi)
Date: 2002-06-24 12:52:44

Gideon Zweijtzer wrote:
> If anyone is planning to do so, please note that generating a huge truth
> table for VHDL or verilog is a lot easier than trying to find the logic
> formula's yourself. Then run the VHDL or verilog to a compiler / fitter for
> a PLD and there you'll be able to find your equations.

Are we talking about the same thing?  We already know the truth table 
(the states of the output lines for any given combination of input line 
states) for the C128 PLA.  This information is not in a very useable 
format for any other purpose than (perhaps) copying the logic equations 
to a chip.  The chip doesn't care how readable the equations are to a 
human; in fact, as far as I understand, they do not allow the formulae 
to be nested very deeply.

A few years ago, I already tried to minimize a small subset of the truth 
table (one output and a subset of the inputs) with a binary decision 
diagram (BDD) based tool whose name escapes from my mind.  It didn't 
perform very well; the equations it derived were far from optimal.

Anyway, let's take an example.  Suppose that there's a logic chip with 3 
inputs (a,b,c) and a number of outputs.  We read out one of the outputs 
as a memory array, covering all input combinations.  This gives us 2^3=8 
elements, say, 0010 1010.  We can view this data as a truth table that 
can be converted to disjunctive normal form (DNF), with the lines being 
joined with the "or" operator:

000 0
001 0
010 1 (!a & b & !c) |
011 0
100 1 (a & !b & !c) |
101 0
110 1 (a & b & !c)
111 0

The whole formula is (!a & b & !c) | (a & !b & !c) | (a & b & !c), which 
is not very readable and could perhaps be simplified.  For instance, we 
could eliminate "b" from the last two equations.

You can swap "and"s and "or"s and use the conjunctive normal form (CNF) 
if there are more lines yielding "0"s.  I would like to have something 
that simplifies the resulting formula.

Of course, this is a toy example.  In the C64 PLA, there are 16 inputs 
and 8 outputs (64 kB worth of data).  All other lines except CASRAM were 
easy to guess and validate with a program that converts the guessed 
formula to a truth table and compares the result with the original truth 
table.  In the C128 PLA, there are even more inputs and outputs (I don't 
remember how many), and I wouldn't try to reverse-engineer it manually 
but use a tool for the process.

	Marko


       Message was sent through the cbm-hackers mailing list

Archive generated by hypermail 2.1.4.