Digital Logic: Gates, Adders, Multiplexers and Flip-Flops

Digital circuits compute Boolean functions with gates built from transistors:

Concept

Digital circuits compute Boolean functions with gates built from transistors:

Output is 1 when both inputs are 1 at least one input is 1 not both inputs are 1 both inputs are 0

NAND (and NOR) are universal: any Boolean function can be built from NAND gates alone. In CMOS technology a NAND gate needs just four transistors.

Their outputs depend only on the current inputs:

Half adder: sum = a XOR b, carry = a AND b.

Full adder: adds a, b and a carry-in; sum = a ⊕ b ⊕ cin, cout = ab + cin(a ⊕ b).

Ripple-carry adder: *n* full adders chained through their carries; simple but slow (the carry ripples through all bits). Real CPUs use carry-lookahead or prefix adders to compute carries in parallel.

Multiplexer (MUX): selects one of several inputs by a select signal — the "if" of hardware.

Decoder: turns an *n*-bit code into one of 2ⁿ active lines (used to select registers and memory rows).

Their outputs also depend on state (memory):

Latch: stores a bit while enabled.

Flip-flop: stores a bit on a clock edge — the basic storage element of registers.

Register: *n* flip-flops sharing a clock.

Clock: a periodic signal; all state changes happen on its edges, which synchronizes the whole circuit. The clock period must be longer than the slowest combinational path (the critical path) — this sets the maximum clock frequency.

Memories: SRAM (flip-flop-like cells, fast, used for caches and registers) and DRAM (a capacitor per bit, dense, must be refreshed, used for main memory).

Why It Matters

Every instruction you write ends up as signals through these circuits. Understanding them explains why addition is fast and division slow, why wider adders are harder, why clock speed is limited, and it is the basis of embedded, VLSI and FPGA work.

Syntax

Boolean algebra notation: A·B (AND), A + B (OR), A' or ¬A (NOT), A ⊕ B (XOR). De Morgan's laws: (A·B)' = A' + B' and (A + B)' = A'·B'.

Example

3.1 Gates, a full adder, a 4-bit adder, a MUX and a D flip-flop — all built from NAND

#include <stdio.h>

/* Every function below is built ONLY from NAND, the universal gate. */
static int NAND(int a, int b) { return !(a && b); }
static int NOT(int a) { return NAND(a, a); }
static int AND(int a, int b) { return NOT(NAND(a, b)); }
static int OR(int a, int b) { return NAND(NOT(a), NOT(b)); }
static int XOR(int a, int b) { int n = NAND(a, b); return NAND(NAND(a, n), NAND(b, n)); }
static int MUX(int sel, int a, int b) { return OR(AND(NOT(sel), a), AND(sel, b)); }

static void full_adder(int a, int b, int cin, int *sum, int *cout)
{
    int s1 = XOR(a, b);
    *sum = XOR(s1, cin);
    *cout = OR(AND(a, b), AND(s1, cin));
}

/* 4-bit ripple-carry adder: four full adders chained through their carries */
static int add4(int a, int b, int *carry_out)
{
    int carry = 0, result = 0;
    for (int i = 0; i < 4; i++) {
        int s;
        full_adder((a >> i) & 1, (b >> i) & 1, carry, &s, &carry);
        result |= s << i;
    }
    *carry_out = carry;
    return result;
}

/* D flip-flop: captures D on the rising clock edge and holds it otherwise */
typedef struct { int q, last_clk; } DFF;
static void dff_tick(DFF *f, int clk, int d)
{
    if (clk && !f->last_clk) f->q = d;
…

Expected Result

The full-adder table is the complete specification of one bit of addition.

11 + 6 = 17 doesn't fit in 4 bits: the result is 1 with carry-out 1 — the same carry flag a CPU sets (Module 4).

The flip-flop changed only on the three rising edges (0→1) of the clock: at step 2 it captured d=1, at step 6 d=1 again and at step 8 d=0. Changes of d between edges were ignored.

a b | AND OR XOR NAND
0 0 |  0   0   0   1
0 1 |  0   1   1   1
1 0 |  0   1   1   1
1 1 |  1   1   0   0

full adder: 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

4-bit adder: 11 + 6 = 1 with carry 1  (17 does not fit in 4 bits: 17 - 16 = 1)
4-bit adder:  5 + 9 = 14 with carry 0

MUX(sel, a=0, b=1): sel=0 -> 0, sel=1 -> 1

D flip-flop (updates only on 0->1 clock edges)
clk: 0 1 1 0 0 1 0 1 
d:   1 1 0 0 1 1 0 0 
q:   0 1 1 1 1 1 1 0

Common Mistakes

Confusing XOR (exactly one input 1) with OR (at least one).

Thinking a flip-flop follows its input continuously (that's a transparent latch).

Forgetting that a ripple-carry adder's delay grows linearly with the number of bits.

Ignoring propagation delay: combinational outputs are only valid after the signals settle.

Best Practices

Describe logic with truth tables first, then simplify (Karnaugh maps, Boolean algebra).

In hardware description languages (Verilog, VHDL), separate combinational and clocked (sequential) logic clearly.

Think in terms of the critical path when reasoning about speed.

Interview Relevance

Medium (high for embedded/VLSI roles): "build XOR from NAND", "half adder vs full adder", "latch vs flip-flop", "what limits clock frequency?", "SRAM vs DRAM".

Practice Questions

Build NOR, then AND, using only NOR gates.

Extend the 4-bit adder into an adder/subtractor using XOR gates on the B inputs and a carry-in of 1.

Write a 2-to-4 decoder in C using only the gate functions.

How many NAND gates does the full adder in the example use?

Quick Quiz

Q1. (Multiple choice) Which gate is universal? A) XOR B) NAND C) OR D) NOT Answer: B.

Q2. (Predict the output) A full adder with a=1, b=1, cin=1 produces sum and carry of?

Answer: sum 1, carry 1 (verified: last row of the table).

Q3. (True/False) A flip-flop changes its output whenever its data input changes.

Answer: False. An edge-triggered flip-flop updates only on the clock edge (verified).

Q4. (Find the bug) "A 64-bit ripple-carry adder is as fast as an 8-bit one because each full adder is equally fast."

Answer: The carry must ripple through all 64 stages, so the delay is about eight times longer; fast adders use carry-lookahead.

Coding Challenge

Using only a NAND function, implement a half adder and print its truth table.

#include <stdio.h>

static int NAND(int a, int b) { return !(a && b); }

static void half_adder(int a, int b, int *sum, int *carry)
{
    int n = NAND(a, b);
    *sum = NAND(NAND(a, n), NAND(b, n));   /* XOR from four NANDs */
    *carry = NAND(n, n);                   /* AND = NOT(NAND) */
}

int main(void)
{
    printf("a b | sum carry\n");
    for (int a = 0; a <= 1; a++)
        for (int b = 0; b <= 1; b++) {
            int s, c;
            half_adder(a, b, &s, &c);
            printf("%d %d |  %d    %d\n", a, b, s, c);
        }
    return 0;
}