Subtractor Subtractor Example: DIP-Switch Subtractor Example

Loading...

ECE 274 - Digital Logic Lecture 12 „

Lecture 12 – Datapath Components

„

„

„

Can build subtractor as we built carry-ripple 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 full-subtractor 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 4-bit subtractor wo

wi

(c)

1

2

Subtractor Example: DIP-Switch

Subtractor Example:

Based Adding/Subtracting Calculator

„

Extend earlier calculator example „

„

Color Space Converter – RGB to CMYK „

DIP switches

8 A

8

8

B ci 8-bit 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 8-bit subtractor

S

0

Perhaps 8 bits each, so specific color is 24 bits „

S

„

8

„

8-bit 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=255-R, M=255-G, Y=255-B 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 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). „

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

„

Signed-magnitude

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 10-4=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 N-bit

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 8-bit adder/subtractor S 8

e

ld

clk

8-bit register CALC 8

DIP switches

1 0

LEDs 8 B ci 0 8-bit adder co S

8 8 A B wi 0 8-bit subtractor wo S

8

A

1 0

f

8

e

ld

clk

0

2x1 8

1

8

8-bit 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 5-bit 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., 4-bit two’s complement addition of 0111+0001 (7+1=8). But 4-bit two’s complement can’t represent number >7 „

„

Determine the two’s complement representation for same decimal numbers assuming we are using 6-bit 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 4-bit 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 carry-in to sign bit and carry-out 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

Arithmetic-Logic 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 8-bit 8⋅ 1 s1 s0

x y z

8

e

Id

clk

8-bit register CALC 8

LEDs

19

20

Arithmetic-Logic 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 arithmetic-logic 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=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

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 8-bit 8 ⋅ 1

8 7

8 Id

8-bit 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: Above-mirror display (earlier example), but this time having 16 32bit registers

B ALU S „

8 e clk

ld

8-bit 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 Nbit-wide 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 i3-i0 a1

e

b a e th o

i m T

r

r

is rd lo p

r

32-bit 8-bit 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 s3-s0 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

Register-File Example: Above-Mirror

Datapath Component Summary

Display

16 32-bit 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

i3-i0

C

32too much W_data fanout

WA

4

„

i0

32 R_data32-bit 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

„

s3-s0

Design a more accurate version of the Celsius to Fahrenheit converter. The new conversion circuit receives a digitized temperature in Celsius as a 16-bit binary number C and outputs the temperature in Fahrenheit as a 16-bit 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 register-transfer-level (RTL) components Registers Shifters Adders Comparators Counters Multipliers Subtractors Arithmetic-Logic 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

Loading...

Subtractor Subtractor Example: DIP-Switch Subtractor Example

ECE 274 - Digital Logic Lecture 12 „ Lecture 12 – Datapath Components „ „ „ Can build subtractor as we built carry-ripple adder „ „ Subtractors ...

169KB Sizes 0 Downloads 0 Views

Recommend Documents

Subtractor
Sep 23, 2009 - 1 Prelab. 1. Write the truth table for a full adder. 2. Write the truth table for a full subtractor. 3. S

Subtractor
Jan 31, 2013 - design an all-optical circuit that can perform full adder and subtractor operations. In this paper, we re

subtractor unit
approaches, the full Adder and Subtractors are realized in a single unit as compared to only full Subtractor in the exis

Full Subtractor Schematic - WordPress.com
Full Subtractor Schematic. Here's a full-adder circuit: The truth table for the above: INPUTS OUTPUTS A B CIN COUT S. 0

Subtractor Lab L03 - c-jump
adder to perform subtraction thus removes the requirement for a subtractor circuit. Practically all hand-held calculator

Subtractor using a Novel Reversible - iarjset
full adder and a full subtractor by using one P2RG and Fredkin gate only. According to the control logic input the propo

subtractor circuits based on reversible gates - ijareeie
The reversible 4-bit full adder/ subtractor design unit is compared with conventional ripple carry adder, .... A four-bi

Subtractor using a Novel Reversible Gate
significant aspect of this work is that it can work both as a full adder and a full subtractor by using one P2RG and Fre

Subtractor Using a Novel - Book Your Project
as full subtractor on a single unit. We need only a control gate to control the mode of operation for the addition / sub

A Novel Design of SET-CMOS Half Subtractor and Full Subtractor
A Novel Design of SET-CMOS Half Subtractor and Full. Subtractor. A. Fathima Thuslim. Department of Electronics and Commu