ECE 2300
Digital Logic & Computer Organization
Spring 2018
More Binary Arithmetic
ALU
Lecture 13: 1
Announcements
• Lab 4 prelab (B) due tomorrow
• Lab 5 to be released tonight
Lecture 13: 2
Example: Fixed Size 2’C Addition
• White stone = 0
• Black stone = 1
• With each row representing a
4-bit 2’s complement, adding
which two rows would
cause an overflow?
– Row 1 + Row 4 : (-3) + (-6)
– Row 3 + Row 4 : (-5) + (-6)
Lecture 13: 3
Review: Full Adder
A
B S
Cin A B
Cout Cin
S
Cout
OR
FA
Lecture 13: 4
Building a Binary Adder
1 1 1 0 0 0 0 0
carries
01101000 (A)
+ 11110000 (B)
01011000 (S)
• Inputs & outputs for the ith bit position
– Inputs: Ai, Bi and Ci (carry-in)
– Outputs: Si (sum) and Ci+1 (carry-out)
• Carry-out of a bit position is the carry-in for next
bit position
Lecture 13: 5
Four Bit Adder
1 1 0 0 0
1100
+0110
0010
a3 b3 a2 b2 a1 b1 a0 b0
A B A B A B A B
c4 c3 c2 c1 0
Cout Cin Cout Cin Cout Cin Cout Cin
S S S S
s3 s2 s1 s0
Ripple Carry Adder (RCA)
Lecture 13: 6
Two’s Complement Subtraction
• Negate second operand and add
01101000 (104)
- 00010001 (17)
01101000 (104)
+ 11101111 (-17)
01010111 (87)
Lecture 13: 7
Four Bit Subtractor
b3 b2 b1 b0
negating the
second operand
b3’ b2’ b1’ b0’
+ 1
a3 b3 a2 b2 a1 b1 a0 b0
A B A B A B A B
c4 c3 c2 c1 1
Cout Cin Cout Cin Cout Cin Cout Cin
S S S S
s3 s2 s1 s0
Lecture 13: 8
Four Bit Adder / Subtractor
a3 b3 a2 b2 a1 b1 a0 b0
0 1 0 1 0 1 0 1
A B A B A B A B
c4 c3 c2 c1
Cout Cin Cout Cin Cout Cin Cout Cin sub
S S S S
s3 s2 s1 s0
Lecture 13: 9
Adder Implementations
• Many different adder implementations exist, which differ
in speed and circuit complexity
• Ripple carry adder is simple but slow
– Each 1-bit full adder must wait for the carry bit to be calculated
from the previous full adder
• Common techniques to speed up carry propagation
– Carry lookahead
– Carry select
– etc.
Lecture 13: 10
Carry Lookahead Adder (CLA)
• Calculation of carry out of MSB is slow for large
RCAs
– Carry has to propagate from LSB to the MSB, which
forms the longest path (critical path)
• CLA adder calculates groups of carries in parallel
Lecture 13: 11
Carry Generation and Propagation
01010010 11000110
+ 00010011 + 00101011
01100101 11110001
generated generated propagated generated
• Cout = 1 from a bit position happens for 2 reasons
– Carry is generated from this bit position
– Carry in to this position is propagated to the next
Lecture 13: 12
Carry Generation and Propagation
• Carry into ith position: ci
– Also the carry out from (i-1)th position
• Carry generation function for the ith position
Gi = a i • b i
• Carry propagation function for the ith position
P i = ai + b i
• Carry out of the ith position
ci+1 = Gi + Pi • ci
Lecture 13: 13
Carry Out Equations for 4-bit Adder
c 1 = G0 + P 0 • c 0 Gi = a i • b i
P i = ai + b i
c 2 = G1 + P 1 • c 1
= G1 + P 1 • G0 + P 1 • P 0 • c 0
c 3 = G2 + P 2 • c 2
= G2 + P 2 • G1 + P 2 • P 1 • G0 + P 2 • P 1 • P 0 • c 0
c 4 = G3 + P 3 • c 3
= G3 + P 3 • G2 + P 3 • P 2 • G1 + P 3 • P 2 • P 1 • G0 + P 3 • P 2 • P 1 • P 0 • c 0
generate propagate propagate propagate propagate
carry from carry carry carry carry in
this generated generated generated to
position in position 2 in position 1 in position 0 position 0
Lecture 13: 14
Carry Out Logic for 4-bit Adder
Gi = a i • b i
P i = ai + b i
c 4 = G3 + P 3 • c 3
= G3 + P 3 • G2 + P 3 • P 2 • G1 + P 3 • P 2 • P 1 • G0 + P 3 • P 2 • P 1 • P 0 • c 0
= G 3 + P 3 • ( G 2 + P 2 • ( G 1 + P 1• G 0 ) ) + ( P 3 • P 2 • P 1 • P 0 ) • c 0
G3:0 – Carry generation P3:0 – Carry propagation through
from bits 3-0 bits 3-0
G3:0 G3
P3
G2
P2
G1
P1
G0
c4
P3:0 P3
P2
c0 P1
P0
Lecture 13: 15
32-bit CLA with 4-bit RCAs
a31:28 b31:28 a27:24 b27:24 a7:4 b7:4 a3:0 b3:0
cout (c32) 4-bit CLA c28 4-bit CLA c24 … 4-bit CLA c4 4-bit CLA cin (c0)
Block Block Block Block
S31:28 S27:24 S7:4 S3:0
• Carry out logic gets more complicated beyond 4 bits
• CLAs are often implemented as 4-bit modules and
instantiated in a hierarchical way to realize wider adders
Lecture 13: 16
32-bit CLA with 4-bit RCAs
a31:28 b31:28 a27:24 b27:24 a7:4 b7:4 a3:0 b3:0
cout (c32) 4-bit CLA c28 4-bit CLA c24 … 4-bit CLA c4 4-bit CLA cin (c0)
Block Block Block Block
S31:28 S27:24 S7:4 S3:0
a3 b3 a2 b2 a1 b1 a0 b0
c3 c2 c1 c0
FA FA FA FA
S3 S2 S1 S0
G3:0 G3 P’s and G’s for all
P3 CLA blocks are
G2
P2 generated in parallel
G1
P1
G0
c4 P3
P3:0 P2
c0 P1
P0 Lecture 13: 17
Longest Delay (Critical Path)
Bits 31-28 Bits 7-4 Bits 3-0
a7 b7 a6 b6 a5 b5 a4 b4 a3 b3 a2 b2 a1 b1 a0 b0
a 31 b 31 a 30 b 30 a 29 b 29 a 28 b 28
c7 c6 c5 c4 c3 c2 c1 c0
c 31 c 30 c 29 c 28 FA FA FA FA FA FA FA FA
FA FA FA FA
S7 S6 S5 S4 S3 S2 S1 S0
S 31 S 30 S 29 S 28
G 7:4 G7 G 3:0 G3
…
G 31:28 G 31
P7 P3
P3 G6 G2
G2 P2
P6
P2 G5 G1
G1 P1
P5
P 29 G4 G0
G 28
c8 c4
c 32 P7 P 3:0 P3
P 31 P 7:4 P2
P 31:28 P6
P 30 P5 c0 P1
P 29 c4 P4 P0
c 28 P 28
Lecture 13: 18
Longest Delay (Critical Path)
Bits 31-28 Bits 7-4 Bits 3-0
a7 b7 a6 b6 a5 b5 a4 b4 a3 b3 a2 b2 a1 b1 a0 b0
a 31 b 31 a 30 b 30 a 29 b 29 a 28 b 28
c7 c6 c5 c4 c3 c2 c1 c0
c 31 c 30 c 29 c 28 FA FA FA FA FA FA FA FA
FA FA FA FA
S7 S6 S5 S4 S3 S2 S1 S0
S 31 S 30 S 29 S 28
G 7:4 G7 G 3:0 G3
…
G 31:28 G 31
P7 P3
P3 G6 G2
G2 P2
P6
P2 G5 G1
G1 P1
P5
P 29 G4 G0
G 28
c8 c4
c 32 P7 P 3:0 P3
P 31 P 7:4 P2
P 31:28 P6
P 30 P5 c0 P1
P 29 c4 P4 P0
c 28 P 28
Lecture 13: 19
Our Microprocessor is Built to Compute
MUX
0
+2 Adder 1
sext({OFF,0})
MP
Fm … F0
DR RF DataA
Inst. RAM
SA M_address
Decoder
SB RW Data
DataB ALU
PC
MB SA Data_in 0
FS
0 RAM
SB 1 1
MD DR
RW D_in VCZN
SE
MW MB MW MD
IMM
ALU is the computing core of a processor
Lecture 13: 20
What is an ALU?
• Arithmetic Logic Unit (ALU): Combinational
logic circuit that combines a variety of
operations into a single unit
• Common operations may include
– Addition and subtraction
– Logical (OR, AND)
– Shift
– Comparisons
Lecture 13: 21
A Simple 8-Bit ALU
8 8
B A
SI SO
CI ALU CO
O
OP
Y Z
3
Lecture 13: 22
ALU Operations, Inputs & Outputs
• Operations
– Addition and Subtraction
– Bitwise AND and OR
– Left Shift and Right Shift
• Inputs
– A, B, Carry In (CI)
– Shift In (SI)
– Code indicating operation to be performed (OP)
• Outputs
– Y, Carry Out (CO)
– Shift Out (SO)
– Flags regarding the result of the operation
• Overflow flag (O), Zero flag (Z)
Lecture 13: 23
Shift Operations
• Left Shift: shifts each bit left by 1 position
A7 A6 A5 A4 A3 A2 A1 A0 SI
SO=A7 A6 A5 A4 A3 A2 A1 A0 SI
– MSB shifted into SO, SI shifted into LSB
• Right Shift: shifts each bit right by 1 position
SI A7 A6 A5 A4 A3 A2 A1 A0
SI A7 A6 A5 A4 A3 A2 A1 A0=SO
– LSB shifted into SO, SI shifted into MSB Lecture 13: 24
ALU Block Diagram
Adder
8 8 8
A A Y
8
B CO CO
B 8 8 CI CI O O
00
8 8 8
01 Logical 00
0 10 8
A
8 Y 8 01
8
Y
B
LOP 10 8
Control Logic Shifter
2 8 NOR Z
BSEL A 8
3 Y
LOP SI SI
OP OP SO SO
SOP SOP
OSEL 2
Lecture 13: 25
Example: ALU Operation Encodings
OP Name OP BSEL CI LOP SOP OSEL Operation
ADD 000 0 - - 00 Y = A + B + CI
SUB 001 1 - - 00 Y = A + B’ + 1
AND 011 - 0 - 01 Y = A AND B
OR 100 - 1 - 01 Y = A OR B
SHL 101 - - - 0 10 Y = A[6..0],SI
SHR 110 - - - 1 10 Y = SI,A[7..1]
PASS A 111 10 0 - - 00 Y = A
Adder
8 8 A 8
A Y
8 B CO CO
B 8 8 00 CI CI O O
8 8 01
8
Logical 00
0 10 8
A
8 Y 8 01 8 Y
B
LOP 10 8
Control Logic Shifter
2 8 NOR Z
BSEL A 8
3 Y
OP OP LOP SI SI
SO SO
SOP SOP
OSEL 2
Lecture 13: 26
Before Next Class
• H&H 7.1-7.3.1
Next Time
Memories
Lecture 13: 27
