ASIC Point Explore

← RTL Design Interviews

Interview Question · Code Writing

Logic Gates from a 2:1 Mux

L0 Fresherlogic puzzlescombinational logicmultiplexers
  • Asked at Micron
  • Asked at Infineon
  • Asked at Texas Instruments

The interviewer asks

You have only 2:1 multiplexers and the constants 0 and 1. Build NOT, AND, OR and XOR.

Reveal the Model Answer

Write the mux as y = s ? b : a and put one input on the select. NOT a is a ? 0 : 1. AND is a ? b : 0, and OR is a ? 1 : b. XOR is a ? ~b : b, so it needs a second mux to make ~b. Five muxes cover all four gates.

XOR from Two MuxesEach mux computes y = s ? d1 : d0. Arrows carry signals; the label names the mux input.
XOR from two muxesEach mux computes `y = s ? d1 : d0`. Arrows carry signals; the label names the mux input. component a input component b input component Mux 1: NOT b ? 0 : 1 gives ~b component Mux 2: XOR a ? ~b : b component y a XOR b sd1 = ~bd0 = bs
  1. Make ~b

    With b on the select and constants 1 and 0 on the data inputs, mux 1 is an inverter.

  2. Pick b or ~b

    When a is 0, mux 2 passes b. When a is 1, it passes ~b. That is XOR.

Read the diagram as text
  • a: input
  • b: input
  • Mux 1: NOT: b ? 0 : 1 gives ~b
  • Mux 2: XOR: a ? ~b : b
  • y: a XOR b
  • b → Mux 1: NOT: s
  • Mux 1: NOT → Mux 2: XOR: d1 = ~b
  • b → Mux 2: XOR: d0 = b
  • a → Mux 2: XOR: s
  • Mux 2: XOR → y

NOT, AND and OR take one mux each. XOR takes two, so five muxes cover all four gates.

GateSelectWhen select is 0When select is 1
NOT aa10
a AND ba0b
a OR bab1
a XOR bab~b (one more mux)

All four input rows, checked against the operators. The synthesizer reduces the five muxes to four plain gates.

RUNIcarus Verilog · in your browser
Edit the code, then run it

        
Expected: a=0 b=0  not=1 and=0 or=0 xor=0 a=1 b=1  not=0 and=1 or=1 xor=0 PASS: five 2:1 muxes give NOT, AND, OR and XOR

        
        
      

          
Self-Check
Tick each key point you covered in your answer.


What Interviewers Listen For (Fresher)
A good fresher answer writes the mux equation first, then fills each data input from a truth table. It checks each gate against all four rows.


        

      

    

    
  

    

    

    
Cross-Questions

    
Where the interviewer goes next. Open a node to practise that follow-up.

    
WhyWhat IfProve ItCompare

    
    
      
  1. Logic Gates from a 2:1 Mux
    2. 
      
  2. 
    
    What IfA 2:1 Mux from NAND GatesL0 Fresher
      
    
      
    What if you have only NAND gates? Build a 2:1 mux.
    
      
    
    
    
    
      
      
    Reveal the Model Answer
        
    Four NANDs are enough. One NAND with its inputs tied makes ~s. Two NANDs gate a with ~s and b with s. A last NAND combines them, because NAND of two NANDs is an OR of two ANDs.
    
        
    RUNIcarus Verilog · in your browser
    
        
    Edit the code, then run it
    
          
    
          
    
          
    
        
    Expected: 4 NAND gates, 8 input rows, 0 wrong PASS: four NANDs make a 2:1 mux
    
        
        
      
    
          
    Self-Check
    Tick each key point you covered in your answer.
    


        
    
      
    
    
    
    
  
    
      
    
    
    Half-Truth
    
    
    Uses five gates because "an inverter is a separate cell".
    
    
    A NAND with both inputs tied is an inverter, so the count stays at four NANDs.
    
  
    
    
    3. 

  3. 
    
    CompareA 4:1 Mux as a Look-Up TableL0 FresherL1 Junior
      
    
      
    Compare building gates from 2:1 muxes with using one 4:1 mux. How can a 4:1 mux make any 2-input function?
    
      
    
    
    
    
      
      
    Reveal the Model Answer
        
    Drive the two inputs onto the select and tie the four data inputs to the truth table. The select then picks the output row directly. Changing the four constants changes the function, with no new wiring. This is how an FPGA look-up table works.
    
        
    RUNIcarus Verilog · in your browser
    
        
    Edit the code, then run it
    
          
    
          
    
          
    
        
    Expected: a=0 b=0  nand=1 xnor=1 a=1 b=1  nand=0 xnor=1 PASS: the same 4:1 mux made NAND and XNOR from two truth tables
    
        
        
      
    
          
    Self-Check
    Tick each key point you covered in your answer.
    


        
    
      
    
    
    
    
  
    
      
    
    
    Missed Corner
    
    
    Puts the truth table in the wrong bit order and blames the mux.
    
    
    Bit {a, b} of the table is the output for that row. Writing the rows from 00 upward reverses the table.
    
    
    Source Measured: the run on design.puzzle.mux-as-lut, Icarus Verilog 12
    
  
    
    
    4. 

  4. 
    
    WhyWhy a 2:1 Mux Is a Universal GateL0 FresherL1 Junior
      
    
      
    Why can a 2:1 mux build any logic function?
    
      
    
    
    
    
      
      
    Reveal the Model Answer
        
    With constants it makes NOT and AND, and NOT plus AND can express every Boolean function. A mux also splits a function on one variable: f = x ? f(x=1) : f(x=0). Repeat the split on each variable and you get a tree of muxes for any truth table.
    
          
    Self-Check
    Tick each key point you covered in your answer.
    


        
    
      
    
    
    
    
  
    
      
    
    
    Half-Truth
    
    
    "Only NAND and NOR are universal."
    
    
    Any set that can make NOT and AND (or NOT and OR) is complete. A mux with constant inputs makes both.
    
  
    
    
    5. 

  5. 
    
    Prove ItSolve R1.1.1: A Four-Input MuxSimulator-graded
      
    Show it, don't just say it: this Silicon Lab problem is graded by the simulator.
    Open Problem R1.1.1
    
    
    6. 
    

  

    
What People Get Wrong
Common wrong answers and why they fail. Run It shows the wrong belief failing on a real simulator.

    
Misconception

    
Writes AND as a ? 0 : b.

    
The input on the 0 side is chosen when a is 0. This mapping gives ~a & b, and the twin finds it wrong in two of four rows.

    
Run It
      
The AND mux with its data inputs swapped.

        
RUNIcarus Verilog · in your browser

        
Edit the code, then run it

          

          

          

        
Expected: FAIL: a ? 0 : b is not AND; it gives ~a & b, wrong in 2 of 4 rows

        
        
      

      
See the Fix
// mux2: y = s ? b : a
module mux2 (input logic s, a, b, output logic y);
  assign y = s ? b : a;
endmodule

module gates (input logic a, b, output logic y_not, y_and, y_or, y_xor);
  logic nb;
  mux2 m_not (.s(a), .a(1'b1), .b(1'b0), .y(y_not));   // a ? 0 : 1
  mux2 m_and (.s(a), .a(1'b0), .b(b),    .y(y_and));   // a ? b : 0
  mux2 m_or  (.s(a), .a(b),    .b(1'b1), .y(y_or));    // a ? 1 : b
  mux2 m_nb  (.s(b), .a(1'b1), .b(1'b0), .y(nb));      // nb = ~b
  mux2 m_xor (.s(a), .a(b),    .b(nb),   .y(y_xor));   // a ? ~b : b
endmodule

module tb;
  logic a, b, y_not, y_and, y_or, y_xor;
  int bad = 0;
  gates g (.*);
  initial begin
    for (int i = 0; i < 4; i++) begin
      {a, b} = i[1:0]; #1;
      $display("a=%b b=%b  not=%b and=%b or=%b xor=%b", a, b, y_not, y_and, y_or, y_xor);
      if (y_not !== ~a || y_and !== (a & b) || y_or !== (a | b) || y_xor !== (a ^ b)) bad++;
    end
    if (bad == 0) $display("PASS: five 2:1 muxes give NOT, AND, OR and XOR");
    
  end
endmodule

Prints: PASS: five 2:1 muxes give NOT, AND, OR and XOR

    

  

    
Half-Truth

    
Claims XOR fits in one mux with only a, b, 0 and 1.

    
With a on the select, the two data inputs must be b and ~b. Without an inverted b signal, one mux cannot do it.

  

    
Delivery

    
Answers without stating which mux input is selected by 0.

    
Every answer depends on that convention. An interviewer expects it said first, so the mapping can be checked.

  

    
Learn It, Then Prove It