Digital Design

Chapter 4: Datapath Components

Digital Design Copyright 2006 Frank Vahid

Introduction
Chapters 2 & 3: Introduced increasingly complex digital building blocks
Gates, multiplexors, decoders, basic registers, and controllers

4.1

Controllers good for systems with control inputs/outputs

Control input: Single bit (or just a few), representing environment event or state
e.g., 1 bit representing button pressed

Data input: Multiple bits collectively representing single entity

e.g., 7 bits representing temperature in binary
i s i s n a

Need building blocks for data

Datapath components, aka register-transfer-level (RTL) components, store/transform data
e z

Put datapath components together to form a datapath

This chapter introduces numerous datapath components, and simple datapaths

Next chapter will combine controllers and datapaths into processors
Digital Design Copyright 2006 Frank Vahid

Registers
b

4.2

x Combinational n1 logic n0 s1 s0

Can store data, very common in datapaths Basic register of Ch 3: Loaded every cycle
Useful for implementing FSM -- stores encoded state For other uses, may want to load only on certain cycles
clk

State register

load
clk

I3

I2

I1

I0 4-bit register

D Q

D Q

D Q

D Q

i s

i s n a

I3 I2 I1 I0 reg(4)

Q3 Q2 Q1 Q0
Q3 Q2 Q1 Q0
e

Basic register loads on every clock cycle How extend to only load on certain cycles?
Digital Design Copyright 2006 Frank Vahid

Register with Parallel Load

Add 2x1 mux to front of each flip-flop Registers load input selects mux input to pass
Either existing flip-flop value, or new value to load
I3 load
1 0 2 1

I2
1 0

I1
1 0

I0
1 0

I3
load

I2

I1

I0

D Q Q3

D Q Q2

D Q Q1

D Q3 Q Q0
(c)
I0
1 0

Q2

Q1

Q0

(a)
I3

I2
1 0

I1
1 0

I3

I2
1 0

I1
1 0

I0
1 0

load = 0

1 0

load = 1

1 0

D Q Q3
Digital Design Copyright 2006 Frank Vahid

D Q Q2

D
Q Q1

D Q Q0

D Q Q3

D Q Q2

D Q Q1

D Q Q0

(b)

Basic Example Using Registers

a3 a2 a1 a0 1 clk ld I3 I2 I1 I0

This example will show how registers load simultaneously on clock cycles
Notice that all load inputs set to 1 in this example -- just for demonstration purposes

R0 Q3 Q2 Q1 Q0

ld I3

I2

I1

I0 R1

1 ld I3

I2

I1

I0 R2

Q3 Q2 Q1 Q0

Q3 Q2 Q1 Q0

Digital Design Copyright 2006 Frank Vahid

Basic Example Using Registers

clk

(a)

given

1
a3..a0

2 0001 1010

1111

R 0 R 1 R 2
a3 a2 a1 a0 1 clk ld I3 I2 I1 I0

???? ???? ????

1111 ???? ????

1111>0001
1111 R 0

0001 1111 0000

0001>1010
0001 R 0

1010 0001 1110

1010
1010 R 0

1010 1010 0101

1010
1010 R 0

1010 1010 0101

1010
1010 R 0

>1111
???? R 0

R0
Q3 Q2 Q1 Q0

(b)

???? R 1
1 ld I3 I2 I1 I0 1 ld I3 I2 I1 I0

???? R 2

???? R 1

???? R 2

1111 R 1

0000 R 2

0001 R 1

1110 R 2

1010 R 1

0101 R 2

1010 R 1

0101 R 2

R1
Q3 Q2 Q1 Q0

R2
Q3 Q2 Q1 Q0

Digital Design Copyright 2006 Frank Vahid

Register Example using the Load Input:

Weight Sampler
Scale has two displays
Present weight Saved weight Useful to compare present item with previous item
Scale Weight Sampler

0 0 1 1 0
Save 2 3 pounds Present weight b clk

Use register to store weight

Pressing button causes present weight to be stored in register
Register contents always displayed as Saved weight, even when new present weight appears
Digital Design Copyright 2006 Frank Vahid

load

I3 I2 I1 I0 Q3 Q2 Q1 Q0

0 0 1 1

3 pounds Saved weight

Register Example: Temperature History Display

Recall Chpt 3 example
Timer pulse every hour Previously used as clock. Better design only connects oscillator to clock inputs -- use registers with load input, connect to timer pulse.

a4 a3 a2 a1 a0
a4 a3 a2 a1 a0

b4 b3 b2 b1 b0 I4 Q4 I3 Q3 I3 Q3 I2 Q2 I2 Rb Q2 I1 Q1 I1 Q1 I0 Q0 I0 Q0 Rb

b4 b3 b2 b1 b0
I4 Q4 I3 Q3 I3 Q3 I2 Q2 I2 Rc Q2 I1 Q1 I1 Q1 I0 Q0 I0 Q0 Rc

c4 c3 c2 c1 c0

c4 c3 c2 c1 c0

t4 x4 t3 x3 t2 x2 t1 x1 t0
x0

Q4 I4 I4 Q4 I3 Q3 I3 Q3 I2 Q2 Ra Q2 I2 I1 Q1 I1 Q1 I0 Q0
I0 Q0

I4

Q4

I4

Q4

Clk osc C C timer

ld

Ra

ld

ld

TemperatureHistoryStorage

new line

TemperatureHistoryStorage

Digital Design Copyright 2006 Frank Vahid

Register Example: Above-Mirror Display

Shorthand notation
a

0001010
r e

8 d0 2 4 a0

Loaded on clock edge

load reg0 T
i m T

u p m o

l a

i0

's r a c e h t m o

Ch2 example: Four simultaneous values from cars computer To reduce wires: Computer writes only 1 value at a time, loads into one of four registers
Was: 8+8+8+8 = 32 wires Now: 8 +2+1 = 11 wires
Digital Design Copyright 2006 Frank Vahid

0 1

d1 i0 i1 d2

8 load reg1

0001010

A 8

i1 load reg2 I i2 8 d 8

a1

load

d3

load reg3

M 8 i3 s1 s0 x y 9

8
b a e h t o r r s l p i d r o

8-bit 41
a y

Register Example: Computerized Checkerboard

Each register holds values for one column of lights
1 lights light
LED lit LED 1 0 1 0 0 0 1 0 R7 d7 8 D microprocessor e R6 d6 R5 d5 R4 R3 R2 R1 R0 Q I d4 d3 i2 i1 i0 d2 d1 d0 3 8 decoder R0 10100010

Microprocessor loads one register at a time

Occurs fast enough that user sees entire board change at once

load

from from microprocessor decoder (b)

Digital Design Copyright 2006 Frank Vahid

(a)

10

Register Example: Computerized Checkerboard

LED lit LED

R7

R6

R5

R4

R3

R2

R1

R0

10100010 10100010 10100010 10100010 01000101 01000101 01000101 01000101

D i2,i1,i0 e clk

10100010 000 (R0)

010000101 001 (R1)

10100010 010 (R2)

010000101 011 (R3)

10100010 100 (R4)

010000101 101 (R5)

10100010 110 (R6)

010000101 111 (R7)

Digital Design Copyright 2006 Frank Vahid

11

Shift Register
Shift right
Move each bit one position right Shift in 0 to leftmost bit
1 1 0 1 0 0 1 1 0 Register contents before shift right
a

Register contents after shift right

Q: Do four right shifts on 1001, showing value after each shift A:

a

1001 (original) 0100 0010 0001 0000

Implementation: Connect flip-flop

output to next flip-flops input
shr_in
a

Digital Design Copyright 2006 Frank Vahid

12

Shift Register
To allow register to either shift or retain, use 2x1 muxes
shr: 0 means retain, 1 shift shr_in: value to shift in
May be 0, or 1

Note: Can easily design shift register that shifts left instead
shr_in shr 1 0 2 1 D Q Q3 1 0

shr=1

1 0

1 0

1 0 2 1 D Q

10 D Q Q2 (b)

10 D Q Q1

1 0 D Q Q0

D Q Q2 (a)

D Q Q1

D Q Q0

Q3

shr_in shr Q3
Digital Design Copyright 2006 Frank Vahid

Q2 (c)

Q1

Q0

13

Rotate Register
1 1 0 1 Register contents before shift right Register contents after shift right

Rotate right: Like shift right, but leftmost bit comes from rightmost bit

1 1 1 0

Digital Design Copyright 2006 Frank Vahid

14

Shift Register Example: Above-Mirror Display

From the car's central computer

Earlier example: 8 +2+1 = 11wires from cars computer to above-mirror displays four registers
Better than 32 wires, but 11 still a lot -want fewer for smaller wire bundles

wir es
C

d0

load

reg0

To the above mirror display

2 4 d1

i0 8

11

a0

load

reg1

A
8

8-bit 4 1
i1

i0 i1 d2

a1

load

reg2

I
i2 8

e load

d3

load

reg3

M 8
i3 s1 s0

Use shift registers

Wires: 1+2+1=4 Computer sends one value at a time, one bit per clock cycle

Note: this line is 1 bit, rather than 8 bits like before x y c shr_in shr reg0 d0 T s1 s0 i0 2 4 8 shr_in 41 shr reg1 d1 A a0 i0 i1 8 i1 a1 shr_in d shr reg2 d2 8 I i2 e d3 shr_in shr reg3 8 M i3 8

Digital Design Copyright 2006 Frank Vahid

shift

15

Multifunction Registers
Many registers have multiple functions
Load, shift, clear (load all 0s) And retain present value, of course

Functions:
s1 0 0 1 1
I0 0 3210 shr_in s1 s0 I3 I2 I1 I0

Easily designed using muxes

Just connect each mux input to achieve desired function
shr_in I3 0 s1 3 2 1 0 s0 4 1 D Q Q3
Digital Design Copyright 2006 Frank Vahid

s0 0 1 0 1

Operation Maintain present value Parallel load Shift right (unused - let's load 0s)

I2 0 3210

I1 0 3210

D Q Q2 (a)

D Q Q1

D Q Q0

Q3 Q2 Q1 Q0

(b)

16

Multifunction Registers
s1 0 0 1 1 s0 0 1 0 1 Operation Maintain present value Parallel load Shift right Shift left

I3 shr_in

I2

I1

I0 shl_in

3210

3210

3210

3210 shl_in shr_in s1 s0

I3

I2

I1

I0

D Q Q3
Digital Design Copyright 2006 Frank Vahid

D Q Q2 (a)

D Q Q1

D Q Q0

Q3 Q2 Q1 Q0

(b)

17

Multifunction Registers with Separate Control Inputs

ld 0 0 0 0 1 1 1 1 shr 0 0 1 1 0 0 1 1 shl 0 1 0 1 0 1 0 1 Operation Maintain present value Shift left Shift right Shift right shr has priority over shl Parallel load Parallel load ld has priority shr_in Parallel load ld has priority Parallel load ld has priority ld shr shl combinational circuit

I3 shr_in s1 s0 I3

I2 I2

I1 I1

I0 I0 shl_in

Truth table for combinational circuit

Inputs shr ld 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1 shl 0 1 0 1 0 1 0 1 Outputs s1 s0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 0 1 Note Operation Maintain value Shift left Shift right Shift right Parallel load Parallel load Parallel load Parallel load
a

shl_in Q3 Q2 Q1 Q0 Q3 Q2 Q1 Q0

s1 = ld*shr*shl + ld*shr*shl + ld*shr*shl s0 = ld*shr*shl + ld

a

Digital Design Copyright 2006 Frank Vahid

18

Register Operation Table

Register operations typically shown using compact version of table
X means same operation whether value is 0 or 1
One X expands to two rows Two Xs expand to four rows

Put highest priority control input on left to make reduced table simple
Inputs shr shl ld 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 Outputs s1 s0 0 1 1 1 0 0 0 0 0 1 0 0 1 1 1 1 Note Operation Maintain value Shift left Shift right Shift right Parallel load Parallel load Parallel load Parallel load ld 0 0 0 1 shr shl 0 0 1 X 0 1 X X Ope ration Maintain value Shi t left f Shift right Parallel load

Digital Design Copyright 2006 Frank Vahid

19

Register Design Process

Can design register with desired operations using simple four-step process

Digital Design Copyright 2006 Frank Vahid

20

Register Design Example

Desired register operations
Load, shift left, synchronous clear, synchronous set
s2 0 0 0 0 1 1 1 1 s1 0 0 1 1 0 0 1 1 s0 0 1 0 1 0 1 0 1 Operation Maintain present value Parallel load Shift left Synchronous clear Synchronous set Maintain present value Maintain present value Maintain present value

Step 1: Determine mux size

a

5 operations: above, plus maintain present value (dont forget this one!) --> Use 8x1 mux

1 0
s2 s1 s0

In from Qn-1

7 6 5 4 3 2 1 0 D Q Qn

Step 2: Create mux operation table Step 3: Connect mux inputs Step 4: Map control lines
s2 = clr*set s1 = clr*set*ld*shl + clr s0 = clr*set*ld + clr
Digital Design Copyright 2006 Frank Vahid

clr 0
0 0

Inputs set ld 0 0
0 0 0 1

shl 0
1 X

Outputs s2 s1 s0 0 0 0
0 0 1 0 0 1

Operation Maintain present value

Shift left Parallel load

0 1
a

1 X

X X

X X

1 0

0 1

0 1

Set to all 1s Clear to all 0s

21

Register Design Example

I3 shl ld set clr combinational circuit s2 s1 s0 I3 I2 I2 I1 I1 I0 I0 shl_in

shl_in Q3 Q2 Q1 Q0 Q3 Q2 Q1 Q0

Step 4: Map control lines

s2 = clr*set s1 = clr*set*ld*shl + clr s0 = clr*set*ld + clr
Digital Design Copyright 2006 Frank Vahid

clr 0
0 0

Inputs set ld 0 0
0 0 0 1

shl 0
1 X

Outputs s2 s1 s0 0 0 0
0 0 1 0 0 1

Operation Maintain present value

Shift left Parallel load

0 1

1 X

X X

X X

1 0

0 1

0 1

Set to all 1s Clear to all 0s

22

Adders
Adds two N-bit binary numbers
2-bit adder: adds two 2-bit numbers, outputs 3-bit result e.g., 01 + 11 = 100 (1 + 3 = 4)
a1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 Inputs a0 b1 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 0 0 1 0 1 0 0 1 0 1 1 1 1 1 b0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 c 0 0 0 0 0 0 0 1 0 0 1 1 0 1 1 1

4.3

Can design using combinational design process of Ch 2, but doesnt work well for reasonable-size N
Why not?

Outputs s1 s0 0 0 0 1 1 0 1 1 0 1 1 0 1 1 0 0 0 1 1 1 0 0 1 0 1 1 0 0 1 0 0 1

Digital Design Copyright 2006 Frank Vahid

23

Why Adders Arent Built Using Standard Combinational Design Process

Truth table too big
2-bit adders truth table shown
Has 2(2+2) = 16 rows

4.3

8-bit adder: 2(8+8) = 65,536 rows 16-bit adder: 2(16+16) = ~4 billion rows 32-bit adder: ...

Big truth table with numerous 1s/0s yields big logic

Plot shows number of transistors for N-bit adders, using state-of-the-art automated combinational design tool
Transistors

a1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 10000 8000

Inputs a0 b1 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

b0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

c 0 0 0 0 0 0 0 1 0 0 1 1 0 1 1 1

Outputs s1 s0 0 0 0 1 1 0 1 1 0 1 1 0 1 1 0 0 1 0 1 1 0 0 0 1 1 1 0 0 0 1 1 0

Q: Predict number of transistors for 16-bit adder

a

s r o

6000 4000 2000 0 1 2 3 4 N 5 6 7 8

A: 1000 transistors for N=5, doubles for each increase of N. So transistors = 1000*2(N-5). Thus, for N=16, transistors = 1000*2(16-5) = 1000*2048 = 2,048,000. Way too many!
Digital Design Copyright 2006 Frank Vahid

s i n a

24

Alternative Method to Design an Adder: Imitate Adding by Hand

Alternative adder design: mimic how people do addition by hand One column at a time
Compute sum, add carry to next column
0 1 0 1 1 1 1 + 0 1 1 0 1 1 1 1 1 1 + 0 1 1 0 1 1 1 1 1 + 0 1 1 0
a

A: B: +

1 1 1 1 0 1 1 0

0 1

1 0 1

1 0 1 0 1

Digital Design Copyright 2006 Frank Vahid

25

Alternative Method to Design an Adder: Imitate Adding by Hand

Create component for each column
Adds that columns bits, generates sum and carry bits
1 1 0

A: B:

1 1 1 1 + 0 1 1 0

1 0 1 0 1 1 1 1 0 b a ci co s 1 0 1 b a ci co s 1 0 1 1 b a ci co s 0 1 0 b a co s 1 SUM

A: 1

B:

Digital Design Copyright 2006 Frank Vahid

Full-adders

Half-adder

26

Half-Adder
1 1 1 1 b a ci co s 1 0 1 1 b a ci co s 0 1 0 b a co s 1 SUM

Half-adder: Adds 2 bits, generates sum and carry Design using combinational design process from Ch 2
Inputs b a 0 0 1 0 0 1 1 1

A: 1

B: 0 b a ci co s

Step 1: Capture the function

Outputs co s 0 0 1 0 1 0 0 1

Step 2: Convert to equations

co = ab s = ab + ab (same as s = a xor b)
a b a b

Step 3: Create the circuit

Digital Design Copyright 2006 Frank Vahid

Half-adder
co s co s

27

Full-Adder
1 1 1 1 b a ci co s 1 0 1 1 b a ci co s 0 1 0 b a co s 1 SUM

Full-adder: Adds 3 bits, generates sum and carry Design using combinational design process from Ch 2

A: 1

B: 0 b a ci co s

Step 1: Capture the function Step 2: Convert to equations Step 3: Create the circuit Inputs Outputs
a b ci a 0 0 0 0 1 1 1 1 b 0 0 1 1 0 0 1 1 ci 0 1 0 1 0 1 0 1 co 0 0 0 1 0 1 1 1 s 0 1 1 0 1 0 0 1

co = abc + abc + abc + abc co = abc +abc +abc +abc +abc +abc co = (a+a)bc + (b+b)ac + (c+c)ab co = bc + ac + ab s = abc + abc + abc + abc s = a(bc + bc) + a(bc + bc) s = a(b xor c) + a(b xor c) s = a xor b xor c

Full adder
co s

Digital Design Copyright 2006 Frank Vahid

28

Carry-Ripple Adder
Using half-adder and full-adders, we can build adder that adds like we would by hand Called a carry-ripple adder
4-bit adder shown: Adds two 4-bit numbers, generates 5-bit output
5-bit output can be considered 4-bit sum plus 1-bit carry out

Can easily build any size adder

a3 b3 a b ci F A co s co a2 b2 a b ci F A s co a1 b1 a b ci F A s co a0 b0 a b HA s co

a3 a2 a1 a0

b3 b2 b1 b0

4-bit adder s3 s2 s1 s0

co

s3

s2 (a)

s1

s0 (b)

Digital Design Copyright 2006 Frank Vahid

29

Carry-Ripple Adder
Using full-adder instead of half-adder for first bit, we can include a carry in bit in the addition
Will be useful later when we connect smaller adders to form bigger adders
a3 b3 a b ci F A co s co a2 b2 a b ci F A s co a1 b1 a b ci F A s co a0 b0 ci a b ci F A s co

a3 a2 a1 a0

b3 b2 b1 b0 ci

4-bit adder s3 s2 s1 s0

co

s3

s2 (a)

s1

s0 (b)

Digital Design Copyright 2006 Frank Vahid

30

Carry-Ripple Adders Behavior

000 a b ci F A co 0 s 0 00 0 a b ci F A co 0 s 0 10 0 a b ci F A co s 0 co2 1 000 a b ci F A co 0 s 0 100 a b ci F A co s 0 co1 1 co 0 0 0 0

a b ci F A s 0 1 1

Assume all inputs initially 0

000 a b ci F A co 0
Digital Design Copyright 2006 Frank Vahid

0111+0001
(answer should be 01000)

a b ci F A co s 0 1 co0

s 0

Output after 2 ns (1FA delay)

Wrong answer -- something wrong? No -- just need more time for carry to ripple through the chain of full adders.

31

Carry-Ripple Adders Behavior

000 a b ci F A co 0 s 0 10 0 a b ci F A co 0 s 1 (b) 000 a b ci F A co 0 s 0 101 0 a b ci F A co s 1 co2 0 10 1 a b ci F A co 1 s 0 101 a b ci F A co 1 (c) s 0 101 a b ci F A co 1 (d) s 0 1 1 1 1 0 101 a b ci F A co s 1 co1 0 1 1 0

0111+0001
(answer should be 01000)

a b ci F A co 1 s 0

Outputs after 4ns (2 FA delays)

a b ci F A co 1 s
a

0 0

Outputs after 6ns (3 FA delays)

0 00 1 a b ci F A co 0 s 1

a b ci F A co 1 s 0 Output after 8ns (4 FA delays)

Digital Design Copyright 2006 Frank Vahid

Correct answer appears after 4 FA delays

32

Cascading Adders

a7a6a5a4 a3a2a1a0

b7b6b5b4 b3b2b1b0 ci

a3a2a1a0 a3a2a1a0

b3b2b1b0 b3b2b1b0 ci co a7.. a0 b7.. b0 ci

4-bit adder co co s3s2s1s0 s7s6s5s4

4-bit adder co s3s2s1s0 s3s2s1s0 (a)

8-bit adder s7.. s0

(b)

Digital Design Copyright 2006 Frank Vahid

33

Adder Example: DIP-Switch-Based Adding Calculator

Goal: Create calculator that adds two 8-bit binary numbers, specified using DIP switches
DIP switch: Dual-inline package switch, move each switch up or down Solution: Use 8-bit adder
DIP switches 1 0

a7..a0

b7..b0 ci 0
a

8-bit carry-ripple adder co s7..s0

CALC LEDs
Digital Design Copyright 2006 Frank Vahid

34

Adder Example: DIP-Switch-Based Adding Calculator

To prevent spurious values from appearing at output, can place register at output
Actually, the light flickers from spurious values would be too fast for humans to detect -- but the principle of registering outputs to avoid spurious values being read by external devices (which normally arent humans) applies here.
DIP switches 1 0

a7..a0 8-bit adder co e clk

Digital Design Copyright 2006 Frank Vahid

b7..b0 ci 0

s7..s0

ld

8-bit register CALC LEDs

35

Adder Example: Compensating Weight Scale

Weight scale with compensation amount of 0-7
To compensate for inaccurate sensor due to physical wear Use 8-bit adder
weight sensor 7 6 5 4 0 1 2 3

01000010
a7..a0

0 0 0 0 0 010 000 b7..b0

8-bit adder co s7..s0

ci

1 clk
Digital Design Copyright 2006 Frank Vahid

ld

display register 01000010 01000100

Weight Adjuster

to display

36

Shifters
Shifting (e.g., left shifting 0011 yields 0110) useful for:
Manipulating bits Converting serial data to parallel (remember earlier above-mirror display example with shift registers) Shift left once is same as multiplying by 2 (0011 (3) becomes 0110 (6))
Why? Essentially appending a 0 -- Note that multiplying decimal number by 10 accomplished just be appending 0, i.e., by shifting left (55 becomes 550)
i3 i2 i1 i0

4.4

Shift right once same as dividing by 2

i3 i2 i1 i0 i3 i2 i1 i0 in in 01 01 01 01 sh inR

inL 201 201 2 01 2 01 s0 s1

a

shL shR

<<1

q3

q2

q1

q0 q3 q2 q1 q0

q3

q2

q1

q0

Symbol

Left shifter

Digital Design Copyright 2006 (a) Frank Vahid

Shifter with left shift or no shift

Shifter with left shift, right shift, and no shift

37

Shifter Example: Approximate Celsius to Fahrenheit

Converter
Convert 8-bit Celsius input to 8-bit Fahrenheit output
F = C * 9/5 + 32 Approximate: F = C*2 + 32 Use left shift: F = left_shift(C) + 32
C 8 <<1

00001100 (12)

*2
0 (shift in 0) 00100000 (32) 8
a

00011000 (24)

8-bit adder

00111000 (56)
Digital Design Copyright 2006 Frank Vahid

8 F

38

Shifter Example: Temperature Averager

Four registers storing a history of temperatures Want to output the average of those temperatures Add, then divide by four
Same as shift right by 2 Use three adders, and right shift by two
0000111 (7) 001000 (8) 001100 (12) 001111 (15)
T clk ld + + + ld Ra Rb Rc Rd

shift in 0 0101010 (42)

0 >>2

divide by 4

0001010 (10)
ld Ravg Tavg

Digital Design Copyright 2006 Frank Vahid

39

Barrel Shifter
A shifter that can shift by any amount
4-bit barrel left shift can shift left by 0, 1, 2, or 3 positions 8-bit barrel left shifter can shift left by 0, 1, 2, 3, 4, 5, 6, or 7 positions
(Shifting an 8-bit number by 8 positions is pointless -- you just lose all the bits)

i3 01

i2 01

i1 01

i0 in 01 sh

q3

q2

q1

q0

Shift by 1 shifter uses 2x1 muxes. 8x1 mux solution for 8-bit barrel shifter: too many wires.

Could design using 8x1 muxes and lots of wires

Too many wires

Q: xyz=??? to shift by 5?

1
x sh

00000110
in 0
a

More elegant design

Chain three shifters: 4, 2, and 1 Can achieve any shift of 0..7 by enabling the correct combination of those three shifters, i.e., shifts should sum to desired amount
Digital Design Copyright 2006 Frank Vahid

<<4 8

0
y sh

01100000 (by 4)
in 0

<<2 8

1
z sh

01100000
in 0
40

<<1 Q

Net result: shift by 5:8

11000000 (by 1)

Comparators
N-bit equality comparator: Outputs 1 if two N-bit numbers are equal
4-bit equality comparator with inputs A and B
a3 must equal b3, a2 = b2, a1 = b1, a0 = b0
Two bits are equal if both 1, or both 0 eq = (a3b3 + a3b3) * (a2b2 + a2b2) * (a1b1 + a1b1) * (a0b0 + a0b0)

4.5

Recall that XNOR outputs 1 if its two input bits are the same
eq = (a3 xnor b3) * (a2 xnor b2) * (a1 xnor b1) * (a0 xnor b0)
a3 b3 a2 b2 a1 b1 a0 b0

0110 = 0111 ?

0 0

1 1

1 1

0 1
a3 a2 a1 a0 b3 b2 b1 b0
a

4-bit equality comparator eq (b)

0
Digital Design Copyright 2006 Frank Vahid

eq (a)

41

Magnitude Comparator
N-bit magnitude comparator: A=1011 B=1001 Indicates whether A>B, A=B, or 1011 1001 Equal A<B, for its two N-bit inputs A and B How design? Consider how compare 1011 1001 Equal
by hand. First compare a3 and b3. If equal, compare a2 and b2. And so on. Stop if comparison not equal -whichevers bit is 1 is greater. If never see unequal bit pair, A=B.

1011

1001 Unequal

So A > B

Digital Design Copyright 2006 Frank Vahid

42

Magnitude Comparator
By-hand example leads to idea for design
Start at left, compare each bit pair, pass results to the right Each bit pair called a stage Each stage has 3 inputs indicating results of higher stage, passes results to lower stage
a3 b3 a Igt Ieq Ilt b a2 b2 a b a1 b1 a b a0 b0 a b AgtB AeqB AltB

in_gt out_gt in_eq out_eq in_lt out_lt Stage 3

in_gt out_gt in_eq out_eq in_lt out_lt Stage 2 (a)

in_gt out_gt in_eq out_eq in_lt out_lt Stage 1

in_gt out_gt in_eq out_eq in_lt out_lt Stage 0

Digital Design Copyright 2006 Frank Vahid

0 1 0

Igt Ieq Ilt

a3a2a1a0

b3b2b1b0

4-bit magnitude comparator (b)

AgtB AeqB AltB

43

Magnitude Comparator
a3 b3 a Igt Ieq Ilt b a2 b2 a b a1 b1 a b a0 b0 a b AgtB AeqB AltB

in_gt out_gt in_eq out_eq in_lt out_lt Stage 3

in_gt out_gt in_eq out_eq in_lt out_lt Stage 2

in_gt out_gt in_eq out_eq in_lt out_lt Stage 1

in_gt out_gt in_eq out_eq in_lt out_lt Stage 0

Each stage:
out_gt = in_gt + (in_eq * a * b)
A>B (so far) if already determined in higher stage, or if higher stages equal but in this stage a=1 and b=0

out_lt = in_lt + (in_eq * a * b)

A<B (so far) if already determined in higher stage, or if higher stages equal but in this stage a=0 and b=1

out_eq = in_eq * (a XNOR b)

A=B (so far) if already determined in higher stage and in this stage a=b too

Simple circuit inside each stage, just a few gates (not shown)
Digital Design Copyright 2006 Frank Vahid

44

Magnitude Comparator
How does it work?
1011 = 1001 ?
1 = 1 a3 b3 a b 0 0 a2 b2 a b 1 0 a1 b1 a b 1 1 a0 b0 a b AgtB AeqB AltB

Ieq=1 causes this stage to compare

0 0 Igt in_gt out_gt in_gt out_gt 1 1 Ieq in_eq out_eq in_eq out_eq 0 0 in_lt out_lt in_lt out_lt Ilt S tage3 S tage2 (a) 0 = 0 a2 b2 a b

in_gt out_gt in_eq out_eq in_lt out_lt S tage1

in_gt out_gt in_eq out_eq in_lt out_lt S tage0

1 1 a3 b3 a b 0 Igt in_gt out_gt 1 Ieq in_eq out_eq 0 in_lt out_lt Ilt S tage3

1 0 a1 b1

1 1 a0 b0 a b AgtB AeqB AltB

a b 0 in_gt out_gt in_gt out_gt 1 in_eq out_eq in_eq out_eq 0 in_lt out_lt in_lt out_lt S tage2 (b) S tage1

in_gt out_gt in_eq out_eq in_lt out_lt S tage0

Digital Design Copyright 2006 Frank Vahid

45

Magnitude Comparator
1011 = 1001 ?
1 1 0 0 1 > 0 a1 b1 1 a0 1 b0 a3 b3 a2 b2

a Igt 0 in_gt in_lt 1 Ieq 0 Ilt

b out_gt out_lt

a in_gt in_lt

b out_gt out_lt

a in_gt in_lt

b out_gt out_lt 1 0 0

a in_gt in_lt

b out_gt out_lt AgtB AltB

in_eq out_eq

in_eq out_eq

in_eq out_eq

in_eq out_eq

AeqB

S tage3

S tage2 (c)

S tage1

S tage0

1 a1 0 b1 1 a0 1 b0

a3 b3

a2 b2

a Igt 0 1 Ieq 0 Ilt in_gt in_lt

b out_gt out_lt

a in_gt in_lt

b out_gt out_lt

a in_gt in_lt

b out_gt out_lt

a in_gt in_lt

b out_gt out_lt 1 0 0 AgtB AeqB AltB

Final answer appears on the right Takes time for answer to ripple from left to right Thus called carry-ripple style after the carry-ripple adder
Even though theres no carry involved
46

in_eq out_eq

in_eq out_eq

in_eq out_eq

in_eq out_eq

S tage3 Digital Design Copyright 2006 Frank Vahid

S tage2 (d)

S tage1

S tage0

Magnitude Comparator Example:

Minimum of Two Numbers
Design a combinational component that computes the minimum of two 8-bit numbers
Solution: Use 8-bit magnitude comparator and 8-bit 2x1 mux
If A<B, pass B through mux. Else, pass A. 11000000
MIN
a

01111111
B 8 8 AgtB AeqB AltB 8 8 I0 A Min C 8 (b) 8 8 B

0 1 0

A B Igt Ieq 8-bit magnitude comparator Ilt

1 0 0

I1

8-bit 2x1 mux 8 C

(a)

01111111
Digital Design Copyright 2006 Frank Vahid

47

Counters
N-bit up-counter: N-bit register that can increment (add 1) to its own value on each clock cycle
0000, 0001, 0010, 0011, ...., 1110, 1111, 0000 Note how count rolls over from 1111 to 0000
Terminal (last) count, tc, equals1 during value just before rollover
cnt ld 4-bit register

4.6

0 1

cnt

4-bit up-counter tc C 4

0 0 1

0101 0100 0011 0010 0001 0000 0001 0000 1111 1110 ...

4-bit up-counter

Internal design
Register, incrementer, and N-input AND gate to detect terminal count
tc
Digital Design Copyright 2006 Frank Vahid

4 4 C

4 +1 4

48

Incrementer
Counter design used incrementer Incrementer design
Could use carry-ripple adder with B input set to 00...001
But when adding 00...001 to another number, the leading 0s obviously dont need to be considered -- so just two bits being added per column

Use half-adders (adds two bits) rather than full-adders (adds three bits)
a3 a2 a b HA co s s2 (a) a1 a b HA co s s1 a0 1 a3 a2 a1 a0 +1 co s3 s2 s1 s0 (b)
49

011 0011 unused + 1 0 0 10 0

carries:

a b HA co s co s3

a b HA co s s0

Digital Design Copyright 2006 Frank Vahid

Incrementer
Can build faster incrementer using combinational logic design process
Capture truth table Derive equation for each output
c0 = a3a2a1a0 ... s0 = a0
Inputs a3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 a2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 a1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 a0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 c0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 Outputs s3 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 s2 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 s1 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 s0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

Results in small and fast circuit Note: works for small N -- larger N leads to exponential growth, like for N-bit adder

Digital Design Copyright 2006 Frank Vahid

50

Counter Example: Mode in Above-Mirror Display

Recall above-mirror display example from Chapter 2
Assumed component that incremented xy input each time button pressed: 00, 01, 10, 11, 00, 01, 10, 11, 00, ... Can use 2-bit up-counter
Assumes mode=1 for just one clock cycle during each button press
Recall Button press synchronizer example from Chapter 3

mode clk

cnt

2-bit upcounter tc c1c0

x y

Digital Design Copyright 2006 Frank Vahid

51

Counter Example: 1 Hz Pulse Generator Using 256 Hz

Oscillator
Suppose have 256 Hz oscillator, but want 1 Hz pulse
1 Hz is 1 pulse per second -- useful for keeping time Design using 8-bit upcounter, use tc output as pulse
Counts from 0 to 255 (256 counts), so pulses tc every 256 cycles
1

cnt

osc (256 Hz)

8-bit up-counter tc C 8 p (unused) (1 Hz)

Digital Design Copyright 2006 Frank Vahid

52

Down-Counter
4-bit down-counter
1111, 1110, 1101, 1100, , 0011, 0010, 0001, 0000, 1111, Terminal count is 0000
Use NOR gate to detect
4-bit down-counter cnt ld 4-bit register

Need decrementer (-1) design like designed incrementer

tc

4 4 C

4 1 4

Digital Design Copyright 2006 Frank Vahid

53

Up/Down-Counter
Can count either up or down
Includes both incrementer and decrementer Use dir input to select, using 2x1: dir=0 means up Likewise, dir selects appropriate terminal count value
dir 4-bit up/down counter

4-bit 2 x 1 0 4

clr cnt

clr ld

4-bit register

4 4

4 1 4

4 +1 4

1 2x 1 0 tc
Digital Design Copyright 2006 Frank Vahid

54

Counter Example: Light Sequencer

Illuminate 8 lights from right to left, one at a time, one per second Use 3-bit up-counter to counter from 0 to 7 Use 3x8 decoder to illuminate appropriate light Note: Used 3-bit counter with 3x8 decoder
NOT an 8-bit counter why not?
1 clk (1 Hz) cnt 3-bit up-counter tc unused 3x 8 dcd c2 c1 c0

0 0 1 0 0 1 0
i2 i1 i0

d7 d6 d5 d4 d3 d2 d1 d0
a

lights

Digital Design Copyright 2006 Frank Vahid

55

Counter with Parallel Load

Up-counter that can be loaded with external value
Designed using 2x1 mux ld input selects incremented value or external value Load the internal register when loading external value or when counting
L ld 1 4 4-bit 2x 1 0 4

cnt

ld 4-bit register

4 4 tc C

4 +1

Digital Design Copyright 2006 Frank Vahid

56

Counter with Parallel Load

Useful to create pulses at specific multiples of clock
Not just at N-bit counters natural wrap-around of 2N
ld 1 cnt

1000
4

Example: Pulse every 9 clock cycles

Use 4-bit down-counter with parallel load Set parallel load input to 8 (1000) Use terminal count to reload
When count reaches 0, next cycle loads 8.

4-bit down-counter
tc 4 C

clk

Why load 8 and not 9? Because 0 is included in count sequence:

8, 7, 6, 5, 4, 3, 2, 1, 0
Digital Design Copyright 2006 Frank Vahid

9 counts
57

Counter Example:
New Years Eve Countdown Display
Chapter 2 example previously used microprocessor to counter from 59 down to 0 in binary Can use 8-bit (or 7- or 6-bit) down-counter instead, initially loaded with 59
59 8 L ld reset c0 c1 c2 c3 c4 c5 c6 c7 i0 i1 i2 i3 i4 i5 d0 d1 d2 d3 0 1 2 3 Happy New Year

cnt countdown clk (1 Hz)

Digital Design Copyright 2006 Frank Vahid

8-bit down- tc counter

d58 d59 d60 d61 d62 6x64 dcd d63

58 59

fireworks

58

Counter Example:
1 Hz Pulse Generator from 60 Hz Clock
U.S. electricity standard uses 60 Hz signal
Device may convert that to 1 Hz signal to count seconds
1 osc (60 Hz) clr cnt 6-bit up counter tc p C

Use 6-bit up-counter

Can count from 0 to 63 Create simple logic to detect 59 (for 60 counts)
Use to clear the counter back to 0 (or to load 0)

(1 Hz)

Digital Design Copyright 2006 Frank Vahid

59

Timer
A type of counter used to measure time
If we know the counters clock frequency and the count, we know the time thats been counted

Example: Compute cars speed using two sensors

First sensor (a) clears and starts timer Second sensor (b) stops timer Assuming clock of 1kHz, timer output represents time to travel between sensors. Knowing the distance, we can compute speed

Digital Design Copyright 2006 Frank Vahid

60

Multiplier Array Style

Can build multiplier that mimics multiplication by hand
Notice that multiplying multiplicand by 1 is same as ANDing with 1

4.7

Digital Design Copyright 2006 Frank Vahid

61

Multiplier Array Style

Generalized representation of multiplication by hand

Digital Design Copyright 2006 Frank Vahid

62

Multiplier Array Style

Multiplier design array of AND gates
a3 b0 a2 a1 a0

b1

pp2

pp1
0

0 + (5-bit)

b2

pp3

00 A + (6-bit) B

b3

pp4

0 00 + (7-bit)

Block symbol

Digital Design Copyright 2006 Frank Vahid

p7..p0

63

Subtractor
Can build subtractor as we built carry-ripple adder
Mimic subtraction by hand Compute borrows from columns on left
Use full-subtractor component:
wi is borrow by column on right, wo borrow from column on left
1stcolumn 0 1 0 1 10 - 0 1 1 1 1 a3 b3 a b wi FS wo s wo s3
Digital Design Copyright 2006 Frank Vahid

4.8

2nd column 0 1 10 1 10 1 0 - 0 1 1 1 1 1

3rd column 0 1 1 10 1 0 - 0 1 0 1 1 1 1

4th column 0 1 0 1 0 - 0 0 1 0 1 1 1 1

a2 b2 a b wi FS wo s s2

a1 b1 a b wi FS wo s s1

a0 b0 wi a b wi FS wo s s0 a3 a2 a1 a0 b3 b2 b1 b0 4-bit subtractor wo s3s2s1s0 wi

a

(b)

(c)

64

Subtractor Example: DIP-Switch Based

Adding/Subtracting Calculator
Extend earlier calculator example
Switch f indicates whether want to add (f=0) or subtract (f=1) Use subtractor and 2x1 mux
1 0 e clk ld DIP switches 1 0 8 A 8 B ci 8-bit adder co f S 8 0 8 8 0

A B wi 8-bit subtractor wo 8 S

2x1 8

8-bit register CALC 8 LEDs

Digital Design Copyright 2006 Frank Vahid

65

Subtractor Example:
Color Space Converter RGB to CMYK
Color
Often represented as weights of three colors: red, green, and blue (RGB)
Perhaps 8 bits each, so specific color is 24 bits
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

Because inks absorb light Use complementary colors of RGB: Cyan (absorbs red), reflects green and blue, Magenta (absorbs green), and Yellow (absorbs blue)
66

Good for computer monitors, which mix red, green, and blue lights to form all colors
Digital Design Copyright 2006 Frank Vahid

Subtractor Example:
Color Space Converter RGB to CMYK
Printers must quickly convert RGB to CMY
C=255-R, M=255-G, Y=255-B Use subtractors as shown
Y M C o t

R 255 8 8 255 8

G 8 255

B 8

B G R

8 8 M Y

Digital Design Copyright 2006 Frank Vahid

67

Subtractor Example:
Color Space Converter RGB to CMYK
Try to save colored inks
Expensive Imperfect mixing C, M, Y doesnt yield good-looking 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).
(200,200,200) is a dark gray use black ink
Digital Design Copyright 2006 Frank Vahid

68

Subtractor Example:
Color Space Converter RGB to CMYK
Call black part K
(200,200,200): K=200
(Letter B already used for blue)

Compute minimum of C, M, Y values

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)
C2
Digital Design Copyright 2006 Frank Vahid

R G B RGB t o CMY C M Y 8 C M MIN 8 MIN 8 K 8 Y 8

M C o

B G

8 M2

8 Y2

8 K 8

69

Representing Negative Numbers: Twos Complement

Negative numbers common
How represent in binary?

Signed-magnitude
Use leftmost bit for sign bit
So -5 would be:
1101 using four bits 10000101 using eight bits

Better way: Twos complement

Big advantage: Allows us to perform subtraction using addition Thus, only need adder component, no need for separate subtractor component!

Digital Design Copyright 2006 Frank Vahid

70

Tens Complement
1 9 8 7 6 5 4 3 2 1

Before introducing twos complement, lets consider tens complement

But, be aware that computers DO NOT USE TENS COMPLEMENT. Introduced for intuition only. Complements for each base ten number shown to right Complement is the number that when added results in 10

2 3 4 5 6 7 8 9

Digital Design Copyright 2006 Frank Vahid

71

Tens Complement
Nice feature of tens complement
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 2 3 4 5 6 7 8 9 0
Digital Design Copyright 2006 Frank Vahid

9 8 7 6 5 4 3 2 1 10 74=3 3 0 4 4 7

10 6

10 +6 13 13 3

20

7+6=13

Adding the complement results in an answer exactly 10 too much dropping the tens column gives the right answer.
72

Twos Complement is Easy to Compute:

Just Invert Bits and Add 1
Hold on!
Sure, adding the tens complement achieves subtraction using addition only But dont 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 10-4=6 in the first place.

True but in binary, it turns out that the twos complement can be computed easily
Twos 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!
a

Q: What is the twos complement of 0101? A: 1010+1=1011

(check: 0101+1011=10000)

Q: What is the twos complement of 0011? A: 1100+1=1101

Digital Design Copyright 2006 Frank Vahid

73

Twos Complement Subtractor Built with an Adder

Using twos complement
A B = A + (-B) = A + (twos complement of B) = A + invert_bits(B) + 1
A B N-bit

So build subtractor using adder by inverting Bs bits, and setting carry in to 1

A Adder

B cin

Digital Design Copyright 2006 Frank Vahid

74

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, Bs bits pass through; if sub input is 1, XORs invert Bs bits

Digital Design Copyright 2006 Frank Vahid

75

Adder/Subtractor Example: Calculator

Previous calculator used separate adder and subtractor Improve by using adder/subtractor, and twos complement numbers
1 0 8 A 8

DIP switches 1 0 8 1 0 f A B sub 8-bit adder/subtractor S

8 ld

e clk
DIP swi tches

8-bit register CALC 8 LEDs

B ci 0 8-bit adder co S 8 ld 0 2x1 8 1

A B wi 0 8-bit subt actor r wo S 8

1 0 clk

f e

8-bit register CALC 8 LEDs

Digital Design Copyright 2006 Frank Vahid

76

Overflow
Sometimes result cant be represented with given number of bits
Either too large magnitude of positive or negative e.g., 4-bit twos complement addition of 0111+0001 (7+1=8). But 4bit twos complement cant represent number >7
0111+0001 = 1000 WRONG answer, 1000 in twos complement is -8, not +8

Adder/subtractor should indicate when overflow has occurred, so result can be discarded

Digital Design Copyright 2006 Frank Vahid

77

Detecting Overflow: Method 1

Assuming 4-bit twos complement numbers, can detect overflow by detecting when the two numbers sign bits are the same but are different from the results sign bit
If the two numbers sign bits are different, overflow is impossible
Adding a positive and negative cant exceed largest magnitude positive or negative

Simple circuit
overflow = a3b3s3 + a3b3s3 Include overflow output bit on adder/subtractor
sign bits 0 1 1 1 +0 0 0 1 1 0 0 0 overflow (a)
Digital Design Copyright 2006 Frank Vahid

1 1 1 1 +1 0 0 0 0 1 1 1 overflow (b)

1 0 0 0 +0 1 1 1 1 1 1 1 no overflow (c)

If the numbers sign bits have the same value, which differs from the results sign bit, overflow has occurred.

78

Detecting Overflow: Method 2

Even simpler method: Detect difference between carry-in to sign bit and carry-out from sign bit Yields simpler circuit: overflow = c3 xor c4

1 1 1 0 1 1 1 +0 0 0 1 0 1 0 0 0 overflow (a)

0 0 0 1 1 1 1 +1 0 0 0 10 1 1 1 overflow (b)

0 0 0 1 0 0 0 +0 1 1 1 01 1 1 1 no overflow (c)

If the carry into the sign bit column differs from the carry out of that column, overflow has occurred.

Digital Design Copyright 2006 Frank Vahid

79

Arithmetic-Logic Unit: ALU

ALU: Component that can perform any of various arithmetic (add, subtract, increment, etc.) and logic (AND, OR, etc.) operations, based on control inputs Motivation:
Suppose want multifunction calculator that not only adds and subtracts, but also increments, ANDs, ORs, XORs, etc.
Digital Design Copyright 2006 Frank Vahid

4.9

80

Multifunction Calculator without an ALU

Can build multifunction calculator using separate components for each operation, and muxes
But too many wires, and wasted power computing all those operations when at any time you only use one of the results
1 0 x y z e clk DIP switches 1 0 8 A B Wasted power 8

+ 8

+1 8 8 8

AND

OR

XOR NOT

8 8

8 A lot of wires

0 1 2 3 4 5 6 7 s2 8-bit 8 1 s1 s0 8 Id 8-bit register

CALC 8

Digital Design Copyright 2006 Frank Vahid

LEDs

81

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 adders A and B inputs
Logic in front is called an arithmetic-logic extender

Extender modifies the A and B inputs such that desired operation will appear at output of the adder

Digital Design Copyright 2006 Frank Vahid

82

Arithmetic-Logic Extender in Front of ALU

xyz=000: Want S=A+B just pass a to ia, b to ib, and set cin=0 xyz=001: Want S=A-B 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 AL-extender component
Digital Design Copyright 2006 Frank Vahid

83

ALU Example: Multifunction Calculator

DIP swi tches 1 0 8 A + 8 8 +1 8 8 8 1 0 x y z e clk 0 s2 s1 s0 Id 1 2 3 8 8 7 8 4 5 6 8-bit 8 1 8 8-bit reg ist er CALC 8 LEDs A lot of wi res. B AND OR XOR NOT Wast ed p o w er 8

DIP switches 1 0 8 A B A x y z ALU S 8 e clk ld 8-bit register 8 CALC B x y z 1 0 8

Design using ALU is elegant and efficient

No mass of wires No big waste of power

LEDs
Digital Design Copyright 2006 Frank Vahid

84

Register Files
MxN register file component provides efficient access to M Nbit-wide registers
s
?

4.10

r e

32 C
r e t

u p m o

8 d0d0 4 16 4 2

load reg0 load

reg0

huge mux 32 8
l p i d r o s

b a e h t o

u p m o

i m

r a c e h t m o

If we have many registers but only need access one or two at a time, a register file is more efficient Ex: Above-mirror display (earlier example), but this time having 16 32-bit registers
r F

l a

i0 i0 32-bit 8-bit 4 16x 1 1 i1 8

b a e h t o

i m

l p i d r o s

's r a c e h t m o

l a

a0

d1 i0 d2

too much fanout load reg1

i3-i0i1 a1

load reg2

I 8

dd

328

DD

i2 congestion i3 i15 s1 s0 s3-s0 x y

d15 e

d3

load reg3 load reg15

M 32 8

load

load

Too many wires, and big mux is too slow

Digital Design Copyright 2006 Frank Vahid

85

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 W_data 4 W_addr W_en 1632 register file R_data R_addr R_en 4
a

32

Digital Design Copyright 2006 Frank Vahid

86

Register File Timing Diagram

Can write one register and read one register each clock cycle
May be same register
clk W_data W_addr W_en R_data R_addr R_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 0: ? 1: 22 2: 177 3: 555 Z X Z X Z 3 9 Z X 22 1 9 3 555 cycle 1 1 9 3 22 1 cycle 2 2 X X cycle 3 3 X X cycle 4 4 177 2 cycle 5 5 555 3 cycle 6 6

32 W_data 2 W_addr W_en 4x32 register file R_addr R_en R_data

32 2

Digital Design Copyright 2006 Frank Vahid

87

Register-File Example: Above-Mirror Display

16 32-bit registers that can be written by cars computer, and displayed
Use 16x32 register file Simple, elegant design
32 C

OLD design
a

d0
From the car s central computer

load reg0
32
C 32 much too W_data fanout 4 W_addr W_en 16 32 register file

huge mux i0
To the abovemirror display
D 32 32-bit R_data 16x 1 4 R_addr R_en 1

4 16 4 i3-i0
WA load

Register file hides complexity internally

And because only one register needs to be written and/or read at a time, internal design is simple
Digital Design Copyright 2006 Frank Vahid

32 RA

congestion e

d15

load reg15

load

i15
32 s3-s0

88

Chapter Summary
Need datapath components to store and operate on multibit data
Also known as register-transfer-level (RTL) components

Components introduced
Registers Shifters Adders Comparators Counters Multipliers Subtractors Arithmetic-Logic Units Register Files

Next, well combine knowledge of combinational logic design, sequential logic design, and datapath components, to build digital circuits that can perform general and powerful computations
Digital Design Copyright 2006 Frank Vahid

89