Help me solve a hard logic task

Black Jack · Dec 3, 2004

logic gates only 2 inverters

Task description.

Have: 3 independent inputs, 3 independent outputs.
Need: Make inversion of 3 inputs using logic and ONLY 2 Inverters.

Ace-X · Dec 3, 2004

HARD LOGIC

Very old task - it was discussed many times on different fpga/asic groups. I will not publish solution right now, probably it will be interesting for some guys here to find solution by their own.

Just keep in mind that it is possible! Our whole Universe needs only 2 inverters to build any logic!

Ace-X.

Black Jack · Dec 3, 2004

Re: HARD LOGIC

Ace-X said:
Very old task - it was discussed many times on different fpga/asic groups. I will not publish solution right now, probably it will be interesting for some guys here to find solution by their own.

Just keep in mind that it is possible! Our whole Universe needs only 2 inverters to build any logic!

Ace-X.

Yes, I know solution, but HOW this result are obtained?

Ace-X · Dec 3, 2004

Re: HARD LOGIC

Black Jack said:
Yes, I know solution, but HOW this result are obtained?

When my students gave me this task some years ago, they told me that solution does exist. So, I supposed that every of these two inverters should be applied to logic combination which simmetrically includes every of three inputs. Then I just tried to compose logic expressions for outputs to remove as much as possible sub-expressions, because output should be simple NOT of input. This is just general description of approach. It is quite difficult for me to reproduce the whole way of solution, because I tried many different variants, before I have found the right one. It took around 30-40 minutes for me to find solution.

Ace-X.

funzero · Dec 4, 2004

Re: HARD LOGIC

input must be connect to VDD or Gnd .output can be float

hamadeh · Dec 24, 2004

HARD LOGIC

So... whta is the right solution for this problem ??

jitendra · Dec 24, 2004

Re: HARD LOGIC

May I please have some hint on this topic??? I was asked the same question in one of interviews.

Mazi3 · Dec 24, 2004

Re: HARD LOGIC

I do not understand this: using logic and only 2 inverters what doest it mean...logic. please explain. are these only AND, OR gates? are this NOR gates? or... XOR gates? which can be used?

Black Jack · Dec 24, 2004

Re: HARD LOGIC

Mazi3 said:
I do not understand this: using logic and only 2 inverters what doest it mean...logic. please explain. are these only AND, OR gates? are this NOR gates? or... XOR gates? which can be used?

AND, OR gates and 2 NOT Only

jitendra · Dec 24, 2004

Re: HARD LOGIC

The question asked in my interview was: 3 or more independant inputs to be inverted using two NOT gates? I think u need different logic depending on number of inputs. Let me focus on three inputs.
At input we need to add logic to make inputs for two NOT gates. Do we need some logic at output as I need to give three independant outputs and only two outputs from NOT gates are available???
Is it something like multiplexing inputs to use less no of gates?

Thanks,
Jitendra

Black Jack · Dec 24, 2004

Re: HARD LOGIC

jitendra said:
The question asked in my interview was: 3 or more independant inputs to be inverted using two NOT gates? I think u need different logic depending on number of inputs. Let me focus on three inputs.
At input we need to add logic to make inputs for two NOT gates. Do we need some logic at output as I need to give three independant outputs and only two outputs from NOT gates are available???
Is it something like multiplexing inputs to use less no of gates?

Thanks,
Jitendra

Code:

SUBDESIGN comb_v1
(
	y[3..1]	:INPUT;
	ny[3..1]	:OUTPUT;
)
VARIABLE
	a, b		:NODE;
	s[8..1]	:NODE;
BEGIN

	a=!(y1&y2 # y1&y3 # y2&y3);
	b=!(a&(y1 # y2 # y3) # y1&y2&y3);
	
	s8 = a&b;
	s7 = a&(y1 # y3) & (y2 # y3);
	s6 = a&(y1 # y2)&(y2 # y3);
	s5 = b&y2&y3;
	s4 = a&(y1 # y2)&(y1 # y3);
	s3 = b&y1&y3;
	s2 = b&y1&y2;
	s1 = y1&y2&y3;
	ny1 = s8 # s7 # s6 # s5;
	ny2 = s8 # s7 # s4 # s3;
	ny3 = s8 # s6 # s4 # s2;

END;

This AHDL code
But after synthesys we have 3 NOT gates

atmaca · Dec 24, 2004

Re: HARD LOGIC

May somebody give a short and understandable answer to this question ?

thanks in advance

Black Jack · Dec 24, 2004

Re: HARD LOGIC

atmaca said:
May somebody give a short and understandable answer to this question ?

thanks in advance

Sorry!
But I don`t know how this result is obtained
and this not my own solution

jitendra · Dec 24, 2004

Re: HARD LOGIC

Thanks for the code, But it will be more helpful if we can discuss the design.

hamadeh · Dec 24, 2004

HARD LOGIC

ok... so we can use any number of AND or OR gates, and only two NOT ... is that right?

rkarthik1 · Dec 24, 2004

Re: HARD LOGIC

the solution is simple if we can use XOR gates as well.... u would need 2 XOR in addition to the 2 NOT gates...

Added after 4 minutes:

take the 3 inputs to be A, B and C..
my solution is :
A to one NOT gate = Anot
B to the other NOT gate = Bnot
B and C to one XOR gate = BxorC
Bnot and BxorC to the second XOR gate = Cnot

yego · Dec 24, 2004

Re: HARD LOGIC

As far as I know, XORs are not basic logic gates, therefore they count as inverters !.

Ace-X · Dec 26, 2004

HARD LOGIC

You have 2 inverters and infinite number of OR and AND gates - that's original conditions.

samcheetah · Dec 26, 2004

Re: HARD LOGIC

Ace-X said:
You have 2 inverters and infinite number of OR and AND gates - that's original conditions.

okay so howz it done?

Ace-X · Dec 26, 2004

HARD LOGIC

Solution was posted by BlackJack early in this topic (AHDL example). Here is solution expressed as logic equations:
n1 = not(i1*i2 + i1*i3 + i2*i3)
n2 = not((i1 + i2 + i3)*n1 + i1*i2*i3)
o1 = (i2 + i3 + n2)*n1 + i2*i3*n2
o2 = (i1 + i3 + n2)*n1 + i1*i3*n2
o3 = (i1 + i2 + n2)*n1 + i1*i2*n2

i1 - i3 are the inputs
o1 - o3 are the outputs
'*' is AND
'+' is OR

Help me solve a hard logic task

Full Member level 4

Advanced Member level 2

Full Member level 4

Advanced Member level 2

Full Member level 4

Member level 5

Member level 3

Advanced Member level 4

Full Member level 4

Member level 3

Full Member level 4

Full Member level 4

Full Member level 4

Member level 3

Member level 5

Member level 1

Full Member level 3

Advanced Member level 2

Advanced Member level 2

Advanced Member level 2

Similar threads

Privacy & Transparency

Privacy & Transparency