Introduction to Logic Circuit Design (University of Utah) - Adders (Lecture 10)

Overview

The lecture develops multi-bit addition and subtraction, then compares faster adder architectures that reduce the serial delay of ripple carry. It derives carry lookahead using generate and propagate signals, introduces block carry lookahead and carry select, and begins designing binary-coded decimal addition with a correction condition for sums greater than 9.

Key takeaways

Two's complement lets an n-bit adder perform subtraction by inverting every bit of Y and setting the initial carry-in to 1.
A single add/subtract unit can conditionally invert Y with XOR gates controlled by the operation signal, then reuse the same adder hardware.
Ripple-carry delay grows with bit width because each carry depends on the previous one; carry lookahead uses Gᵢ = XᵢYᵢ and Pᵢ = Xᵢ OR Yᵢ to calculate carries in parallel.
Block carry lookahead limits the size of local carry logic, while carry select precomputes results for both carry-in values and uses a multiplexer to choose the correct result.
Faster adder designs trade additional gates and area, and potentially power, for reduced carry delay.
BCD addition must detect intermediate digit sums above 9 and conditionally add a correction; four-bit values 10 through 15 are outside the valid single-digit BCD range.

Chapters

0:00 Lecture Agenda and Assignment Policies

Planned topics include subtractors, faster adders, decimal-to-binary and binary-to-decimal coding, and possibly multipliers.
Late homework submissions receive a 25% deduction, and regrade requests must be submitted through Gradescope.
The instructor says grades will appear on Canvas after the regrade-request period.

3:49 Ripple-Carry Adders Scale Poorly with Bit Width

A multi-bit adder can be built by chaining one-bit full adders, each receiving the previous stage's carry.
In a ripple-carry structure, each carry must wait for the prior carry, so delay grows with the number of bits.
A 128-bit ripple-carry adder may require up to 128 carry stages, motivating faster architectures.

6:13 Defining an N-Bit Adder as a Design Component

An n-bit adder takes two n-bit inputs, X and Y, rather than adding two individual n-bit values.
The adder can be treated as a black box with a fixed n-bit interface while additional logic is placed around it.
The design exercise uses that adder block to build an n-bit subtractor.

10:27 Building Subtraction from Two's Complement Addition

Binary subtraction is implemented by adding the two's complement of the subtrahend.
Two's complement is formed by inverting every bit of Y and adding 1.
The existing adder can therefore compute X minus Y by adding X, the inverted Y, and an initial carry-in of 1.

19:29 Combining Addition and Subtraction with a Control Signal

A single circuit can select between X plus Y and X minus Y using a control signal.
The control signal conditionally inverts each bit of Y through XOR logic, while also supplying the initial carry-in for subtraction.
With the usual convention, control 0 selects addition and control 1 selects subtraction, reusing one n-bit adder for both operations.

27:40 Control Signals and XOR-Based Conditional Inversion

A control input lets one circuit perform multiple functions by selecting behavior for control values 0 and 1.
XOR with the control signal leaves an input unchanged when the control is 0 and inverts it when the control is 1.
The add/subtract design combines this conditional inversion with a carry-in of 1 for subtraction.

29:07 Why Ripple Carry Needs a Faster Alternative

Each ripple stage depends on the carry from the preceding stage, creating a serial path through the adder.
The inputs X and Y are available at the start, so the design goal is to calculate later carries directly from those inputs.
Reducing dependence on intermediate carries can shorten the critical path for wide adders.

31:30 Carry Lookahead with Generate and Propagate Signals

For bit i, generate is defined as Gᵢ = XᵢYᵢ, and propagate is defined as Pᵢ = Xᵢ OR Yᵢ.
The carry recurrence is Cᵢ₊₁ = Gᵢ OR (Pᵢ AND Cᵢ).
Expanding the recurrence expresses carries such as C₂ and C₃ directly in terms of G, P, and the initial carry, rather than waiting for every prior carry.

42:34 Carry Lookahead Timing, Gate Depth, and Area

Carry-lookahead logic calculates multiple carries in parallel from the input-derived generate and propagate signals.
Unlike ripple carry, the carry path no longer requires one serial stage for every bit.
The expanded logic uses more gates and can become increasingly complex as the adder width grows, creating an area and implementation tradeoff.

47:14 Block Carry Lookahead for Wide Adders

The block approach groups bits into manageable sections, such as groups of eight, and computes local carries within each group.
Each block can be summarized by group generate and propagate behavior, allowing the next block's carry to be calculated from the prior block's carry.
A second level can calculate carries such as C₈, C₁₆, and C₂₄ from the initial carry, while avoiding one enormous lookahead expression across all bits.

52:58 Carry Select Adders Precompute Both Outcomes

For a 32-bit example, the circuit can divide the work into 16-bit sections.
The later section computes results for both possible incoming carry values before the actual carry arrives.
Once the correct carry is known, a multiplexer selects the matching precomputed result, trading extra hardware for less waiting.

58:18 Adder Design Tradeoffs and Speculative Execution

Carry select and carry lookahead illustrate the tradeoff among speed, circuit area, and power.
The carry-select technique resembles processor speculation: calculate likely or alternative outcomes before a decision is resolved.
The lecture relates branch prediction to avoiding idle time while a condition is being determined, then selecting or correcting the result when the condition becomes known.

1:04:27 Representing Decimal Digits with Binary-Coded Decimal

Binary-coded decimal (BCD) represents each decimal digit separately using a group of bits.
For example, decimal 26 is represented by encoding the digits 2 and 6 independently, rather than encoding 26 as one ordinary binary number.
This digit-by-digit representation provides a direct connection between decimal values and their binary-coded digits.

1:07:00 BCD Addition Requires a Conditional Correction

A BCD adder first adds the binary-coded inputs and observes both the sum bits and carry-out.
The correction decision depends on whether the intermediate digit sum is valid for one decimal digit or exceeds 9.
A flowchart describes using that decision as a control signal to select whether a correction value is added to the intermediate result.

1:12:39 Deriving a Detector for BCD Sums Above 9

The lecture examines a four-bit intermediate result, labeled x₃ through x₀, to identify values greater than 9.
The invalid BCD digit values are 10 through 15, so the detector must recognize those cases.
The class begins grouping shared bit patterns to derive a Boolean condition for the correction control, but the transcript ends before the full expression is completed.

Transcript excerpt

0:49 ‏Good afternoon are we have our 10 and about talking about circuit ‏So if remember last time we got to know one type of and now we gna build based on that we gna see how we can create a subtractor based on the other that we built and then we gna know more types of add we found some problems with the current version the previous version that we looked into that ‏And we see that how we can fix that issue. ‏So we have carry look ahead carry select other types of better others and then we gna

1:39 find time get to know a type of coding something that we can convert someh decimal to binary binary to decimal and then if we find time we gna talk about the arithmetic multiplier all right for announcement don't remember homework for ‏dead upcoming at 1159 home and are graded please take a look into that I will post the grades on canvas after when the regulate request is done the reason is if basically if the homework if the assignment is submitted late 25%

2:29 deduction will be applied ‏So I don't wan change that again. So the you see your homeworks on grade on canvas after when the request the deadline for regrate request is done regrade request deadline for all assignments would be one big from releasing the grades on grade scope. So grade scope now you can see your grade please go over that see if you have missed any points. ‏If you want to do any regrade request, please do it only through grade scope. Do not email or anything because that might get missed. But if you have any questions in general, feel free to email your T. I'm gna mention on canvas that who has

This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.

Related notes

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, MEDAL-Research.