building boolean gates

[Bernd Schneider]

Hi all,

I am trying to build the following two linear gates from basic boolean
gates (XOR, NOT, AND, OR):
1. Enable gate with the following truth table where u,s,e are the inputs
and w is the output
u s e w
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Basically what the gate does is if e=0 then it outputs s and if e=1 then it
outputs u.
2. This time I have a gate with 4 inputs r,e,s,t and two outputs c and c'
The outputs are computed as follows:
if e=1 then c=r XOR t and c' = NOT(r XOR t)
if e=0 then c=c'=s

The first gate should not use any non-linear operation (i.e. not AND and
OR) together with the u signal and the second gadget should not involve t
in a non-linear operation.
Both gadgets look pretty linear to me, so I hope this is somehow possible.

How can I "implement" these gadgets?

Regards and thanks a lot,
Bernd

 

[Frank Buss]

Hi all,

I am trying to build the following two linear gates from basic boolean
gates (XOR, NOT, AND, OR):
1. Enable gate with the following truth table where u,s,e are the inputs
and w is the output
u s e w
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

Should be possible with XOR, NOT, AND and OR. But why not using just one
chip like http://focus.ti.com/lit/ds/symlink/sn74hc151.pdf ?

Basically what the gate does is if e=0 then it outputs s and if e=1 then it
outputs u.
2. This time I have a gate with 4 inputs r,e,s,t and two outputs c and c'
The outputs are computed as follows:
if e=1 then c=r XOR t and c' = NOT(r XOR t)
if e=0 then c=c'=s

Two http://focus.ti.com/lit/ds/symlink/sn74150.pdf

 

[Bernd Schneider]

Hi Frank,

I am sure that you can implement it with using only XOR, NOT, AND and OR
but more intersting for me is whether you can actually implement it such
that in the first case u and in the second case t is not involved in any
non-linear operation.

Do you know of a way?

Regards,
Bernd

 

[Frank Buss]

I am sure that you can implement it with using only XOR, NOT, AND and OR
but more intersting for me is whether you can actually implement it such
that in the first case u and in the second case t is not involved in any
non-linear operation.

I'm not an electronics specialist, what is a non-linear gate or operation?

 

[Bernd Schneider]

I'm not an electronics specialist, what is a non-linear gate or
operation?

Non-linear gates are AND and OR gates. Linear gates are XOR and NOT.

 

[Bernd Schneider]

Have you seen "And Or Select" gates? This is what they do.
http://www.st.com/stonline/products/literature/ds/2034/hcf4019.pdf

This gate however uses AND gates. I am not sure though it one of the AND or
OR gates in the figure gets as input the u bit. Maybe you can help me to
figure out this issue.

Regards and thanks,
Bernd

 

[Jon Slaughter]

Hi all,

I am trying to build the following two linear gates from basic boolean
gates (XOR, NOT, AND, OR):
1. Enable gate with the following truth table where u,s,e are the inputs
and w is the output
u s e w
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Basically what the gate does is if e=0 then it outputs s and if e=1 then
it
outputs u.
2. This time I have a gate with 4 inputs r,e,s,t and two outputs c and c'
The outputs are computed as follows:
if e=1 then c=r XOR t and c' = NOT(r XOR t)
if e=0 then c=c'=s

The first gate should not use any non-linear operation (i.e. not AND and
OR) together with the u signal and the second gadget should not involve t
in a non-linear operation.
Both gadgets look pretty linear to me, so I hope this is somehow possible.

How can I "implement" these gadgets?

Regards and thanks a lot,
Bernd

There are some program's that will take as input a truth table and output
circuit's that express table.

One I like very much is "logic friday". It lets you select the gates you
want and even gives you a circuit(that isn't necessarily perfect but close).

 

[Bernd Schneider]

The question isn't how, it's why?

I put implement in "" because probably in practice nobody will ever implement it. It is only
a theoretical experiment.

I figured out that my first gadget is a multiplexer and that I can implement it with two and
gates and one or gate, i.e. w = (s AND NOT(e)) OR (u AND e). Now, my question is: can I also
implement it without the AND gates? Note that u and s should not be input to a non-linear
gate. Somewhat this multiplexer construction looks similar to a XOR gate itself. I wonder
whether there is a way to implement it with a XOR gate.

Regards,
Bernd

 

[Frank Buss]

Non-linear gates are AND and OR gates. Linear gates are XOR and NOT.

I see. This sounds a bit like reversible gates, which I've read about some
time ago, related to cellular automata. E.g. the Fredkin gate (I've just
added a logic function with XOR and AND gates to the Wikipedia entry for
this gate)

http://en.wikipedia.org/wiki/Fredkin_gate

This is a reversible universal gate (and mass conserving, if you would
really implement it with billiard balls), with which you can implement your
function. The XOR gate alone is not an universal gate (see
http://en.wikipedia.org/wiki/Toffoli_Gate ), so you can't implement the
Fredkin gate with it (NOT is just XOR with 1 as one input).

Your function looks a bit like the Fredkin gate, so I think you can't
implement it with XOR and NOT, only. But if the Fredkin gate is a linear
gate for you, you might solve it with this gate.

 

[Jonathan Kirwan]

One I like very much is "logic friday". It lets you select the gates you
want and even gives you a circuit(that isn't necessarily perfect but close).

That one requires either an AND or OR permitted in its output. You
can't uncheck both. I think the OP wants something without either.

Jon

 

[Helmut Sennewald]

Non-linear gates are AND and OR gates. Linear gates are XOR and NOT.

Hello Bernd,

It looks for me that you have translated some technical
content from German to English with a general dictionary.
It's totally nonsense in my opinion to name XOR and NOT a
linear gate. There are transfer gates of course.
Maybe you want show me a link to the original German text
and/or course material.

Best regards,
Helmut
Germany

 

[[email protected]]

The question isn't how, it's why?

John

I'm thinking draw the K-map and get the job done.

 

[Bernd Schneider]

[email protected] wrote in

I'm thinking draw the K-map and get the job done.

Yes, but the K-map diagram uses a lot of And and Or gates and this way I
cannot achieve my constraint.

Regards,
Bernd

 

[Bernd Schneider]

Hello Bernd,

It looks for me that you have translated some technical
content from German to English with a general dictionary.
It's totally nonsense in my opinion to name XOR and NOT a
linear gate. There are transfer gates of course.
Maybe you want show me a link to the original German text
and/or course material.

No, I havent translated any text from German to English. In fact, I am not
into electronics but a colleague of me has called these gates linear and
And and Or non-linear gates. I think the idea is that the output of a
linear gate is 1 with probability 1/2 whereas the output of a non-linear
gate may differ (in case of an AND gate the probability that the output
takes the value is indeed only 1/4). Following this definition the gates
that I have specified are also linear and that let me hope that I can build
them from only linear basic gates.
My first gate is a multiplexer. I looked up in wikipedia how such a gate
can be built from and and or gates, but there is no description if it can
be build from XOR. The description of the MUX looks very, very similar to
the decription of an XOR gate when it is build with only AND, NOT and OR
gates, so that gives some hope, too.

Regards,
Bernd

 

[Bernd Schneider]

That one requires either an AND or OR permitted in its output. You
can't uncheck both. I think the OP wants something without either.

Yes this is true. I hope it's possible to do so, but the more I look at it,
it seems impossible to me.

Regards,
Bernd

 

[Bernd Schneider]

That's the way the course instructor phrased the problem ;-)

No, I came up with this problem myself.

Regards,
Bernd

 

[Bernd Schneider]

NAND and NOR gates can be used to build any logic function. They are
the universal logic gates.

I know, but NAND and NOR gates are also non-linear (see my definition in
the answer to Helmut's post). I would like to build it without such gates.

Regards,
Bernd

 

[Helmut Sennewald]

[email protected]:

No, I havent translated any text from German to English. In fact, I am not
into electronics but a colleague of me has called these gates linear and
And and Or non-linear gates. I think the idea is that the output of a
linear gate is 1 with probability 1/2 whereas the output of a non-linear
gate may differ (in case of an AND gate the probability that the output
takes the value is indeed only 1/4). Following this definition the gates
that I have specified are also linear and that let me hope that I can
build
them from only linear basic gates.

Hello Bernd,

To be honest, this definition of "linear" together with digital logic is
nonsense.
Please ask your friend for a web-link. I am really interested to see who
uses
this definition.

Best regards,
Helmut

 

[Hot Jock]

I know, but NAND and NOR gates are also non-linear (see my definition
in the answer to Helmut's post). I would like to build it without
such gates.

Regards,
Bernd

You can build any logic function out of XOR gates. Since you have
defined the XOR as a linear gate, use it.

 

[Alex]

hi
I think its a simple misunderstanding with linear and non.. a gate
will always make a change in state, from Vcc to gnd or like , It will
never act like a linear device.

But it is so that Nor ,not ,nand inverts the signal
and and ,or do not invert signals.
So you have inverting and non inverting gates .

alex