3. Digital Logic, Data Representation, and Arithmetic

Introduction and Context

Computer systems ultimately process physical signals by interpreting them as discrete logical values. At the architectural level, an instruction, address, character, image, and numerical result is represented by patterns of bits. The design of a processor therefore depends not only on algorithms and instruction sets, but also on how logic transforms bits, how data formats assign meaning to bit patterns, and how arithmetic circuits manage range, precision, timing, and error.

Digital logic provides the elementary mechanisms of computation. Combinational circuits produce outputs from current inputs, whereas sequential circuits retain state and therefore support memory, control, and sequencing. Clocking coordinates state transitions, and finite-state machines provide a systematic model for controllers. Above this hardware foundation, data representation determines whether a bit pattern denotes an unsigned integer, a signed value, a floating-point number, an instruction, or a non-numeric object. Arithmetic units then implement operations whose behavior is constrained by word length and representation.

These topics are foundational because design decisions made at this level propagate upward. Overflow may corrupt an operating-system address calculation; an inappropriate floating-point format may destabilize a scientific simulation; an unsafe conversion may create a security vulnerability; and an inefficient arithmetic unit may limit processor frequency or energy efficiency.

Learning Objectives

After studying this chapter, the reader should be able to:

1. distinguish combinational and sequential logic and explain their use in processor design;

2. analyze clocked storage elements, setup and hold requirements, and timing hazards;

3. model control behavior with finite-state machines;

4. convert among common integer, fixed-point, and floating-point representations;

5. explain IEEE 754 formats, rounding, exceptional values, and numerical error;

6. describe the operation and design trade-offs of arithmetic units;

7. select data formats using range, precision, performance, energy, and reliability criteria;

8. identify common implementation errors and evaluate their professional consequences.

From Boolean Algebra to Datapaths

A Boolean variable has two logical states, conventionally 0 and 1. Basic operations are AND, OR, and NOT. NAND and NOR are functionally complete: any Boolean function can be constructed using only gates of either type. Boolean algebra permits equivalent expressions to be simplified, reducing gate count, propagation delay, and power consumption. For example, the expression AB + AB' simplifies to A by the distributive and complement laws.

A combinational circuit is memoryless: its output is a function of the current input vector. Adders, multiplexers, decoders, encoders, comparators, and arithmetic-logic units contain combinational components. A multiplexer selects one of several inputs according to control bits. A decoder activates one output corresponding to a binary code. These structures are extensively used in datapaths to select operands, generate control signals, and route results.

A half adder adds two one-bit operands. Its sum is A XOR B and its carry is AB. A full adder additionally accepts an incoming carry. Its sum is A XOR B XOR Cin, while the carry-out is AB + ACin + BCin. Connecting full adders produces a ripple-carry adder. This design is compact, but each carry may have to pass through the preceding stages, so delay increases approximately with word length. Carry-lookahead and prefix adders compute carry information in parallel, reducing delay at the cost of additional hardware and wiring.

The same adder can support subtraction by complementing the second operand and setting the initial carry-in to one. Thus A - B is implemented as A + (~B) + 1 in two's-complement arithmetic. A typical arithmetic-logic unit combines addition, subtraction, logical operations, shifts, comparisons, and flags such as zero, negative, carry, and overflow.

State, Storage, and Clocking

Sequential circuits depend on both current inputs and previous state. A latch is level-sensitive: it can respond throughout an enabled clock level. A flip-flop is generally edge-triggered and samples input at a clock transition. Registers are arrays of flip-flops used to store operands, addresses, instructions, and intermediate results. Counters, pipelines, register files, and controller state machines all rely on sequential logic.

The clock establishes a temporal reference for state changes. For reliable operation, input data must remain stable for a setup interval before the active edge and a hold interval after it. If either condition is violated, a flip-flop may enter metastability, an analog condition in which the output takes an unpredictable time to resolve to a logical value. Synchronizers, usually chains of flip-flops, reduce the probability that metastability propagates when signals cross clock domains. They do not make metastability impossible.

A simplified synchronous timing condition is:

Tclk >= tCQ + tcomb + tsetup + tskew,

where tCQ is clock-to-output delay, tcomb is combinational delay, tsetup is setup time, and tskew represents clock-arrival differences. The maximum clock frequency is consequently limited by the slowest register-to-register path. The minimum delay path also matters because it must satisfy hold-time requirements.

Clock-domain crossing is a frequent source of design failure. A single-bit control signal may be synchronized through a two-flop synchronizer, while multi-bit data requires protocols such as handshaking, asynchronous FIFOs, or Gray-coded pointers. Simply synchronizing each bit of a binary bus independently can produce a combination that never existed at the source.

Hazards are unwanted transient changes caused by unequal path delays. A static hazard may be reduced by adding a redundant consensus term, but synchronous sampling and careful timing constraints are usually the broader engineering response. Simulation alone is insufficient: timing analysis, formal checks, and hardware measurements may be necessary.

Finite-State Machines as Models of Control

A finite-state machine (FSM) represents a system with a finite set of states, inputs, outputs, and transition rules. In a Moore machine, outputs depend only on the current state; in a Mealy machine, outputs depend on state and current input. Moore outputs are often easier to time, while Mealy machines can respond with fewer states but may produce combinational glitches.

An FSM is commonly designed through the following sequence: identify externally observable behavior, define states, specify transitions for each relevant input, assign binary encodings, derive next-state and output logic, and verify reachable and illegal states. In a processor controller, states may represent instruction fetch, decode, operand access, execution, memory access, and write-back. In a bus controller, states can represent idle, request, grant, transfer, and completion.

State encoding is a hardware choice. Binary encoding uses approximately log2(N) flip-flops for N states. One-hot encoding uses one flip-flop per state and often simplifies next-state logic in FPGA implementations. Gray encoding changes one bit between adjacent states and can reduce transition ambiguity, especially in asynchronous counters. Unreachable states should have defined recovery behavior rather than being ignored.

FSM specifications must address reset behavior, illegal inputs, simultaneous events, and termination conditions. A controller that works only for the normal sequence may fail under reset during a transaction, a delayed acknowledgment, or a malformed protocol message.

Representing Integers and Fixed-Point Values

An unsigned n-bit word represents values from 0 through 2^n - 1. Binary positional notation assigns weights 2^0, 2^1, and so on. In two's-complement signed representation, the most significant bit has weight -2^(n-1), while the remaining bits have positive weights. The range is -2^(n-1) through 2^(n-1)-1. Negation is obtained by inverting every bit and adding one.

Two's complement is preferred because addition and subtraction use the same circuitry for signed and unsigned operands. The bit pattern itself does not identify its interpretation; the instruction and hardware context do. Sign extension copies the sign bit when increasing width, whereas zero extension inserts zeros. Confusing these operations can change a negative value into a large positive value.

Overflow is distinct from carry. For unsigned addition, a carry out of the most significant bit indicates a result outside the representable range. For signed two's-complement addition, overflow occurs when two operands with the same sign produce a result with the opposite sign. A carry into the sign bit differing from the carry out is an equivalent test. An arithmetic unit may compute both flags because software uses them differently.

Fixed-point representation assigns a predetermined number of bits to the fractional portion. If an integer storage value X has f fractional bits, its numerical value is X/2^f. Fixed point provides predictable precision and often lower area, latency, and energy than floating point, but its range and scale must be chosen in advance. It is common in embedded control, audio, and digital signal processing.

Binary-coded decimal stores each decimal digit in four bits. It simplifies decimal rounding and financial display requirements but uses storage inefficiently and requires specialized arithmetic. Representation should therefore follow the meaning and required operations of the data rather than convenience alone.

Floating-Point Representation and IEEE 754

Floating point approximates a real number using a sign, a significand (or fraction), and an exponent. A normalized binary value has the form (-1)^s x 1.f x 2^e. This provides a broad dynamic range, but the spacing between adjacent representable numbers grows with magnitude. Floating point is therefore not uniformly precise across its range.

IEEE 754 defines formats and arithmetic behavior. Binary32 uses one sign bit, eight exponent bits, and 23 stored fraction bits, with an implicit leading one for normal numbers; its significand precision is therefore 24 binary digits. Binary64 uses one sign bit, 11 exponent bits, and 52 stored fraction bits, giving 53 bits of precision. The exponent uses a bias so that comparisons and hardware decoding are convenient.

Special encodings include positive and negative zero, positive and negative infinity, NaNs (not-a-number), and subnormal numbers. Normal numbers use a nonzero, biased exponent and an implicit leading one. Subnormals use the smallest exponent and a zero leading bit, allowing gradual underflow and reducing the abrupt gap between the smallest normal number and zero. NaNs propagate information about invalid results, although software and hardware policies may distinguish signaling and quiet NaNs.

IEEE arithmetic commonly supports rounding to nearest, ties to even, as well as directed rounding modes. Rounding to nearest, ties to even reduces systematic bias when many exact values fall halfway between representable values. Operations such as addition, multiplication, division, and square root should be correctly rounded in conforming implementations, subject to the applicable format and environment.

Floating-point equality requires care. The expression (a + b) + c can differ from a + (b + c) because rounding breaks associativity. Subtracting nearly equal values can cause cancellation and loss of significant digits. Repeated operations can accumulate error. A comparison may use an absolute tolerance for values near zero and a relative tolerance for larger values, with tolerances chosen from the algorithm's error analysis rather than copied arbitrarily.

Arithmetic Units and Their Hardware Implications

An integer datapath normally contains registers, operand multiplexers, an ALU, shifters, and status logic. Addition is relatively inexpensive, while multiplication requires more partial-product generation and reduction. Array multipliers are regular but may be slow or large. Booth recoding reduces the number of partial products for signed multiplication. Wallace-tree and Dadda-tree structures reduce partial products rapidly, often followed by a fast final adder.

Division is more complex because quotient digits depend on partial remainders. Restoring and non-restoring division use iterative subtraction and shifting, trading latency for area. Synthesis may select dedicated multipliers or DSP blocks in an FPGA, while an ASIC designer may choose among serial, iterative, and fully parallel units according to throughput and power requirements.

Floating-point hardware includes exponent comparison and alignment, significand addition or multiplication, normalization, rounding, exception detection, and packing. Addition is particularly costly because the smaller operand's significand must be shifted to align exponents. Fused multiply-add (FMA) computes ab+c with a single final rounding, usually improving both performance and numerical accuracy. Its different rounding behavior can affect reproducibility when code is moved between processors.

Precision has hardware costs. Wider registers increase storage, interconnect, multiplier area, switching energy, and often latency. Narrow formats improve throughput but can cause overflow, underflow, or unacceptable model error. Modern processors may support integer, fixed-point, binary floating point, and specialized low-precision formats such as 16-bit floating point. Low precision is attractive for machine-learning inference, but accumulation is often performed at higher precision to control error.

Numerical Error, Verification, and Responsible Use

Three concepts should be distinguished. Representation error occurs when an exact value cannot be encoded, as with most decimal fractions in binary floating point. Round-off error is introduced by finite-precision operations. Truncation error arises when a mathematical process is approximated, for example by stopping an iterative method or replacing a derivative with a finite difference. Conditioning describes how sensitive a problem is to input perturbations; stability describes how well an algorithm controls the effects of those perturbations.

Overflow and underflow can be detected, saturated, wrapped, trapped, or reported through status flags. The appropriate policy depends on the application. Modular wraparound may be correct for cryptographic arithmetic but dangerous in an array-index calculation. Saturation is often preferable in audio and control systems because it avoids sign reversal after overflow.

Verification should combine truth-table reasoning, property checking, directed tests, constrained-random tests, equivalence checking, and numerical reference models. Test cases should include zero, maximum and minimum values, sign changes, carry propagation, NaNs, infinities, subnormals, rounding boundaries, reset sequences, and illegal protocol inputs. A high-level model must not be treated as an oracle without understanding its own precision and exceptional-value behavior.

Professional practice also requires documenting format assumptions, rounding modes, overflow policy, and acceptable error. In safety-critical or regulated systems, traceability and independent review may be required. Silent numerical failure is a governance issue as well as a technical issue: a system that produces plausible but incorrect results can be more dangerous than one that stops visibly.

An Illustrative Case: A Fixed-Point Motor Controller

Background

Consider an illustrative embedded motor controller for a robotic actuator. The controller samples position and current sensors, computes a control signal every 100 microseconds, and drives a power stage. Cost and energy constraints favor a microcontroller with limited floating-point capability.

Situation and Problem

An initial implementation stores sensor values as signed 16-bit integers and multiplies them by gains represented in fixed point. During high-load operation, the control output occasionally changes sign and the motor oscillates. Laboratory tests show that ordinary operating cases pass, but the failure appears near the maximum permitted current.

Analysis

The design uses a Q format with eight fractional bits. Two signed 16-bit values are multiplied, creating a 32-bit intermediate, but the implementation truncates to 16 bits before applying the next gain. The truncation discards high-order information rather than the intended fractional bits. In addition, the final conversion wraps on overflow instead of saturating. A timing review identifies a second issue: a sensor-ready signal crosses from an independent clock domain without synchronization.

Approach and Solution

The engineering team documents the numerical range of every signal and retains a 32-bit accumulator through the multiply-and-accumulate sequence. Results are rounded, shifted by the specified fractional-bit count, and saturated to the actuator's legal range. Worst-case bounds are calculated from sensor limits and gain values. Boundary tests cover maximum positive and negative currents, zero crossings, and values exactly halfway between representable levels. The sensor-ready signal is passed through a synchronizer, and the data transfer uses a handshake so that a partially updated sample cannot be consumed.

Outcome

The corrected design eliminates sign reversal in numerical tests and prevents invalid commands from reaching the power stage. The added accumulator width increases register use slightly, but the controller remains within its timing and energy budget. The explicit range analysis also makes later gain changes safer.

Learning Points

The case illustrates that a data format is an architectural decision, not merely a storage detail. Correct scaling, intermediate precision, rounding, saturation, clock-domain discipline, and boundary verification must be designed together. A mathematically correct control law can fail when its hardware representation is poorly specified.

Common Mistakes, Trade-offs, and Emerging Directions

Frequent mistakes include treating carry as signed overflow, sign-extending an unsigned value, assuming floating-point addition is associative, comparing floating-point values for exact equality, synchronizing bus bits independently, leaving FSM recovery unspecified, and truncating an intermediate result without range analysis. Another error is selecting a format solely from nominal values while ignoring worst-case transients and accumulated error.

Designers must balance area, delay, throughput, energy, precision, determinism, and verification effort. Wider arithmetic may improve accuracy but increase power and routing congestion. Approximate or low-precision arithmetic may be appropriate for tolerant workloads but unacceptable for finance, safety, or scientific reproducibility. The correct choice is application-dependent and should be justified quantitatively.

Current processor design increasingly combines heterogeneous arithmetic units. CPUs, GPUs, DSPs, and neural-processing accelerators may support mixed precision, vector operations, tensor instructions, and configurable rounding. Quantized machine-learning models use integer or low-precision values with calibration and scaling procedures. FMA units, reproducible-reduction techniques, interval or posit-like experimental formats, and hardware support for exception handling remain active areas of engineering interest. These developments do not remove the need for classical Boolean reasoning; they make representation and verification decisions more consequential.

Best practice is to begin with a range-and-error specification, choose the narrowest format that satisfies it, preserve precision in intermediate results, define exceptional behavior, analyze timing and clock crossings, and verify both ordinary and adversarial boundary cases. Hardware, compiler, firmware, and application teams should use a shared specification so that a bit pattern has one documented interpretation at every interface.

Chapter Summary

Digital systems are built from Boolean logic, but useful computation requires state, timing, representation, and arithmetic. Combinational circuits transform current inputs, while sequential circuits store state and operate under clocking constraints. Flip-flop setup and hold times, metastability, clock-domain crossing, and hazards are central reliability concerns. FSMs provide a disciplined model for controllers.

Unsigned and two's-complement formats support efficient integer computation; fixed point offers predictable scaling; and IEEE 754 floating point provides broad range through sign, exponent, and significand fields. Rounding, cancellation, overflow, underflow, subnormals, and exceptional values must be considered in numerical design. Arithmetic units such as adders, multipliers, dividers, ALUs, and floating-point pipelines embody trade-offs among area, delay, energy, and precision. Robust design combines format analysis, explicit policies, timing discipline, verification, and professional documentation.

Key Terms

Boolean algebra: Algebraic system used to express and simplify logical relationships.

Combinational circuit: Circuit whose output depends only on its current inputs.

Sequential circuit: Circuit whose output depends on current inputs and stored state.

Flip-flop: Edge-triggered storage element used in synchronous digital systems.

Metastability: Temporary indeterminate behavior caused by violation of a storage element's timing requirements.

Finite-state machine: Model consisting of states, inputs, outputs, and transition rules.

Two's complement: Signed binary representation using a negative most-significant-bit weight.

Sign extension: Increasing word width by replicating the original sign bit.

Overflow: Result outside the range representable by the selected format.

Fixed point: Representation with a predetermined position for the binary point.

Floating point: Representation using sign, significand, and exponent fields.

Subnormal: IEEE 754 value encoded without the implicit leading significand bit.

NaN: Floating-point encoding representing an invalid or undefined numerical result.

Rounding: Mapping an exact result to a representable finite-precision value.

Cancellation: Loss of significant digits when nearly equal values are subtracted.

Conditioning: Sensitivity of a mathematical problem to perturbations in its inputs.

Arithmetic-logic unit: Datapath component that performs logical and arithmetic operations.

Carry-lookahead adder: Adder that computes carry signals in parallel to reduce delay.

Clock-domain crossing: Transfer of information between independently timed clock domains.

Saturation: Limiting a result to the maximum or minimum representable value.

Review Questions

Short Answer Questions

1. What distinguishes a combinational circuit from a sequential circuit?

2. Why does a two's-complement adder require no separate signed-addition circuit?

3. Define setup time and hold time.

4. What is the purpose of a finite-state machine's reset behavior?

5. Why are most decimal fractions not represented exactly in binary floating point?

Long Answer Questions

1. Explain the operation and timing trade-offs of ripple-carry, carry-lookahead, and prefix adders.

2. Describe IEEE 754 normal, subnormal, infinite, zero, and NaN encodings.

3. Explain how clock-domain crossing can cause data corruption and compare suitable mitigation techniques.

4. Discuss overflow, round-off, truncation, and cancellation errors with relevant examples.

5. Describe the principal stages and hardware costs of a floating-point addition unit.

Analytical / Application Questions

1. A four-bit two's-complement ALU adds 0111 and 0011. Determine the bit result and explain whether signed overflow occurs.

2. A control algorithm uses Q8 fixed-point values and produces a product requiring 32 bits. Propose a safe scaling, rounding, and saturation strategy before storing a 16-bit result.

3. A designer synchronizes each bit of a rapidly changing eight-bit bus with separate flip-flops. Evaluate the design and propose a protocol that guarantees coherent data transfer.

22. Multiple Choice Questions with Answers

Question 1

Which condition indicates signed two's-complement overflow during addition?

A. A carry-out always occurs

B. Operands of opposite signs produce a zero

C. Operands with the same sign produce a result of the opposite sign

D. The least significant bit changes

Correct Answer: C. Operands with the same sign produce a result of the opposite sign

Question 2

Why is independently synchronizing every bit of a multi-bit bus unsafe?

A. Synchronizers cannot store binary values

B. Different bits may resolve from different source cycles

C. The bus becomes permanently metastable

D. It changes the bus from parallel to serial

Correct Answer: B. Different bits may resolve from different source cycles

Question 3

What is the principal advantage of a carry-lookahead adder over a ripple-carry adder?

A. It eliminates the need for full adders

B. It computes carry information with less serial dependence

C. It represents negative numbers more accurately

D. It requires no clock

Correct Answer: B. It computes carry information with less serial dependence

Question 4

In an IEEE 754 normal binary number, the significand generally includes:

A. An implicit leading one

B. Only decimal digits

C. A mandatory sign extension

D. A parity bit

Correct Answer: A. An implicit leading one

Question 5

Which operation is most likely to lose significant digits through cancellation?

A. Adding two large values with the same sign

B. Subtracting two nearly equal values

C. Multiplying by two

D. Converting an integer to binary

Correct Answer: B. Subtracting two nearly equal values

Question 6

What does saturation do when an arithmetic result exceeds the representable range?

A. Wraps the result modulo the word size

B. Sets every bit to zero

C. Limits the result to an endpoint of the range

D. Increases the clock frequency

Correct Answer: C. Limits the result to an endpoint of the range

Question 7

A Moore machine's outputs depend on:

A. Only the current state

B. Only the current input

C. The previous clock frequency

D. The current state and an asynchronous bus

Correct Answer: A. Only the current state

Question 8

Which IEEE 754 value is intended to represent an invalid numerical result such as zero divided by zero?

A. A subnormal

B. NaN

C. Positive zero

D. A normalized one

Correct Answer: B. NaN

Question 9

If an unsigned n-bit addition produces a carry out of the most significant bit, the carry generally indicates:

A. A result outside the unsigned range

B. A guaranteed signed overflow

C. A metastable flip-flop

D. A floating-point underflow

Correct Answer: A. A result outside the unsigned range

Question 10

Why can fused multiply-add improve numerical results?

A. It replaces multiplication with integer addition

B. It performs multiplication and addition with one final rounding

C. It prevents all overflow

D. It removes the need for exponent alignment

Correct Answer: B. It performs multiplication and addition with one final rounding