ADDERS AND MULTIPLIER

MODULE 4
TOPICS

 Adders –
 Static adder
 Concept of generate and propagate
 Carry-bypass adder
 Linear carry select adder
 Square-root carry select adder
 Array Multiplier
A GENERIC DIGITAL PROCESSOR

Main components
• Input–Output (I/O)
• Memory
• Datapath
• Control Unit
• Interconnect (communication links)
OPERATION FLOW

 Input devices provide data or instructions to the system.

 Data moves through the interconnect (bus lines) to the memory or datapath.

 The datapath performs arithmetic and logical operations on the data.

 The control unit coordinates all operations by sending control signals.

 The processed data may be stored in memory or sent to output devices.

Thus, the control unit decides what operation to perform, while the datapath actually performs the
operation.
Datapath (Arithmetic Unit)
 The datapath is responsible for data processing operations in a digital system.
Characteristics
 Usually implemented as a bit-sliced datapath where operations are performed bit-by-bit in
parallel.
 Contains functional units for arithmetic and logical operations.
Components of Datapath
 Adder
 Performs addition operations.
 Used in arithmetic calculations and address generation.
 Multiplier
 Performs multiplication operations.
 Shifter
 Performs left or right shift operations.
 Used for multiplication, division, and bit manipulation.
 Comparator
 Compares two values.
 Determines conditions such as greater than, less than, or equal.
These units together form the Arithmetic Logic functionality of the system.
Memory
 The memory unit stores data, instructions, and intermediate results.
Types of memory components
 RAM (Random Access Memory)
 Temporary storage.
 Data can be read and written.
 ROM (Read Only Memory)
 Stores permanent programs or firmware.
 Buffers
 Temporary storage used to match speed differences between modules.
 Shift Registers
 Registers that shift data sequentially.
 Used in serial communication and data manipulation.
Memory acts as the data storage center for the system.
Control Unit
 The control unit manages the overall operation of the system.
Functions
 Generates control signals.
 Determines when and how operations occur in datapath and memory.
 Ensures the correct sequence of operations.
Control Implementation
 Finite State Machine (FSM)
 The control logic is often implemented as an FSM.
 Each state represents a step in the operation sequence.
 PLA (Programmable Logic Array)
 Used to implement control logic in programmable hardware.
 Random Logic
 Control logic built using gates and combinational circuits.
 Counters
 Used to generate timing signals and sequence operations.
Interconnect
 The interconnect provides communication between all components.
Components
 Switches
 Direct signals between different modules.
 Arbiters
 Resolve conflicts when multiple units request access to shared resources (like memory).
 Bus
 Shared communication pathway used to transfer data, address, and control signals.
Role of Input–Output (I/O)

 The I/O unit connects the digital system with external devices.

Functions

 Accepts input from devices like keyboards, sensors, or other systems.

 Sends processed data to output devices such as displays, printers, or actuators.

BIT SLICED DESIGN
 Data Signals
• Carry actual binary information (0s and 1s).
• Flow through functional units like adder, shifter, multiplier.
• Represent operands and results.

Control Signals
• Generated by the control unit.
• Decide what operation to perform and when.
• Examples: load, shift, add, enable, select.
Physical Layout (Metal Layers)
 Metal 1 (horizontal) → carries data signals
 Metal 2 (vertical) → carries control signals
Why separate layers?
 Avoids signal interference.
 Simplifies routing in chip design.
 Improves performance and scalability.
Bit-Sliced Datapath Structure

•Instead of designing a full datapath at once, it is divided into identical slices, each
handling one bit.
•These slices are replicated (tiled) to form multi-bit systems.
FULL ADDER
FULL ADDER

The full adder adds two bits along with an incoming carry.

 Inputs: A, B, Cin (Carry-in)

 Outputs: Sum (S), Cout (Carry-out)

 Sum: 𝑆𝑆 = 𝐴𝐴 ⊕ 𝐵𝐵 ⊕ 𝐶𝐶𝑖𝑖 𝐺𝐺 = 𝐴𝐴𝐴𝐴

𝐷𝐷 = 𝐴𝐴̅𝐵𝐵�
 Carry-out: 𝐶𝐶𝑜𝑜 = 𝐴𝐴𝐴𝐴 + 𝐵𝐵𝐶𝐶𝑖𝑖 + 𝐴𝐴𝐶𝐶𝑖𝑖
𝑃𝑃 = 𝐴𝐴 ⊕ 𝐵𝐵
 Co (G,P) = G + PCi

 S(G,P) = P ⊕ Ci
 Delete Propagate Generate

• Condition: A = 0, B = 0 Condition: A ≠ B (i.e., 01 Condition: A = 1, B = 1

• Output: Co = 0 or 10) Carry is generated
(regardless of Ci) Output carry depends on regardless of Ci.
• Any incoming carry is input carry (Ci). Output carry is always 1.
eliminated Carry is passed to the
• Carry does NOT next stage.
propagate.
Example:
If Ci = 0 → Co = 0 • 1 + 1 + 0 → Co = 1
If Ci = 1 → Co = 1 • 1 + 1 + 1 → Co = 1
Example:
Example:
• 0 + 0 + 1 → Sum = 1, Carry = 0
• 0 + 1 + 1 → Carry
propagates → Co = 1
Static Adder circuit

 One way to implement full adder circuit is take the logic equation and translate directly in to complementary

CMOS circuitry

 Adjust to reduce transistor count

 It is advantageous to share some logic between the sum and carry generation sub circuits, as long as it does

not slow down the carry generation

COMPLEMENTARY STATIC CMOS FULL ADDER:
4-bit ripple carry adder
 Carry is rippled to next stage of addition. So, it is referred to as ripple carry adder.

 It takes n number of machine cycles to add n bits serially. So, it is a slow adder.

 Delay is proportional to the number of bits in the input

𝑇𝑇𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 = 𝑁𝑁 − 1 𝑇𝑇𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 + 𝑇𝑇𝑠𝑠𝑠𝑠𝑠𝑠

 Important to optimize 𝑇𝑇𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐

 Generate (G), Propagate (P) and Delete (D) are intermediate signals which denotes carry status

𝐺𝐺 = 𝐴𝐴𝐴𝐴

𝐷𝐷 = 𝐴𝐴̅𝐵𝐵�

𝑃𝑃 = 𝐴𝐴 ⊕ 𝐵𝐵
CARRY BYPASS ADDER

 A Carry Bypass Adder, also called a Carry Skip Adder is a fast adder architecture designed to
reduce the delay caused by ripple carry propagation in a Ripple Carry Adder (RCA).

 In a normal ripple carry adder, each bit must wait for the carry from the previous stage which
makes it slow for large bit sizes.

 The Carry Bypass Adder improves this by:

 Dividing the adder into blocks (groups of bits)

 Allowing the carry to bypass (skip) a block if all bits in that block propagate the carry
• In a 4-bit adder block, suppose the value of Ak and Bk(k=0.....3) are such that all propagate
signals Pk(k=0..3) are high ,the incoming carry Ci,0 =1 propagates under these condition
through this adder chain and causes an outgoing carry Co,3 =1
• IF P1P2P3P4 = 1, then Co,3 = Ci,0
For computing delay of an N-bit adder

 First assume the total adder is divided in to (N/M)equal-length bypass stages, each of which
contains M bits

 N = 16, M = 4
Total Propagation Time:

𝑁𝑁
𝑇𝑇𝑝𝑝 = 𝑇𝑇𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 + 𝑀𝑀𝑇𝑇𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 + ( − 1)𝑇𝑇𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏 + (𝑀𝑀 − 1) 𝑇𝑇𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 + 𝑇𝑇𝑠𝑠𝑠𝑠𝑠𝑠
𝑀𝑀

• 𝑇𝑇𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 = Time to create Generate and Propagate signals

• 𝑇𝑇𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 = Propagation delay through single bit

• 𝑇𝑇𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏 = Propagation delay through bypass multiplexer of a single stage

• 𝑇𝑇𝑠𝑠𝑠𝑠𝑠𝑠 = Time to generate sum of final stage

Carry-Bypass vs Ripple Carry Adder:
THE LINEAR CARRY SELECT ADDER

 In a ripple carry adder, each full adder must wait for the incoming carry before producing the
output carry, leading to large propagation delay.

To overcome this delay:

 Compute results in advance for both possible carry inputs: Carry = 0, Carry = 1
 Once the real value of the incoming carry is known, correct result is easily selected with a simple
multiplexer stage

 This removes the need to wait for the actual carry to arrive.
Consider a block of adder which is adding bits k to k+3:

 Instead of waiting for the carry from the previous stage (Cₒ,k−1):

 One adder block assumes carry = 0

 Another adder block assumes carry = 1

 So, two parallel carry paths are created:

 Path 1 → for carry = 0

 Path 2 → for carry = 1

 When Cₒ,k−1 finally settles, either the result of the 0 or the 1 path is selected by the multiplexer, which is
performed with minimal delay
When the actual carry (Cₒ,k−1) arrives:

 A multiplexer (MUX) selects the correct output:

 If carry = 0 → select results from path 1

 If carry = 1 → select results from path 2

Since only selection is needed at this stage:

 Delay is very small compared to recomputation

Setup Stage

 The inputs are used to compute:

 P (Propagate) = A ⊕ B

 G (Generate) = A · B

 These signals are common for both carry assumptions.

Parallel Carry Evaluation
Two parallel paths are created:

“0” Carry Propagation

Path Assumes input carry Ci = 0
• Computes:
• Intermediate carries
• Final carry C₀,k+3
• Partial sums
“1” Carry Propagation
Path Assumes input carry Ci = 1
• Computes:
• Another set of carries
• Final carry
• Partial sums

Both computations happen simultaneously (in parallel)

Multiplexer (MUX) Selection
 Actual carry input C₀,k−1 acts as the select line
 MUX chooses:
 Output from “0” path if carry = 0
 Output from “1” path if carry = 1
 Only selection delay is added (very small)
Sum Generation
 Selected carry vector is used to generate final sum bits
 Output carry: C₀,k+3
Carry-Select adder – critical path:
SQUARE ROOT CARRY-SELECT ADDER

01-04-2026
 The Square Root Carry Select Adder is an optimized version of the Carry Select Adder that
reduces delay by using variable-sized blocks instead of equal-sized ones.
Unlike the previous fixed 4-bit blocks, here:
 Block sizes are non-uniform (increasing):
 Bit 0–1 (2 bits)
 Bit 2–4 (3 bits)
 Bit 5–8 (4 bits)
 Bit 9–13 (5 bits)
 Bit 14–19 (6 bits)
 This is done to balance delays across stages and improve speed.
In a normal CSA:

 Each block has equal delay → inefficient

In this optimized CSA:

 Early blocks are small → fast carry generation

 Later blocks are larger → more computation

 They have more time (carry arrives later)

 This creates a balanced delay pipeline

ADDER DELAY COMPARISON:
ARRAY MULTIPLIER
Binary Multiplication
Partial product generation

Logical AND operation is used to generate partial product.

4X4 Array Multiplier
 For M*N array multiplier,

 M*N AND gates

 N Half Adders

 (M-2) *2 Full Adders

 4X4 multiplier

 16 AND gates, 4 HA and 8 FA

Propagation delay

𝑻𝑻𝒎𝒎𝒎𝒎𝒎𝒎 = 𝑴𝑴 − 𝟏𝟏 + 𝑵𝑵 − 𝟐𝟐 𝑻𝑻𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄𝒄 + 𝑵𝑵 − 𝟏𝟏 𝑻𝑻𝒔𝒔𝒔𝒔𝒔𝒔 + 𝑻𝑻𝒂𝒂𝒂𝒂𝒂𝒂

Array multiplier – critical path: