Arithmetic and logic units

DAPA
E.T.S.I. Informtica Universidad de Sevilla 11/2012

Jorge Juan <jjchico@dte.us.es> 2010, 2011, 2012 You are free to copy, distribute and communicate this work publicly and make derivative work provided you cite the source and respect the conditions of the Attribution-Share alike license from Creative Commons. You can read the complete license at: http://creativecommons.org/licenses/by-sa/3.0

Departamento de Tecnologa Electrnica Universidad de Sevilla

Contents

Introduction Binary arithmetic Basic adder circuits Magnitude adder Signed binary numbers Signed adder: overflow Adder/subtractor ALU

Departamento de Tecnologa Electrnica Universidad de Sevilla

Introduction

Arithmetic circuits: do arithmetic operation: +, -, *, / Arithmetic operations are the most important operations in computers (digital systems) Arithmetic operation in computers

Simple operations: in hardware Complex operation: in software, using simple hardware ops.

Departamento de Tecnologa Electrnica Universidad de Sevilla

Arithmetic hardware support in personal computers

1970-1980 (8 bit processors)

Only addition and subtraction of integer numbers Multipliers and dividers Math co-processors Integrated co-processors Multiple integer units Multimedia support 2-D graphics (on graphics controller) Advanced mathematical operations 3-D graphics (on graphics controller)

1980-1990 (16 bit processors)

1990-2000 (32 bit processors)

2000- (64 bit processors)

Departamento de Tecnologa Electrnica Universidad de Sevilla

Contents

Introduction Binary arithmetic Basic adder circuits Magnitude adder Signed binary numbers Signed adder: overflow Adder/subtractor ALU

Departamento de Tecnologa Electrnica Universidad de Sevilla

Binary arithmetic

Arithmetic in digital systems (computers) Base 2 numerical system Fixed number of bits
8 bit

Storage

Overflow?

Departamento de Tecnologa Electrnica Universidad de Sevilla

Binary arithmetic

Example

A = 100110 B = 1101 A A A A +B B *B /B

Operations

Departamento de Tecnologa Electrnica Universidad de Sevilla

Contents

Introduction Binary arithmetic Basic adder circuits Magnitude adder Signed binary numbers Signed adder: overflow Adder/subtractor ALU

Departamento de Tecnologa Electrnica Universidad de Sevilla

Basic adder circuits. Full adder

cn + cn-1 an-1 bn-1 sn-1 ci+1 ci c1 ci+1 ai bi

ai a1 a0 bi b1 b0 si s1 s0

FA

ci

Full Adder

si
ai 0 0 0 0 1 1 1 1 bi 0 0 1 1 0 0 1 1 ci ci+1 si 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 1 0 1 0 0 1

si = ai bi ci ci+1 = aibi + aici + bici

Departamento de Tecnologa Electrnica Universidad de Sevilla

Basic adder circuits. Half adder

cn + cn-1 an-1 bn-1 sn-1 ci+1 ci c1 c1 a 0 b0

ai a1 a0 bi b1 b0 si s1 s0

HA

Half Adder

s0

a0 0 0 1 1

b0 0 1 0 1

c1 0 0 0 1

s0 0 1 1 0

s0 = a0 b0 c1 = a0b0

Departamento de Tecnologa Electrnica Universidad de Sevilla

FA and HA. Verilog descriptions

x y
module module fa( fa( input input x, x, input input y y input input cin, cin, output output z, z, output output cout cout ); );

cout

FA

cin

assign assign z z= =x x^ ^y y^ ^ cin; cin; assign assign cout cout = = x&y x&y | | x&cin x&cin | | y&cin; y&cin; endmodule endmodule // // fa fa

x y

module module ha( ha( input input x, x, input input y y output output z, z, output output cout cout ); ); assign assign z z= =x x^ ^ y; y; assign assign cout cout = = x&y; x&y; endmodule endmodule // // ha ha

cout

HA

Departamento de Tecnologa Electrnica Universidad de Sevilla

Contents

Introduction Binary arithmetic Basic adder circuits Magnitude adder Signed binary numbers Signed adder: overflow Adder/subtractor ALU

Departamento de Tecnologa Electrnica Universidad de Sevilla

n-bit magnitude adder

cout c3 + c2 c1 a3 b3 a2 b2 a1 b1 a 0 b0 a3 a2 a1 a0 b3 b2 b1 b0 s3 s2 s1 s0 cout FA FA FA HA

s3 A A + B S cout

s2 B

s1

s0

SUM

cout

S
cout is an overflow indicator: the result cannot be represented with the available output bits.
Departamento de Tecnologa Electrnica Universidad de Sevilla

n-bit magnitude adder with carry input

cout c3 + c2 c1 cin a3 b3 a2 b2 a1 b1 a 0 b0 a3 a2 a1 a0 b3 b2 b1 b0 s3 s2 s1 s0 cout FA FA FA FA cin

s3 A A + B cin S cout cin

s2 B

s1

s0

SUM

cout

S
cin is useful to connect various adders together to sum bigger numbers.
Departamento de Tecnologa Electrnica Universidad de Sevilla

Full adder relevance

Arithmetic world

The full adder does the basic arithmetic operation (sum of two bits) by using only logic operations. The full adder is where the logic world of digital systems meets the arithmetic world of computers J. Juan

FA

Logic world

Departamento de Tecnologa Electrnica Universidad de Sevilla

Verilog examples
A
Using full adders
module module adder8_fa( adder8_fa( input input [7:0] [7:0] a, a, input input [7:0] [7:0] b, b, input input cin, cin, output output [7:0] [7:0] s, s, output output cout cout ); ); // // auxiliary auxiliary signal signal wire wire [7:1] [7:1] c; c; fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa0 fa0 fa1 fa1 fa2 fa2 fa3 fa3 fa4 fa4 fa5 fa5 fa6 fa6 fa7 fa7 (a[0], (a[0], (a[1], (a[1], (a[2], (a[2], (a[3], (a[3], (a[4], (a[4], (a[5], (a[5], (a[6], (a[6], (a[7], (a[7], b[0], b[0], b[1], b[1], b[2], b[2], b[3], b[3], b[4], b[4], b[5], b[5], b[6], b[6], b[7], b[7], cin, cin, c[1], c[1], c[2], c[2], c[3], c[3], c[4], c[4], c[5], c[5], c[6], c[6], c[7], c[7], s[0], s[0], s[1], s[1], s[2], s[2], s[3], s[3], s[4], s[4], s[5], s[5], s[6], s[6], s[7], s[7], c[1]); c[1]); c[2]); c[2]); c[3]); c[3]); c[4]); c[4]); c[5]); c[5]); c[6]); c[6]); c[7]); c[7]); cout); cout); 8

B
8

cin

SUM
8

cout

S
Using arithmetic operators
module module adder8( adder8( input input [7:0] [7:0] a, a, input input [7:0] [7:0] b, b, input input cin, cin, output output [7:0] [7:0] s, s, output output cout cout ); ); assign assign {cout, {cout, s} s} = = a+b+cin; a+b+cin; endmodule endmodule // // adder8 adder8

endmodule endmodule

// // adder8_fa adder8_fa

Departamento de Tecnologa Electrnica Universidad de Sevilla

Contents

Introduction Binary arithmetic Basic adder circuits Magnitude adder Signed binary numbers Signed adder: overflow Adder/subtractor ALU

Departamento de Tecnologa Electrnica Universidad de Sevilla

What about negative numbers? Signed binary numbers

In digital circuits there is no sign, just '0' and '1' Sign must be coded in binary Various signed number representations:

Sign-and-magnitude (Excess-e) Ones' complement Two's complement

Departamento de Tecnologa Electrnica Universidad de Sevilla

Sign-and-magnitude representation

Sign: 0(+), 1(-) n-bit different numbers: 2n-1 0 representations: 00000000, 10000000
sign magnitude

0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 1

+90(10 -41(10

2 n 1 1 x 2 n1 1

Departamento de Tecnologa Electrnica Universidad de Sevilla

Excess-e representation

Base-2 representation of the result of summing the excess or bias to the number. The result must be a positive integer. That define the range of numbers that can be represented. Ex: excess-2n-1 (n=8 2n-1=128)

-35(10 -35+128 = 93 = 01011101 exc-128

2n1 x 2n 1 1

Departamento de Tecnologa Electrnica Universidad de Sevilla

n-bit complement representation

Complement representations uses a transformation to represent negative numbers Positive numbers

Represented in natural binary Most Significant Bit (MSB) must be '0' Represented by the complement of the absolute value MSB must be '1' Sign is changed by applying the complement transformation. Ones' complement Two's complement

Negative numbers

Sign change

Complement operations

Departamento de Tecnologa Electrnica Universidad de Sevilla

n-bit ones' complement representation

OC x =2 x 1
n
Binary value 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 Ones' Unsigned complement interpretation interpretation 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 -7 9 -6 10 -5 11 -4 12 -3 13 -2 14 -1 15 0

Fast operation: Complement all the bits of x.

Note: Ones' complement operation should be distinguished from ones' complement representation. Two representation of '0' can be a problem

2n 1 1 x 2n 11

Departamento de Tecnologa Electrnica Universidad de Sevilla

n-bit two's complement representation

TC x =2 x TC x =OC x 1
Fast operation: Starting on the right, leave all the bits unchanged until the first '1' inclusive. Complement the rest.
n
Binary value 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 Two's Unsigned complement interpretation interpretation 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 -8 9 -7 10 -6 11 -5 12 -4 13 -3 14 -2 15 -1

Note: Two's complement operation should be distinguished from two's complement representation. One representation of '0'. One more negative number: -2n-1

2n1 x 2n 1 1

Departamento de Tecnologa Electrnica Universidad de Sevilla

n-bit two's complement representation

Example 1: represent in two's complement with 8 bits

32, -13, 115, -140, 128, -128 01001100, 11110000

Example 2: decimal value of two's complement numbers

Departamento de Tecnologa Electrnica Universidad de Sevilla

Two's complement sign extension

Let A be an integer value

Let a be a binary number representing A in TC with n bits Let a' be a binary number representing A in TC with n+1 bits a=A a' = A a' = a a = 2n A a' = 2n+1 A a' = a + 2n
0 1 1 0

If A 0

0 0 0 0 0 1 1 0

If A < 0

1 0 1 0

1 1 1 1 1 0 1 0

Departamento de Tecnologa Electrnica Universidad de Sevilla

Two's complement properties

Sum property

If the two's complement representation of two values A, B are added like unsigned binary numbers and the possible carry bit is neglected, the resulting binary number is the correct representation of A+B in two's complement notation, except in case of overflow.

TC representations (both positive and negative numbers) can be added with the same circuit used to add magnitudes.

Departamento de Tecnologa Electrnica Universidad de Sevilla

Two's complement properties

Overflow property

If the sign of A and B are equal and the sign of the resulting binary number obtained as described in the sum property is different than the signs of A and B, it is said that overflow has happen and the sum property does not stand.

Departamento de Tecnologa Electrnica Universidad de Sevilla

Two's complement properties

1001 = -7 0101 = +5 ----1110 = -2

1100 = -4 0100 = +4 ----10000 = 0

0011 = +3 0100 = +4 ----0111 = +7

1100 = -4 1111 = -1 ----11011 = -5

0101 = +5 0100 = +4 ----1001 = -7

1001 = -7 1010 = -6 ----10011 = +3

Overflow!
Departamento de Tecnologa Electrnica Universidad de Sevilla

Two's complement properties (optional)

A 0, B < 0

TC representation of A is: A TC representation of B is: 2 n |B| = 2n - (-B) = 2n + B Add like magnitudes

A + 2n + B = 2n + A + B 2n + A + B 2n; there is carry Carry is subtracted: 2n + A + B 2n Result: A + B (TC representation of A + B > 0) 2n + A + B < 2n; there is no carry Result: 2n - |A+B| (TC representation of (A + B < 0)

If A+B0 (A |B|)

If A+B<0

Departamento de Tecnologa Electrnica Universidad de Sevilla

Two's complement properties (optional)

A 0, B 0 (A, B < 2n-1)

TC representation of A is: A TC representation of B is: B A, B < 2n-1 A + B < 2n: there is no carry Add like magnitudes

A+B Result cannot be represented with n bits (overflow) Result can be represented with n bits. Result: A + B

If A+B 2n-1

If A+B < 2n-1

A < 0, B < 0 (left as exercise)

Departamento de Tecnologa Electrnica Universidad de Sevilla

Signed numbers summary

x -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 S-M OC 1111 1000 1110 1001 1101 1010 1100 1011 1011 1100 1010 1101 1001 1110 0000/1000 0000/1111 0001 0001 0010 0010 0011 0011 0100 0100 0101 0101 0110 0110 0111 0111 TC 1000 1001 1010 1011 1100 1101 1110 1111 0000 0001 0010 0011 0100 0101 0110 0111

Departamento de Tecnologa Electrnica Universidad de Sevilla

Contents

Introduction Binary arithmetic Basic adder circuits Magnitude adder Signed binary numbers Signed adder: overflow Adder/subtractor ALU

Departamento de Tecnologa Electrnica Universidad de Sevilla

Signed adder: overflow

Same adder used for magnitudes Carry bit is not a valid overflow indicator for TC addition. Need to include an overflow flag for TC addition.
0 1 0 ... ... ... + 1 0 1 1 0 a3 b3 ... ... ... a2 b2 a1 b1 a0 b0 ov = cn cn-1 ov = an-1 bn-1 sn-1 + an-1 bn-1 sn-1

0 1

cout ov

FA

FA

FA

FA

cin

s3

s2

s1

s0

Departamento de Tecnologa Electrnica Universidad de Sevilla

Signed adder: overflow

a 3 b3 a 2 b2 a1 b1 a0 b0

cout ov

FA

FA

FA

FA

cin

s3

s2 A

s1 B

s0

cout ov

SUM

cin

Departamento de Tecnologa Electrnica Universidad de Sevilla

Signed adder. Verilog examples

Using full adders
module module adder8_fa( adder8_fa( input input [7:0] [7:0] a, a, input input [7:0] [7:0] b, b, input input cin, cin, output output [7:0] [7:0] s, s, output output cout, cout, ov ov ); ); // // auxiliary auxiliary signal signal wire wire [7:1] [7:1] c; c; fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa0 fa0 fa1 fa1 fa2 fa2 fa3 fa3 fa4 fa4 fa5 fa5 fa6 fa6 fa7 fa7 (a[0], (a[0], (a[1], (a[1], (a[2], (a[2], (a[3], (a[3], (a[4], (a[4], (a[5], (a[5], (a[6], (a[6], (a[7], (a[7], b[0], b[0], b[1], b[1], b[2], b[2], b[3], b[3], b[4], b[4], b[5], b[5], b[6], b[6], b[7], b[7], cin, cin, c[1], c[1], c[2], c[2], c[3], c[3], c[4], c[4], c[5], c[5], c[6], c[6], c[7], c[7], s[0], s[0], s[1], s[1], s[2], s[2], s[3], s[3], s[4], s[4], s[5], s[5], s[6], s[6], s[7], s[7], c[1]); c[1]); c[2]); c[2]); c[3]); c[3]); c[4]); c[4]); c[5]); c[5]); c[6]); c[6]); c[7]); c[7]); cout); cout);

A cout ov

SUM

cin

Using arithmetic operators

module module adder8( adder8( input input [7:0] [7:0] a, a, input input [7:0] [7:0] b, b, input input cin, cin, output output [7:0] [7:0] s, s, output output cout, cout, ov ov ); ); assign assign {cout, {cout, s} s} = = a+b+cin; a+b+cin; assign assign ov ov = = ~a[7] ~a[7] & & ~b[7] ~b[7] & & s[7] s[7] | | a[7] a[7] & & b[7] b[7] & & ~s[7]; ~s[7]; endmodule endmodule // // adder8 adder8

assign assign ov ov = = c[7] c[7] ^ ^ cout; cout; endmodule endmodule // // adder8_fa adder8_fa

Departamento de Tecnologa Electrnica Universidad de Sevilla

Contents

Introduction Binary arithmetic Basic adder circuits Magnitude adder Signed binary numbers Signed adder: overflow Adder/subtractor ALU

Departamento de Tecnologa Electrnica Universidad de Sevilla

Adder/subtractor
Notation: X: signed (two's comp.) value x: unsigned (nat. binary) value

A A cout ov B

B T/C Y op

SUM

op

cout ov

SUM

cin

Z
z a+b a+b+1 op 0 1 y b b cin 0 1 z=a+y+cin a+b a+b+1 Z A+B A-B

op 0 1

Z A+B A-B

Departamento de Tecnologa Electrnica Universidad de Sevilla

Adder/subtractor Transfer/Complement (T/C) block

B T/C Y op
bi op 0 0 1 1

0 1
yi

1 0
bi

op yi

bn1

b1

b0 op

yn1

y1

y0

Departamento de Tecnologa Electrnica Universidad de Sevilla

Adder/subtractor. Verilog description

module module addsub addsub #(parameter #(parameter W W= = 8)( 8)( input input wire wire signed signed [W-1:0] [W-1:0] a, a, input input wire wire signed signed [W-1:0] [W-1:0] b, b, input input wire wire op, op, output output reg reg signed signed [W-1:0] [W-1:0] z, z, output output reg reg cout, cout, ov ov ); ); reg reg signed signed [WIDTH:0] [WIDTH:0] s; s; always always @* @* begin begin case case (op) (op) 0: 0: s s= =a a+ + b; b; default: default: s s= =a a- b; b; endcase endcase if if (s[W] (s[W] != != s[W-1]) s[W-1]) ov ov = = 1; 1; else else ov ov = = 0; 0; {cout, {cout, z} z} = = s; s; end end endmodule endmodule // // addsub addsub
Departamento de Tecnologa Electrnica Universidad de Sevilla

cout ov

SUM

op

Contents

Introduction Binary arithmetic Basic adder circuits Magnitude adder Signed binary numbers Signed adder: overflow Adder/subtractor ALU

Departamento de Tecnologa Electrnica Universidad de Sevilla

ALU

Data processing operations concentrated in a single device

A n Selection inputs n

Logic operations Arithmetic operations

ALU
n Z

State outputs

One of the most important parts of a computer

Departamento de Tecnologa Electrnica Universidad de Sevilla

Sample ALU

s2s1s0 A n s[2:0] n B 000 001 Cout ov 010 011 100 101 Z 110 111

Z A+B A-B A+1 A-1

z a+b a+b+1 a+1 a+2n-1 Arithmetic (s 2=0)

ALU
n

a AND b a OR b a XOR b NOT a Logic (s2=1)

Departamento de Tecnologa Electrnica Universidad de Sevilla

ALU design strategy

Divide and conquer! (again)

Design a logic unit and an arithmetic unit independently. Select with s2 (multiplexer?) Select the appropriate operation with s 1 and s0 (multiplexer?) Start with a magnitude's adder Calculate adder's inputs (B and Cin) to obtain the desired result. Select the appropriate B and Cin with s 1 and s0 (multiplexer?)

Logic unit

Arithmetic unit

Departamento de Tecnologa Electrnica Universidad de Sevilla

ALU design

Logic Unit
s1 s0 ZL s2

Arithmetic Unit

cout ov

ZA

Departamento de Tecnologa Electrnica Universidad de Sevilla

1
Z

ALU design. Logic unit

A s1 s0 B s1s0 00 zl a AND b a OR b a XOR b NOT a zli ai AND bi ai OR bi ai XOR bi NOT ai

Logic Unit
ZL

01 10 11

0 ai bi 1 2 3 1 0 s1 s 0 zli

Departamento de Tecnologa Electrnica Universidad de Sevilla

ALU design. Arithmetic unit

A A s1 s0 B B

control Arithmetic Unit

cout ZA a+b+1 ov y

s1 s0

SUM

cin

ZA s1s0 00 01 10 11 y b b 0 2 -1
n

s1s0 00 01 10 11

ZA A+B AB A+1 A1

zA a+b a+b+1 a+1 a + 2 -1

n

yi bi bi 0 1

cin 0 1 1 0

Departamento de Tecnologa Electrnica Universidad de Sevilla

ALU design. Arithmetic unit

B s1s0 s1 s0 00 y b b 0 2n-1 yi bi bi 0 1 cin 0 1 1 0

control

01 10

cin

11

bi

0 1 0 1 2 3 1 0 yi s1 s0

cin

s 1 s0

Departamento de Tecnologa Electrnica Universidad de Sevilla

ALU. Verilog description

module module alu alu #(parameter #(parameter W W= = 8)( 8)( input input signed signed [W-1:0] [W-1:0] a, a, input input signed signed [W-1:0] [W-1:0] b, b, input input [2:0] [2:0] s, s, output output reg reg signed signed [W-1:0] [W-1:0] z, z, output output reg reg cout, cout, output reg ov output reg ov ); ); reg reg signed signed [W:0] [W:0] s; s; always always @* @* begin begin cout cout = = 0; 0; ov ov = = 0; 0; if // if (s[2] (s[2] == == 0) 0) // Arithmetic Arithmetic operations operations begin begin case (s[1:0]) case (s[1:0]) 2'b00: s 2'b00: s= =a a+ + b; b; 2'b01: s 2'b01: s= =a a- b; b; 2'b10: s = a + 1; 2'b10: s = a + 1; 2'b11: s 2'b11: s= =a a- 1; 1; endcase endcase // // Overflow Overflow calculation calculation ov ov = = (s[WIDTH] (s[WIDTH] == == s[WIDTH-1])? s[WIDTH-1])? 0: 0: 1; 1; end end {cout, {cout, z} z} = = s; s; else else // // Logic Logic operations operations case case (s[1:0]) (s[1:0]) 2'b00: z 2'b00: z= =a a& & b; b; 2'b01: z 2'b01: z= =a a| | b; b; 2'b10: z 2'b10: z= =a a^ ^ b; b; 2'b11: z = ~a; 2'b11: z = ~a; endcase endcase end end // // always always endmodule endmodule // // alu alu

A W s[2:0] W

ALU
W Z

Cout ov

Departamento de Tecnologa Electrnica Universidad de Sevilla