Arithmetic and Data-Path Circuits

Introduction

Digital systems do more than store and transmit binary values: they add, subtract, compare, shift, multiply, and route data. These operations are performed by arithmetic and data-path circuits. A processor’s arithmetic logic unit (ALU), a router’s checksum engine, and an embedded controller’s address-generation unit all depend on the principles developed in this chapter.

An arithmetic circuit operates on binary words, while a data path connects registers, multiplexers, buses, functional units, and control signals so that data can be moved and transformed. The central engineering concerns are correctness, speed, hardware cost, power consumption, and predictable handling of exceptional conditions such as carry and overflow.

Learning Objectives

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

• construct and explain half-adders, full-adders, and ripple-carry adders;
• distinguish unsigned carry from signed overflow;
• compare carry-propagation techniques;
• explain subtraction using two’s complement arithmetic;
• describe the structure and operation of an ALU;
• explain logical, arithmetic, and barrel shifters;
• identify the principal components of a basic processor data path;
• apply these ideas to practical processor, router, and embedded-system designs.

1. Binary Addition and Subtraction

1.1 The half-adder

A half-adder adds two one-bit operands, A and B. It produces a sum S and a carry C.

Here, ⊕ denotes exclusive-OR and · denotes AND. The half-adder does not accept a carry input, so it is suitable only for the least significant position when no incoming carry exists.

1.2 The full-adder

A full-adder adds three bits: A, B, and an input carry Cᵢ. It produces a sum S and an output carry Cₒ.

An equivalent majority expression is:

The full-adder can be built from two half-adders and an OR gate. The first half-adder adds A and B; the second adds the intermediate sum to Cᵢ; the two carry outputs are ORed.

1.3 Ripple-carry addition

An n-bit ripple-carry adder connects n full-adders in series. The carry produced by one stage becomes the input carry of the next stage. For operands A and B, the carry must travel from the least significant bit toward the most significant bit.

Figure: A four-bit ripple-carry adder. Each full-adder waits for the carry from the preceding stage.

If the propagation delay of one full-adder carry path is tₐ and there are n stages, the worst-case carry delay is approximately:

This relationship assumes identical stages and ignores interconnect and loading effects. It explains why ripple-carry adders become slow for wide words.

Worked example. Add 0101₂ and 0011₂:

0101
+ 0011
------
  1000

The decimal values are 5 + 3 = 8, confirming the result. The carry generated at the least significant position ripples through the next positions.

1.4 Subtraction with two’s complement

Binary subtraction can be implemented using the same adder used for addition. To calculate A − B, invert every bit of B and add one:

For an n-bit word, the result is interpreted modulo 2ⁿ. The expression is valid for fixed-width two’s complement arithmetic; any carry beyond bit n−1 is discarded for the numerical result.

Worked example. Calculate 7 − 5 using four bits:

0111       7
- 0101       5

The two’s complement of 0101 is 1011. Therefore:

0111
+ 1011
------
1 0010

Discarding the carry gives 0010₂ = 2.

A practical adder-subtractor uses XOR gates to conditionally invert B. With control M, each B input becomes B ⊕ M and the initial carry is M. When M = 0, the circuit adds A + B; when M = 1, it computes A + ¬B + 1 = A − B.

2. Carry, Borrow, and Overflow

2.1 Unsigned carry

For unsigned addition, a carry out of the most significant bit indicates that the mathematical result cannot be represented in the selected width. For n bits, unsigned values range from 0 to 2ⁿ − 1.

For example, in four bits:

1111  (15)
+ 0001  (1)
------
1 0000  (16)

The stored result is 0000 and the carry flag is 1.

2.2 Signed overflow

In two’s complement, an n-bit signed value ranges from −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1. Signed overflow occurs when the mathematical result lies outside this range. It is not equivalent to the carry flag.

For addition, overflow occurs when two operands with the same sign produce a result with the opposite sign. A gate-level expression is:

Here, Aₙ₋₁ and Bₙ₋₁ are operand sign bits and Sₙ₋₁ is the result sign bit. Another useful form is:

where Cₙ₋₁ is the carry into the sign bit and Cₙ is the carry out. This identity applies to two’s complement addition.

Example. In four-bit signed arithmetic, 0111₂ is +7. Adding another +1 gives:

0111 (+7)
+ 0001 (+1)
-----------
  1000

1000₂ represents −8, so signed overflow occurred. There is no carry out, demonstrating that carry and overflow convey different information.

For subtraction, signed overflow occurs when operands have different signs and the result sign differs from A’s sign. A corresponding expression is:

2.3 Carry-lookahead addition

A carry-lookahead adder reduces delay by computing carries in parallel. For bit i, define the propagate and generate terms:

The carry relation is:

For four bits:

The expansion uses more hardware but avoids waiting for each full-adder in sequence. Modern processors commonly use hierarchical forms such as carry-select, carry-skip, and parallel-prefix adders to balance speed, area, and power.

Carry-save addition is especially useful in multipliers. It reduces three or more operands to two without immediately propagating carries; a final adder then produces the ordinary binary result.

3. Arithmetic Logic Units

An ALU combines arithmetic and logical functions under control of operation-select signals. A typical ALU accepts operands A and B, a function code F, and sometimes a carry-in. It produces a result R and status flags.

Common operations include:

• A + B;
• A − B;
• A AND B;
• A OR B;
• A XOR B;
• NOT A;
• increment and decrement;
• comparison through subtraction.

A simple design contains parallel functional blocks followed by a multiplexer. The control field selects which block’s output reaches the result bus. More integrated designs share gates between arithmetic and logical functions to reduce area.

Typical flags are:

A zero flag can be generated using a NOR tree:

This is true only when every result bit is zero. The meaning of the carry flag during subtraction varies by processor architecture: some architectures define it as “no borrow,” while others define or expose borrow differently. Software documentation must therefore be consulted rather than assuming a universal convention.

Comparison

To compare unsigned values A and B, an ALU may compute A − B and inspect carry and zero conditions. For signed comparison, the sign and overflow flags must be combined. A common condition for A < B in signed arithmetic is:

This assumes N is the result sign flag and V is signed overflow. Equality is indicated by Z = 1.

4. Shifters and Rotators

A shifter moves bits left or right. A left logical shift inserts zeros at the right; a right logical shift inserts zeros at the left. An arithmetic right shift replicates the sign bit, preserving the sign of a two’s complement number.

For an unsigned word, shifting left by k positions is equivalent to multiplication by 2ᵏ when no significant bit is discarded:

Similarly, an unsigned right shift by k approximates integer division by 2ᵏ, with discarded low-order bits removed:

These relationships assume fixed-width representation and no overflow for left shifts. For signed values, arithmetic shifting and language-specific rules must be considered carefully.

A barrel shifter performs a shift by any distance in one combinational operation. It is commonly built from stages of 2:1 multiplexers. For an n-bit word, a logarithmic barrel shifter requires approximately log₂ n stages, assuming n is a power of two. A 32-bit design therefore commonly uses five stages controlled by shift-distance bits 1, 2, 4, 8, and 16.

A rotator feeds discarded bits back into the opposite end. Rotate operations are useful in cryptographic algorithms, hash functions, checksums, and bit-field manipulation.

5. Registers and the Basic Data Path

A data path is the portion of a digital system that stores, transfers, and transforms data. Its principal components are:

• Registers: clocked storage elements for operands, addresses, instructions, and results;
• Register file: a collection of registers with one or more read ports and write ports;
• Multiplexers: select one of several data sources;
• ALU: performs arithmetic and logical operations;
• Shifter: performs displacement and rotation;
• Buses: carry data between components;
• Status register: stores flags such as zero, carry, negative, and overflow;
• Control unit: generates timing and selection signals.

A register transfer is often described using a register-transfer notation such as:

This means that, on an active clock edge, the ALU adds R₁ and R₂ and loads the result into R₃. It does not necessarily imply that the operation completes instantaneously; the actual timing depends on the combinational delay and clock design.

A simple single-bus data path may require multiple clock cycles because only one transfer can use the bus at a time. A multiport register file can read two operands simultaneously, allowing an ALU operation and result write-back in a compact sequence.

Figure: A simplified data path showing operand read, ALU processing, and write-back.

Timing and control

The maximum clock frequency is constrained by the longest register-to-register path. A simplified timing condition is:

Here, t₍cq₎ is clock-to-output delay of the source register, tₗₒgᵢc is combinational logic delay, t₍setup₎ is destination setup time, and t₍skew₎ represents clock uncertainty or skew. All quantities have units of time. This expression is a design approximation; routing delay, jitter, and hold-time constraints must also be checked.

Pipelining inserts registers into a long data path. It can increase throughput by allowing several operations to be in progress simultaneously, but it also introduces latency, control complexity, and hazards. In a processor, forwarding paths may reduce delays caused when an instruction needs the result of a preceding instruction.

6. Applications in Computer Architecture and Networking

In processors, ALUs execute instruction operations, calculate branch targets, increment program counters, and form memory addresses. In routers and switches, arithmetic circuits support packet-length calculations, checksum updates, queue counters, address masking, and routing-table comparisons. Embedded systems use them in timers, sensor processing, motor control, and communication protocols.

Fixed-width arithmetic is particularly important in networking. A packet field may be 8, 16, or 32 bits wide, and arithmetic must wrap or saturate according to the protocol. A checksum algorithm may intentionally use end-around carry, in which a carry leaving the most significant bit is added back into the least significant position. This is different from ordinary two’s complement overflow handling.

Applied Case: An 8-bit Embedded Motor Controller

Background

Consider an illustrative embedded motor controller that receives an 8-bit signed speed command and adds a correction generated by a feedback sensor. The controller must detect when the requested value exceeds the signed range −128 to +127.

Problem

Suppose the command is +100 and the correction is +40. In eight-bit two’s complement:

0110 0100   (+100)
+ 0010 1000   (+40)
------------
  1000 1100

The stored bit pattern 10001100₂ represents −116, not +140. Both operands were positive but the result is negative, so the overflow flag is set.

Analysis and solution

The controller should not simply use the eight-bit result as a physical motor command. It can choose one of two policies:

1. Wrap-around arithmetic: retain the low eight bits. This is inexpensive but unsuitable for a speed command because a large positive request becomes a negative command.
2. Saturation arithmetic: if the result exceeds +127, output +127; if it is below −128, output −128. This requires overflow detection and a multiplexer selecting the appropriate limit.

For control systems, saturation is usually safer because it prevents an abrupt reversal caused by wrap-around. The ALU computes the sum, the overflow logic examines operand and result signs, and control logic selects the maximum or minimum representable value.

Outcome and learning points

The example demonstrates that binary addition can be electrically correct yet application-level incorrect if signed overflow is ignored. It also shows why status flags are valuable and why arithmetic policy must match the system’s physical purpose. In safety-related designs, the response to overflow should be specified, tested, and documented rather than left to accidental hardware behavior.

Design Challenges and Best Practices

1. Define representation first. The same bit pattern can represent an unsigned integer, a signed integer, an address, or a field of independent Boolean values.
2. Separate carry and overflow. Carry supports unsigned interpretation; overflow supports signed interpretation.
3. Choose speed and area deliberately. Ripple-carry adders are economical; prefix and lookahead structures are faster but consume more wiring and power.
4. Verify boundary cases. Test zero, maximum positive, minimum negative, carry generation, signed overflow, and shift distances equal to or greater than word width.
5. Document flag semantics. In particular, subtraction carry/borrow conventions differ among instruction-set architectures.
6. Consider power and electromagnetic effects. Wide parallel adders and barrel shifters can switch many nodes simultaneously. Clock gating, operand isolation, and appropriate voltage scaling may reduce unnecessary activity.
7. Use formal and simulation-based verification. Truth-table checks, random tests, assertion-based verification, and equivalence checking can expose corner cases.

Contemporary processors increasingly use configurable arithmetic units, SIMD/vector ALUs, fused operations, and specialized accelerators. These developments improve performance but increase verification difficulty. AI accelerators also use low-precision integer arithmetic, where overflow, rounding, saturation, and quantization must be explicitly designed. AI does not replace the need for Boolean reasoning: incorrect arithmetic hardware produces systematically incorrect results at very high speed.

Chapter Summary

Arithmetic circuits build complex digital operations from Boolean gates. A half-adder handles two input bits, while a full-adder also accepts an incoming carry. Ripple-carry adders are compact but slow for wide operands because carry propagation is sequential. Carry-lookahead, carry-select, carry-save, and prefix structures improve performance at the cost of hardware complexity.

Two’s complement subtraction uses addition of the complemented subtrahend plus one. Unsigned carry and signed overflow are distinct conditions and must be interpreted according to the data representation. ALUs combine arithmetic, logical, comparison, and shifting functions and commonly produce zero, negative, carry, and overflow flags.

Shifters support scaling, bit-field operations, address manipulation, cryptography, and embedded control. A processor data path connects registers, multiplexers, ALUs, shifters, buses, and control logic. Its performance depends on combinational delay, register timing, wiring, and pipeline organization. Practical designs must select arithmetic behavior—especially wrap-around or saturation—according to system requirements.

Key Terms

Half-adder: A circuit that adds two one-bit inputs and produces sum and carry.

Full-adder: A circuit that adds two operand bits and an input carry.

Ripple-carry adder: A cascaded adder in which carry propagates from one stage to the next.

Carry-lookahead adder: An adder that computes carries in parallel using propagate and generate signals.

Propagate: A condition in which an input carry passes through an adder stage.

Generate: A condition in which an adder stage produces a carry independently of its input carry.

Two’s complement: A signed binary representation formed by inverting bits and adding one for negation.

Unsigned carry: A carry beyond the most significant bit of an unsigned addition.

Signed overflow: A result outside the representable signed range.

ALU: Arithmetic logic unit that performs arithmetic and Boolean operations.

Status flag: A bit reporting a condition such as zero, carry, sign, or overflow.

Barrel shifter: A combinational circuit capable of shifting by a selected distance in one operation.

Arithmetic shift: A shift that preserves the sign bit during right shifting.

Rotate: A shift in which discarded bits re-enter at the opposite end.

Data path: Hardware that stores, transfers, and processes digital data.

Register file: A group of registers with controlled read and write access.

Multiplexer: A circuit that selects one input from several sources.

Saturation arithmetic: Arithmetic that limits results to the maximum or minimum representable value.

Pipeline: A sequence of register-separated processing stages.

Review Questions

Short Answer Questions

1. What is the difference between a half-adder and a full-adder?
2. Why does a ripple-carry adder become slower as word width increases?
3. State the condition for signed overflow during addition.
4. What is the purpose of a barrel shifter?
5. Name four common ALU status flags.

Long Answer Questions

1. Explain the construction and operation of a four-bit ripple-carry adder.
2. Describe two’s complement subtraction and illustrate it with an example.
3. Compare ripple-carry, carry-lookahead, carry-select, and carry-save adders.
4. Explain the components and operation of a basic processor data path.
5. Discuss the difference between logical and arithmetic right shifts, including applications.

Analytical / Application Questions

1. An eight-bit ALU adds 01111111₂ and 00000001₂. Determine the stored result, carry flag, and signed overflow flag, and justify each answer.
2. Design an adder-subtractor control scheme using XOR gates and an initial carry input. Explain the circuit behavior when the mode signal is 0 and 1.
3. An embedded actuator accepts signed values from −128 to +127. Evaluate whether wrap-around or saturation arithmetic is safer, and justify your decision for a motor-control application.

Multiple Choice Questions with Answers

Question 1

Which expression gives the sum output of a full-adder?

A. A + B + Cᵢ

B. A ⊕ B ⊕ Cᵢ

C. AB + Cᵢ

D. ¬(A + B + Cᵢ)

Correct Answer: B. A ⊕ B ⊕ Cᵢ

Question 2

What does a carry out of the most significant bit normally indicate for unsigned addition?

A. The result is always zero

B. Signed overflow only

C. The unsigned result exceeds the available word width

D. The operands were equal

Correct Answer: C. The unsigned result exceeds the available word width

Question 3

In four-bit two’s complement arithmetic, what does 1000₂ represent?

A. +8

B. +4

C. −7

D. −8

Correct Answer: D. −8

Question 4

Which condition indicates signed overflow during addition?

A. Adding operands of different signs

B. Adding same-sign operands and obtaining the opposite sign

C. The result contains at least one zero bit

D. The least significant bit is one

Correct Answer: B. Adding same-sign operands and obtaining the opposite sign

Question 5

Which adder computes carry signals using propagate and generate terms?

A. Half-adder

B. Ripple-carry adder

C. Carry-lookahead adder

D. Parity generator

Correct Answer: C. Carry-lookahead adder

Question 6

What does an arithmetic right shift usually preserve?

A. The least significant bit

B. The sign bit

C. The carry input

D. The zero flag

Correct Answer: B. The sign bit

Question 7

Which ALU flag is asserted when every result bit is zero?

A. Carry flag

B. Overflow flag

C. Zero flag

D. Parity-invert flag

Correct Answer: C. Zero flag

Question 8

What is the two’s complement of 0101₂ in four bits?

A. 0011₂

B. 1010₂

C. 1011₂

D. 1100₂

Correct Answer: C. 1011₂

Question 9

For an eight-bit signed motor command, what is the safer response when +100 and +40 produce overflow?

A. Wrap to −116

B. Ignore the result

C. Saturate at +127

D. Invert every result bit

Correct Answer: C. Saturate at +127

Question 10

Which component selects one of several data sources for a data path?

A. Multiplexer

B. Full-adder

C. Register only

D. Parity checker

Correct Answer: A. Multiplexer