Digital Logic: Gates, Adders, Flip-Flops and State Machines

Why digital logic matters

Every processor is built from a few kinds of tiny switching circuits called logic gates. Gates combine into adders, multiplexers and registers; those combine into an ALU and a datapath; and those make up a CPU. Digital logic is the bottom layer of computer architecture, the point where bits become physical voltages.

You will not design chips as a software engineer, but this layer is examined heavily in placement written tests (simplify this expression, how many NAND gates, what does this flip-flop output) and in interviews for embedded, hardware-adjacent and core-company roles. It also explains things you use daily: why bitwise tricks work, why addition of wide numbers takes time, and what a "register" physically is. Interviewers typically probe:

• truth tables and gate symbols, NAND/NOR as universal gates,
• Boolean simplification, De Morgan's laws and K-maps,
• half adders, full adders, ripple-carry versus carry-lookahead,
• multiplexers, decoders and encoders,
• the difference between a latch and a flip-flop, and SR/D/JK/T behavior,
• counters, shift registers and simple state machines.

Signals and logic levels

A digital circuit represents each bit as a voltage: a "high" voltage near the supply means 1 (true), a "low" voltage near ground means 0 (false). Anything in between is avoided. Treating voltages as only two values makes circuits tolerant of noise, which is why computers are digital.

Circuits come in two families:

• Combinational circuits: the output depends only on the current inputs. An adder is combinational: same inputs, same output, always.
• Sequential circuits: the output depends on the current inputs and stored past state. A counter is sequential: pressing "count" gives a different result each time because it remembers where it was.

Logic gates and truth tables

A truth table lists every input combination and the resulting output. With n inputs there are 2^n rows.

And the single-input NOT gate (inverter): output is the opposite of the input. We write NOT A as A' (also seen as Ā or ¬A).

In words:

• AND is 1 only when all inputs are 1.
• OR is 1 when at least one input is 1.
• XOR (exclusive OR) is 1 when the inputs differ; for many inputs, when an odd number of them are 1. That makes it a parity detector and a one-bit adder without carry.
• NAND and NOR are AND and OR followed by NOT.
• XNOR is 1 when the inputs are equal, so it is a one-bit equality checker.

In code these appear as bitwise operators: &, |, ^ and ~ in C, Java and Python. x ^ x == 0 and x ^ 0 == x are the XOR properties behind the classic "find the number that appears once" interview problem.

Boolean algebra

Boolean algebra is algebra on values 0 and 1 with AND (written as multiplication), OR (written as +) and NOT. Its laws let you simplify expressions, and a simpler expression means fewer gates, less area, less power and often less delay.

Note the second distributive law, A + B·C = (A + B)·(A + C), which has no equivalent in ordinary arithmetic. Every law has a dual: swap AND with OR and 0 with 1, and you get another valid law.

De Morgan's laws

De Morgan's laws say how to push a NOT through an AND or OR: break the bar, change the operator.

• (A·B)' = A' + B': "not (both)" equals "at least one is not".
• (A + B)' = A'·B': "not (either)" equals "neither".

Programmers use this all the time: !(x > 0 && y > 0) is the same as x <= 0 || y <= 0.

Worked example: algebraic simplification

Simplify F = A·B + A·B' + A'·B.

1. Group the first two terms: A·B + A·B' = A·(B + B') = A·1 = A.
2. So F = A + A'·B.
3. By the simplification law, A + A'·B = A + B.

F = A + B: three AND terms and an OR reduce to a single OR gate. Check with the truth table: F is 0 only when A = B = 0, which is exactly OR.

Canonical forms: minterms and maxterms

Any Boolean function can be written directly from its truth table:

• Sum of products (SOP): OR together one AND term per row where the output is 1. Each such AND term containing every variable is a minterm, numbered by its row. We write F = Σm(1, 3) for "1 in rows 1 and 3".
• Product of sums (POS): AND together one OR term per row where the output is 0 (a maxterm). Written F = ΠM(0, 2).

These canonical forms are correct but rarely minimal, which is what Karnaugh maps fix.

Karnaugh maps (K-maps)

A Karnaugh map is a grid version of the truth table in which neighboring cells differ in exactly one variable. Because of that, two adjacent 1s can be merged into one term with that variable removed (using X·Y + X·Y' = X). Grouping 1s visually finds a minimal SOP expression.

The rows and columns are labeled in Gray code order (00, 01, 11, 10), where consecutive labels differ by one bit. The map also wraps around: the left edge is adjacent to the right edge, and the top to the bottom.

Rules for grouping:

1. Groups must be rectangles of 1, 2, 4, 8 ... cells (powers of 2).
2. Make each group as large as possible.
3. Use as few groups as possible, covering every 1 at least once (overlaps are allowed).
4. Groups may wrap around edges and corners.
5. "Don't care" cells (written X), for input combinations that never occur, may be included if they help make a group bigger.

Each group becomes one product term containing only the variables that stay constant across the group. A group of 2^k cells eliminates k variables.

Worked example 1: three variables

Simplify F(A, B, C) = Σm(0, 2, 4, 5, 6).

Place minterms: row is A, columns are BC in Gray order. Minterm number = 4A + 2B + C.

            BC
         00   01   11   10
       +----+----+----+----+
  A=0  |  1 |  0 |  0 |  1 |    m0, m1, m3, m2
       +----+----+----+----+
  A=1  |  1 |  1 |  0 |  1 |    m4, m5, m7, m6
       +----+----+----+----+

Groups:

1. Group of 4: columns BC = 00 and BC = 10 in both rows (m0, m2, m4, m6). These columns are adjacent because the map wraps. In all four cells C = 0; A and B both vary. Term: C'.
2. Group of 2: m4 and m5 (row A = 1, columns 00 and 01). Here A = 1 and B = 0; C varies. Term: A·B'.

Every 1 is covered, so:

F = C' + A·B'

Check one row not in the list, m7 (A = 1, B = 1, C = 1): C' = 0, A·B' = 0, F = 0. Correct.

Worked example 2: four variables

Simplify F(A, B, C, D) = Σm(0, 1, 2, 5, 8, 9, 10).

Rows are AB and columns are CD, both in Gray order. Minterm number = 8A + 4B + 2C + D.

               CD
            00   01   11   10
          +----+----+----+----+
  AB=00   |  1 |  1 |  0 |  1 |   m0  m1  m3  m2
          +----+----+----+----+
  AB=01   |  0 |  1 |  0 |  0 |   m4  m5  m7  m6
          +----+----+----+----+
  AB=11   |  0 |  0 |  0 |  0 |   m12 m13 m15 m14
          +----+----+----+----+
  AB=10   |  1 |  1 |  0 |  1 |   m8  m9  m11 m10
          +----+----+----+----+

Groups:

1. Four corners (m0, m2, m8, m10): the corners are mutually adjacent because the map wraps both ways. Constant: B = 0 and D = 0. Term: B'·D'.
2. Square m0, m1, m8, m9 (rows 00 and 10 wrap, columns 00 and 01). Constant: B = 0 and C = 0. Term: B'·C'.
3. Pair m1 and m5 (column CD = 01, rows 00 and 01). Constant: A = 0, C = 0, D = 1. Term: A'·C'·D.

F = B'·D' + B'·C' + A'·C'·D

Could m5 join a larger group? Its neighbors are m1 (1), m4 (0), m7 (0) and m13 (0), so the pair with m1 is the biggest possible. The result needs 3 AND gates and one OR gate, down from 7 four-input minterms.

You can confirm a K-map result by brute force:

def f(a, b, c, d):
    return (not b and not d) or (not b and not c) or (not a and not c and d)

ones = [i for i in range(16) if f(*(int(x) for x in format(i, '04b')))]
print(ones)  # [0, 1, 2, 5, 8, 9, 10]

K-maps are practical up to about 5 or 6 variables. Beyond that, tools use algorithmic methods such as Quine-McCluskey or heuristic minimizers (Espresso is a well-known one).

Universal gates

A gate is universal if any Boolean function can be built using only that gate type. NAND and NOR are both universal. This matters because in CMOS technology NAND and NOR are cheap and fast, so real designs lean on them.

Building the basic gates from NAND:

NOT A    = A NAND A
A AND B  = (A NAND B) NAND (A NAND B)      -> 2 NAND gates
A OR B   = (A NAND A) NAND (B NAND B)      -> 3 NAND gates

Why OR works: by De Morgan, (A'·B')' = A + B.

From NOR, symmetrically:

NOT A    = A NOR A
A OR B   = (A NOR B) NOR (A NOR B)         -> 2 NOR gates
A AND B  = (A NOR A) NOR (B NOR B)         -> 3 NOR gates

A useful fact: an XOR gate needs 4 NAND gates:

N1 = A NAND B
XOR = (A NAND N1) NAND (B NAND N1)

A two-level AND-OR (SOP) circuit converts directly to a two-level NAND-NAND circuit: replace every gate with NAND. That is why SOP from a K-map maps neatly to NAND gates.

Combinational circuits

Half adder

A half adder adds two bits A and B and produces a sum S and a carry C.

From the table: S = A ⊕ B and C = A·B. One XOR gate and one AND gate. It is "half" because it cannot accept a carry coming in from a lower bit.

Full adder

A full adder adds three bits: A, B and a carry-in Cin.

Sum  = A ⊕ B ⊕ Cin
Cout = A·B + Cin·(A ⊕ B)      (equivalently A·B + B·Cin + A·Cin)

The sum is 1 when an odd number of inputs are 1; the carry is 1 when at least two are 1 (the majority function). A full adder can be built from two half adders plus an OR gate:

 A --+                  
     +-[HA1]-- s1 --+         
 B --+      |       +-[HA2]-- s2 ------------> Sum
            c1      |     |
 Cin ---------------+     c2
            |             |
            +----[ OR ]---+--> Cout

Ripple-carry adder

To add two n-bit numbers, chain n full adders: each stage's carry-out feeds the next stage's carry-in.

  A3 B3       A2 B2       A1 B1       A0 B0
   | |         | |         | |         | |
 +-----+ C3  +-----+ C2  +-----+ C1  +-----+
 | FA3 |<----| FA2 |<----| FA1 |<----| FA0 |<-- C0
 +-----+     +-----+     +-----+     +-----+
  |   |        |           |           |
 C4   S3       S2          S1          S0

Worked trace: 1011 (11) + 0110 (6), C0 = 0.

Result: C4 S3 S2 S1 S0 = 1 0001 = 17. Correct, since 11 + 6 = 17.

The problem is delay. Bit 3 cannot produce its final sum until the carry has rippled through bits 0, 1 and 2. If the carry path through one full adder takes 2 gate delays (an AND then an OR), an n-bit ripple-carry adder needs about 2n gate delays for the final carry. A 64-bit adder would need about 128 gate delays, far too slow to finish in one short clock cycle.

Carry-lookahead adder

A carry-lookahead adder (CLA) computes all carries in parallel instead of waiting. For each bit position i define:

• Generate Gi = Ai·Bi: this bit produces a carry by itself (both inputs are 1).
• Propagate Pi = Ai ⊕ Bi: this bit passes an incoming carry through (exactly one input is 1).

Then C(i+1) = Gi + Pi·Ci. Expanding this recurrence so that every carry depends only on the G's, P's and C0:

C1 = G0 + P0·C0
C2 = G1 + P1·G0 + P1·P0·C0
C3 = G2 + P2·G1 + P2·P1·G0 + P2·P1·P0·C0
C4 = G3 + P3·G2 + P3·P2·G1 + P3·P2·P1·G0 + P3·P2·P1·P0·C0

Read C2 aloud: "there is a carry into bit 2 if bit 1 generates one, or bit 1 propagates one generated by bit 0, or bits 1 and 0 both propagate the original carry-in."

Delay: 1 gate delay to form all G and P, 2 more for the two-level AND-OR carry expressions, and 1 more for the final XOR (Si = Pi ⊕ Ci), about 4 gate delays regardless of width. The cost is gates with many inputs: C4 already has a 5-input AND and a 5-input OR, and the size explodes for wide adders. Real designs therefore use hierarchical lookahead: 4-bit CLA blocks that each produce a block-level generate and propagate, combined by a second level of lookahead logic. Delay then grows with the logarithm of the width rather than linearly.

Subtractor using the adder

As covered in the data representation lesson, A − B = A + B' + 1. Put an XOR gate on each B input, controlled by a SUB signal: when SUB = 1, each XOR inverts its B bit, and SUB also feeds C0 to add the 1. One circuit does both addition and subtraction.

Multiplexer (MUX)

A multiplexer is a data selector: it has 2^n data inputs, n select lines and one output. The select lines choose which input is passed to the output. Think of it as a switch controlled by a number.

A 4-to-1 MUX with inputs I0 to I3 and selects S1 S0:

Y = S1'·S0'·I0 + S1'·S0·I1 + S1·S0'·I2 + S1·S0·I3

Multiplexers are everywhere in a datapath: choosing whether the ALU's second operand is a register or an immediate value, or whether the PC gets PC + 4 or a branch target.

Implementing a function with a MUX. Any function of n + 1 variables fits on a 2^n-to-1 MUX. Take F(A, B, C) = Σm(0, 2, 4, 5, 6) from the K-map example on a 4-to-1 MUX with A and B as selects:

Demultiplexer

A demultiplexer is the reverse: one input routed to one of 2^n outputs chosen by the select lines.

Decoder

An n-to-2^n decoder has n inputs and 2^n outputs; exactly one output is 1, the one whose number matches the input. A 3-to-8 decoder with input 101 raises output 5 only. Each output is one minterm, so a decoder plus OR gates can implement any function (OR the outputs for the function's minterms).

The most important use is address decoding: the high bits of a memory address go into a decoder that enables exactly one memory chip or one row of a memory array.

Encoder and priority encoder

An encoder does the opposite: 2^n inputs, n outputs giving the number of the input that is 1. An 8-to-3 encoder with only input 6 active outputs 110.

A plain encoder misbehaves if two inputs are 1 at once. A priority encoder outputs the number of the highest-priority active input and also a "valid" signal saying whether any input is active. Interrupt controllers use priority encoders to pick which pending interrupt to service first.

Comparator

A magnitude comparator compares two numbers A and B and outputs A > B, A = B and A < B.

For one bit:

A > B :  A·B'
A < B :  A'·B
A = B :  (A ⊕ B)'   (XNOR)

For multi-bit numbers, compare from the most significant bit down. Let xi = (Ai ⊕ Bi)' mean "bit i is equal". For 4 bits:

A = B :  x3·x2·x1·x0
A > B :  A3·B3' + x3·A2·B2' + x3·x2·A1·B1' + x3·x2·x1·A0·B0'

A > B if the top bit decides it, or the top bits are equal and the next bit decides it, and so on. In practice, processors often compare by subtracting and checking the flags.

ALU design idea

The arithmetic logic unit (ALU) combines these pieces. A simple 1-bit ALU slice computes several operations in parallel and uses a multiplexer to pick one:

          A    B
          |    |
          |   [XOR with Binvert]   (for subtraction)
          |    |
    +-----+----+----------------+
    |     |    |                |
  [AND] [OR] [Full adder]<--Cin |
    |     |    |   |            |
    +--+--+----+   +--> Cout    |
       |                        |
   [ MUX ]<--- Operation select (2 bits)
       |
     Result

Chain 32 or 64 slices (with a faster carry scheme than ripple) to get a full-width ALU. Extra logic produces status flags:

• Z (zero): all result bits are 0 (a NOR of all result bits).
• N (negative): the result's MSB.
• C (carry): the carry out of the top bit.
• V (overflow): carry into the MSB XOR carry out of it.

The control unit drives the select and Binvert lines based on the instruction being executed. Comparison instructions are typically a subtraction whose result is discarded but whose flags are kept; "set if less than" uses the sign of the subtraction, corrected by the overflow flag.

Sequential circuits

Combinational circuits forget everything. To store a bit, you need feedback: an output fed back into an input so that the circuit holds its value.

SR latch

The simplest memory element is the SR latch (Set-Reset), made from two cross-coupled NOR gates.

 R -------->+-------+
            |  NOR  |----+-----> Q
      +---->+-------+    |
      |                  |
      |   +--------------+
      |   |
      |   +-->+-------+
      |       |  NOR  |----+---> Q'
 S ---|------>+-------+    |
      |                    |
      +--------------------+
  (each gate's output feeds the other gate's input)

A latch is level-sensitive: when enabled, its output follows its inputs continuously. A gated latch adds an enable input so it responds only while enable is 1.

D latch

The D latch (data latch) removes the invalid state by deriving S and R from one input: S = D, R = D'. While enable is 1, Q follows D (the latch is "transparent"); when enable goes to 0, Q holds the last value.

Flip-flops and clocking

A flip-flop is edge-triggered: it samples its input only at the instant the clock changes, usually the rising edge (0 to 1), and holds that value for the whole cycle no matter how the input changes afterwards. A common construction is the master-slave design: two latches in series with opposite enables, so data passes the first latch while the clock is low and the second only when it goes high.

Why does edge triggering matter? In a processor, a register's output feeds logic whose result goes back into the same register (for example PC = PC + 4). With a transparent latch, the new value would race around the loop many times within one clock pulse. A flip-flop takes exactly one new value per clock edge, which makes the whole system advance in clean steps.

Clock    __|‾‾|__|‾‾|__|‾‾|__
            ^     ^     ^        rising edges: D is sampled here
D        ‾‾‾‾‾|______|‾‾‾‾‾‾‾‾
Q (D FF) ‾‾‾‾‾‾‾‾|_____|‾‾‾‾‾   changes only at edges

Two timing rules govern a flip-flop:

• Setup time: the input must be stable for a short time before the clock edge.
• Hold time: the input must stay stable for a short time after the edge.

The minimum clock period of a circuit is the longest path through combinational logic between flip-flops, plus the flip-flop's own clock-to-output delay and setup time. This is exactly why a pipeline stage's delay sets the clock rate, as you will see in the pipelining lesson.

The four flip-flop types

D flip-flop: Q takes the value of D at the clock edge. Q(next) = D. The workhorse of registers.

SR flip-flop: clocked version of the SR latch. S = R = 1 is still not allowed. Q(next) = S + R'·Q (with S·R = 0).

JK flip-flop: like SR, but J = K = 1 toggles the output instead of being invalid. Q(next) = J·Q' + K'·Q.

T flip-flop: "toggle". If T = 1, Q flips at each clock edge; if T = 0, it holds. Q(next) = T ⊕ Q. Natural building block for counters.

Designers also use excitation tables, which answer the reverse question: "to go from Q to Q(next), what inputs do I need?" For JK:

X means "don't care". For example, to go from 0 to 1 you can either set (J=1, K=0) or toggle (J=1, K=1), so K does not matter.

Registers

A register is a group of D flip-flops sharing one clock, storing a multi-bit word. A 64-bit register is 64 D flip-flops. Usually a load enable input decides whether the register takes a new value at the edge (enable = 1) or keeps its value (enable = 0), implemented with a 2-to-1 MUX in front of each D input.

A register file is an array of registers with read ports (a MUX selects which register to output, using the register number from the instruction) and a write port (a decoder selects which register to write).

Shift registers

A shift register is a chain of flip-flops where each one's output feeds the next one's input, so at each clock edge the stored bits move one position.

 Serial in --> [D Q] --> [D Q] --> [D Q] --> [D Q] --> Serial out
                 |         |         |         |
                Q3        Q2        Q1        Q0   (parallel outputs)

They are classified by how data enters and leaves:

Shifting left by one multiplies an unsigned number by 2; shifting right divides by 2. An arithmetic right shift copies the sign bit to preserve sign for two's complement numbers, which is the difference between >> and >>> in Java.

Counters

A counter is a register that steps through a sequence of states, usually binary numbers, on each clock edge.

Asynchronous (ripple) counter: each T flip-flop (with T = 1) is clocked by the output of the previous one. Bit 0 toggles every clock; bit 1 toggles every time bit 0 falls from 1 to 0; and so on. It is simple, but the outputs settle one after another (the delay ripples), so for a moment the count passes through wrong values. Fine for dividing a frequency, unsuitable for driving logic that reads intermediate values.

Synchronous counter: all flip-flops share the same clock, and logic decides which ones toggle. For a 3-bit up counter using T flip-flops:

T0 = 1            (bit 0 toggles every clock)
T1 = Q0           (bit 1 toggles when bit 0 is 1)
T2 = Q0·Q1        (bit 2 toggles when bits 0 and 1 are both 1)

A bit toggles exactly when all lower bits are 1, which is what happens when you add 1 in binary.

An n-bit binary counter has 2^n states (it is a mod-2^n counter). A mod-N counter for other N resets to 0 after reaching N − 1; for a mod-6 counter, detect state 101 and force the next state to 000 (or, in a synchronous design, add logic so 101 goes to 000 directly).

Other common counters: the ring counter (a shift register whose output feeds back to its input, circulating a single 1; n flip-flops give n states) and the Johnson counter (feeds back the inverted output; n flip-flops give 2n states).

The program counter in a CPU is essentially a register with an adder (to add 4) and a MUX (to load a branch target), rather than a pure counter.

Finite state machines

A finite state machine (FSM) is a sequential circuit described by a finite set of states, transitions between states triggered by inputs, and outputs. It is implemented as a state register (flip-flops holding the current state) plus combinational logic computing the next state and outputs.

           +---------------------+
inputs --->| next-state logic    |----+
     +---->| (combinational)     |    |
     |     +---------------------+    v
     |                          +-----------+
     +--------------------------| state reg |<-- clock
     |                          +-----------+
     |     +---------------------+
     +---->| output logic        |---> outputs
           +---------------------+

Two styles:

• Moore machine: outputs depend only on the current state. Outputs are stable for a whole cycle but react one cycle later.
• Mealy machine: outputs depend on the current state and the current inputs. Often needs fewer states and reacts in the same cycle, but outputs can glitch when inputs change.

Worked example: detect the sequence 101

Design a Moore machine whose output is 1 when the last three input bits were 1, 0, 1, with overlapping allowed (so 10101 contains two matches).

States record how much of the pattern has been seen:

• S0: nothing useful seen.
• S1: seen 1.
• S2: seen 10.
• S3: seen 101 (output 1).

The overlap is handled by S3: after 101, the final 1 may start a new match, so input 0 leads to S2 ("seen 10") and input 1 to S1.

Trace for input 1 0 1 0 1 1 0 1:

Three matches, at positions 3, 5 and 8. Four states need 2 flip-flops (ceil(log2 4) = 2).

The same machine in Python, which you can run to check the trace:

NEXT = {('S0', 0): 'S0', ('S0', 1): 'S1',
        ('S1', 0): 'S2', ('S1', 1): 'S1',
        ('S2', 0): 'S0', ('S2', 1): 'S3',
        ('S3', 0): 'S2', ('S3', 1): 'S1'}

state, outputs = 'S0', []
for bit in [1, 0, 1, 0, 1, 1, 0, 1]:
    state = NEXT[(state, bit)]
    outputs.append(1 if state == 'S3' else 0)
print(outputs)  # [0, 0, 1, 0, 1, 0, 0, 1]

FSMs appear throughout hardware: the control unit of a multi-cycle CPU is an FSM, as are bus protocols, cache coherence controllers and traffic-light controllers. In software, the same idea drives parsers, network protocol handlers (TCP's connection states) and UI workflows.

Interview questions

Q1. Why are NAND and NOR called universal gates?

Each can implement NOT, AND and OR on its own: NOT A is A NAND A, AND is a NAND followed by a NAND-inverter, and OR is NAND of the two inverted inputs (De Morgan). Since AND, OR and NOT can express any truth table in sum-of-products form, NAND alone can build any circuit. NOR works the same way by duality.

Q2. State De Morgan's laws and give a use.

(A·B)' = A' + B' and (A + B)' = A'·B'. They convert between AND-OR and NAND-NAND forms in hardware, and in code they let you rewrite !(a && b) as !a || !b. They are also how you prove that NAND is universal.

Q3. How does a K-map simplify a function, and why use Gray code?

A K-map arranges the truth table so that adjacent cells differ in exactly one variable; groups of 1, 2, 4 or 8 adjacent 1s then merge into one term with the changing variables removed. Gray code ordering (00, 01, 11, 10) guarantees the one-variable difference between neighbors, including across the wrapping edges. Larger groups give fewer literals, and fewer groups give fewer terms.

Q4. What is the difference between a half adder and a full adder?

A half adder adds two bits, giving sum = A XOR B and carry = A AND B. A full adder also takes a carry-in, giving sum = A XOR B XOR Cin and carry = majority of the three inputs. Full adders can be chained for multi-bit addition; half adders cannot accept the incoming carry.

Q5. Why is a ripple-carry adder slow and how does carry-lookahead help?

Each stage must wait for the previous stage's carry, so delay grows linearly with width, roughly 2n gate delays. Carry-lookahead computes generate (A·B) and propagate (A XOR B) for every bit and then forms all carries in parallel with two-level logic, giving roughly constant delay for a small block. For wide adders, lookahead is applied hierarchically, giving delay that grows with log n.

Q6. What is a multiplexer and where is it used in a CPU?

A multiplexer selects one of 2^n inputs to pass to its output based on n select bits. In a CPU datapath, MUXes choose the ALU's second operand (register or immediate), the value written back (ALU result or loaded data), and the next PC (PC + 4 or branch target). A 2^n-to-1 MUX can also implement any function of n + 1 variables.

Q7. What is the difference between a decoder and an encoder?

A decoder takes an n-bit code and activates exactly one of 2^n outputs, used for address decoding and instruction decoding. An encoder does the reverse, producing the code of the active input among 2^n inputs. A priority encoder handles several active inputs by reporting the highest-priority one, as interrupt controllers do.

Q8. What is the difference between a latch and a flip-flop?

A latch is level-sensitive: while its enable is active, the output follows the input. A flip-flop is edge-triggered: it samples the input only at a clock edge and holds it for the rest of the cycle. Synchronous designs use flip-flops so that each register takes exactly one new value per cycle.

Q9. Explain the JK flip-flop and the race-around condition.

A JK flip-flop holds when J = K = 0, resets when J = 0 and K = 1, sets when J = 1 and K = 0, and toggles when J = K = 1, removing the invalid state of SR. If it is level-triggered and the clock pulse is longer than the propagation delay, J = K = 1 makes it toggle repeatedly within one pulse, the race-around condition. Master-slave or edge-triggered designs fix this.

Q10. What are setup and hold time?

Setup time is how long a flip-flop's input must be stable before the clock edge; hold time is how long it must stay stable after. Violating them can cause metastability, where the output hovers between 0 and 1 for an unpredictable time. The clock period must cover the longest logic path plus clock-to-output delay plus setup time.

Q11. How does a synchronous counter differ from a ripple counter?

In a ripple counter each flip-flop is clocked by the previous one's output, so the bits change one after another and the delays accumulate. In a synchronous counter all flip-flops share one clock and toggle logic (for T flip-flops, Ti = AND of all lower bits) decides which ones change, so all bits update together. Synchronous counters are faster and have no transient wrong values.

Q12. How many flip-flops does a mod-N counter need?

At least ceil(log2 N). A mod-10 (decade) counter needs 4 flip-flops, since 3 give only 8 states. A ring counter needs N flip-flops for N states, and a Johnson counter needs N/2.

Q13. What is the difference between Moore and Mealy machines?

In a Moore machine outputs depend only on the current state, so they are stable but react one clock later. In a Mealy machine outputs depend on the state and current inputs, which usually needs fewer states and reacts immediately but can produce glitches. Both are a state register plus combinational next-state and output logic.

Q14. How would you build a register from flip-flops?

Use one D flip-flop per bit, all driven by the same clock. Add a 2-to-1 MUX in front of each D input that selects either the new data (when load enable is 1) or the flip-flop's own output (to hold). Shift registers connect each flip-flop's output to the next one's input.

Key takeaways

• Combinational circuits depend only on current inputs; sequential circuits also depend on stored state held in flip-flops.
• Boolean laws and De Morgan's rules simplify logic; K-maps with Gray-coded, wrap-around axes find minimal SOP forms by grouping 1s in powers of 2.
• NAND and NOR are universal; an SOP circuit maps directly onto NAND-NAND logic.
• Full adder: sum = A ⊕ B ⊕ Cin, carry = majority. Ripple-carry delay grows linearly; carry-lookahead uses generate and propagate to compute carries in parallel.
• Multiplexers select, decoders activate one of many outputs, encoders compress, and comparators order numbers; the ALU combines them with flags Z, N, C and V.
• Latches are level-sensitive; flip-flops are edge-triggered. D, SR, JK and T differ in how inputs map to the next state.
• Registers, shift registers and counters are built from flip-flops; synchronous designs share one clock and the slowest path sets the clock period.
• An FSM is a state register plus next-state and output logic; Moore outputs depend on state only, Mealy outputs on state and input.

Next lesson

Continue with Instruction set architecture.