Digital Systems

and
VLSI Design
By
VIJAYA PRAKASH A M
Modules
1. Review of digital logic circuits design
2. MOS transistor theory
3. Circuit characterization
4. CMOS circuit and logic design
5. Memory, registers and system timing
aspects
6. Practical realities and ground rules
Modules
1. Review of digital logic circuits design
2. MOS transistor theory
3. Circuit characterization
4. CMOS circuit and logic design
5. Memory, registers and system timing
aspects
6. Practical realities and ground rules
Review of Digital Logic Circuits Design
Combinational Circuits - Design steps
Sequential Circuits - Design steps
Finite State Machines
Review of Logic Families
Combinational Circuit
There are two types of digital circuits:
Combinational circuit
Sequential circuit
Combinational Circuit performs an operation that
can be specified logically by a set of Boolean
functions
A combinational circuit consists of logic gates
whose outputs at any instant of time are
determined from the present combinations of input
5
Combinational Circuit
6
Combinational circuits are circuits without memory where the
outputs are obtained from the inputs only. A n-input m-output
combinational circuit is of the form
where, oi = f (i1; : : : ; in);
Combinational Circuits
Combinational circuit performs an operation that can be
specified logically by a set of Boolean functions.
It consists of logic gates whose outputs at any time are
determined from the present combinations of inputs.
Combinational circuits are circuits without memory where the
outputs are obtained from the inputs only.
An n-input m-output combinational circuit is as shown.
Combinational Circuit
Example:
Half/Full adder/substractor
- Binary ripple adder/substractor
- Look-ahead carry adder
- Code converter, Encoder/Decoder
- Magnitude comparator
- Multiplexer/Demultiplexer
- Read-only memory
- Programmable logic array
- Programmable array logic
- Arithmetic logic unit
8
Combinational Circuit Design
Design Procedure:
1. Determine the required number of inputs
and outputs
2. Derive the truth table that defines the
required relationship
3. Obtain the simplified Boolean functions for
each outputs
4. Draw the logic diagram and verify its
correctness
9
Arithmetic Adders
Addition: a fundamental operation
Basic block of most arithmetic operations
Address calculation
Faster, faster and faster
How?
Architectural level optimization
Gate-level optimization
Speed/area trade-off
11
Half Adder
The half adder accepts two binary digits on its input and produce
two binary digits on its outputs, the sum bit and carry bit as
shown above.
S = X Y
C = XY
12
Full Adder
The full adder accepts three inputs and generates a sum
and carry out put.
Three inputs. Third is C
in
Two outputs: sum and carry
Full Adder
13
14
K Map for S
What is this?
15
K Map for C
Carry out:
Logic diagram
16
17
Two Half Adders (and an OR)
LOGIC CIRCUIT
Four bit parallel adder (RCA)
18
Four bit parallel adder (Ripple carry adder)
It is possible to create a logical circuit using multiple full adders to add N-
bit numbers. Each full adder inputs a C
in
, which is the C
out
of the
previous adder. This kind of adder is a ripple carry adder, since each
carry bit "ripples" to the next full adder. Note that the first (and only
the first) full adder may be replaced by a half adder.
In Ripple Carry Adder
Multiple full adders with carry ins and carry outs
chained together
Small Layout area
Large delay time
If the delay for each full adder is 8ns then the total delay for four bit parallel adder is
32ns.
19
Subtractor
20
Four bit subtractor
21
Four bit parallel adder/Subtractor
22
Serial Adder with Accumulator
Block Diagram for Serial Adder with Accumulator
23
Serial Adder with Accumulator
: Operation of Serial Adder
X Y C
i
S
i
C
i
+
t
0
t
1
t
2
t
3
t
4
0101
0010
0001
1000
1100
0111
1011
1101
1110
0111
0
1
1
1
0
0
0
1
1
(1)
1
1
1
0
(0)
24
Carry-Look ahead Adder: Idea
New look: carry propagation
Idea:
Try to predict C
k
earlier than T
c
*k
Instead of passing through k stages, compute C
k
separately
using 1-stage logic
Carry propagation: an example
Bit position
Carry
A
B
Sum
7 6 5 4 3 2 1 0
1 0 0 1 1 1 1
0 1 0 0 1 1 0 1 +
0 1 0 0 0 1 1 1
1 0 0 1 0 1 0 0
Carry-Look ahead Adder: Idea
In the example:
By looking at (A4, B4), we can say for sure that C5=0, no matter what
C4 is.
By looking at (A2, B2), we can say for sure that C3=1.
C3, generated by (A2, B2) (or by A0, B0 if you wish), propagated as
far as C4, and then got killed by (A4, B4)
The idea is, can we look at A(3..0) and B(3..0) and determine the value of
C4 in one shot?
Design of Fast Adders (CLA)
Carry lookahead logic uses the concepts of generating and propagating carries. Although in
the context of a carry lookahead adder, it is most natural to think of generating and
propagating in the context of binary addition, the concepts can be used more generally than
this. In the descriptions below, the word digit can be replaced by bit when referring to binary
addition.
In carry look ahead adder ,the carry signals are calculated in advance , based on the input
signals.
Carry C
i+1
= X
i
Y
i
+ Y
i
C
i
+ C
i
X
i
= X
i
Y
i
+ C
i
(X
i
Y
i
)
= G
i
+ C
i
P
i
. (Generate Carry + C
i
* Propagate Carry)
Where G
i
is carry generate function and P
i
is carry propagate function
27
Carry C
i+1
= G
i
+ C
i
P
i
i.e. C
i
= (G
i-1
+ P
i-1
C
i-1
) &
C
i-1
= (G
i-2
+ P
i-2
C
i-2
).
Design of 4-bit CLA
28
P
i
C
i
+ G
i =
C
i +1
Si = P
i
C
i

P
i
G
i
A
i
Bi
C
i
Design of 4-bit CLA
29
Design of 4-bit CLA
The carry bits are the look-ahead carry bits.they are
expressed in terms of generate and propagate functions
along with initial carry C0.Thus the sum and carry from
the any stage can be calculated with out waiting for the
carry to ripple through all the previous stages.
The disadvantage of the carry-look-ahead is that the look
ahead carry logic is not simple.it gets completed for more
than 4 bits. For that reason carry look ahead adders are
usually implemented as 4-bit modules and are used in a
hierarchical structure to realize adders that have multiple
of 4 bits.
30
Design of 4-bit CLA
31
Design of 4-bit CLA
32
Carry Look-ahead Adder
34
16 bit carry-look ahead adder
Summary: Carry Look ahead Adder
CLA compared to ripple-carry adder:
Faster (4 times) ?,
but delay still linear (w.r.t. # of bits)
Larger area:
P & G signal generation
Carry generation circuits
Carry generation ckt. for each bit position (no re-use)
Limitation:
cannot go beyond 4 bits of look-ahead
Large p, g fan-out slows down carry generation
Carry select adder
The Carry select adder generally consists of two Ripple Carry
Adder and one multiplexer. Adding two n-bit numbers with a
Carry select adder is done with two adders (therefore 2 Ripple
Carry Adder) in order to perform the calculation twice, one time
with the assumption of the carry being zero and the other being
one. After the two results are calculated the correct sum, as well
as the correct carry is then selected with the multiplexer, which
is usually controlled by the carry from the previous Ripple carry
adder. multiplexers are used to select the correct one of both
precalculated partial sums. Also, the resulting carry-out is
selected and propagated to the next carry-select block.
36
4 bit Carry select adder
37
2 bit Carry select adder
38
Parity generator
Binary information is normally handle by a digital system in a group of bits called
words. A word always contains either an even or an odd number of ones. A parity
bit is attached to the group of information bits in order to make the total number of
1s even or always odd. An even parity bit makes the total number of ones even, and
an odd parity bit makes total odd.
The parity bit is attached to the at either
beginning or at the end of the code.
note that total number of 1s,including
the parity bit,is always even for even
parity and always odd for odd parity.
Table : 8421 BCD code with parity bits.
39
Even
parity
Odd
parity
P 8421 P 8421
0 0000 1 0000
1 0001 0 0001
1 0010 0 0010
0 0011 1 0011
1 0100 0 0100
0 0101 1 0101
0 0110 1 0110
1 0111 0 0111
1 1000 0 1000
0 1001 0 1001
Parity bits and parity checking
40
Parity generator/checker
41
Parity checking
42
Three bit odd parity generator
43
Three bit odd parity generator
44
Three bit odd parity generator
45
Three bit odd parity generator
46
3-bit even parity generator
47
48
Digital Comparators
Digital or Binary Comparators are made up from standard AND, NOR and
NOT gates that compare the digital signals at their input terminals and
produces an output depending upon the condition of the inputs. For
example, whether input A is greater than, smaller than or equal to input B
etc.
Digital Comparators can compare a variable or unknown number for
example A (A1, A2, A3, .... An, etc) against that of a constant or known
value such as B (B1, B2, B3, .... Bn, etc) and produce an output depending
upon the result. For example, a comparator of 1-bit, (A and B) would
produce the following three output conditions.
A>B; A<B; A=B
This is useful if we want to compare two values and produce an output
when the condition is achieved. For example, produce an output from a
counter when a certain count number is reached.
49
Equality Comparator
XNOR
X
Y
Z
Z = not(x y)
X Y Z
0 0 1
0 1 0
1 0 0
1 1 1
50
4-Bit Equality Comparator
A 0
A 1
A 2
A 3
B 0
B 1
B 2
B 3
A _ E Q_ B
C0
C1
C3
C2
FIELD A = [A0..3];
FIELD B = [B0..3];
FIELD C = [C0..3];
51
One bit comparator
52
You may notice two distinct features about the comparator from the above truth table.
Firstly, the circuit does not distinguish between either two "0" or two "1"'s as an output A =
B is produced when they are both equal, either A = B = "0" or A = B = "1". Secondly, the
output condition for A = B resembles that of a commonly available logic gate, the
Exclusive-NOR or Ex-NOR gate giving Q = AB
Magnitude comparator
53
Magnitude comparator
54
Four bit Magnitude comparator
55
Design Approaches
The truth table 2
2n
entries - too cumbersome for larger n
use inherent regularity of the problem reduce design
efforts reduce human errors
Four bit Magnitude comparator
56
Four bit Magnitude comparator
57
Four bit Magnitude comparator
58
Four bit Magnitude comparator
59
Four bit Magnitude comparator
60
61
The Binary Multiplication
x
+
Partial products
Multiplicand
Multiplier
Result
1 0 1 0 1 0
1 0 1 0 1 0
1 0 1 0 1 0
1 1 1 0 0 1 1 1 0
0 0 0 0 0 0
1 0 1 0 1 0
1 0 1 1
Multiplication
Example:
M x N-bit multiplication
Produce N M-bit partial products
Sum these to produce M+N-bit product
1100 : 12
10
0101 : 5
10
1100
0000
1100
0000
00111100 : 60
10
multiplier
multiplicand
partial
products
product
General Form
Multiplicand: Y = (y
M-1
, y
M-2
, , y
1
, y
0
)
Multiplier: X = (x
N-1
, x
N-2
, , x
1
, x
0
)
Product:
1 1 1 1
0 0 0 0
2 2 2
M N N M
j i i j
j i i j
j i i j
P y x x y

+
= = = =
| |
| |
= =
|
|
\ .
\ .

x
0
y
5
x
0
y
4
x
0
y
3
x
0
y
2
x
0
y
1
x
0
y
0
y
5
y
4
y
3
y
2
y
1
y
0
x
5
x
4
x
3
x
2
x
1
x
0
x
1
y
5
x
1
y
4
x
1
y
3
x
1
y
2
x
1
y
1
x
1
y
0
x
2
y
5
x
2
y
4
x
2
y
3
x
2
y
2
x
2
y
1
x
2
y
0
x
3
y
5
x
3
y
4
x
3
y
3
x
3
y
2
x
3
y
1
x
3
y
0
x
4
y
5
x
4
y
4
x
4
y
3
x
4
y
2
x
4
y
1
x
4
y
0
x
5
y
5
x
5
y
4
x
5
y
3
x
5
y
2
x
5
y
1
x
5
y
0
p
0
p
1
p
2
p
3
p
4
p
5
p
6
p
7
p
8
p
9
p
10
p
11
multiplier
multiplicand
partial
products
product
Array Multiplier
y
0
y
1
y
2
y
3
x
0
x
1
x
2
x
3
p
0
p
1
p
2
p
3
p
4
p
5
p
6
p
7
B
A Sin Cin
Sout Cout
B A
Cin Cout
Sout
Sin
=
CSA
Array
CPA
critical path
B A
Sout
Cout Cin Cout
Sout
=
Cin
B A
4*4 Array Multiplier
X
3
X
2
X
1
X
0
Multiplicand
Y
3
Y
2
Y
1
Y
0
Multiplier
X
3
Y
0
X
2
Y
0
X
1
Y
0
X
0
Y
0
Partial product 0
X
3
Y
1
X
2
Y
1
X
1
Y
1
X
0
Y
1
Partial Product 1
C
12
C
11
C
10
1
st
row of carries
C
13
S
13
S
12
S
11
S
10
1
st
row of sums
X
3
Y
2
X
2
Y
2
X
1
Y
2
X
0
Y
2
partial product 2
C
22
C
21
C
20
2
nd
row of carries
C
23
S
23
S
22
S
21
S
20
2
nd
row of sums
X
3
Y
3
X
2
Y
3
X
1
Y
3
X
0
Y
3
partial product 3
C
32
C
31
C
30
3
rd
row of carries
C
33
S
33
S
32
S
31
S
30
3
rd
row of sums
P
7
P
6
P
5
P
4
P
3
P
2
P
1
P
0
Final Product
65
4*4 Array Multiplier
X
3
X
2
X
1
X
0
Multiplicand
Y
3
Y
2
Y
1
Y
0
Multiplier
X
3
Y
0
X
2
Y
0
X
1
Y
0
X
0
Y
0
Partial product 0
X
3
Y
1
X
2
Y
1
X
1
Y
1
X
0
Y
1
Partial Product 1
C
12
C
11
C
10
1
st
row of carries
C
13
S
13
S
12
S
11
S
10
1
st
row of sums
X
3
Y
2
X
2
Y
2
X
1
Y
2
X
0
Y
2
partial product 2
C
22
C
21
C
20
2
nd
row of carries
C
23
S
23
S
22
S
21
S
20
2
nd
row of sums
X
3
Y
3
X
2
Y
3
X
1
Y
3
X
0
Y
3
partial product 3
C
32
C
31
C
30
3
rd
row of carries
C
33
S
33
S
32
S
31
S
30
3
rd
row of sums
P
7
P
6
P
5
P
4
P
3
P
2
P
1
P
0
Final Product
66
67
4*4 Array Multiplier
Y
0
Y
1
X
3
X
2
X
1
X
0
X
3
HA
X
2
FA
X
1
FA
X
0
HA
Y
2 X
3
FA
X
2
FA
X
1
FA
X
0
HA
Z
1
Z
3
Z
6
Z
7
Z
5
Z
4
Y
3
X
3
FA
X
2
FA
X
1
FA
X
0
HA
Z
2
Z
0
4*4 Array Multiplier
The 4*4 array multiplier requires 16 AND gates, 8 full
adders, and 4 half adders.
In array multiplier the propagation delay is more.
If tad is the worst case delay through an adder,and tg is the
longest AND gate delay then the worst case to complete
the multiplication is 8ad+t8.
In general,an n-bit by n-bit array multiplier requires n*n
AND gates, n(n-2) full adders and n-half adders.
For an nXn array multiplier, the longest path from input to
output goes through 2n adders, and the corresponding
worst-case multiply time is 2nt
ad
+ t
8
.
68
Design of a Binary Multiplier
69
Binary multiplication requires only shifting and adding. For example,
multiplication 13
10
by 05
10
in binary:
Multiplicand 1 1 0 1 (13)
Multiplier 0 1 0 1 (05)
Partial Product 1 1 0 1
0 0 0 0
0 1 1 0 1
1 1 0 1
1 0 0 0 0 0 1
0 0 0 0
0 1 0 0 0 0 0 1 (65)
Note that each partial product is either the multiplicand (1101) shifted over by
the appropriate number of places or zero.
Multiplication of two 4-bit numbers requires a 4-bit multiplicand register, a 4-
bit multiplier register, a 4-bit full adder, and an 8-bit register for the product
Block diagram of Binary Multiplier
70
Operation of multiplier
71
Multiplication Steps:
Initial contents of product register 0 0 0 0 0 0 1 0 1 M (5)
(add multiplicand since M=1) 1 1 0 1
after addition 0 1 1 0 1 0 1 0 1
after shift 0 0 1 1 0 1 0 1 0M
(skip addition since M=0) 0 0 0 0
after addition 0 0 1 1 0 1 0 1 0
after shift 0 0 0 1 1 0 1 0 1M
(add multiplicand since M = 1) 1 1 0 1
after addition 1 0 0 0 0 0 1 0 1
after shift 0 1 0 0 0 0 0 1 0
(skip addition since M=0)
after shift (final answer) 0 0 1 0 0 0 0 0 1
Combinational Shifters
Useful for arithmetic operations, bit field
extraction, etc.
Latch-based shift register can shift only one bit per
clock cycle.
A multiple-shift shifter requires additional
connectivity.
Barrel shifter
Can perform n-bit shifts in a single cycle.
Efficient layout.
Does require transmission gates and long wires.
Barrel shifter structure
Accepts 2n data inputs and n control signals,
producing n data outputs.
d
a
t
a

1
d
a
t
a

2
n bits
n bits
o
u
t
p
u
t
n bits
Barrel shifter operation
Selects arbitrary contiguous n bits out of 2n input
buts.
Examples:
right shift: data into top, 0 into bottom;
left shift: 0 into top, data into bottom;
rotate: data into top and bottom.
Barrel shifter cell
Barrel shifter in action