CS203: Digital Logic Design

Module 3: Combinational Circuit Design

Neeraj Goel
IIT Ropar
 Objectives
• Commonly used combinational circuits
– Multiplexers, decoders, encoders
• Arithmetic circuits
– Adders and multipliers
• Design and analysis of combinational circuits
• Programmable logic devices (PLDs)
– PALs, CPLDs, FPGAs

Digital Logic Design:Combinational Circuits. 2

 Boolean Expressions from plain
English-1
• You should laugh at a joke if it funny, it is good
in taste, and it is not offensive, or it is told in
class by your professor and it is not offensive.
• Input: F (Joke is funny), T (Joke is good in
taste), O (Joke is offensive), P (Told by
professor)
• Output: L (laugh)
• L = F . T . O’ + P . O’

Digital Logic Design:Combinational Circuits. 3

Boolean expression from plain English-
2
• An IoT node should stop if manual stop button
pressed or error occurred or no more data to
process
• Input :
– M (manual stop), E (Error), D (data)
• Output: S (Stop)
• Boolean expression
S = M E D’

Digital Logic Design:Combinational Circuits. 4

 ADD Example
• Adding three bits A, B, C
• Sum is ‘1’ when either only one bit is ‘1’ or all
three bits are ‘1’
• Carry is ‘1’ when two or more bits are ‘1’
• Sum = A B’C’ + A’BC’ + A’B’C + ABC
• Carry = ABC’ + AB’C + A’BC + ABC

Digital Logic Design:Combinational Circuits. 5

 Output as one of the input(1)
• Two input case (A and B Input, Z output)
– Output is A, if A is selected
– Output is B, if B is selected
• How A or B is selected – Say one bit Control.
– If Control is 0 => A is selected
– If Control is 1 => B is selected
• Z = A . Control’ + B . Control

Digital Logic Design:Combinational Circuits. 6

 Output as one of the input(2)
• Four inputs (A, B, C, D) and one output Z
• Control will have two bits c0 and c1
• If c1c0 = “00” Z = A
• If c1c0 = “01” Z = B
• If c1c0 = “10” Z = C
• If c1c0 = “11” Z = D
• Z = c1’c0’ A + c1’c0 B + c1c0’ C + c1c0 D

Digital Logic Design:Combinational Circuits. 7

 Output as one of the input(3)
• Standard combination logic – Multiplexer

I0 What if N ≠2k

N-to-1 MUX
I1
Z
IN-2
IN-1

• Number of bits in C = ceil(log2 N)

• Z = ∑mkIk

Digital Logic Design:Combinational Circuits. 8

 Cost of a multiplexer
• Cost of N:1 Mux
– N+M inputs and 1 output
– M control bits
– N AND gates with (M+1) inputs (1st stage)
– One OR gate with N inputs (2nd stage)

Digital Logic Design:Combinational Circuits. 9

 Hierarchical Design of Mux
• Using 4:1 Mux to design 16:1 Mux
I0

4 to-1
To I3 MUX

I4
4 to-1
MUX

To I7 Z

4 to-1
MUX
I8
4 to-1
MUX

c3c2
To I11

I12
4 to-1
MUX

To I15

Digital Logic Design:Combinational Circuits. 10

c1c0
 Heirarchical Design of Mux
• 16:1 Mux cost
– 16 AND gates of 5 inputs and one 16 input OR
gate
• 4:1 Mux cost
– 4 AND gate of 3 input and one 4 input OR gate
• Design of 16:1 Mux using 4:1 Mux
– Four 4:1 Mux at stage 1
– One 4:1 Mux at stage 2

Digital Logic Design:Combinational Circuits. 11

 MultiBit Multiplexer
• 4 bit 2:1 Mux
4
I0

2-to-1 MUX
I01
2-to-1 MUX

I02 4
2-to-1 MUX

I03 Z
2-to-1 MUX

I04 Z1 4
2-to-1 MUX

Z2 I1
I11 Z3
I12 Z4
I13
I14

C C
C
C
C

Digital Logic Design:Combinational Circuits. 12

 Application of Mux (1)
• Designing any generic circuit

4x1 Memory

4-to-1 MUX
0 0
0 1 Z = A AND B
0 2
1 3

A B

•2N input mux can design any N input function

•Typically used in FPGAs – Known as LUT or Look up tables

Digital System Design 13

 Application of MUX(2)
• Hardware realization
of if-else/switch
construct 4
10

4-to-1 MUX
If(a == 0) 4 4
15 Z
z = 10 0
4
4
else if (a == 1) ?

z = 15 2
a
else if (a == 2)
z = 0 Q: Can’t we make 3:1 mux?

Digital System Design 14

 Application of MUX(2)
• Hardware realization 4
of if-else/switch 10

3-to-1 MUX
4 4
construct 15
4
Z
– What if condition are 0
not 0,1,2...
If(a < 0) 3
z = 10 cond

else if (a == 0)
One hot encoded Mux
z = 15
Cond[0] = (a < 0)
else if (a > 0) Cond[1] = (a == 0)
z = 0 Cond[2] = (a > 0)
Digital System Design 15
 Application of Mux(3)
• Where selection of one input is required out
several inputs
– Arbiter
– Device hub controller
– Bus controllers
– Routers
– Network switches

Digital System Design 16

 Summary
• We learnt how to give generate Boolean
expression from plain English
• We learnt about a useful standard
combinational circuit - Multiplexer

Digital Logic Design:Combinational Circuits. 17

 M3.02

Digital Logic Design:Combinational Circuits. 18

• Is it possible that multiple wires
driving single input? Four states
-High ( 1 )
-Low ( 0 )
Z1
-Unknown (X )
A
-High impedance (Z)

B
Z2

Digital Logic Design:Combinational Circuits. 19

 Four state logic simulation

AND 0 1 X Z OR 0 1 X Z
0 0 0 0 0 0 0 1 X X
1 0 1 X X 1 1 1 1 1
X 0 X X X X X 1 X X
Z 0 X X X Z X 1 X X
Simulations shows X output due to
Wrong connections, missing inputs or incorrect design
Actual gates:
X means not certain (could be 0 or 1)
IC or gates can also be faulty
Inputs or connections can be wrong
Digital Logic Design:Combinational Circuits. 20
 Tri-state buffer
• Buffer
– used to strengthen the signal
– increase driving capability
• Tristate buffer
B AA BB Y YY
00 01 0 00
A Y
11 01 1 11
00 10 ZZ
11 10 ZZ

Digital Logic Design:Combinational Circuits. 21

 Tri-state Buffer for designing circuits
• Mux implementation
A
• Used where multiple
Output
sources driving a Control

signal B

– Interconnects
2:1 Mux
• Not preferred by
digital designers

Digital Logic Design:Combinational Circuits. 22

 Demultiplexer (DEMUX)
One input, multiple outputs. Input value is
forwarded to selected output line based on control
X and Y could be bus
Y0 = X a’b’c’
X Y1 =X a’b’c
Y2= X a’bc’
Y3= X a’bc
1:8 demux
Y4= X ab’c’
a Y5= X ab’c
b Y6= X abc’
c Y7= Xabc

Digital Logic Design:Combinational Circuits. 23

 Decoder

Y0 = a’b’c’
Y1 = a’b’c
a
Y2= a’bc’
b 3 to 8 line Y3= a’bc
decoder Y4= ab’c’
c
Y5= ab’c
Y6= abc’
Y7= abc

• 3 to 8 line decoder

Digital Logic Design:Combinational Circuits. 24

 Design exercise
• We have a hardware that can store one bit
data – we call it memory cell
– Memory cell has two inputs, E and W. If E is 1, W
gets written into memory cell
– Memory cell has one output R, which reads the
content of cell

W
One bit R
Memory Cell
E

Digital Logic Design:Combinational Circuits. 25

 Design exercise
• Design a memory which has 16 cells, which can
be accessed using 4 bit address
• If W is 1, write DataIn. Data-out always reads

DataIn
Data-out
16 bit memory
4
Address
W

Digital Logic Design:Combinational Circuits. 26

 Functionality of the design
• Read – dataOut should be able to read given
an address
• Write – DataIn should be written to memory
cell at given address, if W is 1

Digital Logic Design:Combinational Circuits. 27

 Writing to the memory
Using Demux Generate E
DataIn will be connected to all W0 to W15

W0
E0
W1
E1
1:16 DEMUX

1:16 DEMUX
W2
E2
DataIN
W

W15
E15
4
Address 4
Address

Digital Logic Design:Combinational Circuits. 28

 Reading from the memory
• Using Mux

D0
16-to-1 MUX
D1
DataOut

D15

4
Address

Digital Logic Design:Combinational Circuits. 29

 Overall Design

DataIn
W0
E M0 D
W1 0 0
M1 D1
1:16 DEMUX

E1

16-to-1 MUX
DataOut

W15
E15 M15 D
15

4
Address 4
Address

Digital Logic Design:Combinational Circuits. 30

 Summary
• Learnt about tri-state buffers
• De-mux
• Decoder

Digital Logic Design:Combinational Circuits. 31

 M2.03
• Decoders
• Encoders

Digital Logic Design:Combinational Circuits. 32

 Decoder

Y0 = a’b’c’
Y1 = a’b’c
a
Y2= a’bc’
b 3 to 8 line Y3= a’bc
decoder Y4= ab’c’
c
Y5= ab’c
Y6= abc’
Y7= abc

• 3 to 8 line decoder

Digital Logic Design:Combinational Circuits. 33

 Decoder with inverted output

Y0 = a + b + c
Y1 = a + b + c’
a
Y2= a + b’ + c
b 3 to 8 line Y3= a + b’ + c’
decoder Y4= a’ + b + c
c
Y5= a’ + b + c’
Y6= a’ + b’ + c
Y7= a’ + b’ + c’

• 3 to 8 line decoder with inverted output

Digital Logic Design:Combinational Circuits. 34

 Decoder with enable
Does it look like demux?

Y0 = E a’b’c’
Y1 = E a’b’c
a
Y2= E a’bc’
b 3 to 8 line Y3= E a’bc
decoder Y4= E ab’c’
c
Y5= E ab’c
Y6= E abc’
E Y7= E abc

• 3 to 8 line decoder with enable

Digital Logic Design:Combinational Circuits. 35

 Designing decoders hierarchically

b Y0
c 2 to 4 line Y1
decoder Y2
a’ Enable
Y3
Y4
b
Y5
c 2 to 4 line Y6
decoder
Enable Y7
a

• 3 to 8 line decoder with enable

Digital Logic Design:Combinational Circuits. 36

 Designing decoders hierarchically

b Y0
c 2 to 4 line Y1
decoder Y2
a Enable
Y3
1 to 2 line Y4
decode b
Y5
c 2 to 4 line Y6
decoder
Enable Y7

• 3 to 8 line decoder designed heirachically

Digital Logic Design:Combinational Circuits. 37

 Designing decoder hierarchically
• Design 8 to 256 line decoder
• Option 1: Monolithic design
– Input 8 (+1 if enable is also there)
– Output 256
• Option 2: Hierarchical design
– Two levels
• First level 4 to 16 decode (MSB)
• Second level, sixteen 4 to 16 decoders
– Three levels

Digital Logic Design:Combinational Circuits. 38

 Designing generic circuit with
decoders
• Sum of Minterm
• Product of max term
F(a, b, c) = ∑m(1,3,5)

Y0
Y1
a Y2
b 3 to 8 line Y3 F
decoder Y4
c Y5
Y6
Y7

Digital Logic Design:Combinational Circuits. 39

 Encoders
• 2N inputs and N outputs
– Assume only one of the input is high, output
encodes the input number
Encoder/Decoder for specific coding,
e.g., gray codes
X0
X1 Y2 = X4 + X5 + X6 + X7
X2
X3 8 to 3 Y1 = X2 + X3 + X6 + X7
X4 Encoder
Y0 = X1 + X3 + X5 + X7
X5
X6
X7

Digital Logic Design:Combinational Circuits. 40

 Priority encoding
• What if more than one input is high at input of
encoder
X7 has highest priority
X0 has least
X0
X1 Y2 Z is one if any of input is one
X2
X3 8 to 3 Y1
X4 Encoder
Y0
X5
X6 Z
X7

Digital Logic Design:Combinational Circuits. 41

Priority encoding – 8 to 3 example
X0 X1 X2 X3 X4 X5 X6 X7 Y2 Y1 Y0 Z
0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 1
x 1 0 0 0 0 0 0 0 0 1 1
x x 1 0 0 0 0 0 0 1 0 1
x x x 1 0 0 0 0 0 1 1 1
x x x x 1 0 0 0 1 0 0 1
x x x x x 1 0 0 1 0 1 1
x x x x x x 1 0 1 1 0 1
x x x x x x x 1 1 1 1 1

Y2 = x7 + x6x7’ + x5x6’x7’ + x4x5’x6’x7’

Y1 = x7 + x6x7’ + x3x4’x5’x6’x7’ + x2x3’x4’x5’x6’x7’
Y0 = x7 + x5x6’x7’ + x3x4’x5’x6’x7’ + x1x2’x3’ x4’x5’x6’x7’
Z = X0 + X1 + X2 + X3 + X4 + X5 + X6 + X7 42
Example: Seven segment display encoders
• Input binary number or BCD number
• Output – seven segment display
X3 X2 X1 X0 A G
0 0 0 0 1 0
0 0 0 1 0 0 A
0 0 1 0 1 1
F B
0 0 1 1 1 1
0 1 0 0 0 1 G
0 1 0 1 1 1
0 1 1 0 1 E C
1
0 1 1 1 1 0
D
1 0 0 0 1 1
1 0 0 1 1 1
Digital Logic Design:Combinational Circuits. 43
 Summary
• Decoders
• Encoders
• Methods:
– Identify inputs and outputs
– Find the functionality
– Boolean function for each output

Digital Logic Design:Combinational Circuits. 44

 M3.04
ROM and Programmable logic

Digital Logic Design:Combinational Circuits. 45

 How many distinct functions with N
variables possible?
• Number of truth table entries with N variables
– 2N
• Each of entry could be true or false
• 2 x 2 x 2 x ... (2N) times = 22^N
• Example
– 2 Variables, possible distinct functions = 24 = 16
– 4 variables, possible distinct functions = 216 =
~64K

Digital Logic Design:Combinational Circuits. 46

 Example – Two variables
A=0, B=0 A=0, B=1 A=1, B=0 A=1, B=1
0 0 0 0 False
0 0 0 1 A.B
0 0 1 0 A and NOT B
0 0 1 1 A
0 1 0 0 B and NOT A
0 1 0 1 B
0 1 1 0 XOR
0 1 1 1 A OR B
1 0 0 0 NOR
1 0 0 1 XNOR
1 0 1 0 NOT B
1 0 1 1 If A then B
1 1 0 0 NOT A
1 1 0 1 If Not A then B
1 1 1 0 NAND
1 1 1 1 True
Digital Logic Design:Combinational Circuits. 47
 ROM – Read only memory
• Input: Address
• Output: Bits stored at that address
– Word: Number of bits stored at an address
• Memory size
– N bit address, word size M bit
– 2N * M bits
• Typical sizes: 1KB, 512KB, 4MB
– 256K x 32 bits = 1MB

Digital Logic Design:Combinational Circuits. 48

 Example: Designing a ROM 8x4 bits
A B C F3 F2 F1 F0
0 0 0 1 1 0 0
F0 = ∑m(1,2,4,5)
0 0 1 1 0 1 1
0 1 0 0 1 1 1 F1 = ∑m(1,2,5)
0 1 1 0 1 0 0 F2 = ∑m(0,2,3,5,7)
1 0 0 1 0 0 1
F3 = ∑m(0,1,4,5,7)
1 0 1 1 1 1 1
1 1 0 0 0 0 0
1 1 1 1 1 0 0

Digital Logic Design:Combinational Circuits. 49

8x4 ROM using memory cells

M0
ROM cells
M1 -PROM

8-to-1 MUX
F0 -EEPROM
4 -Magnetic
-Optical
-Flash
M7

3
Address

Digital Logic Design:Combinational Circuits. 50

 ROM
• To design a combinational circuit with N
variables and M output
– ROM size 2N x M
• To design a ROM of size NxM
– M functions with ceil(Log2N) variables

Digital Logic Design:Combinational Circuits. 51

Programmable Logic Devices (PLD)
• Programmable
• Examples
– PLA
– CPLD
– FPGA

Digital Logic Design:Combinational Circuits. 52

 Programmable Logic Array
M functions of N variables can be designed

M output
N Input lines
lines AND array OR Array

K product
Word lines

Fuse wires connect input to AND/OR gates

Digital Logic Design:Combinational Circuits. 53

Complex Programmable Logic Devices
• Multiple functional block
– Each function block is AND-OR PLA
• Interconnect Array
– Connects signals from input/output or from one
function block to other

Digital Logic Design:Combinational Circuits. 54

 FPGA
• FPGA – Field Programmable Gate Array
• Logic Cell : Configurable Logic Block (CLB)
– LUT (Lookup table)
• Programmable interconnect

Digital Logic Design:Combinational Circuits. 55

 Configurable Logic Block

A1
A2
LUT Out1
A3
A4
C 2:1 Out2
B1 Mux
B2
LUT Out3
B3
B4

Digital Logic Design:Combinational Circuits. 56

 Summary
• We can design programmable logic using
combinational logic
– ROM
– PLA
– CPLD
– FPGA

Digital Logic Design:Combinational Circuits. 57

 M3.05
Addition

Digital Logic Design:Combinational Circuits. 58

 Addition in Binary
• Similar to decimal
1 0 1 1 1
additions
1 1 0 1 1 1
1 + 1 = (10)2 + 1 1 0 1 0 1
1 + 1 + 1 = (11)2
1 1 0 1 1 0 0
1 + 0 = (1)2

Each adder unit has three inputs:

- one bit from operand 1,
- One bit from operand 2
- Carry from previous adder
Two outputs: Sum and carry

Digital Logic Design:Introduction. 59

 Single Bit Adder
A B C Sum Cout
0 0 0 0 0 Sum = A’B’C + A’BC’ + AB’C’ + ABC
0 0 1 1 0 =ABC
0 1 0 1 0 Cout = AB + AC + BC
0 1 1 0 1
1 0 0 1 0 Delay = max (2 XOR delay, AND-OR delay)
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

A A
B
B C
C
Digital Logic Design:Combinational Circuits. 60
 Structure of N Bit Adder
Bn-1 An-1 B1 A1 B0 A0

Addern-1 Cn-1 Adder1 Adder0 C0

Cn C2 C1

Sn-1 S1 S0

S0 = A0  B0  C0
C1 = A0 . B0 + A0 C0 + B0 C0

Si = Ai  Bi  Ci
Ci+1 = Ai . Bi + Ai Ci + Bi Ci

Digital Logic Design:Combinational Circuits. 61

 Delay and area analysis
Bn-1 An-1 B1 A1 B0 A0

Addern-1 Cn-1 Adder1 Adder0 C0

Cn C2 C1

Sn-1 S1 S0

Area: N (Two 2-input XOR gate + 3 two input AND + one Three input OR)
Delay N bit adder: (N-1) (2 level Gate delay) + max(XOR delay, AND-OR delay)
= ~ N (2 level Gate delay)

Ripple carry adder

Digital Logic Design:Combinational Circuits. 62

 Can we reduce overall delay?
• Source of delay in adder
– Sequential generation and consumption of carry
• Can carry be generated in parallel?

Digital Logic Design:Combinational Circuits. 63

 Closer look at carry generation
• Carry generation: When both Ai and Bi are ‘1’
• Carry propagation: When either Ai or Bi is ‘1’
• Carry kill: When both Ai and Bi is ‘0’
• Gi = Ai Bi
• Pi = Ai + Bi Ideally Pi = Ai  Bi

• A carry out a particular stage is ‘1’ if either it

is generated at that stage or propagated from
previous stage
Digital Logic Design:Combinational Circuits. 64
 4 Bit adder
• A carry out a particular stage is ‘1’ if either it is
generated at that stage or propagated from
previous stage
• C4 = G3 + P3 C3 P & G depends on primary input
C4 = G3 + P3 G2 + P3P2G1 + P3P2P1G0 + P3P2P1P0C0
• C3 = G2 + P2C2
Carry Look Ahead Adder
C3 = G2 + P2G1 + P2P1G0 + P2P1P0C0
• C2 = G1 + P1C1
C2 = G1 + P1G0 + P1P0C0
• C1= G0 + P0C0

Digital Logic Design:Combinational Circuits. 65

 4 Bit CLA Adder
B3 A3 B2 A2 B1 A1 B0 A0

Adder0 C3 Adder2 C2 Adder1 C1 Adder0 C0

S3 G3 P3 S2 G2 P2 S1 G1 P1 S0 G0 P0

Carry Generation Block

C4

Delay analysis
-Assume simplistic model, One AND/OR gate -> ∆G
-Total delay = 1 ∆G delay (P, G) generation + 2 ∆G delay carry generation
+ 2 ∆G delay for Sum

Digital Logic Design:Combinational Circuits. 66

 Large CLA adders
• For example 16 bit adder
– Carry generation will have large fan-in gates
– To generate C16 critical path
• 17 input AND gate + 17 input OR gate
– Same gate delay will for large fanin is not applicable
– Area implications
– Not scalable
• Alternative
– Use blocks of 4bit CLA
– Multiple level CLA

Digital Logic Design:Combinational Circuits. 67

 Large Adders: CLA Blocks
B12-15 A12-15 B8-11 A8-11 B4-7 A4-7 B0-3 A0-3

Group 0 C12 Group 0 C8 Group 1 C4 Group 0 C0

• Delay: (n/2 + 3) ∆G
– ∆G for propagate and generate values
– (n/4) (2 ∆G ) for generating carry
– 2 ∆G for calculating sum
• For 16 bit adder = 11 ∆G

Digital Logic Design:Combinational Circuits. 68

 Two Level CLA Adder
B15:12 A15:12 B11:8 A11:8 B7:4 A7:4 B3:0 A3:0

Group 3 Group 2 C8 Group 1 C4 Group 0 C0

C12

Sum3:0
Sum15:12 Sum11:8 Sum7:4
G3* P3* G2* P2* G1* P1* G0* P0*

Carry Generation Block

C16

G** P**

Digital Logic Design:Combinational Circuits. 69

 Two level CLA adders
• Use group carry and group propagate
– G* = G3 + G2P3 + G1P2P3 + G0P1P2P3
– P* = P0P1P2P3
– C4 = G*0 + C0P*0
– C8 = G*1 + G*0P*1 + C0P*0P*1
– C12 = G*2+ G*1P*2 + G*0P*2P*1 + C0P*2P*1P*0
• Can be hierarchically designed
• Delay : 7 ∆G

Digital Logic Design:Combinational Circuits. 70

Verilog Modelling

Digital Logic Design:Combinational Circuits. 71

 Multiple Bit-width
• Declaration
– wire [3:0] A, B; //4 bit wide A and B
– wire [15:0] sum;
– wire a1,a2,a3,a4;
– reg [high#, low#] variable_name
• Port select
– A = sum[15:12];
– T = sum[15];
– A = B;

Digital Logic Design:Combinational Circuits. 72

 Multiple bit width
• Concatenation operator
– A = {a4,a3,a2,a1}
– sum = {16{1’b1}
//sum = 1111 1111 1111 1111
- sum = {4{a4}, 4{a3}, 4{a2}, 4{a1}}
• Constant assignment
– A = 4’b0001;
– Sum = 16’h123C
• Display : %d decimal, %b binary, %h hex
– $display(“A: %b, B: %b, Sum: %h”, A, B,
sum);
Digital Logic Design:Combinational Circuits. 73
 Generate statement
• Instantiate a group of statements multiple times
– Can use used in data-flow as well as structural
• Like macro in ‘c’. Need to be resolvable at compile
time
genvar i;
generate for(i=0; i < N; i=i+1)
begin: xor_loop
xor g1 (out[i], in1[i], in2[i]);
end
endgenerate

Digital Logic Design:Combinational Circuits. 74

 Summary

Digital Logic Design:Combinational Circuits. 75

 M3.06
Adders - continued

Digital Logic Design:Combinational Circuits. 76

 Adders – previous lecture
• We learnt about
– Ripple carry adder, and a faster design of carry
look ahead adder
• We observed
– How Boolean equations are formed
– To generate C4 Boolean equations had 9 variables
• No minimization was performed
– Delay and area trade-off

Digital Logic Design:Combinational Circuits. 77

 Fast adders
• Parallel Prefix adder
– The Brent Kung adder
– The Ladner-Fischer adder
– The Kogge-Stone adder
• Ling adders
• Carry select adders
• Carry skip adders
• Carry save adders
Digital Logic Design:Combinational Circuits. 78
 Carry Select Adders
Delay of K bit adder:
k A k B 2K ∆G
Cout0 Delay of Mux
K bit adder 0 2 ∆G

Sum0
Overall delay of K bit adder
k A k B 2K ∆G + 2 ∆G
Cout1 K bit adder 1

Sum1
Cin
Mux Cin

Cout
Sum

Digital Logic Design:Combinational Circuits. 79

Carry select adders – Unequal groups

K Bit carry select K-1 Bit carry select K-2 Bit carry select
adder adder adder

Forms an arithmetic progression

Largest size adder √N
Delay of adder : 2 √N + 2

For N = 32, 9 groups would be required

1, 1, 2, 3, 4, 5, 6, 7, and 3

Digital Logic Design:Combinational Circuits. 80

 Carry Select Adder equal groups
A[31:16] B[31:16]
k A[15:0] k B[15:0]
16 bit adder 16 bit adder
0
Sum0 Cout Sum
A[31:16] k B[31:16]

16 bit adder Delay = 16 bit adder delay + 2 ∆G

1
Sum1
Cin
Mux

Sum

Hierarchically designing adders using carry select:

Delay = Order of Log2 N
Digital Logic Design:Combinational Circuits. 81
 Adding Multiple Operands
• Adding multiple operands simultaneously
– For example: Add four operands, 4 bits each
– X[3:0], Y[3:0], Z[3:0], W[3:0] Size of final sum:
• Naive approach N + Log2 K
N size of operands
– Step 1: T1[4:0] = X[3:0] + Y[3:0] K Number of operands
– Step 2: T2[5:0] = T1[4:0] + Z[3:0]
– Step 3: S[5:0] = T2[5:0] + W[3:0]
– Delay: 3 x (delay of 6 bit adder)
– Area = 3 x (Area of 6 bit adder)

Digital Logic Design:Combinational Circuits. 82

 Carry save adders
• Cause of delay: carry propagation
• Carry save adders:
– Save the carry, propagate in the end
• Each addition: partial sum and partial carry
• Use full adder as building block

21 20
22 21 21 20

Digital Logic Design:Combinational Circuits. 83

 Example – Add 16 operands of one bit
A15 A14 A13 A12 A11 A10 A9 A8 A7 A6 A5 A4 A3 A2 A1 A0

20 20 20 20 20

21 20 21 20

22 21 20

23 22 21

S4 S3 S2 S1 S0
Digital Logic Design:Combinational Circuits. 84
 Example: 4 four bit operands

Image source: Computer Arithmetic Algorithms by Israel Koren

Digital Logic Design:Combinational Circuits. 85
 Summary
• Carry select adders and carry save adders

Digital Logic Design:Combinational Circuits. 86

 M3.07
Multiplication

Digital Logic Design:Combinational Circuits. 87

 Classical multiplication
Example of 4 bit
• Two step process Multiplication
– Step 1: 0010
• Multiplicand is multiplied with one bit of x1101
multiplier --------
• Each partial product is shifted left by one place 0010
– Step 2: addition of partial products 0000
0010
• N bit multiplicand, M bit multiplier 0010
– Result is N + M bits ---------
0011010
• Hardware cost (worst case)
– M adders of size N+M
– Can be reduced by proper sizing of adders

Digital Logic Design:Combinational Circuits. 88

 Can we do better?
• Use carry save adders!

Digital Logic Design:Combinational Circuits. 89

8x8 Multiplication example

Digital Logic Design:Combinational Circuits. 90

 8x8 Multiplication example
Result of stage 1

Digital Logic Design:Combinational Circuits. 91

 8x8 Multiplication example – stage 2
Rearranging Result of stage 1

Digital Logic Design:Combinational Circuits. 92

 8x8 Multiplication example – stage 3
Result of stage 2

Digital Logic Design:Combinational Circuits. 93

 8x8 Multiplication example – stage 3
Rearranging result of stage 2

Digital Logic Design:Combinational Circuits. 94

 8x8 Multiplication example – stage 4
Result of stage 3

Digital Logic Design:Combinational Circuits. 95

 8x8 Multiplication example – stage 4
Rearranging result of stage 3

Digital Logic Design:Combinational Circuits. 96

 8x8 Multiplication example – stage 5
Result of stage 4

Adding these using carry propagation adder

Overall reduction in area and delay!

This is called Wallace tree Multiplier.

Digital Logic Design:Combinational Circuits. 97

Issues with Wallace tree multiplier
• Irregular structure
• More and irregular interconnects
• Not Layout friendly
• Solutions
– Different tree structures that are more balanced

Digital Logic Design:Combinational Circuits. 98

 Array multiplier
• Combining generation of partial product and
summation
• Identical cells in each row
• Example : 5x5 multiplication
– Inputs X ( x4 x3 x2 x1 x0) and A (a4 a3 a2 a1 a0)

Digital Logic Design:Combinational Circuits. 99

 5x5 Array multiplier
a 4 x0 a 3 x0 a 2 x0 a 1 x0 a 0 x0
0 0 0 0
Delay ~2N
Area: ~N2 a 4 x1 a 3 x1 a 2 x1 a 1 x1 a 0 x1

a 4 x2 a 3 x2 a 2 x2 a 1 x2 a 0 x2

a 4 x3 a 3 x3 a 2 x3 a 1 x3 a 0 x3

a 4 x4 a 3 x4 a 2 x4 a 1 x4 a 0 x4

p3 p2 p1 p0
p4
p9 p8 p6 p5
p7
100
 Summary
• Efficient design of multipliers
• Are these multipliers valid for unsigned as well
as signed numbers?
– No, for signed number, partial products need to
be signed extended
– Need some modification in the design

Digital Logic Design:Combinational Circuits. 101

 M3.08
Iterative circuits

Digital Logic Design:Combinational Circuits. 102

 Iterative circuits
• One cell is designed, it iteratively used with
different inputs
• Applications
– Adder
– Comparator
– Parity checkers
– Pattern recognition

Digital Logic Design:Combinational Circuits. 103

 Comparator design
• Input: two numbers, A and B of size N
• Output
– G = 1, if A > B
– L = 1, if A < B
– E = 1, if A = B
• Design
– Option 1: Use subtractor

Digital Logic Design:Combinational Circuits. 104

 Comparator design – option 2
• Write the complete binary equation for each
output
• Comparing from left to right
• For example for 4 bit
• G = a3 b3’ + (a3  b3) a2 b2’ + (a3  b3) (a2  b2)
a1b1’ + (a3  b3) (a2  b2) (a1  b1) a0b0’

Digital Logic Design:Combinational Circuits. 105

 Iterative comparator design
• Start comparing from right to left
• ith block comparator:
gi+1 = ai bi’ + gi(aibi + ai’bi’)
ai bi
ei+1 = ei(aibi + ai’bi’)
gi gi+1

ei 1 bit ei+1 li+1 = ai’bi + li(aibi + ai’bi’)

Comparator
li li+1

Digital Logic Design:Combinational Circuits. 106

 N bit comparator
Bn-1 An-1 B2 A2 B1 A0 B0 A0

G g0
E Compn-1 Comp2 Comp1 Comp0 e0
L l0

Boundary conditions: What should be g0, e0 and l0 ?

Option 1: connect g0, e0 and l0 to ‘0’

Option 2: Design simpler Comp0 design:

g1 = a0 b0’ e1 = a0b0 + a0’b0’ l1 = a0’b0

Digital Logic Design:Combinational Circuits. 107

 Parity Generator/detector
• Even parity is ‘1’ if number of 1’s are even

a0 a1 ai a15

p0 p1 p2 pi pi+1 p15 p16

PG PG PG PG

pi+1 = pi ai’ + pi’ ai

Boundary condition
p1 = a0’
Digital Logic Design:Combinational Circuits. 108
 Sequence detector
• Example
yi = 1 if {xi, xi-1, xi-2, xi-3} == 1101
0 otherwise
• Designing a system irrespective if input size.
• Example input and output. Rightmost bit is x0
– 101101101010 - Input
– 001001000000 - Output

Digital Logic Design:Combinational Circuits. 109

 Iterative design
• At input of every cell if we know how many
bits of pattern have matched already
– We can know how many bits matched including
current input
• Two bit input ci
– ci = 00 if no bit matched till now
– ci = 01 if one bit matched till now
– ci = 10 if two bits matched till now
– ci = 11 if three bits matched till now

Digital Logic Design:Combinational Circuits. 110

Sequence detector: Pattern “1101”
xi
ci xi ci+1 yi
ci+1
00 0 00 0 ci
SD
00 1 01 0
01 0 10 0 yi

01 1 01 0
10 0 00 0 ci+10 =ci0 xi + ci1ci0’ xi
ci+11 = xi
10 1 11 0 yi = ci0 ci1 xi
11 0 10 0
11 1 01 1

Digital Logic Design:Combinational Circuits. 111

 Other examples
• Sum of an array X
– Z = ∑ i Xi
• Dot product of two arrays X and Y
– Z = ∑iXi Yi

Digital Logic Design:Combinational Circuits. 112

 Summary of M3.08
• Iterative design could be simplistic and
powerful way of designing circuits
• Overall approach is
– Focus on one cell that is generic
– Decide its input and outputs
– Truth table or boolean equations can be used to
design, once input is decided

Digital Logic Design:Combinational Circuits. 113

 Summary of M3
• Overall we learnt
– How to write Boolean equations given a problem
statement
– Commonly used combinational circuit: Mux, Demux,
encoder, decoder
– Arithmetic circuits: Adder, multiplier, comparator
– Iterative circuits
• Given a problem, we can use these in original
form or modified form according to requirements

Digital Logic Design:Combinational Circuits. 114