Arithmetic

20 September 2005

Arithmetic

ALU

ALU.png

Numbers

Possible Representations

Bits

Sign Magnitude

1's complement

2's complement

000

+0

+0

+0

001

+1

+1

+1

010

+2

+2

+2

011

+3

+3

+3

100

-0

-3

-4

101

-1

-2

-3

110

-2

-1

-2

111

-3

-0

-1

MIPS uses 2's complement

0000 0000 0000 0000 0000 0000 0000 0000 = 0
0000 0000 0000 0000 0000 0000 0000 0001 = +1
0000 0000 0000 0000 0000 0000 0000 0010 = +2
...
0111 1111 1111 1111 1111 1111 1111 1110 = +2,147,483,646
0111 1111 1111 1111 1111 1111 1111 1111 = +2,147,483,647
1000 0000 0000 0000 0000 0000 0000 0000 = –2,147,483,648
1000 0000 0000 0000 0000 0000 0000 0001 = –2,147,483,647
1000 0000 0000 0000 0000 0000 0000 0010 = –2,147,483,646
...
1111 1111 1111 1111 1111 1111 1111 1101 = – 3
1111 1111 1111 1111 1111 1111 1111 1110 = – 2
1111 1111 1111 1111 1111 1111 1111 1111 = – 1

2's complement operations

Addition & Subtraction

Just like in grade school (carry/borrow 1's)

00111

00111

00110

+ 00110

- 00110

- 00101

01101

00001

00001

2's complement operations are easy

00000111

00000111

- 00000110

+ 11111010

00000001

Overflow (result too large for finite word)

01110000

+ 00010000

10000000

Detecting Overflow

Effects of Overflow

Logic Functions

LogicFunctions.png

Boolean Algebra & Gates

Truth Table

A

B

C

D

E

F

0

0

0

0

0

0

0

0

1

1

0

0

0

1

0

1

0

0

0

1

1

1

1

0

1

0

0

1

0

0

1

0

1

1

1

0

1

1

0

1

1

0

1

1

1

1

0

1

D=A|B|C   E=(~A&B&C)|(A&~B&C)|(A&B&~C)   F=A&B&C

An ALU

Let's build an ALU to support andi and ori instructions. We'll build a 1 bit ALU and use 32 of them.

AndOrALU.png

ALU truth table

op

a

b

result

0

0

0

0

0

0

1

1

0

1

0

1

0

1

1

1

1

0

0

0

1

0

1

0

1

1

0

0

1

1

1

1

~op & (a|b) | op & a & b == ~op&a | ~op&b | op&a&b

Multiplexor

Selects one of the inputs to be the output

Multiplexor.png

1-bit ALU for Addition

AddALU.png

1-bit ALU for Addition

a

b

cin

sum

cout

0

0

0

0

0

0

0

1

1

0

0

1

0

1

0

0

1

1

0

1

1

0

0

1

0

1

0

1

0

1

1

1

0

0

1

1

1

1

1

1

Cout = a&b | a&Cin | b&Cin 
sum = a&~b&~Cin | ~a&b&~Cin | ~a&~b&Cin | a&b&Cin

Building a 32 bit ALU

ALU32.png

What about subtraction?

2's complement: just negate b and add, how?

SubtractALU.png

Tailoring the ALU to MIPS

Implement SLT

SLTALU.png

Test for equality

Equality.png

Conclusion

Educational Highlight

IEEE Computer Society 7th Annual International Design Competition

Work in a team to design a computer-based application that makes the world a better place

last edited 2005-09-20 17:28:34 by GaryBishop