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.