ECE 274  Digital Logic Lecture 12
Lecture 12 – Datapath Components
Can build subtractor as we built carryripple adder
Subtractors
Mimic subtraction by hand Compute borrows from columns on left
Register Files
wi is borrow by column on right, wo borrow from column on left
1stcolumn 0 1 0 1 10
Overflow ALUs
Use fullsubtractor component:
Two’s Complement
4.8
Subtractor
 0
1
1
2nd column 0 1 10 1 10 1 0
1
 0
1
1
1
1
1
1
3rd column 0 1 1 10 1 0  0
1
 0
1
1
1
0
1
1
0
0
1
1
a2 b2
a1 b1
a0 b0 wi
a
a
a
a
FS
b wi FS
wo s
wo s
wo s3
s2
b wi FS
(b)
b wi FS
wo s
4th column 0 0 1 0
1
a3 b3 b wi
1
1
wo s
s1
s0
a3 a2 a1 a0 b3 b2 b1 b0 4bit subtractor wo
wi
(c)
1
2
Subtractor Example: DIPSwitch
Subtractor Example:
Based Adding/Subtracting Calculator
Extend earlier calculator example
Color Space Converter – RGB to CMYK
DIP switches
8 A
8
8
B ci 8bit adder co
1 0
Color
1 0
Switch f indicates whether want to add (f=0) or subtract (f=1) Use subtractor and 2x1 mux
f e
0
wo 8
ld
clk
8
0
2x1 8
1
Often represented as weights of three colors: red, green, and blue (RGB)
A B wi 8bit subtractor
S
0
Perhaps 8 bits each, so specific color is 24 bits
S
8
8bit register CALC 8
LEDs
White: R=11111111, G=11111111, B=11111111 Black: R=00000000, G=00000000, B=00000000 Other colors: values in between, e.g., R=00111111, G=00000000, B=00001111 would be a reddish purple
• Printers use opposite color scheme
Good for computer monitors, which mix red, green, and blue lights to form all colors
– Because inks absorb light – Use complementary colors of RGB: Cyan (absorbs red), reflects green and blue, Magenta (absorbs green), and Yellow (absorbs blue)
3
4
Subtractor Example:
Subtractor Example:
Color Space Converter – RGB to CMYK
R
Printers must quickly convert RGB to CMY
C=255R, M=255G, Y=255B Use subtractors as shown
255
Color Space Converter – RGB to CMYK
G 8
255
8
B 8
255
8
8
Try to save colored inks
8
Y M C o
t


B G
R
8 C
8 M
a
s3s2s1s0
8 Y
Expensive Imperfect – mixing C, M, Y doesn’t yield goodlooking black
Solution: Factor out the black or gray from the color, print that part using black ink
e.g., CMY of (250,200,200)= (200,200,200) + (50,0,0).
5
(200,200,200) is a dark gray – use black ink
6
Representing Negative Numbers: Two’s Complement
Subtractor Example:
Color Space Converter – RGB to CMYK
Call black part K
(200,200,200): K=200
(Letter “B” already used for blue)
R
G
8
B
8
Negative numbers common
Signedmagnitude
K
Y
R G B RGB t o CMY C M Y
Compute minimum of C, M, Y values
8
Use MIN component designed earlier, using comparator and mux, to compute K Output resulting K value, and subtract K value from C, M, and Y values Ex: Input of (250,200,200) yields output of (50,0,0,200)
8
8 M
C
M C o
t
How represent in binary?
B G
R
8
Use leftmost bit for sign bit
8
So 5 would be: 1101 using four bits 10000101 using eight bits
Y
MIN 8
8
Better way: Two’s complement
MIN K

8
C2
8
M2
8 Y2
Big advantage: Allows us to perform subtraction using addition Thus, only need adder component, no need for separate subtractor component!
8 K
7
8
Ten’s Complement
Ten’s Complement
Before introducing two’s complement, let’s consider ten’s complement
But, be aware that computers DO NOT USE TEN’S COMPLEMENT. Introduced for intuition only. Complements for each base ten number shown to right – Complement is the number that when added results in 10
1
9
2
8
3
7
Nice feature of ten’s complement
4
6
5
5
6
Instead of subtracting a number, adding its complement results in answer exactly 10 too much So just drop the 1 – results in subtracting using addition only complements 1
9
2
8
3
7
4
6
5
5
6
4
7
3
8
2
9
1
10 4
6
4
7
3
8
2
9
1
7 0
10
Ð4
3
20
+6
13 13
0
10
3

7Ð4=3
7+6=13
3
Adding the complement results in an answer exactly 10 too much – dropping the tenscolumn gives the right answer.
9
10
Two’s Complement Subtractor Built with an Adder
Two’s Complement is Easy to Compute: Just Invert Bits and Add 1
Hold on!
Sure, adding the ten’s complement achieves subtraction using addition only But don’t we have to perform subtraction to have determined the complement in the first place? e.g., we only know that the complement of 4 is 6 by subtracting 104=6 in the first place.
A – B = A + (B) = A + (two’s complement of B) = A + invert_bits(B) + 1
True – but in binary, it turns out that the two’s complement can be computed easily
Using two’s complement
Two’s complement of 011 is 101, because 011 + 101 is 1000 Could compute complement of 011 as 1000 – 011 = 101 Easier method: Just invert all the bits, and add 1 The complement of 011 is 100+1 = 101  it works!
So build subtractor using adder by inverting B’s bits, and setting carry in to 1
A
B Nbit
A
B Adder
cin
1
S
Q: What is the two’s complement of 0101? A: 1010+1=1011
a
(check: 0101+1011=10000)
Q: What is the two’s complement of 0011? A: 1100+1=1101 11
12
Adder/Subtractor Example: Calculator
Adder/Subtractor
Adder/subtractor: control input determines whether add or subtract
Can use 2x1 mux – sub input passes either B or inverted B Alternatively, can use XOR gates – if sub input is 0, B’s bits pass through; if sub input is 1, XORs invert B’s bits
Previous calculator used separate adder and subtractor Improve by using adder/subtractor, and two’s complement numbers
DIP switches 1 0 8 f
1 0
sub
8
A B 8bit adder/subtractor S 8
e
ld
clk
8bit register CALC 8
DIP switches
1 0
LEDs 8 B ci 0 8bit adder co S
8 8 A B wi 0 8bit subtractor wo S
8
A
1 0
f
8
e
ld
clk
0
2x1 8
1
8
8bit register CALC 8 LEDs
13
14
Design Challenge
Overflow
Not Really a Quiz
Determine the two’s complement representation for the following decimal numbers (assume we are using 5bit binary numbers):
Sometimes result can’t be represented with given number of bits
1 11 15
Either too large magnitude of positive or negative e.g., 4bit two’s complement addition of 0111+0001 (7+1=8). But 4bit two’s complement can’t represent number >7
Determine the two’s complement representation for same decimal numbers assuming we are using 6bit binary numbers.
0111+0001 = 1000 WRONG answer, 1000 in two’s complement is 8, not +8
Adder/subtractor should indicate when overflow has occurred, so result can be discarded
15
16
Detecting Overflow: Method 1
Assuming 4bit two’s complement numbers, can detect overflow by detecting when the two numbers’ sign bits are the same but are different from the result’s sign bit
If the two numbers’ sign bits are different, overflow is impossible
Detecting Overflow: Method 2
Adding a positive and negative can’t exceed largest magnitude positive or negative
Simple circuit
Even simpler method: Detect difference between carryin to sign bit and carryout from sign bit Yields simpler circuit: overflow = c3 xor c4
overflow = a3’b3’s3 + a3b3s3’ Include “overflow” output bit on adder/subtractor
1 1 1 0 1 1 1
0 0 0 1 1 1 1
0 0 0 1 0 0 0
+0 0 0 1
+1 0 0 0
+0 1 1 1
0 1 0 0 0
10 1 1 1
01 1 1 1
sign bits 0 1 1 1
1 1 1 1
1 0 0 0
+0 0 0 1
+1 0 0 0
+0 1 1 1
1 0 0 0 overflow (a)
0 1 1 1 overflow (b)
overflow (a)
overflow (b)
no overflow (c)
If the carry into the sign bit column differs from the carry out of that column, overflow has occurred.
1 1 1 1 no overflow (c)
If the numbers’ sign bits have the same value, which differs from the result’s sign bit, overflow has occurred. 17
18
ALU: Component that can perform any of various arithmetic (add, subtract, increment, etc.) and logic (AND, OR, etc.) operations, based on control inputs Motivation:
Multifunction Calculator without an ALU
4.9
ArithmeticLogic Unit: ALU
Can build multifunction calculator using separate components for each operation, and muxes
DIP switches 1 0
But too many wires, and wasted power computing all those operations when at any time you only use one of the results
8
+
Ð
B
+1
AND
Wasted power
XOR NOT
8 8
1 0
OR
8
8
8
Suppose want multifunction calculator that not only adds and subtracts, but also increments, ANDs, ORs, XORs, etc.
8
A
8 8
8 A lot of wires
0 1 2 3 4 5 6 7 s2 8bit 8⋅ 1 s1 s0
x y z
8
e
Id
clk
8bit register CALC 8
LEDs
19
20
ArithmeticLogic Extender in Front of ALU
ALU More efficient design uses ALU
ALU design not just separate components multiplexed (same problem as previous slide!), Instead, ALU design uses single adder, plus logic in front of adder’s A and B inputs
Logic in front is called an arithmeticlogic extender
Extender modifies the A and B inputs such that desired operation will appear at output of the adder
xyz=000: Want S=A+B – just pass a to ia, b to ib, and set cin=0 xyz=001: Want S=AB – pass a to ia, b’ to ib, and set cin=1 xyz=010: Want S=A+1 – pass a to ia, set ib=0, and set cin=1 xyz=011: Want S=A – pass a to ia, set ib=0, and set cin=0 xyz=1000: Want S=A AND B – set ia=a*b, b=0, and cin=0 others: likewise Based on above, create logic for ia(x,y,z,a,b) and ib(x,y,z,a,b) for each abext, and create logic for cin(x,y,z), to complete design of the ALextender component
21
22
ALU Example: Multifunction Calculator DIP swi tches
1 0 8
8
A +
Ð 8
B
+1
AND
0
x y z e
clk
XOR
NOT
Wast ed po w er
DIP switches
8 8
1
OR
8
8
0 s2 s1 s0
8 8
1 2 3
4 5 6 8bit 8 ⋅ 1
8 7
8 Id
8bit reg ist er
CALC 8
8
8
Design using ALU is elegant and efficient
No mass of wires No big waste of power
32
r e
C
x y z
If we have many registers but only need access one or two at a time, a register file is more efficient Ex: Abovemirror display (earlier example), but this time having 16 32bit registers
B ALU S
8 e clk
ld
8bit register CALC
8
LEDs
23
Too many wires, and big mux is too slow
a
8
d0d0
load reg0 load
reg0
huge mux
T
32
u p m o
c r a c e th m o
4⋅ 162⋅ 4
l a
c
r
t r's a c e th m o
r l a
n
r
F
e t
d1
c
r
B A
x y z
C
r e
t
u p m o
t
n
4
F
A
component provides efficient access to M Nbitwide registers s
1 0
LEDs
MxN register file
?
A lot of wi res.
1 0
4.10
Register Files
e
c
a0
too much fanout load reg1
i m
T
i0 i0 8
A
i0
i1 i3i0 a1
e
b a e th o
i m T
r
r
is rd lo p
r
32bit 8bit 4×1 16x1
r
o
v
a
e o
i1 8 d2
load reg2
I
d3
load reg3 load reg15
M
d15 e
y
v
a
e
y

dd DD 328 8
load
load
b a e th o
is rd lo p
32
8
i2 congestion
i15i3 s1 s0 s3s0 x y
24
Register File
Instead, want component that has one data input and one data output, and allows us to specify which internal register to write and which to read
32 4
Register File Timing Diagram
32 W_data
R_data
W_addr
R_addr
W_en
a
4
Can write one register and read one register each clock cycle
R_en 16×32 register file
clk
cycle 1
cycle 2 1
cycle 3 2
cycle 4
cycle 5 4
3
cycle 6 5
6
W_data
9
22
X
X
177
555
W_addr
3
1
X
X
2
3
W_en
May be same register
R_data
Z
R_addr
X
Z
Z X
9
Z
3
22
X
9
1
555
3
R_en
32
32 W_data
R_data
2
2 W_addr
R_addr
W_en
0: 1: 2: 3:
? ? ? ?
0: 1: 2: 3:
? ? ? 9
0: ? 1: 22 2: ? 3: 9
0: ? 1: 22 2: ? 3: 9
0: ? 1: 22 2: ? 3: 9
0: ? 1: 22 2: 177 3: 9
R_en 4x32 register file
a
25
26
RegisterFile Example: AboveMirror
Datapath Component Summary
Display
16 32bit registers that can be written by car’s computer, and displayed
Use 16x32 register file Simple, elegant design
Register file hides complexity internally
And because only one register needs to be written and/or read at a time, internal design is simple
OLD design a
load reg0
d0
i3i0
C
32too much W_data fanout
WA
4
i0
32 R_data32bit 16x1 4
W_addr
D
R_addr
load W_en
d
R_en
1
16⋅ 32 register file
32 RA
e
d15
load
Extra Credit (Homework)
D
i15 32
s3s0
Design a more accurate version of the Celsius to Fahrenheit converter. The new conversion circuit receives a digitized temperature in Celsius as a 16bit binary number C and outputs the temperature in Fahrenheit as a 16bit output F. Our more accurate equation for calculating an approximate conversion from Celsius to Fahrenheit is: F = C*30/16 + 32. Due:
load reg15
Design Challenge
congestion
Design Challenge
Components introduced
27
huge mux 32
4⋅ 16 4
Need datapath components to store and operate on multibit data
To the abovemirror display
32 C
From the car s central computer
0: ? 1: 22 2: 177 3: 555
Next Lecture (Wednesday, October 19) 3 points
29
Also known as registertransferlevel (RTL) components Registers Shifters Adders Comparators Counters Multipliers Subtractors ArithmeticLogic Units Register Files
Next, we’ll combine knowledge of combinational logic design, sequential logic design, and datapath components, to build digital circuits that can perform general and powerful computations
28