Skip to content
CampusPrep
CS-304 · Digital Systems/Quick Revision Short Notes

Digital Systems (CS-304) - Unit 2 Short Notes

How unit 2 is examined

Adders and subtractors, MUX/DEMUX, encoders/decoders and arithmetic circuits; the marks sit in the multiplexer, the encoder-decoder and the full adder, with the half adder, full subtractor and arithmetic circuits next.

Combinational Logic: Half adder

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>A combinational circuit is one whose output depends only on the present inputs (no memory), and a half adder is the combinational circuit that adds two 1-bit numbers and gives a Sum and a Carry.</mark>

Key points.

  1. A half adder has inputs A, B and outputs Sum and Carry.
  2. Sum is 1 when exactly one input is 1, so $S = A \oplus B$.
  3. Carry is 1 only when both inputs are 1, so $C = AB$.
  4. It has no carry input, so it cannot add a carry from a lower bit; hence the full adder.
  5. NAND-only, it takes five gates: $n_1=\overline{AB}$, $n_2=\overline{An_1}$, $n_3=\overline{Bn_1}$, $S=\overline{n_2n_3}$, $C=\overline{n_1n_1}$.

Truth table (A B -> Sum Carry): 00 -> 0 0; 01 -> 1 0; 10 -> 1 0; 11 -> 0 1.

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-01" viewBox="0 0 510 338" width="510" height="338" role="img" aria-label="NAND-only half adder: N1..N3 are NAND gates, S = Sum, C = Carry (N1 inverted by a NAND)"><style>#dsfig-u2-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-01 .t{fill:#16181D;font-weight:500}#dsfig-u2-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-01 .dot{fill:#16181D}#dsfig-u2-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-01 .ah{fill:#454C5A}#dsfig-u2-01 .ah.hi{fill:#2340B8}#dsfig-u2-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-01 .e{stroke:#B1B7C3}html.dark #dsfig-u2-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-01 .t{fill:#E6E8ED}html.dark #dsfig-u2-01 .t.inv{fill:#0F1115}html.dark #dsfig-u2-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-01 .dot{fill:#E6E8ED}html.dark #dsfig-u2-01 .ann{fill:#8FA3FF}html.dark #dsfig-u2-01 .lbl{fill:#858D9C}html.dark #dsfig-u2-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-01 .ah{fill:#B1B7C3}html.dark #dsfig-u2-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M55.8,50.5 L151.5,114.4" marker-end="url(#ah3)"/><path class="e" d="M55.8,201.5 L151.5,137.6" marker-end="url(#ah3)"/><path class="e" d="M59,40 L277,40" marker-end="url(#ah3)"/><path class="e" d="M184.8,115.5 L280.5,51.6" marker-end="url(#ah3)"/><path class="e" d="M59,212 L277,212" marker-end="url(#ah3)"/><path class="e" d="M184.8,136.5 L280.5,200.4" marker-end="url(#ah3)"/><path class="e" d="M316.4,44.6 L449.6,77.9" marker-end="url(#ah3)"/><path class="e" d="M313.2,200.6 L453.2,95.6" marker-end="url(#ah3)"/><path class="e" d="M185.5,135.4 L451.8,287.6" marker-end="url(#ah3)"/><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="40" cy="212" r="18"/><text class="t" x="40" y="212" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="169" cy="126" r="18"/><text class="t" x="169" y="126" dy=".35em" text-anchor="middle">N1</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">N2</text><circle class="n" cx="298" cy="212" r="18"/><text class="t" x="298" y="212" dy=".35em" text-anchor="middle">N3</text><circle class="n" cx="470" cy="83" r="18"/><text class="t" x="470" y="83" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="470" cy="298" r="18"/><text class="t" x="470" y="298" dy=".35em" text-anchor="middle">C</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">NAND-only half adder: N1..N3 are NAND gates, S = Sum, C = Carry (N1 inverted by a NAND)</figcaption></figure>

Answer frame. Open with the definition; give the truth table and $S$, $C$; draw XOR + AND (or the NAND diagram); explain the four cases; close by noting it has no carry-in.

Asked: [7 marks] (Dec 2020) Design Half adder using NAND gates. Also draw the diagram. Asked: [7 marks] (Dec 2023) Design a Half adder circuit with truth table and logic diagrams.

Half subtractor

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. A half subtractor subtracts one 1-bit number from another (A - B) and gives a Difference and a Borrow.

Key points.

  1. Difference is $D = A \oplus B$.
  2. Borrow is $Bo = \bar A B$, because a borrow is needed only when 0 is reduced by 1.
  3. Its truth table is 00 -> D0 Bo0; 01 -> D1 Bo1; 10 -> D1 Bo0; 11 -> D0 Bo0 (rows A B).
  4. It differs from the half adder only in the inverter on A in the borrow term.

Full adder

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>A full adder is a combinational circuit that adds three 1-bit inputs, A, B and the carry-in $C_{in}$, and produces a Sum and a carry-out $C_{out}$.</mark>

Design steps.

Step 1: Specify: add A, B, Cin to give Sum and Cout.
Step 2: Write the 8-row truth table.
Step 3: Simplify Sum and Cout with K-maps.
Step 4: Draw the gate circuit.

Truth table (A B Cin -> Sum Cout): 000 -> 0 0; 001 -> 1 0; 010 -> 1 0; 011 -> 0 1; 100 -> 1 0; 101 -> 0 1; 110 -> 0 1; 111 -> 1 1.

Formula. $$S = A \oplus B \oplus C_{in}, \qquad C_{out} = AB + C_{in}(A \oplus B)$$

Key points.

  1. Sum is 1 when an odd number of inputs are 1, which is the three-input XOR.
  2. Cout is 1 when at least two inputs are 1: $AB + BC_{in} + AC_{in} = AB + C_{in}(A\oplus B)$.
  3. Two half adders and an OR gate make a full adder: the first adds A and B, the second adds its sum to $C_{in}$, and the OR merges the two carries.
  4. It is required because every bit position except the first receives a carry, and only a full adder accepts it; n of them cascaded form a ripple-carry n-bit adder.

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-02" viewBox="0 0 596 363.8" width="596" height="363.8" role="img" aria-label="Full adder from two half adders (H1, H2) and an OR gate; s1 = A xor B, Sum = s1 xor Cin, Cout = c1 + c2"><style>#dsfig-u2-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-02 .t{fill:#16181D;font-weight:500}#dsfig-u2-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-02 .dot{fill:#16181D}#dsfig-u2-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-02 .ah{fill:#454C5A}#dsfig-u2-02 .ah.hi{fill:#2340B8}#dsfig-u2-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-02 .e{stroke:#B1B7C3}html.dark #dsfig-u2-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-02 .t{fill:#E6E8ED}html.dark #dsfig-u2-02 .t.inv{fill:#0F1115}html.dark #dsfig-u2-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-02 .dot{fill:#E6E8ED}html.dark #dsfig-u2-02 .ann{fill:#8FA3FF}html.dark #dsfig-u2-02 .lbl{fill:#858D9C}html.dark #dsfig-u2-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-02 .ah{fill:#B1B7C3}html.dark #dsfig-u2-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah4" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh4" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M58,46 L149.1,76.4" marker-end="url(#ah4)"/><path class="e" d="M58,120 L149.1,89.6" marker-end="url(#ah4)"/><path class="e" d="M187.4,87.6 L320.6,120.9" marker-end="url(#ah4)"/><path class="e" d="M184.2,243.6 L324.2,138.6" marker-end="url(#ah4)"/><path class="e" d="M358,117.5 L494.2,49.4" marker-end="url(#ah4)"/><path class="e" d="M185.5,92.4 L451.8,244.6" marker-end="url(#ah4)"/><path class="e" d="M354.4,139.4 L455.2,240.2" marker-end="url(#ah4)"/><path class="e" d="M484.8,266.9 L539.6,310.7" marker-end="url(#ah4)"/><g class="wl"><rect x="241.8" y="95.5" width="26.4" height="18" rx="9"/><text class="t" x="255" y="104.5" dy=".35em" text-anchor="middle">s1</text></g><g class="wl"><rect x="410.2" y="74" width="33.6" height="18" rx="9"/><text class="t" x="427" y="83" dy=".35em" text-anchor="middle">Sum</text></g><g class="wl"><rect x="306.3" y="160" width="26.4" height="18" rx="9"/><text class="t" x="319.5" y="169" dy=".35em" text-anchor="middle">c1</text></g><g class="wl"><rect x="392.3" y="181.5" width="26.4" height="18" rx="9"/><text class="t" x="405.5" y="190.5" dy=".35em" text-anchor="middle">c2</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="169" cy="83" r="18"/><text class="t" x="169" y="83" dy=".35em" text-anchor="middle">H1</text><circle class="n" cx="169" cy="255" r="18"/><text class="t" x="169" y="255" dy=".35em" text-anchor="middle">Ci</text><circle class="n" cx="341" cy="126" r="18"/><text class="t" x="341" y="126" dy=".35em" text-anchor="middle">H2</text><circle class="n" cx="470" cy="255" r="18"/><text class="t" x="470" y="255" dy=".35em" text-anchor="middle">OR</text><circle class="n" cx="513" cy="40" r="18"/><text class="t" x="513" y="40" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="556" cy="323.8" r="18"/><text class="t" x="556" y="323.8" dy=".35em" text-anchor="middle">Co</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Full adder from two half adders (H1, H2) and an OR gate; s1 = A xor B, Sum = s1 xor Cin, Cout = c1 + c2</figcaption></figure>

Example. Add $1010_2 + 1011_2$ (10 + 11), starting with carry 0 at the LSB.

Bit A B Cin Sum Cout
0 0 1 0 1 0
1 1 1 0 0 1
2 0 0 1 1 0
3 1 1 0 0 1

The last carry becomes bit 4, so the result is $10101_2 = 21$.

Answer frame. Open with the definition; give the truth table and derive Sum and Cout; draw two half adders plus OR; for the numerical go column by column as above; close with the need for cascading.

Pitfall: In the addition example, write the carry out of the last column as the fifth bit; dropping it gives 0101.

Asked: [7 marks] (Nov 2019, Jun 2023) Write steps of designing a full adder circuit; what is an adder circuit; design and implement a full adder using two half adders and an OR gate. Asked: [7 marks] (Dec 2020) Explain the addition of $1010_2$ to $1011_2$ using full adder step by step. Asked: [7 marks] (Dec 2025) Explain the working of a Full Adder with truth table and logic diagram. Why is it required in arithmetic circuits?

Full subtractor

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>A full subtractor is a combinational circuit that subtracts B and the borrow-in $B_{in}$ from A and produces a Difference and a borrow-out $B_{out}$.</mark>

Truth table (A B Bin -> D Bout): 000 -> 0 0; 001 -> 1 1; 010 -> 1 1; 011 -> 0 1; 100 -> 1 0; 101 -> 0 0; 110 -> 0 0; 111 -> 1 1.

Formula. $$D = A \oplus B \oplus B_{in}, \qquad B_{out} = \bar A B + B_{in}\,\overline{(A \oplus B)}$$

Key points.

  1. A combinational circuit has outputs that depend only on present inputs and has no memory.
  2. Difference is 1 when an odd number of inputs are 1, like the full-adder Sum.
  3. Borrow is 1 when A is smaller than B plus the incoming borrow: $\bar AB + \bar AB_{in} + BB_{in}$.
  4. It is built from two half subtractors and an OR gate.
  5. The NAND-only circuit has nine NAND gates: $n_1=\overline{AB}$, $n_2=\overline{An_1}$, $n_3=\overline{Bn_1}$, $x=\overline{n_2n_3}$, $n_5=\overline{xB_{in}}$, $n_6=\overline{xn_5}$, $n_7=\overline{B_{in}n_5}$, $D=\overline{n_6n_7}$, $B_{out}=\overline{n_3n_7}$.

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-03" viewBox="0 0 596 363.8" width="596" height="363.8" role="img" aria-label="Full subtractor from two half subtractors (X, Y) and an OR gate; each half subtractor is 4 NAND gates and the shared borrow OR is one NAND, so 9 NAND in all"><style>#dsfig-u2-03 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-03 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-03 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-03 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-03 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-03 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-03 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-03 .t{fill:#16181D;font-weight:500}#dsfig-u2-03 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-03 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-03 .dot{fill:#16181D}#dsfig-u2-03 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-03 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-03 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-03 .ah{fill:#454C5A}#dsfig-u2-03 .ah.hi{fill:#2340B8}#dsfig-u2-03 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-03 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-03 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-03 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-03 .e{stroke:#B1B7C3}html.dark #dsfig-u2-03 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-03 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-03 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-03 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-03 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-03 .t{fill:#E6E8ED}html.dark #dsfig-u2-03 .t.inv{fill:#0F1115}html.dark #dsfig-u2-03 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-03 .dot{fill:#E6E8ED}html.dark #dsfig-u2-03 .ann{fill:#8FA3FF}html.dark #dsfig-u2-03 .lbl{fill:#858D9C}html.dark #dsfig-u2-03 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-03 .ah{fill:#B1B7C3}html.dark #dsfig-u2-03 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-03 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-03 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-03 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah5" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh5" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M58,46 L149.1,76.4" marker-end="url(#ah5)"/><path class="e" d="M58,120 L149.1,89.6" marker-end="url(#ah5)"/><path class="e" d="M187.4,87.6 L320.6,120.9" marker-end="url(#ah5)"/><path class="e" d="M184.2,243.6 L324.2,138.6" marker-end="url(#ah5)"/><path class="e" d="M358,117.5 L494.2,49.4" marker-end="url(#ah5)"/><path class="e" d="M185.5,92.4 L451.8,244.6" marker-end="url(#ah5)"/><path class="e" d="M354.4,139.4 L455.2,240.2" marker-end="url(#ah5)"/><path class="e" d="M484.8,266.9 L539.6,310.7" marker-end="url(#ah5)"/><g class="wl"><rect x="245.4" y="95.5" width="19.2" height="18" rx="9"/><text class="t" x="255" y="104.5" dy=".35em" text-anchor="middle">x</text></g><g class="wl"><rect x="406.6" y="74" width="40.8" height="18" rx="9"/><text class="t" x="427" y="83" dy=".35em" text-anchor="middle">Diff</text></g><g class="wl"><rect x="306.3" y="160" width="26.4" height="18" rx="9"/><text class="t" x="319.5" y="169" dy=".35em" text-anchor="middle">b1</text></g><g class="wl"><rect x="392.3" y="181.5" width="26.4" height="18" rx="9"/><text class="t" x="405.5" y="190.5" dy=".35em" text-anchor="middle">b2</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="169" cy="83" r="18"/><text class="t" x="169" y="83" dy=".35em" text-anchor="middle">X</text><circle class="n" cx="169" cy="255" r="18"/><text class="t" x="169" y="255" dy=".35em" text-anchor="middle">Bi</text><circle class="n" cx="341" cy="126" r="18"/><text class="t" x="341" y="126" dy=".35em" text-anchor="middle">Y</text><circle class="n" cx="470" cy="255" r="18"/><text class="t" x="470" y="255" dy=".35em" text-anchor="middle">OR</text><circle class="n" cx="513" cy="40" r="18"/><text class="t" x="513" y="40" dy=".35em" text-anchor="middle">D</text><circle class="n" cx="556" cy="323.8" r="18"/><text class="t" x="556" y="323.8" dy=".35em" text-anchor="middle">Bo</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Full subtractor from two half subtractors (X, Y) and an OR gate; each half subtractor is 4 NAND gates and the shared borrow OR is one NAND, so 9 NAND in all</figcaption></figure>

Answer frame. Open with the definition; give the truth table; derive D and Bout; draw two half subtractors plus OR, or the nine NANDs above; close by comparing with the full adder.

Asked: [7 marks] (Dec 2024) Draw a full subtractor circuit using NAND gate. Asked: [7 marks] (May 2019) What is combinational circuit? Explain full subtractor.

Look-ahead carry generator

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. A carry look-ahead generator computes all the carries of an adder directly from the inputs, without waiting for the carry to ripple through each stage.

Key points.

  1. Define generate $G_i = A_iB_i$ and propagate $P_i = A_i \oplus B_i$; then $C_{i+1} = G_i + P_iC_i$ and $S_i = P_i \oplus C_i$.
  2. Expanding gives $C_1 = G_0 + P_0C_0$ and $C_2 = G_1 + P_1G_0 + P_1P_0C_0$.
  3. Likewise $C_3 = G_2 + P_2G_1 + P_2P_1G_0 + P_2P_1P_0C_0$, and every carry is a two-level AND-OR function of the inputs.
  4. All carries appear after about three gate delays whatever the width, so it is much faster than ripple carry, at the cost of more gates.

BCD adder

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. A BCD adder adds two BCD digits (0-9) and a carry-in and gives a BCD digit with a carry.

Key points.

  1. The first 4-bit binary adder adds the digits, giving sum $S_3S_2S_1S_0$ and carry K.
  2. The result is invalid if it exceeds 9 or K = 1, so $C_{out} = K + S_3S_2 + S_3S_1$.
  3. When $C_{out}$ = 1 the second adder adds $0110_2$ (6); otherwise it adds 0000.
  4. Example: 8 + 9 gives 10001 with K = 1; adding 0110 to 0001 gives 0111, so the answer is 0001 0111 = 17.

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-04" viewBox="0 0 603 295" width="603" height="295" role="img" aria-label="BCD adder: ADD1 and ADD2 are 4-bit binary adders, Cor is the correction logic K + S3S2 + S3S1"><style>#dsfig-u2-04 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-04 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-04 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-04 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-04 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-04 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-04 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-04 .t{fill:#16181D;font-weight:500}#dsfig-u2-04 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-04 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-04 .dot{fill:#16181D}#dsfig-u2-04 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-04 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-04 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-04 .ah{fill:#454C5A}#dsfig-u2-04 .ah.hi{fill:#2340B8}#dsfig-u2-04 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-04 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-04 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-04 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-04 .e{stroke:#B1B7C3}html.dark #dsfig-u2-04 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-04 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-04 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-04 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-04 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-04 .t{fill:#E6E8ED}html.dark #dsfig-u2-04 .t.inv{fill:#0F1115}html.dark #dsfig-u2-04 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-04 .dot{fill:#E6E8ED}html.dark #dsfig-u2-04 .ann{fill:#8FA3FF}html.dark #dsfig-u2-04 .lbl{fill:#858D9C}html.dark #dsfig-u2-04 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-04 .ah{fill:#B1B7C3}html.dark #dsfig-u2-04 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-04 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-04 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-04 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah6" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh6" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M58,89 L142.4,117.1" marker-end="url(#ah6)"/><path class="e" d="M58,163 L142.4,134.9" marker-end="url(#ah6)"/><path class="e" d="M187.4,144.4 L283.2,240.2" marker-end="url(#ah6)"/><path class="e" d="M190.6,111.6 L280.5,51.6" marker-end="url(#ah6)"/><path class="e" d="M298,236 L298,61" marker-end="url(#ah6)"/><path class="e" d="M311.4,53.4 L407.2,149.2" marker-end="url(#ah6)"/><path class="e" d="M313.8,244.5 L403.7,184.5" marker-end="url(#ah6)"/><path class="e" d="M317,40 L535,40" marker-end="url(#ah6)"/><g class="wl"><rect x="223.9" y="181.5" width="19.2" height="18" rx="9"/><text class="t" x="233.5" y="190.5" dy=".35em" text-anchor="middle">S</text></g><g class="wl"><rect x="223.9" y="74" width="19.2" height="18" rx="9"/><text class="t" x="233.5" y="83" dy=".35em" text-anchor="middle">K</text></g><g class="wl"><rect x="342.1" y="95.5" width="40.8" height="18" rx="9"/><text class="t" x="362.5" y="104.5" dy=".35em" text-anchor="middle">0110</text></g><circle class="n" cx="40" cy="83" r="18"/><text class="t" x="40" y="83" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="40" cy="169" r="18"/><text class="t" x="40" y="169" dy=".35em" text-anchor="middle">B</text><rect class="n" x="144" y="111" width="50" height="30" rx="15"/><text class="t" x="169" y="126" dy=".35em" text-anchor="middle">ADD1</text><circle class="n" cx="298" cy="255" r="18"/><text class="t" x="298" y="255" dy=".35em" text-anchor="middle">Z</text><rect class="n" x="402" y="154" width="50" height="30" rx="15"/><text class="t" x="427" y="169" dy=".35em" text-anchor="middle">ADD2</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">Cor</text><circle class="n" cx="556" cy="40" r="18"/><text class="t" x="556" y="40" dy=".35em" text-anchor="middle">Cy</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">BCD adder: ADD1 and ADD2 are 4-bit binary adders, Cor is the correction logic K + S3S2 + S3S1</figcaption></figure>

Asked: [7 marks] (Jun 2023) Draw and explain the BCD adder circuit.

Series and parallel addition

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. A serial adder adds one bit pair per clock using a single full adder, while a parallel adder adds all bits at the same time with one full adder per bit.

Key points.

  1. A serial adder has shift registers, one full adder and a carry flip-flop, and needs n clocks for n bits; it is cheap but slow.
  2. Parallel adders are ripple carry, carry look-ahead, carry save and carry select.
  3. A ripple-carry adder chains full adders, so its delay grows with n.
  4. A carry look-ahead adder forms every carry from $G_i$ and $P_i$, so its delay is nearly independent of n.
  5. A carry save adder adds three numbers with independent full adders and outputs a sum word and a carry word without propagating; one ordinary adder combines them, which suits multi-operand addition and multipliers.

Asked: [7 marks] (Dec 2023) What are the different types of parallel adders? Explain carry save and carry look-ahead adders.

Multiplexer and demultiplexer

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>A multiplexer (data selector) is a combinational circuit that routes one of $2^n$ data inputs to a single output under the control of n select lines; a demultiplexer does the reverse, sending one input to one of $2^n$ outputs.</mark>

Key points.

  1. A $2^n\times1$ MUX has $2^n$ data inputs, n select lines, an optional enable and one output.
  2. Its roles are data routing, parallel-to-serial conversion and implementing Boolean functions.
  3. For 4:1, $Y = \bar S_1\bar S_0I_0 + \bar S_1S_0I_1 + S_1\bar S_0I_2 + S_1S_0I_3$.
  4. For 8:1, $Y = \sum_{k=0}^{7} m_kI_k$ with $m_k$ the minterm of $S_2S_1S_0$.
  5. Inside, a decoder picks one line, AND gates gate the data, and an OR gate merges them.
  6. An 8:1 MUX from two 4:1: both share $S_1S_0$ and $S_2$ drives a 2:1 MUX (or OR) that picks the group.
  7. A demultiplexer is a decoder whose enable is the data input; the selects choose the output.
  8. As a ROM, the selects are the address, the data inputs are tied to stored bits 0 or 1, and the output is the stored bit.

Truth table: for select code $S_2S_1S_0$ = 000, 001, ..., 111 the output Y equals $I_0, I_1, \dots, I_7$ respectively.

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-05" viewBox="0 0 553 338" width="553" height="338" role="img" aria-label="8:1 MUX from two 4:1 MUX: L takes I0-I3, U takes I4-I7, both use S1 S0; F is a 2:1 MUX selected by S2"><style>#dsfig-u2-05 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-05 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-05 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-05 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-05 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-05 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-05 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-05 .t{fill:#16181D;font-weight:500}#dsfig-u2-05 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-05 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-05 .dot{fill:#16181D}#dsfig-u2-05 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-05 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-05 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-05 .ah{fill:#454C5A}#dsfig-u2-05 .ah.hi{fill:#2340B8}#dsfig-u2-05 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-05 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-05 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-05 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-05 .e{stroke:#B1B7C3}html.dark #dsfig-u2-05 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-05 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-05 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-05 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-05 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-05 .t{fill:#E6E8ED}html.dark #dsfig-u2-05 .t.inv{fill:#0F1115}html.dark #dsfig-u2-05 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-05 .dot{fill:#E6E8ED}html.dark #dsfig-u2-05 .ann{fill:#8FA3FF}html.dark #dsfig-u2-05 .lbl{fill:#858D9C}html.dark #dsfig-u2-05 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-05 .ah{fill:#B1B7C3}html.dark #dsfig-u2-05 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-05 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-05 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-05 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah7" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh7" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M55.8,115.5 L151.5,51.6" marker-end="url(#ah7)"/><path class="e" d="M55.8,136.5 L151.5,200.4" marker-end="url(#ah7)"/><path class="e" d="M186,48.5 L322.2,116.6" marker-end="url(#ah7)"/><path class="e" d="M186,203.5 L322.2,135.4" marker-end="url(#ah7)"/><path class="e" d="M341,279 L341,147" marker-end="url(#ah7)"/><path class="e" d="M360,126 L492,126" marker-end="url(#ah7)"/><g class="wl"><rect x="234.6" y="74" width="40.8" height="18" rx="9"/><text class="t" x="255" y="83" dy=".35em" text-anchor="middle">I0-3</text></g><g class="wl"><rect x="234.6" y="160" width="40.8" height="18" rx="9"/><text class="t" x="255" y="169" dy=".35em" text-anchor="middle">I4-7</text></g><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">L</text><circle class="n" cx="169" cy="212" r="18"/><text class="t" x="169" y="212" dy=".35em" text-anchor="middle">U</text><circle class="n" cx="341" cy="126" r="18"/><text class="t" x="341" y="126" dy=".35em" text-anchor="middle">F</text><circle class="n" cx="513" cy="126" r="18"/><text class="t" x="513" y="126" dy=".35em" text-anchor="middle">Y</text><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">S10</text><circle class="n" cx="341" cy="298" r="18"/><text class="t" x="341" y="298" dy=".35em" text-anchor="middle">S2</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">8:1 MUX from two 4:1 MUX: L takes I0-I3, U takes I4-I7, both use S1 S0; F is a 2:1 MUX selected by S2</figcaption></figure>

Steps (implementing a function).

Step 1: For n variables use a 2^(n-1):1 MUX; the first n-1 variables are selects, the last is data.
Step 2: List minterms in pairs (2r, 2r+1) under each select code.
Step 3: Input = 0 if none present, 1 if both, the data variable if only the odd one, its complement if only the even one.

Example. $f(A,B,C,D)=\sum(0,1,5,7,10,14,15)$ on an 8:1 MUX with A, B, C as selects and D as data.

ABC Minterms present Input
000 0, 1 $I_0 = 1$
001 none $I_1 = 0$
010 5 (D=1) $I_2 = D$
011 7 (D=1) $I_3 = D$
100 none $I_4 = 0$
101 10 (D=0) $I_5 = \bar D$
110 none $I_6 = 0$
111 14, 15 $I_7 = 1$

So $I_0=1,\ I_1=0,\ I_2=D,\ I_3=D,\ I_4=0,\ I_5=\bar D,\ I_6=0,\ I_7=1$; connect these to the 8:1 MUX with A, B, C on $S_2S_1S_0$.

Variants: for $F=\sum m(1,3,6,7)$ on a 4:1 MUX (selects A, B): $I_0=C$, $I_1=C$, $I_2=0$, $I_3=1$. For $f=\pi(1,4,6,10,14)+d(0,8,11,15)$ the minterms are $\sum(2,3,5,7,9,12,13)+d(0,8,11,15)$; the 16:1 MUX inputs $I_0..I_{15}$ are $x,0,1,1,0,1,0,1,x,1,0,x,1,1,0,x$ (x = don't care, tie to 0 or 1); on an 8:1 MUX with A, B, C as selects, $I_0..I_7 = 0,1,D,D,1,D,1,D$.

Answer frame. For "explain 8:1": define, draw the block with $I_0$-$I_7$, $S_2S_1S_0$, enable and Y, give the truth table and expression, then the roles. For "design 8:1 from smaller": draw the diagram above and show which select drives which stage. For "implement a function": prepare the table, read off the data inputs, draw the connections. Close with one line on uses.

Pitfall: Pair the minterms by the last variable ($2r$ and $2r+1$) and never by the select code alone; mis-pairing gives wrong data inputs.

Asked: [7 marks] (Nov 2019, Nov 2022) How to design a $8\times 1$ MUX using two $4\times 1$ MUX (or one $4\times 1$ and four $2\times 1$ MUX)? Draw the circuit. Asked: [7 marks] (May 2019, Dec 2024) What is a Multiplexer? Explain 8:1 multiplexer with its truth table and expression; explain its role and how it selects one input. Asked: [7 marks] (Dec 2020) How a multiplexer can be used as ROM? Explain in brief. Asked: [7 marks] (Jun 2020, Jun 2023, Dec 2025) Implement $f(A,B,C,D)=\sum(0,1,5,7,10,14,15)$ using 8:1 MUX; realize $f=\pi(1,4,6,10,14)+d(0,8,11,15)$ using 16:1 and 8:1 MUX; implement $F(A,B,C)=\sum m(1,3,6,7)$ using 4:1 MUX.

Encoder and decoder

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>A decoder is a combinational circuit with n coded inputs and up to $2^n$ outputs of which exactly one is active for each input code; an encoder does the opposite, converting one active input line among many into a binary code on fewer outputs.</mark>

Key points.

  1. A 3-to-8 decoder has inputs A, B, C, enable E and outputs $Y_0..Y_7$, where $Y_i=m_i$ when E = 1.
  2. It uses three inverters and eight 3-input AND gates (NAND for active-low outputs): $Y_0=\bar A\bar B\bar C$, $Y_7=ABC$.
  3. With E inactive all outputs are off; enable lets small decoders combine into larger ones.
  4. For 1x2 + two 2x4: A drives the 1-to-2 decoder, its outputs enable the two 2-to-4 decoders, B and C go to both; the upper gives $Y_0$-$Y_3$ (A = 0), the lower $Y_4$-$Y_7$.
  5. A decoder plus OR gates realises any function: $F_1=\sum m(0,5,7)$ and $F_2=\sum m(1,3,6)$ give $F_1=Y_0+Y_5+Y_7$, $F_2=Y_1+Y_3+Y_6$.
  6. A BCD-to-decimal decoder has 4 inputs and 10 outputs, each a 4-input AND; codes 1010-1111 give no output.
  7. An encoder has one active input among many and n output bits; the decimal-to-BCD encoder uses OR gates: $A=D_8+D_9$, $B=D_4+D_5+D_6+D_7$, $C=D_2+D_3+D_6+D_7$, $D=D_1+D_3+D_5+D_7+D_9$.
  8. A priority encoder gives the highest-numbered active input priority when several are active.
  9. Decoders serve memory address decoding, data demultiplexing and seven-segment drivers.

Truth table: with E = 1, input code ABC = 000, 001, ..., 111 makes $Y_0, Y_1, \dots, Y_7$ = 1 respectively and all others 0; with E = 0 every output is 0.

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-06" viewBox="0 0 553 295" width="553" height="295" role="img" aria-label="3-to-8 decoder from one 1-to-2 decoder (X) and two 2-to-4 decoders (U, L); A is the MSB, BC go to both"><style>#dsfig-u2-06 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-06 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-06 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-06 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-06 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-06 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-06 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-06 .t{fill:#16181D;font-weight:500}#dsfig-u2-06 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-06 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-06 .dot{fill:#16181D}#dsfig-u2-06 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-06 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-06 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-06 .ah{fill:#454C5A}#dsfig-u2-06 .ah.hi{fill:#2340B8}#dsfig-u2-06 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-06 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-06 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-06 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-06 .e{stroke:#B1B7C3}html.dark #dsfig-u2-06 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-06 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-06 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-06 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-06 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-06 .t{fill:#E6E8ED}html.dark #dsfig-u2-06 .t.inv{fill:#0F1115}html.dark #dsfig-u2-06 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-06 .dot{fill:#E6E8ED}html.dark #dsfig-u2-06 .ann{fill:#8FA3FF}html.dark #dsfig-u2-06 .lbl{fill:#858D9C}html.dark #dsfig-u2-06 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-06 .ah{fill:#B1B7C3}html.dark #dsfig-u2-06 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-06 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-06 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-06 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah8" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh8" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L148,40" marker-end="url(#ah8)"/><path class="e" d="M187.4,44.6 L320.6,77.9" marker-end="url(#ah8)"/><path class="e" d="M180.9,54.8 L327.9,238.6" marker-end="url(#ah8)"/><path class="e" d="M56.5,245.6 L322.8,93.4" marker-end="url(#ah8)"/><path class="e" d="M59,255 L320,255" marker-end="url(#ah8)"/><path class="e" d="M360,83 L492,83" marker-end="url(#ah8)"/><path class="e" d="M360,255 L492,255" marker-end="url(#ah8)"/><g class="wl"><rect x="241.8" y="52.5" width="26.4" height="18" rx="9"/><text class="t" x="255" y="61.5" dy=".35em" text-anchor="middle">E0</text></g><g class="wl"><rect x="241.8" y="138.5" width="26.4" height="18" rx="9"/><text class="t" x="255" y="147.5" dy=".35em" text-anchor="middle">E1</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="40" cy="255" r="18"/><text class="t" x="40" y="255" dy=".35em" text-anchor="middle">BC</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">X</text><circle class="n" cx="341" cy="83" r="18"/><text class="t" x="341" y="83" dy=".35em" text-anchor="middle">U</text><circle class="n" cx="341" cy="255" r="18"/><text class="t" x="341" y="255" dy=".35em" text-anchor="middle">L</text><circle class="n" cx="513" cy="83" r="18"/><text class="t" x="513" y="83" dy=".35em" text-anchor="middle">Y03</text><circle class="n" cx="513" cy="255" r="18"/><text class="t" x="513" y="255" dy=".35em" text-anchor="middle">Y47</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">3-to-8 decoder from one 1-to-2 decoder (X) and two 2-to-4 decoders (U, L); A is the MSB, BC go to both</figcaption></figure>

Truth table (ABCD for the active input): D0 = 0000, D1 = 0001, D2 = 0010, D3 = 0011, D4 = 0100, D5 = 0101, D6 = 0110, D7 = 0111, D8 = 1000, D9 = 1001.

Answer frame. Decoder: define, draw the block (3 inputs, enable, 8 outputs), truth table, AND/NAND circuit, then enable and uses. 1x2 + 2x4: draw the diagram above with the combined truth table. Encoder: define, 10-to-4 table, four OR equations, OR-gate diagram. Two-function design: expand to minterms, decoder plus two OR gates.

Pitfall: In the decimal-to-BCD encoder, $D_0$ is not connected to any OR gate because all outputs are 0 for it.

Asked: [7 marks] (Nov 2019, Dec 2020) What is decoder? Design a $3\times 8$ decoder; design the binary to octal decoder and explain it with a block diagram. Asked: [7 marks] (May 2019, Dec 2025) What is Encoder? Explain decimal to BCD encoder; design a decimal-to-BCD encoder and explain its working. Asked: [7 marks] (Jun 2020) What is decoder? Explain BCD to decimal decoder. Asked: [7 marks] (Nov 2022) Design a $3\times 8$ decoder using one $1\times 2$ decoder and two $2\times 4$ decoders with Enable input. Asked: [7 marks] (Dec 2023) Design with a decoder and external gates: $F_1 = x'y'z' + xz$, $F_2 = xyz' + x'z$. Asked: [7 marks] (Dec 2024) Write a short note on decoder.

Arithmetic circuits

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>Arithmetic circuits are combinational circuits, such as adders, subtractors, the two's complementer and the adder-subtractor, that perform arithmetic on binary numbers.</mark>

Key points.

  1. Two's complement is $B=\bar A+1$: invert all bits and add 1.
  2. Bit by bit: $B_0=A_0$, $B_1=A_1\oplus A_0$, $B_2=A_2\oplus(A_1+A_0)$, $B_3=A_3\oplus(A_2+A_1+A_0)$.
  3. In NOR form each XNOR takes four NOR gates, and $n_1=\overline{A_1+A_0}$ is shared: $B_1$ = XOR of $A_1,A_0$ (four NOR from $n_1$), $B_2$ = XNOR($A_2,n_1$), and $B_3$ = XNOR($A_3,q$) with $q=\overline{A_2+A_1+A_0}$ = NOR($A_2$, NOR($n_1,n_1$)).
  4. $B_0$ is a wire, and the total is 15 NOR gates (checked for all 16 inputs).
  5. An adder-subtractor XORs B with a mode input M and uses M as carry-in: M = 1 gives A + B' + 1 = A - B.

Answer frame. Open with $B=\bar A+1$; write the four equations; convert each to NOR form sharing $n_1$; draw $A_3..A_0$ in, $B_3..B_0$ out; close with the gate count.

Asked: [7 marks] (Nov 2022) Draw a schematic for a minimal circuit that uses only NOR gates that performs the two's complement operation on a four bit input value. Let the input be $A_{3:0}$ and the output be $B_{3:0}$.

ALU

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. An arithmetic logic unit is a combinational circuit that performs a selected arithmetic or logic operation on two n-bit operands.

Key points.

  1. Select lines choose the operation, such as add, subtract, AND, OR, XOR and NOT, and a mode input M separates arithmetic from logic operations.
  2. A 4-bit ALU such as the 74181 has 16 logic and 16 arithmetic functions, with a carry-in, carry-out and status flags.
  3. It combines an adder-subtractor, a logic unit and a multiplexer that picks the result, and it is the core of the CPU's data path.

Last-minute revision

  • Half adder: $S = A\oplus B$, $C = AB$; 5 NAND gates.
  • Full adder: $S = A\oplus B\oplus C_{in}$, $C_{out} = AB + C_{in}(A\oplus B)$; two half adders + OR.
  • Full subtractor: $D = A\oplus B\oplus B_{in}$, $B_{out} = \bar AB + B_{in}\overline{(A\oplus B)}$; 9 NAND gates.
  • $1010_2 + 1011_2 = 10101_2$ (21).
  • CLA: $G_i = A_iB_i$, $P_i = A_i\oplus B_i$, $C_{i+1} = G_i + P_iC_i$.
  • BCD adder: correct by adding 0110 when $K + S_3S_2 + S_3S_1 = 1$; 8 + 9 = 0001 0111.
  • $2^n$:1 MUX has n selects; 8:1 from two 4:1 plus a 2:1 MUX driven by $S_2$.
  • $f=\sum(0,1,5,7,10,14,15)$ on 8:1: $I_0..I_7 = 1,0,D,D,0,\bar D,0,1$ with ABC as selects and D as data.
  • 3-to-8 decoder from 1-to-2 + two 2-to-4: A enables, BC common.
  • Decimal-to-BCD: $A=D_8+D_9$, $B=D_4+D_5+D_6+D_7$, $C=D_2+D_3+D_6+D_7$, $D=D_1+D_3+D_5+D_7+D_9$.
  • Two's complement: $B_1=A_1\oplus A_0$, $B_2=A_2\oplus(A_1+A_0)$, $B_3=A_3\oplus(A_2+A_1+A_0)$.

Memory hooks

  • Half adder: XOR gives the sum, AND gives the carry; full adder = two halves + OR.
  • Subtractor borrow: the inverter sits on A ($\bar A B$).
  • MUX = many in, one out (selector); DEMUX and decoder = one in, many out.
  • Encoder = OR gates, decoder = AND gates.
  • BCD adder: "greater than 9, add 6".

Coverage checklist

  • Combinational Logic: Half adder — Dec 2020 NAND half adder; Dec 2023 half adder design.
  • Half subtractor — not asked recently; definition, D and Bo.
  • Full adder — Nov 2019/Jun 2023 design steps and two-half-adder design; Dec 2020 1010+1011; Dec 2025 explain.
  • Full subtractor — Dec 2024 NAND full subtractor; May 2019 combinational circuit and full subtractor.
  • look- ahead carry generator — not asked recently; G, P and carry equations.
  • BCD adder — Jun 2023 draw and explain.
  • Series and parallel addition — Dec 2023 types of parallel adders, carry save, CLA.
  • Multiplexer – demultiplexer — Nov 2019/Nov 2022 8:1 from smaller; May 2019/Dec 2024 explain 8:1; Dec 2020 MUX as ROM; Jun 2020/Jun 2023/Dec 2025 function implementations.
  • encoder- decoder — Nov 2019/Dec 2020 3x8 decoder; May 2019/Dec 2025 decimal-to-BCD encoder; Jun 2020 BCD-to-decimal decoder; Nov 2022 1x2 + 2x4; Dec 2023 F1, F2; Dec 2024 short note.
  • arithmetic circuits — Nov 2022 NOR two's complement.
  • ALU — not asked recently; operations, select lines, 74181.
Go to where you left off?

Quick Add to Notes

Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.

Create free account

Have an account? Log in