h1

Puzzle #1

May 18, 2007

Since 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?

high-z_problem.png

Advertisements

9 comments

  1. 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)


  2. Connect 2 [ X , Y ] to get inverter …
    use 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


  3. 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.


  4. 2 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.


  5. For 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.


  6. — Here is my evolution toward an answer.

    — 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.


  7. — 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;
    end process;
    end;


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



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: