Convert some table into combinatorial circuit + optimization

[sdf]

Hi.
Let's say, I have big table which is usually suitable to fit it in
some ROM.
But it's possible to construct some circuit containing only primitive
gates that acts just as that ROM.
Here is an example of converting tables from DES cipher into gates:
http://www.darkside.com.au/bitslice/
I'm interesting, is there any automated way to do so, thus to have on
output circuit with the smallest possible primitive gates (AND, OR,
NOT, XOR).

 

[Jason Zheng]

Usually you leave such things to the synthesis tools and just implement
the damn circuit in plain case statements. Optimizing such circuits
prematurely could end up making the circuit less optimal.

For example, Xilinx's Virtex architecture lends itself to
lookup-table-style logic, so trying to implement such logic in AND/OR
gates could only hurt.

On the other hand, Actel's AX architecture is based on 4-1 muxes, so
optimizing such logic to AND/OR gates probably won't help either.

So the short answer is no, unless you have a good knowledge of what the
target platform is like, there is no simple way to "optimize".

On Tue, 26 Feb 2008 15:56:08 -0800 (PST)
sdf <drop669@gmail.com> wrote:

Hi.
Let's say, I have big table which is usually suitable to fit it in
some ROM.
But it's possible to construct some circuit containing only primitive
gates that acts just as that ROM.
Here is an example of converting tables from DES cipher into gates:
http://www.darkside.com.au/bitslice/
I'm interesting, is there any automated way to do so, thus to have on
output circuit with the smallest possible primitive gates (AND, OR,
NOT, XOR).

--
Romeo wasn't bilked in a day.
-- Walt Kelly, "Ten Ever-Lovin' Blue-Eyed Years With
Pogo"

 

On Feb 26, 6:56 pm, sdf <drop...@gmail.com> wrote:

I'm interesting, is there any automated way to do so, thus to have on
output circuit with the smallest possible primitive gates (AND, OR,
NOT, XOR).

There are efficient algorithms using Karnaugh maps to find the optimal
sum-of-products implementation of a truth table. A sum-of-products
implementation consists of AND-gates feeding an OR-gate, where the
inputs to each AND-gate consist of some combination of primary inputs
or their inverses. Such an implementation uses only 2 levels of logic
(or 3 if you count the NOT gates to get the inverses). This
implementation can easily be converted into 2 levels of NAND gates
(plus NAND gates used as inverters) instead.

However, if you are willing to allow more than 2 levels of gates
(despite the extra delay), there can be implementations using fewer
total gates. Adding other gate types such as XOR can also allow
smaller results. The sum-of-products solution also assumes that you
have AND and OR gates with arbitrarily large numbers of inputs. In
reality, you may have to cascade multiple gates to handle the number
of inputs. With these changes, I don't think there is an easy
solution to the optimization problem.