Full Adder Using 2:1 MUX Only
A 2:1 multiplexer is a universal logic element capable of implementing any Boolean function through Shannon's expansion theorem. This problem demonstrates MUX universality by constructing a complete 1-bit full adder — both the Sum and Carry outputs — using only MUX 2:1 components. No AND, OR, XOR, NOT, or any other gate type is permitted.
A full adder takes three 1-bit inputs A, B, Cin and produces Sum = A XOR B XOR Cin and Cout = majority(A, B, Cin). Applying Shannon's expansion on A: Sum(A=0) = XOR(B, Cin) and Sum(A=1) = XNOR(B, Cin). Applying Shannon's expansion on A for carry: Cout(A=0) = AND(B, Cin) and Cout(A=1) = OR(B, Cin).
The truth table for reference:
| A | B | Cin | Sum | Cout | |---|---|-----|-----|------| | 0 | 0 | 0 | 0 | 0 | | 0 | 0 | 1 | 1 | 0 | | 0 | 1 | 0 | 1 | 0 | | 0 | 1 | 1 | 0 | 1 | | 1 | 0 | 0 | 1 | 0 | | 1 | 0 | 1 | 0 | 1 | | 1 | 1 | 0 | 0 | 1 | | 1 | 1 | 1 | 1 | 1 |
For the Sum output: expand on B first. When B=0, Sum = XOR(A, Cin) which itself expands as: MUX with SEL=A, I0=Cin, I1=NOT_Cin. When B=1, Sum = XNOR(A, Cin) = MUX with SEL=A, I0=NOT_Cin, I1=Cin. The top Sum MUX has SEL=B, I0=XOR result, I1=XNOR result. NOT_Cin is itself a MUX (SEL=Cin, I0=1, I1=0). For Cout: MUX with SEL=A, I0=AND(B,Cin), I1=OR(B,Cin). AND(B,Cin) = MUX(SEL=B, I0=0, I1=Cin). OR(B,Cin) = MUX(SEL=B, I0=Cin, I1=1). The optimal implementation uses 5 MUX components total.
| Signal | Direction | Width | Description | |--------|-----------|-------|-------------| | A | input | 1 | First addend bit | | B | input | 1 | Second addend bit | | Cin | input | 1 | Carry-in | | Sum | output | 1 | XOR of A, B, Cin | | Cout | output | 1 | Carry-out: majority of A, B, Cin |
Constraints
- Only MUX 2:1 components are allowed. No AND, OR, NOT, XOR, NAND, NOR gates.
- Constants 0 and 1 may be connected directly to MUX data inputs (I0 or I1).
- The optimal solution uses exactly 5 MUX 2:1 components.
- All 8 input combinations must produce correct Sum and Cout outputs.
Topics
Solve this problem
Place the gates, wire them up and watch the signals settle. Every submission runs on the same simulation engine that grades it.
This problem is part of Codiode Pro. The statement above is free to read.
The circuit builder and code editor need a desktop screen. On a phone, read the problem here and open it on a laptop to solve.