Help me solve a hard logic task

[Black Jack]

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]

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]

Re: 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.

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

 

[Ace-X]

Re: HARD LOGIC

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]

Re: HARD LOGIC

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

 

[hamadeh]

HARD LOGIC

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

 

[jitendra]

Re: HARD LOGIC

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

 

[Mazi3]

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]

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?

AND, OR gates and 2 NOT Only

 

[jitendra]

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]

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

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]

Re: HARD LOGIC

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

thanks in advance

 

[Black Jack]

Re: HARD LOGIC

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]

Re: HARD LOGIC

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

 

[hamadeh]

HARD LOGIC

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

 

[rkarthik1]

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]

Re: HARD LOGIC

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

 

[Ace-X]

HARD LOGIC

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

 

[samcheetah]

Re: HARD LOGIC

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

okay so howz it done?

 

[Ace-X]

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