Transcript + 1 - UniMAP Portal

CHAPTER 2
Digital Combinational
Logic/Arithmetic Circuits
Problem Solving 1
 Design a logic circuit whose output is HIGH when at
least 2 of inputs W,X and Y are LOW.
INPUTS
OUTPUT
W
X
Y
D
0
0
0
1
0
0
1
1
0
1
0
1
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
0
1
1
1
0
Problem Solving 2
 Design a logic circuit whose output is HIGH when a
majority of inputs A, B, C and D are LOW. Assume the
output as DON’T CARE when the total input of HIGH and
LOW is equivalent. Provide the appropriate truth table,
Boolean expression and logic circuit.
Digital Combinational
Logic/Arithmetic Circuits



Arithmetic

Adder/Subtractor
Converters

Decoder/Encoder/Comparator

Multiplexer/ Demultiplexer
Parity Circuits

Generators

Checkers
Basic Combinational Logic AND-OR Logic
AND-OR logic produces a SOP expression
Basic Combinational Logic AND-OR Logic
A
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
INPUTS
B
C
0
0
0
0
0
1
0
1
1
0
1
0
1
1
1
1
0
0
0
0
0
1
0
1
1
0
1
0
1
1
1
1
D
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
AB
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
CD
0
0
0
1
0
0
0
1
0
0
0
1
0
0
0
1
OUTPUT
X
0
0
0
1
0
0
0
1
0
0
0
1
0
0
0
1
For a 4-input AND-OR logic circuit, output X is HIGH(1) if both input A
and input B are HIGH(1) or both input C and input D are HIGH(1).
Basic Combinational Logic AND-OR-Invert Logic
AND-OR invert logic produces a POS expression
For a 4-input AND-OR invert logic circuit, output X is LOW(0) if both input
A and input B are HIGH(1) or both input C and input D are HIGH(1).
Basic Combinational Logic Exclusive-OR logic (XOR)
A combination of two AND gates, one OR
gates, and two inverters.
XOR Truth Table
A
B
X
0
0
0
0
1
1
1
0
1
1
1
0
By looking at truth table, output is HIGH(1) when
the two input are at opposite level.
X=AB + AB
=A + B
Summary
Inputs Output
Exclusive-NOR Logic (XNOR)
The complement of XOR is XNOR.
The truth table for an exclusive-NOR gate is
Notice that the output is HIGH whenever A and B
are at the same level.
The Boolean expression is
A
0
0
1
1
B
0
1
0
1
X
1
0
0
1
X = AB + AB
The circuit can be drawn as
A
Symbols:
X
B
=1
Distinctive shape
outline
Floyd, Digital Fundamentals, 10th ed
Rectangular
© 2009 Pearson Education, Upper Saddle River, NJ 07458. All Rights
Reserved
Problem Solving 3
How to solve this?
Summary
Universal Gates
NAND gates are sometimes called universal gates because they
can be used to produce the other basic Boolean functions.
A
A
B
A
One NAND gate can be Inverter
AB
Two NAND gates can be an AND gate
A
A
A+B
A+B
B
B
Three NAND gates can be an OR gate
Four NAND gates can be a NOR gate
Floyd 10th ed page 255
Floyd, Digital Fundamentals, 10th ed
© 2009 Pearson Education, Upper Saddle River, NJ 07458. All Rights
Reserved
Summary
Universal Gates
NOR gates are also universal gates and can form all of the basic
gates.
A
A
B
A
One NOR can be an Inverter
A+ B
Two NOR can be an OR gate
A
A
AB
AB
B
Three NOR can be an AND gate
Floyd, Digital Fundamentals, 10th ed
B
Four NOR can be a NAND gate
© 2009 Pearson Education, Upper Saddle River, NJ 07458. All Rights
Reserved
Problem Solving 4
 Given an expression X = A + B
a) Use NAND gates
b) Use NOR gates
to implement the expression.
(Taken from Section 3 Checkup Floyd 10th ed. Pg 257)
Complements(1)
 Allow the representation of negative numbers.
 Complements are used in digital computers for
simplifying the subtraction operation.
 Two types of complement for binary numbers:
 One’s complement
 Two’s complement
 The 1’s complement of a binary number is formed by
changing 1’s to 0’s and 0’s to 1’s
 Example:
 The 1’s complement of 1011000 is 0100111
 The 1’s complement of 0101101 is 1010010
Complements(2)
 The 2’s complement of a binary number is formed
by adding 1 to the 1’s complement.
2’s complement = (1’s complement) + 1
Complements(3)
 Alternative method to find 2’s complement:
 Start at the right with the LSB and write the
bits as they are up to including the first 1.
 Do 1’s complements of the remaining bits.
Example:
 The 2’s complement of 1101100 is 0010100
 The 2’s complement of 0110111 is 1001001
Binary Arithmetic Operations
Subtraction
Two binary numbers are subtracted by subtracting
each pair of bits together with borrowing, where
needed.
Example:
X:
229
Y: - 46
183
0
1
- 0
1
0
1
0
0
1
1
1
1
1 1 1
001
0 1 1
1 0 1
1
0
1
1
0
1
0
1
Borrow
Combinational Arithmetic Circuits
Addition:
 Half
Adder (HA)
 Full Adder (FA)
 Carry Ripple Adders
Subtraction:
 Half
Subtractor
 Full Subtractor
 Borrow Ripple Subtractors
 Subtraction using adders
Half Adder
 Adding two single-bit binary values, X, Y produces a sum S bit and
a carry out C-out bit.
 This operation is called half addition and the circuit to realize it is
called a half adder.
S(X,Y) = S (1,2)
S = X’Y + XY’
S = XY
Half Adder Truth Table:
Outputs
Inputs
X
0
0
1
1
Y
0
1
0
1
S
0
1
1
0
X
Half
Y
Adder
C-out
0
0
0
1
S
C-OUT
C-out(x, y, C-in) = S (3)
C-out = XY
X
Y
Sum S
C-out
Full Adder(1)
 Adding two single-bit binary values, X, Y
with a carry input bit C-in produces a
Sum S
XY
Y
0
0
1
1
0
0
1
1
C-in
0
1
0
1
0
1
0
1
01
0
11
10
6
2
0
4
1
1
1
3
1
Full Adder Truth Table
Inputs
00
C-in
sum bit S and a carry out C-out bit.
X
0
0
0
0
1
1
1
1
X
5
7
1
1
C-in
Outputs
S
0
1
1
0
1
0
0
1
C-out
0
0
0
1
0
1
1
1
Y
S = X’Y’(C-in) + X’Y(C-in)’ + XY’(C-in)’ + XY(C-in)
S = X  Y  (C-in)
Carry C-out
X
XY
00
C-in
0
01
11
6
2
0
4
1
1
1
10
3
5
7
1
1
1
S(X,Y, C-in) = S (1,2,4,7)
C-out(X, Y, C-in) = S (3,5,6,7)
Y
C-out = XY + X(C-in) + Y(C-in)
C-in
Full Adder(2)
Full Adder Circuit Using AND-OR:
X
X
X’
Y
Y
Y’
C-in
C-in’
C-in
X
Y
X
XY
Y
C-out
Full
Adder
C-in
X
XC-in
C-in
Y
S
C-in
YC-in
C-out
Full Adder(3)
Full Adder Circuit Using XOR:
X
Sum S
Y
C-in
X
C-out
Y
Full
Adder
X
XY
Y
C-in
X
XC-in
C-in
S
Y
C-in
YC-in
C-out
n-bit Carry Ripple Adders
 An n-bit adder used to add two n-bit binary numbers can built by connecting in
series n full adders.
 Each full adder represents a bit position j (from 0 to n-1).
 Each carry out C-out from a full adder at position j is connected to the carry
in C-in of the full adder at the higher position j+1.
 The output of a full adder at position j is given by:
Sj = Xj Å Yj Å Cj
Cj+1 = Xj . Yj + Xj . Cj + Y . Cj
 In the expression of the sum Cj must be generated by the full adder at the lower
position j-1.
 The propagation delay in each full adder to produce the carry is equal to two
gate delays = 2 D
 Since the generation of the sum requires the propagation of the carry from the
lowest position to the highest position , the total propagation delay of the adder
is approximately:
Total Propagation delay
= 2 nD
4-bit Carry Ripple Adder
Inputs to be added
X3X2X1X0
Adds two 4-bit numbers:
X = X3 X2 X1 X0
Y = Y3 Y2 Y1 Y0
producing the sum S = S3 S2 S1 S0 ,
C-out = C4 from the most significant
position j=3
Total Propagation delay
C4
C-out
= 2 nD = 8D
Y3Y2Y1Y0
4-bit
Adder
C-in
C0 =0
S3 S2 S1 S0
or 8 gate delays
Sum Output
Data inputs to be added
X3
C4
C-out
Y3
Full
C3
C-in
Adder
S3
X2
C-out
Y2
Full
C2
C-in
Adder
X1
C-out
S2
Full
C-in
Adder
S1
Sum output
Y1
X0
C1
C-out
Y0
Full
C-in
Adder
S0
C0 =0
Larger Adders
 Example: 16-bit adder using 4, 4-bit adders
 Adds two 16-bit inputs X (bits X0 to X15), Y (bits Y0 to Y15) producing a 16-bit
Sum S (bits S0 to S15) and a carry out C16 from most significant position.
Data inputs to be added X (X0 to X15) , Y (Y0-Y15)
X3X2X1X0
C16
C-out
Y3Y2Y1Y0
X3X2X1X0
Y3Y2Y1Y0
4-bit
4-bit
C12
C8
C-in
C-in
C-out
Adder
Adder
S3 S2 S1 S0
S3 S2 S1 S0
X3X2X1X0
C-out
Y3Y2Y1Y0
4-bit
C-in
Adder
S3 S2 S1 S0
X3X2X1X0
C4
C-out
Y3Y2Y1Y0
4-bit
C-in
Adder
S3 S2 S1 S0
Sum output S (S0 to S15)
Propagation delay for 16-bit adder = 4 x propagation delay of 4-bit adder
= 4 x 2 nD = 4 x 8D = 32 D
or
32 gate delays
C0 =0
Negative Binary Number Representations
 Signed-Magnitude Representation:
 For an n-bit binary number:
Use the first bit (most significant bit, MSB) position to
represent the sign where 0 is positive and 1 is negative.
Ex:
Sign
1 1 1 1 1 1 1 12 = - 12710
Magnitude
 Remaining n-1 bits represent the magnitude which may range from:
-2(n-1) + 1 to 2(n-1) – 1
 This scheme has two representations for 0; i.e., both positive and negative 0:
for 8 bits: 00000000, 10000000
 Arithmetic under this scheme uses the sign bit to indicate the nature of the
operation and the sign of the result, but the sign bit is not used as part of the
arithmetic.
Half Subtractor
 Subtracting a single-bit binary value Y from anther X (I.e. X -Y ) produces a
difference bit D and a borrow out bit B-out.
 This operation is called half subtraction and the circuit to realize it is called
a half subtractor.
Half Subtractor Truth Table:
Outputs
Inputs
X
0
0
1
1
Y
0
1
0
1
D(X,Y) = S (1,2)
D = X’Y + XY’
D = XY
D B-out
0
0
1
1
1
0
0
0
B-out(X, Y) = S (1)
B-out = X’Y
X
X
Half
Y
Subtractor
D
B-OUT
Y
Difference
D
B-out
Full Subtractor(1)
 Subtracting two single-bit binary values, Y,
B-in from a single-bit value X produces a
Difference D
X
XY
00
B-in
01
0
10
6
2
0
difference bit D and a borrow out B-out
bit. This is called full subtraction.
11
4
1
3
1
1
1
5
7
1
1
B-in
Full Subtractor Truth Table:
Y
Inputs
X
0
0
0
0
1
1
1
1
Y
0
0
1
1
0
0
1
1
Outputs
B-in
0
1
0
1
0
1
0
1
D
0
1
1
0
1
0
0
1
B-out
0
1
1
1
0
0
0
1
D = X’Y’(B-in) + X’Y(B-in)’ + XY’(B-in)’ + XY(B-in)
D = X  Y  (B-in)
Borrow B-out
X
XY
00
B-in
0
01
2
0
10
6
4
7
5
1
3
1
1
11
1
1
1
Y
S(X,Y, B-in) = S (1,2,4,7)
B-out(x, y, B-in) = S (1,2,3,7)
B-out = X’Y + X’(B-in) + Y(B-in)
B-in
Full Subtractor(2)
X’
Y’
B-in
X
X’
X
X’
Y
B-in’
Y
Y’
Y
B-in’
X
Y
B-in’
X’
X
X’YB-in’
Difference D
X
Y
B-in
B-in’
B-in
X’Y’B-in
Y
XY’B-in’
XYB-in
X’Y
Y
B-out
Full
Subtractor
D
X’
B-in
X’B-in
B-in
Y
B-in
YB-in
Full Adder Circuit Using AND-OR
B-out
Full Subtractor(3)
X
X
B-out
Y
Full
Subtractor
Difference D
Y
B-in
X’
B-in
X’Y
Y
X’
D
X’B-in
B-in
Y
B-in
YB-in
Full Subtractor Circuit Using XOR
B-out
n-bit Subtractors
An n-bit subtractor used to subtract an n-bit number Y from
another n-bit number X (i.e X-Y) can be built in one of two
ways:
 By using n full subtractor and connecting them in series,
creating a borrow ripple subtractor:
 Each borrow out B-out from a full subtractor at position j is
connected to the borrow in B-in of the full subtractor at the higher
position j+1.
 By using an n-bit adder and n inverters:
 Find two’s complement of Y by:
 Inverting all the bits of Y using the n inverters.

Adding 1 by setting the carry in of the least significant position to 1
 The original subtraction (X - Y) now becomes an addition of
X to two’s complement of Y using the n-bit adder.
4-bit Borrow Ripple Subtractor
Inputs
Subtracts two 4-bit numbers:
Y = Y3 Y2 Y1 Y0 from
X = X3 X2 X1 X0
Y = Y3 Y2 Y1 Y0
producing the difference D = D3 D2 D1
D0 ,
B-out = B4 from the most significant
position j=3
X3X2X1X0
B4
B-out
Y3Y2Y1Y0
4-bit B-in
Subtractor
B0 =0
D3 D2 D1 D0
Difference Output D
Data inputs to be subtracted
X3
B4
B-out Full
Y3
B-in
X2
B3
B-out Full
Y2
B-in
Subtractor
Subtractor
D3
D2
X1
B2
B-out Full
Y1
B-in
Subtractor
D1
Difference output D
X0
B1
B-out Full
Y0
B-in
Subtractor
D0
B0 =0
4-bit Subtractor Using 4-bit Adder
Inputs to be subtracted
Y3
X3 X2 X1
C4
C-out
Y2
Y1
Y0
X0
4-bit
Adder
C-in
S3
S2
S1
S0
D3
D2
D1
D0
Difference Output
C0 = 1
Examples:
 Add the two 4-bit binary numbers A = 1101 and B = 0111.
Then show that the parallel binary adder adds the two
numbers correctly.
 Use 2’s compliment addition to subtract 12 from 25. Then
draw subtraction process by using a binary adder.
 Determine the binary output for the parallel binary adder
for the inputs shown.
1
C4
C-out
0
Full
C3
C-in
Adder
S3
1
C-out
1
Full
C2
C-in
Adder
0
C-out
S2
1
Full
C-in
Adder
S1
Sum output
1
C1
C-out
1
Full
C-in
Adder
S0
C0 = gnd
Next lecture….
 Converters
~ Comparator
~ Decoder
~ Encoder
~ Code converter