Transcript Combinational Logic

Combinational Logic
1
Combinational Circuits
n binary
inputs
Combinational
circuit
(logic gates)
m binary
outputs
– n input bits  2n possible binary input combinations
– For each possible input combination, there is one
possible output value
• truth table
• Boolean functions (with n input variables)
– Examples: adders, subtractors, comparators,
decoders, encoders, and multiplexers.
2
Possible Design Steps
1. Find out the number of inputs and outputs
2. Derive the truth table that defines the
required relationship between inputs and
outputs
3. Obtain a simplified Boolean function for each
output
4. Draw the logic diagram
5. Verify the correctness of the design
3
Example: Design Process
• BCD-to-2421 Converter
• Verbal specification:
– Given a BCD digit (i.e. {0, 1, …, 9}), the circuit computes
2421 code equivalent of the decimal number
• Step 1: how many inputs and how many outputs?
– four inputs and four outputs
• Step 2:
–
–
–
–
Obtain the truth table
0000  0000
1001  1111
etc.
4
BCD-to-2421 Converter
• Truth Table
Inputs
Outputs
A
B
C
D
x
y
z
t
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
0
0
0
1
0
0
0
1
1
0
0
1
1
0
1
0
0
0
1
0
0
0
1
0
1
1
0
1
1
0
1
1
0
1
1
0
0
0
1
1
1
1
1
0
1
1
0
0
0
1
1
1
0
1
0
0
1
1
1
1
1
5
BCD-to-2421 Converter
• Step 3: Obtain simplified Boolean expression
for each output
A
B
C
D
0
0
0
0
• Output x:
0
0
0
1
CD
AB
00
01
00
01
11
10
0
0
0
0
0
1
1
1
11
x
x
x
10
1
1
x
x = BD + BC + A
x
x
x
0
0
0
0
1
0
0
0
0
1
1
0
0
1
0
0
0
0
1
0
1
1
0
1
1
0
1
0
1
1
1
1
1
0
0
0
1
1
0
0
0
1
The rest
X
6
Boolean Expressions for Outputs
CD
AB
00
01
11
10
CD
AB
00
01
11
10
• Output y:
00
01
11
10
0
1
0
0
0
1
0
1
A
B
C
D
y
z
0
0
0
0
0
0
0
0
0
1
0
0
X
1
X
1
X
X
X
X
0
0
1
0
0
1
0
0
1
1
0
1
0
1
0
0
1
0
0
1
0
1
0
1
0
1
1
0
1
0
0
1
1
1
1
0
1
0
0
0
1
1
1
0
0
0
1
1
X
X
• Output z:
00
01
11
10
0
0
0
1
1
0
1
0
X
1
X
1
X
X
X
X
The rest
7
Boolean Expressions for Outputs
CD
AB
00
01
11
10
• Output t:
00
01
11
10
0
0
1
1
1
1
0
0
X
0
X
1
X
X
X
X
t=D
• Step 4: Draw the logic diagram
x = BC + BD + A
y = A + BD’ + BC
z = A + B’C + BC’D
A
B
C
D
T
0
0
0
0
0
0
0
0
1
1
0
0
1
0
0
0
0
1
1
1
0
1
0
0
0
0
1
0
1
1
0
1
1
0
0
0
1
1
1
1
1
0
0
0
0
1
0
0
0
1
The rest
X
8
Example: Logic Diagram
A
B
C
D
x = BC + BD + A
y = A + BD’ + BC
z = A + B’C + BC’D
t=D
9
Example: Verification
• Step 5: Check the functional correctness of the
logic circuit
• Apply all possible input combinations
• And check if the circuit generates the correct
outputs for each input combinations
• For large circuits with many input combinations,
this may not be feasible.
• Statistical techniques may be used to verify the
correctness of large circuits with many input
combinations
10
Design Example
1. Specification
–
–
–
–
BCD to Excess-3 code converter
Transforms BCD code for the decimal digits to
Excess-3 code for the decimal digits
BCD code words for digits 0 through 9: 4-bit
patterns 0000 to 1001, respectively
Excess-3 code words for digits 0 through 9: 4-bit
patterns consisting of 3 (binary 0011) added to
each BCD code word
Chapter 3 - Part 1
11
Design Example (continued)
2.
Formulation (Find truth table)
–
–
–
–
Conversion of 4-bit codes can be most easily
formulated by a truth table
Variables
Input BCD
Output Excess-3
- BCD:
ABCD
WXYZ
A,B,C,D
0000
0011
0001
0100
Variables
0010
0101
- Excess-3
0011
0110
W,X,Y,Z
0100
0111
0101
1000
Don’t Cares
0110
1001
- BCD 1010
0111
1010
to 1111
Chapter 3 - Part 1
12
1000
1001
1011
1011
Design Example (continued)
z
C
1
1
W = A + BC + BD
A
X = B C + B D + BC D
Y = CD + C D
0
1
3
4
5
7
X
12
1
X
13
8
X
X
15
9
6
1
B
1
4
5
X
14
11
0
12
A
10
1
X
1
1
4
X
12
8
1
5
X
13
1
9
1
8
3
2
7
6
X
X
X
X
15
9
B
14
11
10
D
C
1
1
13
D
0
A
1
2
1
X
x
Z=D
1
X
C
y
3
1
7
X
X
X
X
15
D
11
C
w
2
0
6
4
B
X
14
10
12
A
1
8
1
3
1
1
5
X
13
1
9
7
2
1
X
X
X
X
15
D
11
Chapter 3 - Part 1
6
14
10
13
B
Design Example (continued)
4. Technology Mapping
A
W
B
X
C
D
Y
Z
Chapter 3 - Part 1
14
Binary Adder/Subtractor
• (Arithmetic) Addition of two binary digits
– 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, and 1 + 1 = 10
– The result has two components
• the sum (S)
• the carry (C)
• (Arithmetic) Addition of three binary digits
0 +
0 +
0 =
0
0
0 +
0 +
1 =
0
1
0 +
1 +
0 =
0
1
0 +
1 +
1 =
1
0
1 +
0 +
0 =
0
1
1 +
0 +
1 =
1
0
1 +
1 +
0 =
1
0
1 +
1 +
1 =
1
1
15
Half Adder
• Truth table
x
y
C
S
0
0
0
0
0
1
0
1
1
0
0
1
1
1
1
0
x
S = x’y + xy’ = x  y
C = xy
S
y
HA
C
16
Full Adder 1/2
• A circuit that performs the arithmetic sum of
three bits
– Three inputs
– Two binary outputs
x
y
z
C
S
0
0
0
0
0
0
0
1
0
1
0
1
0
0
1
0
1
1
1
0
1
0
0
0
1
1
0
1
1
0
1
1
0
1
0
1
1
1
1
1
17
Full Adder 2/2
• Karnaugh Maps
yz
x
S
00
01
11
10
0
0
1
0
1
1
1
0
1
0
= xy’z’ + x’y’z + xyz + x’yz’
= ...
= ...
=xyz
yz
x
00
01
11
10
0
0
0
1
0
1
0
1
1
1
C = xy + xz + yz
Two level implementation
1st level: three AND gates
2nd level: One OR gate
18
Full Adder: Hierarchical Realization
• Sum
– S=xyz
• Carry
– C = xy + xy’z + x’yz
= (xy’ + x’y) z + xy
= (x  y) z + xy
yz
x
00
01
11
10
0
0
0
1
0
1
0
1
1
1
• This allows us to implement a full-adder using two
half adders.
x
y
HA
S
C
HA
S
C
xyz=S
C
z
19
Full Adder Using Half Adders
x
y
z
HA
HA
S
C
20
Integer Addition 1/2
• Binary adder:
– A digital circuit that produces the arithmetic sum of
two binary numbers
– A = (an-1, an-2, …, a1, a0)
– B = (bn-1, bn-2, …, b1, b0)
• A simple case: 4-bit binary adder
C4
a3
b3
a2
b2
a1
b1
a0
b0
x
y
x
y
x
y
x
y
C
FA
z
C3
C
FA
z
C2
C
FA
z
C1
C
HA
S
S
S
S
S3
S2
S1
S0
21
Integer Addition 2/2
C4
a3
b3
a2
b2
a1
b1
x
y
x
y
x
y
C
FA
z
C3
C
FA
z
C2
C
FA
z
C1
a0
b0
x
y
C
FA
S
S
S
S
S3
S2
S1
S0
z
C0=0
Ripple-carry adder
22
Unsigned Subtraction
• Algorithm:
– Subtract the subtrahend N from the minuend M
– If no end borrow occurs, then M  N, and the result is
a non-negative number and correct.
– If an end borrow occurs, the N > M and the difference
M - N + 2n is subtracted from 2n, and a minus sign is
appended to the result.
• Examples:
Chapter 4 23
Complements
• Two complements:
– Diminished Radix Complement of N
• (r - 1)’s complement for radix r
• 1’s complement for radix 2
– Radix Complement
• r’s complement for radix r
• 2’s complement in binary
• Defined as rn - N
Chapter 4 24
Binary 1's Complement
• The one's complement is obtained by
complementing each individual bit (bitwise
NOT).
• 1’s complement of 10111010 is 01000101
Chapter 4 25
Binary 2's Complement
• Note the result is the 1's complement plus 1, a
fact that can be used in designing hardware
Chapter 4 26
Alternate 2’s Complement Method
• Given: an n-bit binary number, beginning at
the least significant bit and proceeding
upward:
– Copy all least significant 0’s
– Copy the first 1
– Complement all bits thereafter.
• 2’s Complement Example:
10010100
– Copy underlined bits:
100
– and complement bits to the left:
01101100
Chapter 4 27
Subtraction with 2’s Complement
• For n-digit, unsigned numbers M and N, find M N in base 2:
– Add the 2's complement of the subtrahend N to the
minuend M:
M + (2n - N) = M - N + 2n
– If M  N, the sum produces end carry rn which is
discarded; from above, M - N remains.
– If M < N, the sum does not produce an end carry and,
from above, is equal to 2n - ( N - M ), the 2's
complement of ( N - M ).
– To obtain the result - (N – M) , take the 2's
complement of the sum and place a - to its left.
Chapter 4 28
Unsigned 2’s Complement Subtraction Example 1
• Find 010101002 – 010000112
01010100
– 01000011
01010100
2’s comp
+ 10111101
1 00010001
• The carry of 1 indicates that no correction of
the result is required.
Chapter 4 29
Unsigned 2’s Complement Subtraction Example 2
• Find 010000112 – 010101002
01000011
– 01010100
01000011
+ 10101100
0 11101111
00010001
• Result = – (00010001)
Chapter 4 30
2’s comp
2’s comp
Signed Integers
• Positive numbers and zero can be represented by
unsigned n-digit, radix r numbers. We need a
representation for negative numbers.
• To represent a sign (+ or –) we need exactly one
more bit of information (1 binary digit gives 21 = 2
elements which is exactly what is needed).
• Since computers use binary numbers, by
convention, the most significant bit is interpreted
as a sign bit:
s an–2  a2a1a0
where:
s = 0 for Positive numbers
s = 1 for Negative numbers
Chapter 4 31
and ai = 0 or 1 represent the magnitude in some
Signed Integer Representations
•Signed-Magnitude – here the n – 1 digits are
interpreted as a positive magnitude.
•Signed-Complement – here the digits are
interpreted as the rest of the complement of
the number. There are two possibilities
here:
– Signed 1's Complement
• Uses 1's Complement Arithmetic
– Signed 2's Complement
• Uses 2's Complement Arithmetic
Chapter 4 32
Signed-Magnitude Arithmetic
• If the parity of the three signs is 0:
1. Add the magnitudes.
2. Check for overflow (a carry out of the MSB)
3. The sign of the result is the same as the sign
of the
first operand.
• If the parity of the three signs is 1:
Chapter 4
1. Subtract the second magnitude from the
first.
2. If a borrow occurs:
– take the two’s complement of result
– and make the result sign the complement of
the sign of the first operand.
33
3. Overflow will never occur.
Sign-Magnitude Arithmetic
Examples
• Example 1:
0010
+0101
• Example 2:
0010
+1101
• Example 3:
1010
- 0101
Chapter 4 34
Signed-Complement Arithmetic
• Addition:
1. Add the numbers including the sign bits, discarding a
carry out of the sign bits (2's Complement), or using
an end-around carry (1's Complement).
2. If the sign bits were the same for both
numbers and the sign of the result is different, an
overflow has occurred.
3. The sign of the result is computed in step 1.
• Subtraction:
Form the complement of the number you are
subtracting and follow the rules for addition.
Chapter 4 35
Signed 2’s Complement Examples
• Example 1: 1101
+ 0011
• Example 2: 1101
- 0011
Chapter 4 36
2’s Complement Adder/Subtractor
• Subtraction can be done by addition of the 2's Complement.
1. Complement each bit (1's Complement.)
2. Add 1 to the result.
• The circuit shown computes A + B and A – B:
• For S = 1, subtract,
the 2’s complement
A
B
A
B
A
B
A
of B is formed by using B
XORs to form the 1’s
comp and adding the 1
applied to C0.
• For S = 0, add, B is
passed through
C
C
C
unchanged
FA
FA
FA
FA
3
3
2
2
3
C4
Chapter 4 37
S3
1
1
2
S2
0
1
S1
S0
0
S
C0
Subtractor
• Recall how we do subtraction (2’s complement)
– X – Y = X + (2n – Y) = X + ~Y + 1
x3
a3
y3
b3
y2
a2
b2
x1
y1
a1
b1
x0
y0
a0
b0
4-bit adder circuit
C4
C4
x2
logic-1
C0
S3
S2
S1
S0
S3
S2
S1
S0
38
Overflow
• How to detect overflows:
– two n-bit numbers
– we add them, and result may be an (n+1)-bit number 
overflow.
– Unsigned numbers:
• easy
• check the carryout.
– Signed numbers
• more complicated
• overflow occurs in addition, when the operands are
of the same sign
39
Examples: Overflows
• Example 1: 8-bit signed numbers
0
1
0
0
0
1
0
0
68
0
1
0
1
1
0
1
1
91
1
0
0
1
1
1
1
1
159
• Example 2: 8-bit signed numbers
1
0
1
1
1
1
0
0
-68
1
0
1
0
0
1
0
1
-91
0
1
1
0
0
0
0
1
-159
40
Detecting Overflows
– Remember we have other variables when adding:
• Carries
0
1
0
0
0
1
0
0
A
0
1
0
1
1
0
1
1
B
0
C
1
0
0
1
1
1
1
1
S
1
0
1
1
1
1
0
0
A
1
0
1
0
0
1
0
1
B
0
C
1
S
0
1
1
0
0
0
0
Look at C7
and C8 in
both cases
41
Detecting Overflows: Second Method
• Observations
–
–
–
–
Case 1: V = 1 when C7 = 1 and C8 = 0
Case 2: V = 1 when C7 = 0 and C8 = 1
V = C7  C8 = 1
Think about whether this could happen when the
operands have different signs.
• C7 = C8
42
Multiplication/Division by 2n
• (a) Multiplication
by 100
B3
B2
– Shift left by 2
• (b) Division
by 100
– Shift right by 2
– Remainder
preserved
C5
C4
C3
C2
B0
0
0
C1
C0
(a)
B3
B2
0
0
C3
C2
B1
B0
C1
C0
(b)
Chapter 4 43
B1
C2 1
C2 2
Multiplication by a Constant
• Multiplication of B(3:0) by 101
• See text Figure 513 (a) for contraction
B3
B2
B1
B0
0
B2
B1
B0
C1
C0
Sum
output
Chapter 4 44
B3
4-bit Adder
Carry
C6
0
C5
C4
C3
C2
Binary Multipliers
• Two-bit multiplier
×
y1
y0
Y
x1
x0
X
x0 y1 x0 y0
+
x1 y1 x1 y0
z3
z2
z1
z0
Z
y1
x0
y0
y1
x1
HA
HA
z3
y0
z2
z1
z0
45