## Puzzle #1

May 18, 2007Since I am a big fan of puzzles, I will try to post here from time to time a few digital design related puzzles.

This particular one was given to me in an interview at IBM over 10 years ago.

Due to the war in the land of Logicia there is a shortage of XOR gates. Unfortunately, the only logic gates available are two weird components called “X” and “Y”. The truth table of both components is presented below – Z represents a High-Z value on the output.

Could you help the poor engineers of Logicia to build an XOR gate?

Advertisements

I like this question a lot. Using tri-state outputs as OR logic is an old trick from PLDs that had too few AND terms but did have tri-states on the outputs. It takes two of these gates to make an inverter (tie the inputs together). Now with the X gate, you can create any 2-input min-term. Or 4 together to create any function you want. (Or use duality and the Y gate)

by Carl March 12, 2008 at 6:43 pmConnect 2 [ X , Y ] to get inverter …

by Vamsi May 7, 2008 at 11:45 amuse inverter for to get not A , not B ..

now use Y for not A , B to get nand [ not exactly nand but sort of ] .. and invert the nand to get “and” and we get (not A and B )..

similarly get (A and not B ) ..

Now connect both the outputs … to get ..

{NotA and B} + {A and notB} … XOR

Done !!

mail me for doubts !

Vamsi

BITS Goa

INDIA

bunnynu@gmail.com

I believe you have to add two terms for (not A * not B) and (A * B), otherwise the outputs will float instead of go to zero for the “not true” xor cases.

by Dick Vieau November 6, 2008 at 2:04 am2 of X and Y to get INV (inputs tied together).

Following 4 outputs tied together (wire-or):

A,B into X, then into INV, get 1st output;

A,B into Y, get 2nd output;

A,~B into X, get 3rd output;

~A,B into X, get 4th output.

Here the output of wire-or is what we get – XOR.

by Troy October 14, 2009 at 9:48 pmFor Invertor, u need X and Y

___

==| X |—-|

-| |___| |–

| ___ |

==| Y |—-|

|___|

X gives A.B

Y gives A+B

so for xor, A`B + AB` you need four X component and 3 Y component.

So minimum you need 7 Component to realize XOR.

by AK February 2, 2011 at 4:57 pm— Here is my evolution toward an answer.

by Michael Vincze October 25, 2011 at 8:53 pm—

— From the equation XOR_OUT <= (A and B_NOT) or (B and A_NOT);

— and noting how X and Y behave when A and B are tied together, it is

— assumed we need an inverter. Yeah that's really how I started it.

—

— We almost see inverters if we tie A and B inputs together. The following

— results:

—

— A | X2_OUT | Y2_OUT We can see X drives its output only while it

— —-+——–+—— is inverting a '0'. And Y drives its output

— '0' | '1' | 'Z' only while it is inverting a '1'. Wiring these

— '1' | 'Z' | '0' two outputs together results in an inverter.

— 'X' | 'X' | 'X'

—

— From the XOR equation we know that we need to operate on (A and B_NOT) and

— (B and B_NOT). With this in mind every combination of A, B, A_NOT, B_NOT

— is translated through each X and Y gate. Just to see what happens. The

— following results:

—

— A A~ B B~|XOR_OUT|X(A,B)|Y(A,B)|X(A,B~)|Y(A,B~)|X(A~,B)|Y(A~,B)|X(A~,B~)|Y(A~,B~)

— ———+——-+——+——+——-+——-+——-+——-+——–+——–

— 0 1 0 1 |0 |1 |Z |Z |Z |Z |Z |Z |0

— 0 1 1 0 |1 |Z |Z |1 |Z |Z |0 |Z |Z

— 1 0 0 1 |1 |Z |Z |Z |0 |1 |Z |Z |Z

— 1 0 1 0 |0 |Z |0 |Z |Z |Z |Z |1 |Z

—

— Keeping in mind how an XOR gate operates, we want a '1' when the inputs are

— different and a '0' when the inputs are the same. We note in the columns

— for when this occurs. Seeing what drives a '1' when A and B are different

— yields X(A,B~) and X(A~,B). Seeing what drives a '0' when A and B are the

— same yields Y(A,B) and Y(A~,B~). These four terms are wired together, and

— is the final answer.

—

— And if you're counting, each inverter takes 1 X gate and 1 Y gate. The four

— terms take 2 X gates and 2 Y gates. Totat X gates = 3, total Y gates = 3.

— Six gates in all!

Oops, there are 2 inverters, therefore 8 gates in all.

by Michael Vincze October 26, 2011 at 12:56 pm— Here is the VHDL for a solution.

library ieee; use ieee.std_logic_1164.all;

entity X is port(A,B:in std_logic; X_OUT:out std_logic); end;

library ieee; use ieee.std_logic_1164.all;

entity Y is port(A,B:in std_logic; Y_OUT:out std_logic); end;

architecture weird of X is

begin

X_OUT <= '1' when A & B = "00" else 'Z';

end;

architecture weird of Y is

begin

Y_OUT <= '0' when A & B = "11" else 'Z';

end;

library ieee; use ieee.std_logic_1164.all;

entity NOT_GATE is port(NOT_IN:in std_logic; NOT_OUT:out std_logic); end;

architecture rtl of NOT_GATE is

component X is port(A,B:in std_logic; X_OUT:out std_logic); end component;

component Y is port(A,B:in std_logic; Y_OUT:out std_logic); end component;

signal X2_OUT: std_logic;

signal Y2_OUT: std_logic;

begin

u_x2_out: X port map(NOT_IN, NOT_IN, X2_OUT);

u_y2_out: Y port map(NOT_IN, NOT_IN, Y2_OUT);

NOT_OUT <= Y2_OUT;

NOT_OUT <= X2_OUT;

end;

library ieee; use ieee.std_logic_1164.all;

entity puzzle_01 is end;

architecture rtl of puzzle_01 is

component X is port(A, B :in std_logic; X_OUT :out std_logic); end component;

component Y is port(A, B :in std_logic; Y_OUT :out std_logic); end component;

component NOT_GATE is port(NOT_IN:in std_logic; NOT_OUT:out std_logic); end component;

signal A, B, XOR_OUT: std_logic;

signal A_NOT, B_NOT : std_logic;

signal XOR_OUT_WIRE : std_logic_vector(3 downto 0);

begin

u_not_a: NOT_GATE port map(A, A_NOT);

u_not_b: NOT_GATE port map(B, B_NOT);

u_y_a_not_b_not: Y port map(A_NOT, B_NOT, XOR_OUT_WIRE(3));

u_x_a_not_b : X port map(A_NOT, B , XOR_OUT_WIRE(2));

u_x_a_b_not : X port map(A , B_NOT, XOR_OUT_WIRE(1));

u_y_a_b : Y port map(A , B , XOR_OUT_WIRE(0));

XOR_OUT <= XOR_OUT_WIRE(0);

XOR_OUT <= XOR_OUT_WIRE(1);

XOR_OUT <= XOR_OUT_WIRE(2);

XOR_OUT <= XOR_OUT_WIRE(3);

p_main: process

begin

wait for 10 ns; a <= '0'; b <= '0';

wait for 10 ns; a <= '0'; b <= '1';

wait for 10 ns; a <= '1'; b <= '1';

wait for 10 ns; a <= '1'; b <= '0';

wait for 10 ns; a <= '0'; b <= '0';

wait for 10 ns; a <= '1'; b <= '0';

wait for 10 ns; a <= '1'; b <= '1';

wait for 10 ns; a <= '0'; b <= '1';

wait for 10 ns; a <= '0'; b <= '0';

wait for 10 ns;

wait for 10 ns; a <= 'X'; b <= '0';

wait for 10 ns; a <= '0'; b <= '0';

wait for 10 ns; a <= '0'; b <= 'X';

wait for 10 ns; a <= '0'; b <= '0';

wait for 10 ns;

wait;

by Michael Vincze October 25, 2011 at 8:54 pmend process;

end;

what happens if either x or y is driven by a Z?

by vk July 26, 2014 at 6:53 am