Digital Logic and Hardware Building Blocks

Introduction

Every processor, memory system, controller, and communication interface is constructed from circuits that represent and manipulate binary information. At the lowest practical level, these circuits are built from transistors, but computer architects normally reason about them using logic gates, Boolean algebra, and organized circuit blocks. This chapter develops the foundations needed to understand how a binary instruction is selected, how an arithmetic operation is performed, how a result is stored, and how a control unit progresses through a sequence of actions.

Digital circuits are commonly described using two logic levels: 0 and 1. These levels may correspond to voltage ranges rather than exact voltages. A logic family defines which voltage ranges are interpreted as LOW and HIGH, together with limits on noise, timing, and current. Thus, Boolean notation is an abstraction of physical electronic behavior.

Learning Objectives

By the end of this chapter, you should be able to:

• explain binary variables, truth tables, and Boolean operations;
• identify and apply the operation of basic logic gates;
• simplify Boolean expressions using algebraic laws and Karnaugh maps;
• distinguish combinational from sequential circuits;
• design adders, multiplexers, decoders, registers, counters, and clocked systems;
• explain propagation delay, setup time, hold time, and race conditions;
• describe finite-state machines and their use in processor control;
• analyze a small digital control application using appropriate building blocks.

1. Boolean Logic and Logic Gates

A Boolean variable has one of two values, conventionally 0 or 1. A Boolean function maps one or more binary inputs to a binary output. The principal operations are AND, OR, and NOT.

The corresponding two-input truth table is:

The NOT gate has the truth table 0 → 1 and 1 → 0. NAND and NOR are called universal gates because any Boolean function can be constructed using only NAND gates or only NOR gates. For example, using NAND gates:

• NOT A = A NAND A;
• A AND B = (A NAND B) NAND (A NAND B);
• A OR B = (A NAND A) NAND (B NAND B).

Boolean Laws

Important laws include:

The complement of a complement is the original variable: (A̅)̅ = A. De Morgan’s laws are particularly important when converting between gate types:

These laws assume binary Boolean variables and are applicable to ideal logical operations. They do not by themselves describe propagation delay or electrical loading.

Simplification Example

Consider:

Factoring A gives:

Therefore, a circuit that appears to require two AND gates and an OR gate can be replaced by a direct connection from A. Simplification reduces hardware area, power consumption, and often propagation delay.

A Karnaugh map provides a graphical method for simplifying functions with a small number of variables. Cells are arranged in Gray-code order, so adjacent cells differ in only one variable. Groups must contain 1, 2, 4, 8, or another power of two cells. The largest valid groups normally produce the simplest expression. Wraparound adjacency at the map edges is permitted.

2. Combinational Circuits

A combinational circuit has outputs determined only by its current inputs. It has no stored state. In an ideal model:

where X is the vector of inputs, Y is the vector of outputs, and f is a Boolean function. Real circuits also have a finite propagation delay between an input change and the corresponding output change.

Half Adder and Full Adder

A half adder adds two one-bit numbers. Its sum and carry outputs are:

A full adder adds A, B, and an incoming carry Cᵢₙ:

The expressions assume unsigned one-bit binary addition. A multi-bit ripple-carry adder connects the carry output of each stage to the carry input of the next stage. It is simple, but its worst-case delay increases with the number of bits because a carry may propagate through every stage.

Multiplexers

A multiplexer, or MUX, selects one of several data inputs and connects it to one output. A 2-to-1 multiplexer has inputs D₀ and D₁, select input S, and output Y:

When S = 0, Y = D₀; when S = 1, Y = D₁. A 2ⁿ-to-1 multiplexer requires n select lines for 2ⁿ data inputs. Multiplexers are used in processor datapaths to select an ALU operand, choose a register destination, or select the next program-counter value.

Decoders and Encoders

An n-to-2ⁿ decoder activates one output corresponding to an n-bit input code. With an enable input, all outputs may be disabled when the decoder is not required. Decoders are used for memory address selection, instruction decoding, register selection, and control-signal generation.

An encoder performs the reverse conceptual operation, converting one active input into a binary code. A priority encoder resolves the case in which multiple inputs are active by assigning priority to one of them. This is useful in interrupt systems.

Comparators

A one-bit equality detector can be written as an XNOR gate:

For two n-bit words, equality is obtained by XNORing corresponding bits and ANDing all results:

Here, n is the word width, i indexes each bit, and the product symbol represents AND across all bit positions. The expression is valid for equal-width binary words.

3. Sequential Circuits and Storage

A sequential circuit depends on present inputs and previous state. Its general model is:

The state is stored in latches or flip-flops. This distinction is fundamental: combinational logic computes, while sequential logic remembers.

Latches and Flip-Flops

A latch is level-sensitive: it can respond while an enable signal is active. A flip-flop is normally edge-triggered and captures data at a rising or falling clock edge. Common types are:

• SR latch: has set and reset controls; some input combinations may be invalid depending on implementation;
• D flip-flop: captures D at the active clock edge and is the standard single-bit storage element;
• JK flip-flop: an improved SR form that can toggle when J = K = 1;
• T flip-flop: toggles when T = 1 and holds when T = 0.

For a D flip-flop, the next state is:

This equation applies at the active clock edge, assuming setup and hold-time requirements are met.

Registers

A register is a group of flip-flops used to store a multi-bit word. An n-bit register stores n bits. Common controls include load, clear, enable, and shift. A register with parallel load captures all bits simultaneously. A shift register moves bits left or right on each clock edge and can support serial-to-parallel or parallel-to-serial conversion.

Processor registers include the program counter, instruction register, general-purpose registers, status register, and memory-address or memory-data registers. Their functions are defined by the processor’s instruction-set architecture and implemented by datapath and control logic.

Counters

A counter is a sequential circuit that advances through a defined sequence of states. A binary up-counter increments its stored value on each active clock edge. For an n-bit modulo counter, the sequence contains up to:

states, ranging from 0 to 2ⁿ − 1 before returning to 0. A decade counter has ten states, usually 0 through 9, and then returns to 0. Counters are used for timing, event counting, frequency division, address generation, and sequencing control operations.

A synchronous counter clocks all flip-flops simultaneously. A ripple, or asynchronous, counter clocks one stage from the output of another. Ripple counters use fewer control connections but can produce temporary invalid states because changes propagate from stage to stage.

4. Clocking and Timing

A clock is a periodic signal used to coordinate state changes. Its frequency f and period T are related by:

Frequency is measured in hertz and period in seconds. For example, a 100 MHz clock has a period of 10 ns because 100 MHz = 100 × 10⁶ Hz.

Important timing terms include:

• setup time: minimum interval before the active clock edge during which input data must remain stable;
• hold time: minimum interval after the edge during which data must remain stable;
• clock-to-Q delay: time from the clock edge to a flip-flop output change;
• propagation delay: time for a logic circuit’s output to respond to an input change;
• clock skew: difference in clock arrival time at different storage elements;
• jitter: short-term variation in clock edge timing.

For a simple single-cycle register-to-register path, a conservative timing condition is:

where t_cq is clock-to-Q delay, t_logic is combinational-path delay, t_setup is receiving-flip-flop setup time, and t_skew represents the relevant clock-skew margin. The formula assumes one active edge, no intentional multicycle behavior, and that other uncertainties have been included in the timing margin.

If t_cq = 1 ns, t_logic = 6 ns, t_setup = 1 ns, and the design reserves 0.5 ns for skew and uncertainty, then the minimum period is 8.5 ns. The maximum idealized frequency is approximately 117.6 MHz, calculated as 1 ÷ 8.5 ns. In practice, designers use additional safety margins and verified timing constraints.

If setup or hold requirements are violated, a flip-flop may enter metastability, an unpredictable temporary condition in which its output takes an unusually long time to resolve to 0 or 1. Synchronizer circuits, commonly using two or more flip-flops, reduce—but do not mathematically eliminate—the probability that metastability reaches synchronous logic.

5. Finite-State Machines

A finite-state machine (FSM) is a sequential model with a finite number of states, input-dependent transitions, and outputs. It is widely used in processor control units, bus controllers, communication protocols, vending machines, and embedded systems.

An FSM is specified by:

1. a set of states;
2. input signals;
3. output signals;
4. a next-state function;
5. an initial or reset state.

A Moore machine produces outputs based only on the current state. A Mealy machine produces outputs based on the current state and current inputs. Moore outputs are often easier to synchronize, while Mealy machines can respond more quickly but may be sensitive to input changes.

A practical FSM design proceeds as follows:

1. describe the required behavior in words;
2. identify states representing meaningful phases of operation;
3. draw a state-transition diagram or create a state table;
4. assign binary codes to states;
5. derive next-state and output logic;
6. implement the logic with gates, multiplexers, and flip-flops;
7. simulate and test reset, normal transitions, and illegal inputs.

Figure: Illustrative three-state controller. Transitions occur at active clock edges, subject to input conditions.

6. Building a Processor Datapath

A processor datapath combines registers, an arithmetic logic unit (ALU), multiplexers, buses, and status logic. The ALU may perform addition, subtraction, Boolean operations, shifts, and comparisons. Multiplexers select operands; registers hold intermediate values; the control unit determines which operations occur and when.

A simplified instruction cycle illustrates the relationship:

1. the program counter supplies an instruction address;
2. instruction memory returns the instruction;
3. the instruction register stores it;
4. a decoder identifies the operation and operands;
5. register-file outputs feed the ALU through multiplexers;
6. the result is written to a destination register or memory;
7. the program counter is updated for the next instruction.

The control unit can be hardwired using Boolean logic or implemented as an FSM. A hardwired controller may be fast but difficult to modify. An FSM-based controller provides an explicit sequence of states and is easier to analyze for a modest instruction set. More complex processors may use microprogrammed control, in which control words are stored in a control memory.

Applied Case: A Synchronous Conveyor Controller

Background

Consider an illustrative packaging conveyor that must load a box, run the conveyor, and stop when a sensor confirms that the box has reached the exit. The controller operates from a fixed clock.

Problem

The system must accept a start command only when idle, activate a load actuator, run the motor after loading, stop on completion, and return safely to idle on reset. Incorrect sequencing could damage equipment or cause a box to be misplaced.

Analysis

Three states are sufficient: IDLE, LOAD, and RUN. The state register consists of flip-flops. A decoder or combinational output logic generates actuator signals from the current state. Input signals include start, loaded, done, and reset. Because sensors may not change exactly at clock edges, each external sensor should be synchronized before entering the FSM. If sensors are mechanically operated, debouncing is also required.

Approach and Solution

• In IDLE, the motor and load actuator are off. A synchronized start signal causes transition to LOAD.
• In LOAD, the load actuator is active. When loaded is asserted, the controller transitions to RUN.
• In RUN, the motor is active. When done is asserted, the controller returns to IDLE.
• Reset forces IDLE, ensuring a known safe output condition.

A Moore implementation makes motor output equal to 1 only in RUN and load output equal to 1 only in LOAD. This avoids output changes caused directly by asynchronous sensor transitions. The state register is clocked synchronously, and illegal state encodings should be directed to IDLE.

Outcome and Learning Points

The design separates state storage from next-state logic and output logic. This makes simulation and verification straightforward. It also demonstrates that reliable hardware requires more than Boolean correctness: synchronization, reset behavior, timing constraints, fault recovery, and safe actuator defaults are essential.

Limitations, Reliability, and Best Practices

Digital logic diagrams often assume ideal signals, but physical circuits have finite delay, power limits, noise, temperature dependence, and manufacturing variation. Good design practice includes:

• use a single well-defined clock domain where practical;
• synchronize asynchronous inputs;
• avoid combinational feedback unless deliberately designed;
• define reset behavior for every state-holding element;
• avoid relying on propagation-delay accidents;
• use registered outputs for critical control signals;
• test boundary cases, illegal states, overflow, and simultaneous events;
• verify designs with truth tables, simulation, timing analysis, and hardware tests;
• document signal polarity, clock edge, reset type, and assumptions.

In safety-critical or industrial systems, hardware should also follow applicable organizational and sector standards. Redundant sensing, watchdog timers, fail-safe outputs, and formal review may be required. Security is relevant as well: malicious or accidental manipulation of control signals can create unsafe behavior, so access control, secure boot, fault logging, and design verification may be necessary in connected devices.

Contemporary digital systems increasingly use hardware-description languages such as Verilog or VHDL, automated synthesis, FPGA prototyping, and formal verification. These tools do not remove the need to understand logic. A poorly specified state machine or timing assumption can be synthesized accurately into incorrect hardware. Modern processors also employ pipelining, clock gating, multiple clock domains, and specialized accelerators, all of which build upon the gates, storage elements, and control structures introduced here.

Chapter Summary

Boolean algebra provides the language for describing binary hardware. AND, OR, NOT, XOR, NAND, NOR, and XNOR gates form the basic vocabulary, while Boolean laws and Karnaugh maps support simplification. Combinational circuits produce outputs from present inputs and include adders, multiplexers, decoders, encoders, and comparators.

Sequential circuits include storage and therefore depend on previous state. Latches and flip-flops form registers and counters. Clocks coordinate state changes, but setup time, hold time, propagation delay, skew, jitter, and metastability determine whether a design operates reliably. Finite-state machines organize sequential behavior into states, transitions, and outputs. In a processor, these concepts combine into a datapath and control unit that fetch, decode, and execute instructions. Professional designs must consider timing, synchronization, reset, fault recovery, verification, safety, and security rather than Boolean function alone.

Key Terms

Boolean variable: A variable restricted to the values 0 and 1.

Logic gate: A circuit that performs a Boolean operation.

Truth table: A complete listing of outputs for all input combinations.

Universal gate: A gate type, such as NAND or NOR, capable of implementing any Boolean function.

Propagation delay: Time between an input change and the resulting output change.

Combinational circuit: A circuit whose output depends only on current inputs.

Sequential circuit: A circuit whose behavior depends on current inputs and stored state.

Half adder: A circuit that adds two one-bit values.

Full adder: A circuit that adds two bits and an incoming carry.

Multiplexer: A circuit that selects one of several inputs.

Decoder: A circuit that converts a binary code into one of multiple active outputs.

Register: A group of flip-flops that stores a binary word.

Counter: A sequential circuit that advances through a state sequence.

Flip-flop: An edge-triggered one-bit storage element.

Clock: A periodic timing signal used to coordinate state changes.

Setup time: Required data-stability interval before a clock edge.

Hold time: Required data-stability interval after a clock edge.

Metastability: An uncertain temporary state caused by a timing violation.

Finite-state machine: A sequential model with finite states and defined transitions.

Datapath: Processor hardware that stores and transforms data.

Multiple Choice Questions with Answers

Question 1

Which gate produces 1 only when its two inputs are different?

A. AND

B. OR

C. XOR

D. XNOR

Correct Answer: C. XOR

Question 2

Using Boolean algebra, what is A·B + A·B̅ equal to?

A. A

B. B

C. A + B

D. 0

Correct Answer: A. A

Question 3

What is the main function of a multiplexer?

A. Store a binary word

B. Select one input for connection to an output

C. Count clock pulses

D. Invert every input

Correct Answer: B. Select one input for connection to an output

Question 4

A full adder differs from a half adder because it includes which additional input?

A. Enable

B. Clock

C. Incoming carry

D. Reset

Correct Answer: C. Incoming carry

Question 5

Which circuit type retains information about previous inputs?

A. Combinational circuit

B. Sequential circuit

C. Decoder only

D. Comparator only

Correct Answer: B. Sequential circuit

Question 6

A 100 MHz clock has an ideal period of:

A. 1 ns

B. 5 ns

C. 10 ns

D. 100 ns

Correct Answer: C. 10 ns

Question 7

Which timing requirement specifies how long data must remain stable after a clock edge?

A. Setup time

B. Hold time

C. Clock-to-Q delay

D. Propagation delay

Correct Answer: B. Hold time

Question 8

In a Moore finite-state machine, outputs depend on:

A. Inputs only

B. Current state only

C. Previous input only

D. Clock frequency only

Correct Answer: B. Current state only

Question 9

How many distinct states can an n-bit binary counter represent, assuming all bit combinations are used?

A. n

B. 2n

C. n²

D. 2ⁿ

Correct Answer: D. 2ⁿ

Question 10

Why are synchronizer flip-flops used for asynchronous inputs?

A. To increase the number of input bits

B. To reduce the chance of metastability spreading into synchronous logic

C. To perform arithmetic addition

D. To eliminate all propagation delay

Correct Answer: B. To reduce the chance of metastability spreading into synchronous logic