Notes unit 2

ELECTRICAL AND COMPUTER ENGINEERING DEPARTMENT, OAKLAND UNIVERSITY
ECE-378: Computer Hardware Design Winter 2017
1 Instructor: Daniel Llamocca
Computer Arithmetic
INTEGER NUMBERS
UNSIGNED INTEGER NUMBERS
 𝑛 − 𝑏𝑖𝑡 number: 𝑏𝑛−1𝑏𝑛−2 … 𝑏0.
 Here, we represent 2𝑛 integer positive numbers from 0 to 2𝑛 − 1.
SIGNED INTEGER NUMBERS
 𝑛-bit number 𝑏𝑛−1𝑏𝑛−2 … 𝑏1𝑏0.
 Here, we represent integer positive and negative numbers. There exist three common representations: sign-and-magnitude,
1’s complement, and 2’s complement. In these 3 cases, the MSB always specifies whether the number is positive (MSB=0)
or negative (MSB=1).
 It is common to refer to signed numbers as numbers represented in 2’s complement arithmetic.
SIGN-AND-MAGNITUDE (SM):
 Here, the sign and the magnitude are represented separately.
 The MSB only represents the sign and the remaining 𝑛 − 1 bits the magnitude. With 𝑛 bits, we can represent 2𝑛 − 1 numbers.
 Example (n=4): 0110 = +6 1110 = -6
1'S COMPLEMENT (1C) and 2’S COMPLEMENT (2C):
 If MSB=0  the number is positive and the remaining 𝑛 − 1 bits represent the magnitude.
 If MSB=1  the number is negative and the remaining 𝑛 − 1 bits do not represent the magnitude.
 When using the 1C or the 2C representations, it is mandatory to specify the number of bits being used. If not, assume the
minimum possible number of bits.
1’S COMPLEMENT 2’S COMPLEMENT
Range of values −2𝑛−1
+ 1 𝑡𝑜 2𝑛−1
− 1 −2𝑛−1
𝑡𝑜 2𝑛−1
− 1
Numbers represented 2𝑛 − 1 2𝑛
Inverting sign of a
number
Apply 1C operation: invert all bits Apply 2C operation: invert all bits and add 1
Examples
 +6=0110  -6=1001
 +5=0101  -5=1010
 +7=0111  -7=1000
 +6=0110  -6=1010
 +5=0101  -5=1011
 +7=0111  -7=1001
 If -6=1001, we get +6 by applying the 1C
operation to 1001  +6 = 0110.
 If -6=1010, we get +6 by applying the 2C
operation to 1010  +6 = 0110.
 Represent -4 in 1C: We know that
+4=0100. To get -4, we apply the 1C
operation to 0100. Thus, -4 = 1011.
 Represent -4 in 2C: We know that
+4=0100. To get -4, we apply the 2C
operation to 0100. Thus -4 = 1100.
 Represent 8 in 1C: This is a positive
number  MSB=0. The remaining 𝑛 − 1
bits represent the magnitude.
Magnitude (unsigned number) with a min.
of 4 bits: 8=10002. Thus, with a minimum
of 5 bits, 8=010002 (1C).
 What is the decimal value of 1100? We
first apply the 1C operation (or take the 1’s
complement) to 1100, which results in
0011(+3). Thus 1100=-3.
 Represent 12 in 2C: This is a positive number
 MSB=0. The remaining 𝑛 − 1 bits
represent the magnitude.
Magnitude (unsigned number) with a min. of
4 bits: 12=11002. Thus, with a minimum of
5 bits, 12=011002 (2C).
 What is the decimal value of 1101? We first
apply the 2C operation (or take the 2’s
complement) to 1101, which results in
0011(+3). Thus 1101=-3.
Getting the decimal value of a number in 2C representation:
 If the number 𝐵 is positive, then MSB=0: 𝑏𝑛−1 = 0.
→ 𝐵 = ∑ 𝑏𝑖2𝑖
𝑛−1
𝑖=0
= 𝑏𝑛−12𝑛−1
+ ∑ 𝑏𝑖2𝑖
𝑛−2
𝑖=0
= ∑ 𝑏𝑖2𝑖
𝑛−2
𝑖=0
(𝑎)
 If the number 𝐵 is negative, 𝑏𝑛−1 = 1 (MSB=1). If we take the 2’s complement of 𝐵, we get 𝐾 (which is a positive number).
In 2’s complement representation, 𝐾 represents −𝐵. Using 𝐾 = 2𝑛
− 𝐵 (𝐾 and 𝐵 are treated as unsigned numbers):

∑ 𝑘𝑖2𝑖
𝑛−1
𝑖=0
= 2𝑛
− ∑ 𝑏𝑖2𝑖
𝑛−1
𝑖=0
 We want to express – 𝐾 in terms of 𝑏𝑖, since the integer value – 𝐾 is the actual integer value of 𝐵.
−𝐾 = − ∑ 𝑘𝑖2𝑖
𝑛−1
𝑖=0
= ∑ 𝑏𝑖2𝑖
𝑛−1
𝑖=0
− 2𝑛
= 𝑏𝑛−12𝑛−1
+ ∑ 𝑏𝑖2𝑖
𝑛−2
𝑖=0
− 2𝑛
= 2𝑛−1(𝑏𝑛−1 − 2) + ∑ 𝑏𝑖2𝑖
𝑛−2
𝑖=0
𝐵 = −𝐾 = 2𝑛−1(1 − 2) + ∑ 𝑏𝑖2𝑖
𝑛−2
𝑖=0
= −2𝑛−1
+ ∑ 𝑏𝑖2𝑖
𝑛−2
𝑖=0
(𝑏)
 Using (a) and (b), the formula for the decimal value of 𝐵 (either positive or negative) is:
𝐵 = −𝑏𝑛−12𝑛−1
+ ∑ 𝑏𝑖2𝑖
𝑛−2
𝑖=0
 Examples: 101102 = −24
+ 22
+ 21
= −10 110002 = −24
+ 23
= −8
SUMMARY
 The following table summarizes the signed representations for a 4-bit number:
n=4:
b3b2b1b0
SIGNED REPRESENTATION
Sign-and-magnitude 1’s complement 2’s complement
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
0
1
2
3
4
5
6
7
0
-1
-2
-3
-4
-5
-6
-7
0
1
2
3
4
5
6
7
-7
-6
-5
-4
-3
-2
-1
0
0
1
2
3
4
5
6
7
-8
-7
-6
-5
-4
-3
-2
-1
Range for 𝑛 bits: [−(2𝑛−1
− 1), 2𝑛−1
− 1] [−(2𝑛−1
− 1), 2𝑛−1
− 1] [−2𝑛−1
, 2𝑛−1
− 1]
 Keep in mind that 1C (or 2C) representation and the 1C (or 2C) operation are very different concepts.
 Note that the sign-and-magnitude and the 1C representations have a redundant representation for zero. This is not the case
in 2C, which can represent an extra number.
 Special case in 2C: If −2𝑛−1
is represented with 𝑛 bits, the number 2𝑛−1
requires 𝑛 + 1 bits. For example, the number -8
can be represented with 4 bits: -8=1000. To obtain +8, we apply the 2C operation to 1000, which results in 1000. But
1000 cannot be a positive number. This means that we require 5 bits to represent +8=01000.
 Representation of Integer Numbers with 𝒏 bits: 𝑏𝑛−1𝑏𝑛−2 … 𝑏0.
UNSIGNED SIGNED (2C)
Decimal Value 𝐷 = ∑ 𝑏𝑖2𝑖
𝑛−1
𝑖=0
𝐷 = −2𝑛−1
𝑏𝑛−1 + ∑ 𝑏𝑖2𝑖
𝑛−2
𝑖=0
Range of values [0, 2𝑛
− 1] [−2𝑛−1
, 2𝑛−1
− 1]
SIGN EXTENSION
 UNSIGNED NUMBERS: Here, if we want to use more bits, we just append zeros to the left.
Example: 12 = 11002 with 4 bits. If we want to use 6 bits, then 12 = 0011002.
 SIGNED NUMBERS:
 Sign-and-magnitude: The MSB only represents the sign. If we want to use more bits, we append zeros to the left,
with the MSB (leftmost bit) always being the sign.
Example: -12 = 111002 with 5 bits. If we want to use 7 bits, then -12 = 10011002.
 2’s complement (also applies to 1C): In many circumstances, we might want to represent numbers in 2's complement
with a certain number of bits. For example, the following two numbers require a minimum of 5 bits:
101112 = −24
+ 22
+ 21
+ 20
= −9 011112 = 23
+ 22
+ 21
+ 20
= +15

What if we want to use 8 bits to represent them? In 2C, we sign-extend: If the number is positive, we append 0’s to the
left. If the number is negative, we attach 1’s to the left. In the examples, we copied the MSB three times to the left:
111101112 = −24 + 22 + 21 + 20 = −9 000011112 = 23 + 22 + 21 + 20 = +15
Demonstration of sign-extension in 2C arithmetic:
 To increase the number of bits for representing a number, we append the MSB to the left as many times as needed:
𝑏𝑛−1𝑏𝑛−2 … 𝑏0  𝑏𝑛−1 … 𝑏𝑛−1𝑏𝑛−1𝑏𝑛−2 … 𝑏0
Examples: 001012 = 00001012 = 22
+ 20
= 5
101012 = 11101012 = −24
+ 22
+ 20
= −26
+ 25
+ 24
+ 22
+ 20
= −11
We can think of the sign-extended number as an 𝑚-bit number, where 𝑚 > 𝑛:
𝑏𝑛−1 … 𝑏𝑛−1𝑏𝑛−1𝑏𝑛−2 … 𝑏0 = 𝑏𝑚−1 … 𝑏𝑛𝑏𝑛−1𝑏𝑛−2 … 𝑏0, where: 𝑏𝑖 = 𝑏𝑛−1, 𝑖 = 𝑛, 𝑛 + 1, … , 𝑚 − 1
 We need to demonstrate that 𝑏𝑛−1𝑏𝑛−2 … 𝑏0 represents the same decimal number as 𝑏𝑛−1 … 𝑏𝑛−1𝑏𝑛−1𝑏𝑛−2 … 𝑏0, i.e., that the
sign-extension is correct for any 𝑚 > 𝑛.
We need that: 𝑏𝑚−1 … 𝑏𝑛𝑏𝑛−1𝑏𝑛−2 … 𝑏0 = 𝑏𝑛−1 … 𝑏𝑛−1𝑏𝑛−1𝑏𝑛−2 … 𝑏0 = 𝑏𝑛−1𝑏𝑛−2 … 𝑏0
Using the formula for 2's complement numbers:
−2𝑚−1
𝑏𝑚−1 + ∑ 2𝑖
𝑏𝑖
𝑚−2
𝑖=0
= −2𝑛−1
𝑏𝑛−1 + ∑ 2𝑖
𝑏𝑖
𝑛−2
𝑖=0
−2𝑚−1
𝑏𝑚−1 + ∑ 2𝑖
𝑏𝑖
𝑚−2
𝑖=𝑛−1
+ ∑ 2𝑖
𝑏𝑖
𝑛−2
𝑖=0
= −2𝑛−1
𝑏𝑛−1 + ∑ 2𝑖
𝑏𝑖
𝑛−2
𝑖=0
 − 2𝑚−1
𝑏𝑚−1 + ∑ 2𝑖
𝑏𝑖
𝑚−2
𝑖=𝑛−1
= −2𝑛−1
𝑏𝑛−1
−2𝑚−1
𝑏𝑛−1 + 𝑏𝑛−1 ∑ 2𝑖
𝑚−2
𝑖=𝑛−1
= −2𝑛−1
𝑏𝑛−1,
𝑅𝑒𝑐𝑎𝑙𝑙: ∑ 𝑟𝑖
𝑙
𝑖=𝑘
=
𝑟𝑘 − 𝑟𝑙+1
1 − 𝑟
, 𝑟 ≠ 1 → ∑ 2𝑖
𝑙
𝑖=𝑘
=
2𝑘 − 2𝑙+1
1 − 2
= 2𝑙+1
− 2𝑘
Then:
−2𝑚−1
𝑏𝑛−1 + 𝑏𝑛−1(2𝑚−1
− 2𝑛−1) = −2𝑛−1
𝑏𝑛−1
−2𝑚−1
𝑏𝑛−1 + 2𝑚−1
𝑏𝑛−1 − 2𝑛−1
𝑏𝑛−1 = −2𝑛−1
𝑏𝑛−1 ∴ −2𝑛−1
𝑏𝑛−1 = −2𝑛−1
𝑏𝑛−1
ADDITION/SUBTRACTION
UNSIGNED NUMBERS
 The example depicts addition of two 8-bit numbers using binary
and hexadecimal representations. Note that every summation
of two digits (binary or hexadecimal) generates a carry when
the summation requires more than one digit. Also, note that c0
is the carry in of the summation (usually, c0 is zero).
 The last carry (c8 when n=8) is the carry out of the summation.
If it is ‘0’, it means that the summation can be represented with
8 bits. If it is ‘1’, it means that the summation requires more
than 8 bits (in fact 9 bits); this is called an overflow. In the
example, we add two numbers and overflow occurs: an extra
bit (in red) is required to correctly represent the summation.
This carry out can also be used for multi-precision addition.
Arithmetic Overflow:
 Suppose we have only 4 bits to represent binary numbers. Overflow
occurs when an arithmetic operation requires more bits than the bits
we are using to represent our numbers. For 4 bits, the range is 0 to 15.
If the summation is greater than 15, then there is overflow.
 For 𝑛 bits, overflow occurs when the sum is greater than 2𝑛
− 1. Also: 𝑜𝑣𝑒𝑟𝑓𝑙𝑜𝑤 = 𝑐𝑛 = 𝑐𝑜𝑢𝑡.
Overflow is commonly avoided by sign-extending the two operators. For unsigned numbers, sign-
extension amounts to zero-extension. For example, if the summands are 4-bits wide, then we append
a 0 to both summands, using 5 bits to represent the summands (see figure on the right).
 For two 𝑛-bits summands, the result will have at most 𝑛 + 1 bits (2𝑛
− 1 + 2𝑛
− 1 = 2𝑛+1
− 2).
0x3F = 0 0 1 1 1 1 1 1 +
0xB2 = 1 0 1 1 0 0 1 0
0xF1 = 1 1 1 1 0 0 0 1
c
8
=0
c
7
=0
c
6
=1
c
5
=1
c
4
=1
c
3
=1
c
2
=1
c
1
=0
c
0
=0
3 F +
B 2
F 1
c
2
=0
c
1
=1
c
0
=0
0x3F = 0 0 1 1 1 1 1 1 +
0xC2 = 1 1 0 0 0 0 1 0
c
8
=1
c
7
=1
c
6
=1
c
5
=1
c
4
=1
c
3
=1
c
2
=1
c
1
=0
c
0
=0
3 F +
C 2
c
2
=1
c
1
=1
c
0
=0
1 0 0 0 0 0 0 0 1 1 0 1
01011 +
00110
10001
cout=0
0101 +
1001
1110
cout=0
No Overflow
1011 +
0110
10001
cout=1
Overflow!

Subtraction:
 In the example, we subtract two 8-bit numbers using the
binary and hexadecimal (this is a short-hand notation)
representations. A subtraction of two digits (binary or
hexadecimal) generates a borrow when the difference is
negative. So, we borrow 1 from the next digit so that the
difference is positive. Recall that a borrow in a subtraction of
two digits is an extra 1 that we need to subtract. Also, note
that b0 is the borrow in of the summation. This is usually zero.
 The last borrow (b8 when n=8) is the borrow out of the
subtraction. If it is zero, it means that the difference is positive
and can be represented with 8 bits. If it is one, it means that
the difference is negative and we need to borrow 1 from the
next digit. In the example, we subtract two 8-bit numbers, the
result we have borrows 1 from the next digit.
 Subtraction using unsigned numbers only makes sense if the result is positive (or when doing multi-precision subtraction).
In general, we prefer to use signed representation (2C) for subtraction.
SIGNED NUMBERS (2C REPRESENTATION)
 The advantage of the 2C representation is that the summation can be carried out using the same circuitry as that of the
unsigned summation. Here the operands can be either positive or negative.
 The following are addition examples of two 4-bit signed numbers. Note that the carry out bit DOES NOT necessarily indicate
overflow. In some cases, the carry out must be ignored, otherwise the result is incorrect.
 Now, we show addition examples of two 8-bit signed numbers. The carry out c8 is not enough to determine overflow. Here,
if c8≠c7 there is overflow. If c8=c7, no overflow and we can ignore c8. Thus, the overflow bit is equal to c8 XOR c7.
 Overflow: It occurs when the summation falls outside the 2’s complement range for 8 bits: [−27
, 27
− 1]. If there is no
overflow, the carry out bit must not be part of the result.
 To avoid overflow, a common technique is to sign-extend the two
summands. For example, for two 4-bits summands, we add an
extra bit; thereby using 5 bits to represent the operators. +7 = 0 0 1 1 1 +
+2 = 0 0 0 1 0
+9 = 0 1 0 0 1
-7 = 1 1 0 0 1 +
-2 = 1 1 1 1 0
-9 = 1 0 1 1 1
c
5
=0
c
4
=0
c
3
=1
c
2
=1
c
1
=0
c
0
=0
c
5
=1
c
4
=1
c
3
=0
c
2
=0
c
1
=0
c
0
=0
+14  [-27, 27-1] -> no overflow
overflow = c8c7=1 -> overflow!
+170  [-27, 27-1] -> overflow!
+92 = 0 1 0 1 1 1 0 0 +
+78 = 0 1 0 0 1 1 1 0
+170 = 0 1 0 1 0 1 0 1 0
c
8
=0
c
7
=1
c
6
=0
c
5
=1
c
4
=1
c
3
=1
c
2
=0
c
1
=0
c
0
=0
overflow = c8c7=1 -> overflow!
-170  [-27, 27-1] -> overflow!
-92 = 1 0 1 0 0 1 0 0 +
-78 = 1 0 1 1 0 0 1 0
-170 = 1 0 1 0 1 0 1 1 0
c
8
=1
c
7
=0
c
6
=1
c
5
=0
c
4
=0
c
3
=0
c
2
=0
c
1
=0
c
0
=0
overflow = c8c7=0 -> no overflow
+92 = 0 1 0 1 1 1 0 0 +
-78 = 1 0 1 1 0 0 1 0
+14 = 1 0 0 0 0 1 1 1 0
c
8
=1
c
7
=1
c
6
=1
c
5
=1
c
4
=0
c
3
=0
c
2
=0
c
1
=0
c
0
=0
overflow = c8c7=0 -> no overflow
-92 = 1 0 1 0 0 1 0 0 +
+78 = 0 1 0 0 1 1 1 0
-14 = 0 1 1 1 1 0 0 1 0
c
8
=0
c
7
=0
c
6
=0
c
5
=0
c
4
=1
c
3
=1
c
2
=0
c
1
=0
c
0
=0
-14  [-27, 27-1] -> no overflow
+5 = 0101 +
+2 = 0010
+7 = 0111
cout=0
-5 = 1011 +
+2 = 0010
-3 = 1101
cout=0
+5 = 0101 +
-2 = 1110
+3 =10011
cout=1
-5 = 1011 +
-2 = 1110
-7 =11001
cout=1
0x3A = 0 0 1 1 1 0 1 0 -
0x2F = 0 0 1 0 1 1 1 1
0x0B = 0 0 0 0 1 0 1 1
b
8
=0
b
7
=0
b
6
=0
b
5
=0
b
4
=1
b
3
=1
b
2
=1
b
1
=1
b
0
=0
3 A -
2 F
0 B
b
2
=0
b
1
=1
b
0
=0
0x3A = 0 0 1 1 1 0 1 0 -
0x75 = 0 1 1 1 0 1 0 1
b
8
=1
b
7
=1
b
6
=0
b
5
=0
b
4
=0
b
3
=1
b
2
=0
b
1
=1
b
0
=0
3 A -
7 5
b
2
=1
b
1
=0
b
0
=0
0xC5 = 1 1 0 0 0 1 0 1 C 5

Subtraction
 Note that 𝐴 − 𝐵 = 𝐴 + 2𝐶(𝐵). To subtract two signed (2C) numbers,
we first apply the 2’s complement operation to 𝐵 (the subtrahend), and
then add the numbers. So, in 2’s complement arithmetic, subtraction
ends up being an addition of two numbers.
 For an 𝑛-bit number, overflow occurs when the summation/addition
result is outside the range [−2𝑛−1, 2𝑛−1 − 1]. The overflow bit can quickly be computed as 𝑜𝑣𝑒𝑟𝑓𝑙𝑜𝑤 = 𝑐𝑛𝑐𝑛−1. 𝑐𝑛 = 𝑐𝑜𝑢𝑡.
 The largest value (in magnitude) of addition of two 𝑛-bits operators is −2𝑛−1
+ (−2𝑛−1) = −2𝑛
. In the case of subtraction,
the largest value (in magnitude) is −2𝑛−1 − (2𝑛−1 − 1) = −2𝑛 + 1. Thus, the addition/subtraction of two 𝑛-bit operators
needs at most 𝑛 + 1 bits. 𝑐𝑛 = 𝑐𝑜𝑢𝑡 is used in multi-precision addition/subtraction.
SUMMARY
 Addition/Subtraction of two 𝑛-bit numbers:
UNSIGNED SIGNED (2C)
Overflow bit 𝑐𝑛 𝑐𝑛𝑐𝑛−1
Overflow occurs when: 𝐴 + 𝐵[0, 2𝑛
− 1], 𝑐𝑛 = 1 (𝐴 ± 𝐵)[−2𝑛−1
, 2𝑛−1
− 1], 𝑐𝑛𝑐𝑛−1 = 1
Result range: [0, 2𝑛+1
− 1] 𝐴 + 𝐵 ∈ [−2𝑛
, 2𝑛
− 2], 𝐴 − 𝐵 ∈ [−2𝑛
+ 1, 2𝑛
− 2]
Result requires at most: 𝑛 + 1 𝑏𝑖𝑡𝑠
 In general, if one operand has 𝑛 bits and the other has 𝑚 bits, the result will have at most 𝑚𝑎𝑥(𝑛, 𝑚) + 1. When adding
both numbers, we first force (via sign-extension) the two operators to have the same number of bits: 𝑚𝑎𝑥(𝑛, 𝑚).
MULTIPLICATION OF INTEGER NUMBERS
UNSIGNED NUMBERS
 Simple operation: first, generate the products, then add up all the columns (consider the carries).
 If the two operators are 𝑛-bits wide, the maximum result is (2𝑛 − 1) × (2𝑛 − 1) = 22𝑛 − 2𝑛+1 + 1. Thus, in the worst case,
the multiplication requires 2𝑛 bits.
 If one operator in 𝑛-bits wide and the other is 𝑚-bits wide, the maximum result is: (2𝑛
− 1) × (2𝑚
− 1) = 2𝑛+𝑚
− 2𝑛
− 2𝑚
+
1. Thus, in the worst case, the multiplication requires 𝑛 + 𝑚 bits.
SIGNED NUMBERS (2C)
 A straightforward implementation consists of checking the sign of the multiplicand and multiplier. If one or both are negative,
we change the sign by applying the 2’s complement operation. This way, we are left with unsigned multiplication.
 As for the final output: if only one of the inputs was negative, then we modify the sign of the output. Otherwise, the result
of the unsigned multiplication is the final output.
 Note: If one of the inputs is −2𝑛−1
, then when we change the sign we get 2𝑛−1
, which requires 𝑛 + 1 bits. Here, we are
allowed to use only 𝑛 bits; in other words, we do not have to change its sign. This will not affect the final result since if we
were to use 𝑛 + 1 bits for 2𝑛−1
, the MSB=0, which implies that the last row is full of zeros.
0 0 1 x
0 1 0
0 0 0
0 0 1
0 0 0
0 0 0 0 1 0
0 1 1 x
0 1 0
0 0 0
0 1 1
0 0 0
0 0 0 1 1 0
1 1 1 x
1 1 0
1 0 1 x
0 1 0
0 1 1 x
0 1 0
0 0 0
0 1 1
0 0 0
0 0 0 1 1 0
1 1 1 0 1 0
0 1 0 x
0 1 0
0 0 0
0 1 0
0 0 0
0 0 0 1 0 0
0 1 0 x
1 1 0
1 1 1 1 0 0
+7 = 0 1 1 1 +
-3 = 1 1 0 1
+4 = 0 1 0 0
cout = 1
overflow = 0
7 - 3 = 7 + (-3):
+3=0011  -3=1101
c
4
=1
c
3
=1
c
2
=1
c
1
=1
c
0
=0
1 0 1 1 x
1 1 0 1
1 0 1 1
0 0 0 0
1 0 1 1
1 0 1 1
1 0 0 0 1 1 1 1
a3 a2 a1 a0 x
b3 b2 b1 b0
a3b0 a2b0 a1b0 a0b0
a3b1 a2b1 a1b1 a0b1
a3b2 a2b2 a1b2 a0b2
a3b3 a2b3 a1b3 a0b3
p7 p6 p5 p4 p3 p2 p1 p0
11 x
13
---
143
1 1 0 1 x
1 1 1 1
1 1 0 1
1 1 0 1
1 1 0 1
1 1 0 1
1 1 0 0 0 0 1 1
13 x
15
---
195
10
10
10
1
1
1
1
1
0
0
0
0
1
0
0
0

 Note: If one input is negative and the other is positive, we can use the negative
number as the multiplicand and the positive number as the multiplier. Then, we can
operate as if it were unsigned multiplication, with the caveat that we need to sign
extend each partial sum to 2𝑛 bits (if both operators are 𝑛-bits wide), or to 𝑛 + 𝑚 (if
one operator is 𝑛-bits wide and the other is 𝑚-bits wide).
 For two 𝑛-bit operators, the final output requires 2𝑛 bits. Note that it is only because of the multiplication −2𝑛−1
× −2𝑛−1
=
22𝑛−2
that we require those 2𝑛 bits (in 2C representation).
 For an 𝑛-bit and an 𝑚-bit operator, the final output requires 𝑛 + 𝑚 bits. Note that it is only because of the multiplication
−2𝑛−1
× −2𝑚−1
= 2𝑛+𝑚−2
that we require those 𝑛 + 𝑚 bits (in 2C representation).
DIVISION OF INTEGER NUMBERS
UNSIGNED NUMBERS
 The division of two unsigned integer numbers 𝐴
𝐵
⁄ (where 𝐴 is the dividend and 𝐵 the divisor), results in a quotient 𝑄 and
a remainder 𝑅, where 𝐴 = 𝐵 × 𝑄 + 𝑅. Most divider architectures provide 𝑄 and 𝑅 as outputs.
 For 𝑛-bits dividend (𝐴) and 𝑚-bits divisor (𝐵):
 The largest value for 𝑄 is 2𝑛
− 1 (by using 𝐵 = 1). The smallest value for 𝑄 is 0. So, we use 𝑛 bits for 𝑄.
 The remainder 𝑅 is a value between 0 and 𝐵 − 1. Thus, at most we use 𝑚 bits for 𝑅.
 If 𝐴 = 0, 𝐵 ≠ 0, then 𝑄 = 𝑅 = 0.
 If 𝐵 = 0, we have a division by zero. The result is undetermined.
 In computer arithmetic, integer division usually means getting 𝑄 = ⌊𝐴 𝐵
⁄ ⌋.
 Examples:
1 0 0 x
0 1 1
1 0 0
1 0 0
0 0 0
0 0 1 1 0 0
1 0 0 x
0 1 1
1 1 0 1 0 0
0 1 1 x
1 0 0
0 0 0
0 0 0
0 1 1
0 0 1 1 0 0
0 1 1 x
1 0 0
1 1 0 1 0 0
1 0 0 x
1 0 0
0 0 0
0 0 0
1 0 0
0 1 0 0 0 0
1 0 0 x
1 0 0
1 0 0 1 x
0 1 1 0
1 0 0 1 x
0 1 1 0
0 0 0 0 0 0 0 0
1 1 1 1 0 0 1
1 1 1 0 0 1
0 0 0 0 0
1 1 0 1 0 1 1 0
00001111
10011101
1010
10011
1010
10010
1010
10001
1010
111
1010
00000111
10100001
10101
100110
10101
100011
10101
1110
10101
000010100
110100010
10100
11000
10100
10010
10100
000000111
101010001
101110
1001100
101110
111101
101110
1111
101110
157/10:
Q = 15
R = 7
161/21:
Q = 7
R = 14
418/20:
Q = 20
R = 18
337/46:
Q = 7
R = 15
00001111
10001100
1001
10001
1001
10000
1001
1110
1001
101
1001 A
B
Q
R
ALGORITHM
R = 0
for i = n-1 downto 0
left shift R (input = ai)
if R  B
qi = 1, R  R-B
else
qi = 0
end
end
15
140
90
50
45
5
9 A
B
Q
R

SIGNED NUMBERS
 The division of two signed numbers 𝐴
𝐵
⁄ should result in 𝑄 and 𝑅 such that 𝐴 = 𝐵 × 𝑄 + 𝑅. As in signed multiplication, we
first perform the unsigned division
|𝐴|
|𝐵|
⁄ and get 𝑄’ and 𝑅’ such that: |𝐴| = |𝐵| × 𝑄′ + 𝑅′. Then, to get 𝑄 and 𝑅, we apply:
Quotient 𝑄 Residue 𝑅
𝐴 × 𝐵 < 0 −𝑄’
−𝑅’ 𝐴 < 0, 𝐵 > 0
𝑅’ 𝐴 > 0, 𝐵 < 0
𝐴 × 𝐵 ≥ 0, 𝐵 ≠ 0 𝑄’
𝑅’ 𝐴 ≥ 0, 𝐵 > 0
−𝑅’ 𝐴 < 0, 𝐵 < 0
 Important: To apply 𝑄 = −𝑄′ = 2𝐶(𝑄’), 𝑄’ must be in 2C representation. The same applies to 𝑅 = −𝑅′ = 2𝐶(𝑅′). So, if 𝑄’ =
1101 = 13, we first turn this unsigned number into a signed number  𝑄’ = 01101. Then 𝑄 = 2𝐶(01101) = 10011 = −13.
 Example:
011011
0101
=
27
5
 Convert both numerator and denominator into unsigned numbers:
11011
101

|𝐴|
|𝐵|
 𝑄′ = 101, 𝑅′ = 10. Note that these are unsigned numbers.
 Get 𝑄 and 𝑅: 𝐴 ≤ 0, 𝐵 > 0  𝑄 = 𝑄′ = 0101 = 5, 𝑅 = 𝑅′ = 010 = 2.
Note that 𝑄 and 𝑅 are signed numbers.
 Verification: 27 = 5 × 5 + 2.
 Example:
0101110
1011
=
46
−5
 Turn the denominator into a positive number 
0101110
0101
101110
101
=
|𝐴|
|𝐵|

|𝐴|
|𝐵|
 Get 𝑄 and 𝑅: 𝐴 > 0, 𝐵 < 0  𝑄 = 2𝐶(𝑄′) = 2𝐶(01001) = 10111 = −9, 𝑅 = 𝑅′ = 001 = 1.
 Verification: 46 = −5 × −9 + 1.
 Example:
10110110
01101
=
−74
13
 Turn the numerator into a positive number 
01001010
01101
1001010
1101

|𝐴|
|𝐵|
 Get 𝑄 and 𝑅: 𝐴 < 0, 𝐵 > 0  𝑄 = 2𝐶(0101) = 1011 = −5, 𝑅 = 2𝐶(𝑅′) = 2𝐶(01001) = 10111 = −9.
 Verification: −74 = 13 × −5 + (−9).
 Example:
10011011
1001
=
−101
−7
 Turn the numerator and denominator into positive numbers 
01100101
0111
1100101
111

|𝐴|
|𝐵|
 𝑄′ = 1110, 𝑅′ = 11. These are unsigned numbers.
 Get 𝑄 and 𝑅: 𝐴 < 0, 𝐵 < 0  𝑄 = 𝑄′ = 01110 = 14, 𝑅 = 2𝐶(𝑅′) = 2𝐶(011) = 101 = −3.
 Verification: −101 = −7 × 14 + (−3).
001001
101110
101
0110
101
1
101
0000101
1001010
1101
10110
1101
1001
1101
0001110
1100101
111
1011
111
1000
111
11
111
00101
11011
101
111
101
10
101

BASIC ARITHMETIC UNITS FOR INTEGER NUMBERS
 Boolean Algebra is a very powerful tool for the implementation of digital circuits. Here, we map Boolean Algebra expressions
into binary arithmetic expressions for the implementation of binary arithmetic units. Note the operators ‘+’, ‘.’ in Boolean
Algebra are not the same as addition/subtraction, and multiplication in binary arithmetic.
UNSIGNED NUMBERS
 1-bit Addition:
 Addition of a bit with carry in: The circuit that performs this operation is called Half Adder (HA).
 Addition of a bit with carry in: The circuit that performs this operation is called Full Adder (FA).
 𝒏-bit Addition:
The figure on the right shows a 5-bit addition. Using the truth table
method, we would need 11 inputs and 6 outputs. This is not practical!
Instead, it is better to build a cascade of Full Adders.
For an n-bit addition, the circuit will be:
 Overflow
x +
y
co s
ci
FA
x
y
ci
s
co
HA
x
y
s
c
FA
x
y
0
s
co

carry out sum
x +
y
c s
carry out sum
0 +
0
0 0
0 +
1
0 1
1 +
0
0 1
1 +
1
1 0
x y
0 0
0 1
1 0
1 1
c s
0 0
0 1
0 1
1 0
x
y
c
s
HA
x
y
s
c
15: 0 1 1 1 1 +
10: 0 1 0 1 0
25: 1 1 0 0 1
x4x3x2x1x0 +
y4y3y2y1y0
s4s3s2s1s0
c
5
=0
c
4
=1
c
3
=1
c
2
=1
c
1
=0
c
0
=0
cin
cout
cn-1
FA
x0 y0
c0
s0
FA
x1 y1
c1
s1
FA
x2 y2
c2
s2
c3
FA
xn-1 yn-1
sn-1
cn ...
cout
cin
0 1
xi yi ci ci+1 si
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 1 1
1 0
ci
xiyi
0
1
00 01
0 1
1 0
11 10 si = xiyici + xiyici + xiyici + xiyici
si = (xiyi)ci + (xiyi)ci
si = xiyici
0 0
0 1
ci
xiyi
0
1
00 01
1 0
1 1
11 10
ci+1 = xiyi + xici + yici
xn-1xn-2...x1x0 +
yn-1yn-2...y1y0
sn-1sn-2...s1s0
cin
cout
Full Adder Design
cn-1
FA
x0 y0
c0
s0
FA
x1 y1
c1
s1
FA
x2 y2
c2
s2
c3
FA
xn-1 yn-1
sn-1
cn ...
overflow=cout
cin
+ cin
cout


 n-bit Subtractor:
We can build an 𝑛-bit subtractor for unsigned numbers using Full Subtractor circuits. In practice, subtraction is better
performed in the 2’s complement representation (this accounts for signed numbers).
SIGNED NUMBERS
 The figure depicts an 𝑛-bit adder for 2’s complement numbers:
 Subtraction: 𝐴 − 𝐵 = 𝐴 + 2𝐶(𝐵). In 2C arithmetic, subtraction is actually an addition of two numbers.
The digital circuit for 2C subtraction is based on the adder. We account for the 2’s complement operation for the subtrahend
by inverting every bit in the subtrahend and by making the cin bit equal to 1.
 Adder/Subtractor Unit for 2's complement numbers:
We can combine the adder and subtractor in a single circuit if we are willing to give up the input cin.
bn-1
FS
x0 y0
b0
d0
FS
x1 y1
b1
d1
FS
x2 y2
b2
d2
b3
FS
xn-1 yn-1
dn-1
bn
...
bout
bin
0 1
xi yi bi bi+1 di
0 0 0 0 0
0 0 1 1 1
0 1 0 1 1
0 1 1 1 0
1 0 0 0 1
1 0 1 0 0
1 1 0 0 0
1 1 1 1 1
1 0
bi
xiyi
0
1
00 01
0 1
1 0
11 10 di = xiyibi + xiyibi + xiyibi + xiyibi
di = (xiyi)bi + (xiyi)bi
di = xiyibi
0 1
1 1
bi
xiyi
0
1
00 01
0 0
1 0
11 10
bi+1 = xiyi + xibi + yibi
xn-1xn-2...x1x0 -
yn-1yn-2...y1y0
dn-1dn-2...d1d0
bin
bout
Full Subtractor Design
cn-1
FA
x0 y0
c0
s0
FA
x1 y1
c1
s1
FA
x2 y2
c2
s2
c3
FA
xn-1 yn-1
sn-1
cn ...
cin
overflow
cout
cn-1
FA
x0 y0
c0
s0
FA
x1 y1
c1
s1
FA
x2 y2
c2
s2
c3
FA
xn-1 yn-1
sn-1
cn ... cin = 1
overflow
cout
...
 + cin=1
cout
overflow
add/sub yi
0 0
0 1
1 0
1 1
f
0
1
1
0
add/sub
yi
f
cn-1
FA
c0
s0
FA
c1
s1
FA
c2
s2
c3
FA
xn-1 yn-1
sn-1
cn ...
overflow
cout
...
x2 y2 x1 y1 x0 y0
add/sub
add = 0
sub = 1
+/- +/- add/sub
Adder/Subtractor:
cout
overflow

MULTIPLICATION
UNSIGNED NUMBERS
 The figure shows the process for multiplying two unsigned numbers of 4 bits.
 A straightforward implementation of the multiplication operation is also depicted in the figure below: at every diagonal of
the circuit, we add up all terms in a column of the multiplication.
b(3)
p(0)
p(1)
p(2)
p(3)
p(4)
p(5)
p(6)
p(7)
b(2) b(1) b(0)
a(0)
a(1)
a(2)
a(3)
x y
cin
cout
s
a3 a2 a1 a0 x
b3 b2 b1 b0
a3b0 a2b0 a1b0 a0b0
a3b1 a2b1 a1b1 a0b1
a3b2 a2b2 a1b2 a0b2
a3b3 a2b3 a1b3 a0b3
p7 p6 p5 p4 p3 p2 p1 p0
a1b0
a0b0
a2b0
a3b0
a0b1
a1b1
a2b1
a3b1
a0b2
a1b2
a2b2
a3b2
a0b3
a1b3
a2b3
a3b3
FULL
ADDER
m10
m11
m12
m13
m00
m01
m02
m03
m20
m21
m22
m23
m30
m31
m32
m33
s10
s11
s12
s20
s21
s22
s30
s31
s32
c02 c01 c00
c12 c11 c10
c22 c21 c20
c32 c31 c30
s13
s23
s33
s00
s01
s02
s03
m40
m41
m42
m43

 An alternative implementation of the multiplication operation is depicted below for 4-bit unsigned numbers. It is much simpler
to see how only two rows are added up at each stage.
SIGNED NUMBERS (2C)
 This signed multiplier uses an unsigned multiplier, three adder subtractors (with one constant input), and a logic gate.
 The initial adder/subtractor units provide the absolute values of 𝐴 and 𝐵.
 The largest unsigned product is given by 2𝑛+𝑚−2
(𝑛 + 𝑚 − 1 bits suffice to represent this number), so the (𝑛 + 𝑚)-bit
unsigned product has its MSB=0. Thus, we can use this (𝑛 + 𝑚)-bit unsigned number as a positive signed number. The
final adder/subtractor might change the sign of the positive product based on the signs of A and B.
 Absolute Value: For an 𝑛-bit signed number 𝑋, the absolute value is defined as: |𝑋| = {
0 + 𝑋, 𝑋 ≥ 0
0 − 𝑋, 𝑋 < 0
 Thus, the absolute value |𝑋| can have at most 𝑛 + 1 bits. To avoid overflow, we sign-extend the inputs to 𝑛 + 1 bits. The
result |𝑋| has 𝑛 + 1 bits. Since |𝑋| is an absolute value, then |𝑋|𝑁 = 0. Thus, we can get |𝑋| as an unsigned number by
discarding the MSB, i.e., using only 𝑛 bits: |𝑋|𝑛−1 downto |𝑋|0.
 Alternatively, we can omit the sign-extension (since we are discarding |𝑋|𝑛 anyway), and we will get |𝑋| as an unsigned
number. If we need |𝑋| as a signed number (for further computations), we append a ‘0’ to the unsigned number.
b0
b1
a0
a1
a2
a3
FA
PU
PU
PU
PU
PU
PU
PU
PU
0
b2
PU
PU
PU
PU
b3
p0
p1
p2
p3
p4
p5
p6
p7
bi
aj
cin
cout
PU
x +
+
+
0
0
0
+/- +/-
0
+/- +/-
0
ARRAY
MULTIPLIER
+/- +/-
0
+/- +/-
0
Xn-1
signed
unsigned
,
+/- +/-
0
Xn-1
unsigned

Absolute Value Circuit
unsigned unsigned
signed
signed
unsigned
signed
signed
signed

a3
b3
a2
b2
a1
b1
a0
b0
A=B
a3
b3
a2
b2
e3
e2
e1
e0
e3
a1
b1
e3
e2
a0
b0
e3
e2
e1
A>B
A<B
AB
AB
A=B
A<B
A>B
COMPARATOR
A
B
4
4
COMPARATORS
UNSIGNED NUMBERS
 For 𝐴 = 𝑎3𝑎2𝑎1𝑎0, 𝐵 = 𝑏3𝑏2𝑏1𝑏0
 𝐴 > 𝐵 when:
𝑎3 = 1, 𝑏3 = 0
Or: 𝑎3 = 𝑏3 and 𝑎2 = 1, 𝑏2 = 0
Or: 𝑎3 = 𝑏3, 𝑎2 = 𝑏2 and 𝑎1 = 1, 𝑏1 = 0
Or: 𝑎3 = 𝑏3, 𝑎2 = 𝑏2, 𝑎1 = 𝑏1 and 𝑎0 = 1, 𝑏0 = 0
SIGNED NUMBERS
 First Approach:
 If 𝐴 ≥ 0 and 𝐵 ≥ 0, we can use the unsigned comparator.
 If 𝐴 < 0 and 𝐵 < 0, we can also use the unsigned comparator.
Example: 10002 < 10012 (-8 < -7). The closer the number is
to zero, the larger the unsigned value is.
 If one number is positive and the other negative:
Example: 10002 < 01002 (-8 < 4). If we were to use the
unsigned comparator, we would get 10002 > 01002. So, in this
case, we need to invert both the A>B and the A<B bit.
 Example: For a 4-bit number in 2’s complement:
 If 𝑎3 = 𝑏3, 𝐴 and 𝐵 have the same sign. Then, we do not need to invert any bit.
 If 𝑎3 ≠ 𝑏3, 𝐴 and 𝐵 have a different sign. Then, we need to invert the A>B and A<B bits of the unsigned comparator.
𝑒3 = 1 when 𝑎3 = 𝑏3. 𝑒3 = 0 when 𝑎3 ≠ 𝑏3.
Then it follows that: (𝐴 < 𝐵)𝑠𝑖𝑔𝑛𝑒𝑑 = 𝑒3
̅ (𝐴 < 𝐵)𝑢𝑛𝑠𝑖𝑔𝑛𝑒𝑑 = 𝑒3(𝐴 < 𝐵)𝑢𝑛𝑠𝑖𝑔𝑛𝑒𝑑
̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
(𝐴 > 𝐵)𝑠𝑖𝑔𝑛𝑒𝑑 = 𝑒3(𝐴 > 𝐵)𝑢𝑛𝑠𝑖𝑔𝑛𝑒𝑑
̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
 Second Approach:
 Here, we use an adder/subtractor in 2C arithmetic. We need
to sign-extend the inputs to consider the worst-case scenario
and then subtract them.
 We can determine whether 𝐴 is greater than 𝐵, based on:
𝑅𝑛 = {
1 → 𝐴 − 𝐵 < 0
0 → 𝐴 − 𝐵 ≥ 0
 To determine whether 𝐴 = 𝐵, we compare the 𝑛 + 1 bits of 𝑅
to 0 (𝑅 = 𝐴 − 𝐵). However, note that (𝐴 − 𝐵) ∈ [−2𝑛
+ 1, 2𝑛
−
2]. So, the case 𝑅 = −2𝑛
= 10 … 0 will not occur. Thus, we only
need to compare the bits 𝑅𝑛−1 to 𝑅0 to 0.
A=B
A<B
A>B
UNSIGNED
COMPARATOR
A
B
4
4
e3
A=B
A<B
A>B
+/- +/- 1
...
...

ARITHMETIC LOGIC UNIT (ALU)
 Two types of operation: Arithmetic and Logic (bit-wise). The sel(3..0) input selects the operation. sel(2..0) selects
the operation type within a specific unit. The arithmetic unit consist of adders and subtractors, while the Logic Unit consist
of 8-input logic gates.
BARREL SHIFTER
 Two types of operation: Arithmetic (mode=0, it implements 2𝑖
) and Rotation (mode=1)
 Truth table for a 8-bit Barrel Shifter:
result[7..0] (output): It is shifted version of the input data[7..0]. sel[2..0]: number of bits to shift.
dir: It controls the shifting direction (dir=1: to the right, dir=0: to the left). When shifting to the right in the Arithmetic
Mode, we use sign extension so as properly account for both unsigned and signed input numbers.
Function
Transfer 'a'
Increment 'a'
Decrement 'a'
Transfer 'b'
Increment 'b'
Decrement 'b'
Add 'a' and 'b'
Subtract 'b' from 'a'
Complement 'a'
Complement 'b'
AND
OR
NAND
NOR
XOR
XNOR
ARITHMETIC
UNIT
LOGIC UNIT
a
b
sel
y
sel(3)
8
8
4
8
0
1
sel
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
Operation
y <= a
y <= a + 1
y <= a - 1
y <= b
y <= b + 1
y <= b - 1
y <= a + b
y <= a - b
y <= NOT a
y <= NOT b
y <= a AND b
y <= a OR b
y <= a NAND b
y <= a NOR b
y <= a XOR b
y <= a XNOR b
Unit
ARITHMETIC
LOGIC
0 1
0 1
result[7..0]
abcdefgh
bcdefgh0
cdefgh00
defgh000
efgh0000
fgh00000
gh000000
h0000000
aabcdefg
aaabcdef
aaaabcde
aaaaabcd
aaaaaabc
aaaaaaab
aaaaaaaa
dist[2..0]
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
data[7..0]
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
dir
X
0
0
0
0
0
0
0
1
1
1
1
1
1
1
mode = 0. ARITHMETIC MODE
result[7..0]
abcdefgh
bcdefgha
cdefghab
defghabc
efghabcd
fghabcde
ghabcdef
habcdefg
habcdefg
ghabcdef
fghabcde
efghabcd
defghabc
cdefghab
bcdefgha
dist[2..0]
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
data[7..0]
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
dir
X
0
0
0
0
0
0
0
1
1
1
1
1
1
1
mode = 1. ROTATION MODE
data
shifter to
left
0
1
2
3
4
5
6
7
dist 3
shifter to
right
0
1
2
3
4
5
6
7
rotate to
left
0
1
2
3
4
5
6
7
rotate to
right
0
1
2
3
4
5
6
7
dir 0 1
mode
8
result
8

FIXED-POINT (FX) ARITHMETIC
INTRODUCTION
FX FOR UNSIGNED NUMBERS
 We know how to represent positive integer numbers. But what if we wanted to represent numbers with fractional parts?
 Fixed-point arithmetic: Binary representation of positive decimal numbers with fractional parts.
FX number (in binary representation): (𝑏𝑛−1𝑏𝑛−2 … 𝑏1𝑏0. 𝒃−𝟏𝒃−𝟐 … 𝒃−𝒌)2
 Conversion from binary to decimal:
𝐷 = ∑ 𝑏𝑖 × 2𝑖
𝑛−1
𝑖=−𝑘
= 𝑏𝑛−1 × 2𝑛−1 + 𝑏𝑛−2 × 2𝑛−2 + ⋯ + 𝑏1 × 21 + 𝑏0 × 20 + 𝒃−𝟏 × 𝟐−𝟏 + 𝒃−𝟐 × 𝟐−𝟐 + ⋯ 𝒃−𝒌 × 𝟐−𝒌
Example: 1011.1012 = 1 × 23 + 0 × 22 + 1 × 21 + 1 × 20 + 1 × 𝟐−𝟏 + 𝟎 × 𝟐−𝟐 + 𝟏 × 𝟐−𝟑 = 11.625
To convert from binary to hexadecimal:
 Conversion from decimal to binary: We divide the number into its integer and fractional parts. We get the binary
representation of the integer part using the successive divisions by 2. For the fractional part, we apply successive
multiplications by 2 (see example below). We then combine the integer and fractional binary results.
 Example: Convert 31.625 to FX (in binary): We know 31 = 111112. In the figure below, we have that 0.625 = 0.1012.
Thus: 31.625 = 11111.1012.
FX FOR SIGNED NUMBERS
 Method: Get the FX representation of +379.21875, and then apply the 2’s complement operation to that result.
 Example: Convert -379.21875 to the 2’s complement representation.
 379 = 1011110112. 0.21875 = 0.001112. Then: +379.21875 (2C) = 0101111011.001112.
 We get -379.2185 by applying the 2C operation to +379.21875  -379.21875 = 1010000100.110012 = 0xE84.C8.
To convert to hexadecimal, we append zeros to the LSB and sign-extend the MSB. Note that the 2C operation involves
inverting the bits and add 1; the addition by ‘1’ applies to the LSB, not to the rightmost integer.
Binary: 10101.101012
0001 0101.1010 1000
1 5
hexadecimal: A
. 8
0.625
Number in
base 10
Number in
base 2
????2
0.625x2 = 1.25 = 1 + 0.25
0.25x2 = 0.5 = 0 + 0.5
0.5x2 = 1 = 1 + 0
stop here!
0.1012
MSB
0.7
Number in
base 10
Number in
base 2
????2
0.7x2 = 1.4 = 1 + 0.4
0.4x2 = 0.8 = 0 + 0.8
0.8x2 = 1.6 = 1 + 0.6
0.6x2 = 1.2 = 1 + 0.2
0.4x2 = 0.8 = 0 + 0.8
0.2x2 = 0.4 = 0 + 0.4
0.10110 0110 ...2
MSB

INTEGER REPRESENTATION
 𝑛 − 𝑏𝑖𝑡 number: 𝑏𝑛−1𝑏𝑛−2 … 𝑏0
UNSIGNED SIGNED
Decimal
Value
𝐷 = ∑ 𝑏𝑖2𝑖
𝑛−1
𝑖=0
𝐷 = −2𝑛−1
𝑏𝑛−1 + ∑ 𝑏𝑖2𝑖
𝑛−2
𝑖=0
Range of
values
[0, 2𝑛
− 1] [−2𝑛−1
, 2𝑛−1
− 1]
FIXED POINT REPRESENTATION
 Typical representation [𝑛 𝑝]: 𝑛 − 𝑏𝑖𝑡 number with 𝑝 fractional bits: 𝑏𝑛−𝑝−1𝑏𝑛−𝑝−2 … 𝑏0. 𝑏−1𝑏−2 … 𝑏−𝑝
UNSIGNED SIGNED
Decimal
Value
𝐷 = ∑ 𝑏𝑖2𝑖
𝑛−𝑝−1
𝑖=−𝑝
𝐷 = −2𝑛−𝑝−1
𝑏𝑛−𝑝−1 + ∑ 𝑏𝑖2𝑖
𝑛−𝑝−2
𝑖=−𝑝
Range of
values
[
0
2𝑝
,
2𝑛 − 1
2𝑝
] = [0, 2𝑛−𝑝
− 2−𝑝] [
−2𝑛−1
2𝑝
,
2𝑛−1 − 1
2𝑝
] = [−2𝑛−𝑝−1, 2𝑛−𝑝−1 − 2−𝑝]
Dynamic
Range
|2𝑛−𝑝
− 2−𝑝|
|2−𝑝|
= 2𝑛 − 1
(𝑑𝐵) = 20 × log10(2𝑛
− 1)
|−2𝑛−𝑝−1|
|2−𝑝|
= 2𝑛−1
(𝑑𝐵) = 20 × log10(2𝑛−1)
Resolution
(1 LSB)
2−𝑝
2−𝑝
 Dynamic Range:
𝐷𝑦𝑛𝑎𝑚𝑖𝑐 𝑅𝑎𝑛𝑔𝑒 =
𝑙𝑎𝑟𝑔𝑒𝑠𝑡 𝑎𝑏𝑠. 𝑣𝑎𝑙𝑢𝑒
𝑠𝑚𝑎𝑙𝑙𝑒𝑠𝑡 𝑛𝑜𝑛𝑧𝑒𝑟𝑜 𝑎𝑏𝑠. 𝑣𝑎𝑙𝑢𝑒
𝐷𝑦𝑛𝑎𝑚𝑖𝑐 𝑅𝑎𝑛𝑔𝑒(𝑑𝐵) = 20 × log10(𝐷𝑦𝑛𝑎𝑚𝑖𝑐 𝑅𝑎𝑛𝑔𝑒)
 Unsigned numbers: Range of Values
 Signed numbers: Range of Values
 Examples:
FX Format Range Dynamic Range (dB) Resolution
UNSIGNED
[8 7] [0, 1.9922] 48.13 0.0078
[12 8] [0, 15.9961] 72.24 0.0039
[16 10] [0, 63.9990] 96.33 0.0010
SIGNED
[8 7] [-1, 0.9921875] 42.14 0.0078
[12 8] [-8, 7.99609375] 66.23 0.0039
[16 10] [-64, 63.9990234375] 90.31 0.0010
n-p p
n
... ...
... ...

FIXED-POINT ADDITION/SUBTRACTION
 Addition of two numbers represented in the format [𝑛 𝑝]:
𝐴 × 2−𝑝 ± 𝐵 × 2−𝑝 = (𝐴 ± 𝐵) × 2−𝑝
We perform integer addition/subtraction of 𝐴 and 𝐵. We just need to interpret the result
differently by placing the fractional point where it belongs. Notice that the hardware is
the same as that of integer addition/subtraction.
When adding/subtracting numbers with different formats [𝑛 𝑝] and [𝑚 𝑘], we first need to align the fractional point so that
we use a format for both numbers: it could be [𝑛 𝑝], [𝑚 𝑘], [𝑛 − 𝑝 + 𝑘 𝑘], [𝑚 − 𝑘 + 𝑝 𝑝]. This is done by zero-padding and
sign-extending where necessary. In the figure below, the format selected for both numbers is [𝑚 𝑘], while the result is in
the format [𝑚 + 1 𝑘].
Important: The result of the addition/subtraction requires an extra bit in the
worst-case scenario. In order to correctly compute it in fixed-point
arithmetic, we need to sign-extend (by one bit) the operators prior to
addition/subtraction.
Multi-operand Addition: 𝑁 numbers of format [𝑛 𝑝]: The total number of bits is given by : 𝑛 + ⌈log2 𝑁⌉ (this can be
demonstrated by an adder tree). Notice that the number of fractional bits does not change (it remains 𝑝), only the integer
bits increase by ⌈log2 𝑁⌉, i.e., the number of integer bits become 𝑛 − 𝑝 + ⌈log2 𝑁⌉.
 Examples: Calculate the result of the additions and subtractions for the following fixed-point numbers.
UNSIGNED SIGNED
0.101010 +
1.0110101
1.00101 -
0.0000111
10.001 +
1.001101
0.0101 -
1.0101101
10.1101 +
1.1001
100.1 +
0.1000101
1000.0101 -
111.01001
101.0001 +
1.0111101
Unsigned:
Signed:
n-p p
m-k k
m-k+1 k
+
n-p p
m-k k
n-p p
m-k k
m-k+1 k
+
n-p p
n-p p
n-p+1 p
+
0.1 0 1 0 1 0 0 +
1.0 1 1 0 1 0 1
1 0.0 0 0 1 0 0 1
c
8
=1
c
7
=1
c
6
=1
c
5
=1
c
4
=0
c
3
=1
c
2
=0
c
1
=0
c
0
=0
1.0 0 1 0 1 0 0 -
0.0 0 0 0 1 1 1
1.0 0 0 1 1 0 1
b
7
=0
b
6
=0
b
5
=0
b
4
=1
b
3
=1
b
2
=1
b
1
=1
b
0
=0
1 0.1 1 0 1 +
1.1 0 0 1
1 0 0.0 1 1 0
c
6
=1
c
5
=1
c
4
=1
c
3
=0
c
2
=0
c
1
=1
c
0
=0
1 0 0.1 0 0 0 0 0 0 +
0.1 0 0 0 1 0 1
1 0 1.0 0 0 0 1 0 1
c
10
=0
c
9
=0
c
8
=0
c
7
=1
c
6
=0
c
5
=0
c
4
=0
c
3
=0
c
2
=0
c
1
=0
c
0
=0
1 1 0.0 0 1 0 0 0 +
1 1 1.0 0 1 1 0 1
1 0 1.0 1 0 1 0 1
c
9
=1
c
8
=1
c
7
=0
c
6
=0
c
5
=0
c
4
=1
c
3
=0
c
2
=0
c
1
=0
c
0
=0
0.0 1 0 1 0 0 0 -
1.0 1 0 1 1 0 1
c
8
=0
c
7
=0
c
6
=0
c
5
=0
c
4
=0
c
3
=0
c
2
=0
c
1
=0
c
0
=0
0.0 1 0 1 0 0 0 +
0.1 0 1 0 0 1 1
0.1 1 1 1 0 1 1
1 0 0 0.0 1 0 1 0 -
1 1 1 1.0 1 0 0 1
c
9
=0
c
8
=0
c
7
=0
c
6
=0
c
5
=1
c
4
=1
c
3
=1
c
2
=1
c
1
=0
c
0
=0
1 0 0 0.0 1 0 1 0 +
0 0 0 0.1 0 1 1 1
1 0 0 1.0 0 0 0 1
1 0 1.0 0 0 1 0 0 0 +
1 1 1.0 1 1 1 1 0 1
1 0 0.1 0 0 0 1 0 1
c
10
=1
c
9
=1
c
8
=1
c
7
=0
c
6
=1
c
5
=1
c
4
=1
c
3
=0
c
2
=0
c
1
=0
c
0
=0

FIXED-POINT MULTIPLICATION
 Unsigned multiplication
Multiplication of two signed numbers represented with different formats [𝑛 𝑝], [𝑚 𝑘]:
(𝐴 × 2−𝑝) × (𝐵 × 2−𝑘) = (𝐴 × 𝐵) × 2−𝑝−𝑘
. We can perform integer multiplication of A and B and then place the fractional
point where it belongs. The format of the multiplication result is given by [𝑛 + 𝑚 𝑝 + 𝑘]. There is no need to align the
fractional point of the input quantities.
Special case: 𝑚 = 𝑛, 𝑘 = 𝑝
(𝐴 × 2−𝑝) × (𝐵 × 2−𝑝) = (𝐴 × 𝐵) × 2−2𝑝
. Here, the format of the
multiplication result is given by [2𝑛 2𝑝].
 Multiplication procedure for unsigned integer numbers:
Example: when multiplying, we treat the numbers as integers. Only
when we get the result, we place the fractional point where it belongs.
 Signed Multiplication: We first take the absolute value of the operands. Then, if at least one of the operands was negative,
we need to change the sign of the result. We then place the fractional point where it belongs.
Examples:
n-p p
m-k k
x
n+m-p-k p+k
a3 a2 a1 a0 x
b3 b2 b1 b0
a3b0 a2b0 a1b0 a0b0
a3b1 a2b1 a1b1 a0b1
a3b2 a2b2 a1b2 a0b2
a3b3 a2b3 a1b3 a0b3
p7 p6 p5 p4 p3 p2 p1 p0
1 0 1 1 x
1 1 0 1
1 0 1 1
0 0 0 0
1 0 1 1
1 0 1 1
1 0 0 0 1 1 1 1
2.75 = 10.11 x
6.5 = 110.1
17.875 = 1 0 0 0 1.1 1 1
1 1 0 1 0 1 x
1 0 1
1 1 0 1 0 1
0 0 0 0 0 0
1 1 0 1 0 1
1 0 0 0 0 1 0 0 1
01.001 x
1.001001
1 1 0 1 1 1 x
1 0 0 1
1 1 0 1 1 1
0 0 0 0 0 0
0 0 0 0 0 0
1 1 0 1 1 1
1 1 1 1 0 1 1 1 1
01.001 x
0.110111
0.1 1 1 1 0 1 1 1 1
1.0 0 0 0 1 0 0 0 1
10.0001 x
01.01001
1 0 1 0 0 1 x
1 1 1 1 1
1 0 1 0 0 1
1 0 1 0 0 1
1 0 1 0 0 1
1 0 1 0 0 1
1 0 1 0 0 1
1 0 0 1 1 1 1 0 1 1 1
01.1111 x
01.01001
0 1 0.0 1 1 1 1 0 1 1 1
1 0 1.1 0 0 0 0 1 0 0 1
1000.000 x
10.010101
01000.000 x
01.101011
1 1 0 1 0 1 1 x
1 0 0 0 0 0 0
0 0 0 0 0 0 0
1 1 0 1 0 1 1
1 1 0 1 0 1 1 0 0 0 0 0 0
0 1 1 0 1.0 1 1 0 0 0 0 0 0
0.1101010 x
11.1111011
0.110101 x
0.0000101
0.0 0 0 0 1 0 0 0 0 1 0 0 1
1.1 1 1 1 0 1 1 1 1 0 1 1 1

FIXED-POINT DIVISION
 Unsigned Division: 𝐴𝑓 𝐵𝑓
⁄
We first need to align the numbers so they have the same number of fractional bits, then divide them treating them as
integers. The quotient will be integer, while the remainder will have the same number of fractional bits as 𝐴𝑓.
𝐴𝑓 is in the format [𝑛𝑎 𝑎]. 𝐵𝑓 is in the format [𝑛𝑏 𝑏]
Step 1: For 𝑎 ≥ 𝑏, we align the fractional points and then get the integer numbers 𝐴 and 𝐵, which result from:
𝐴 = 𝐴𝑓 × 2𝑎 𝐵 = 𝐵𝑓 × 2𝑎
Step 2: Integer division:
𝐴
𝐵
=
𝐴𝑓
𝐵𝑓
The numbers 𝐴 and 𝐵 are related by the formula: 𝐴 = 𝐵 × 𝑄 + 𝑅, where 𝑄 and 𝑅 are the quotient and remainder of the
integer division of 𝐴 and 𝐵. Note that 𝑄 is also the quotient of
𝐴𝑓
𝐵𝑓
.
Step 3: To get the correct remainder of
𝐴𝑓
𝐵𝑓
, we re-write the previous equation:
𝐴𝑓 × 2𝑎
= (𝐵𝑓 × 2𝑎
) × 𝑄 + 𝑅 → 𝐴𝑓 = 𝐵𝑓 × 𝑄 + (𝑅 × 2−𝑎)
Then: 𝑄𝑓 = 𝑄, 𝑅𝑓 = 𝑅 × 2−𝑎
Example:
1010.011
11.1
Step 1: Alignment, 𝑎 = 3
1010.011
11.1
=
1010.011
11.100
=
1010011
11100
Step 2: Integer Division
1010011
11100
 1010011 = 11100(10) + 11011 → 𝑄 = 10, 𝑅 = 11011
Step 3: Get actual remainder: 𝑅 × 2−𝑎
𝑅𝑓 = 11.011
Verification: 1010.011 = 11.1(10) + 11,011, 𝑄𝑓 = 10, 𝑅𝑓 = 11011
 Adding precision bits to 𝑄𝑓 (quotient of 𝐴𝑓 𝐵𝑓
⁄ ):
The previous procedure only gets 𝑄 as an integer. What if we want to get the division result with 𝑥 number of fractional
bits? To do so, after alignment, we append 𝑥 zeros to 𝐴𝑓 × 2𝑎
and perform integer division.
𝐴 = 𝐴𝑓 × 2𝑎
× 2𝑥
𝐵 = 𝐵𝑓 × 2𝑎
𝐴𝑓 × 2𝑎+𝑥 = (𝐵𝑓 × 2𝑎) × 𝑄 + 𝑅 → 𝐴𝑓 = 𝐵𝑓 × (𝑄 × 2−𝑥) + (𝑅 × 2−𝑎−𝑥)
Then: 𝑄𝑓 = 𝑄 × 2−𝑥, 𝑅𝑓 = 𝑅 × 2−𝑎−𝑥
Example:
1010,011
11,1
with 𝑥 = 2 bits of precision
Step 1: Alignment, 𝑎 = 3
1010.011
11.1
=
1010.011
11.100
=
1010011
11100
Step 2: Append 𝑥 = 2 zeros
1010011
11100
=
1010011𝟎𝟎
11100
Step 3: Integer Division
1010011𝟎𝟎
11100
 1010011𝟎𝟎 = 11100(1011) + 11000
𝑄 = 1011, 𝑅 = 11000
Step 4: Get actual remainder and quotient (or result): 𝑄𝑓 = 𝑄 × 2−𝑥
, 𝑅𝑓 = 𝑅 × 2−𝑎−𝑥
𝑄𝑓 = 10.11, 𝑅𝑓 = 0.11000
Verification: 1010.01100 = 11.1(10.11) + 0,11000.

 Signed division: In this case (just as in the multiplication), we first take the absolute value of the operators 𝐴 and 𝐵. If
only one of the operators is negative, the result of abs(A)/abs(B) requires a sign change.
What about the remainder? You can also correct the sign of 𝑅𝑓 (using the procedure specified in the case of signed integer
numbers). However, once the quotient is obtained with fractional bits, getting 𝑅𝑓 with the correct sign is not very useful.
 Example: We get the division result (with 𝑥 = 4 fractional bits ) for the following signed fixed-point numbers:

101.1001
1.011
: To positive (numerator and denominator), alignment, and then to unsigned: 𝑎 = 4:
101.1001
1.011
=
010.0111
0.1010
≡
100111
1010
Append 𝑥 = 4 zeros:
100111𝟎𝟎𝟎𝟎
1010
Unsigned integer Division:
𝑄 = 111110, 𝑅 = 100
→ 𝑄𝑓 = 11.1110 (𝑥 = 4)
Final result (2C):
101.1001
1.011
= 011.111 (this is represented as a signed number)

11.011
1.01011
: To positive (numerator and denominator), alignment, and then to unsigned, 𝑎 = 5:
00.101
0.10101
=
0.10100
0.10101
≡
10100
10101
10100𝟎𝟎𝟎𝟎
10101
𝑄 = 1111, 𝑅 = 101
→ 𝑄𝑓 = 0.1111(𝑥 = 4)
Final result (2C):
11.011
1.01011
= 0.1111 (this is represented as a signed number)

10.0110
01.01
: To positive (numerator), alignment, and then to unsigned, 𝑎 = 4:
01.1010
01.01
=
01.1010
01.0100
≡
11010
10100
11010𝟎𝟎𝟎𝟎
10100
𝑄 = 10100, 𝑅 = 10000
→ 𝑄𝑓 = 1.0100(𝑥 = 4)  𝑄𝑓 here is represented as an unsigned number
Final result (2C):
10.0110
01.01
= 2𝐶(01.01) = 10.11

0.101010
110.1001
: To positive (denominator), alignment, and then to unsigned, 𝑎 = 5:
0.10101
001.0111
=
0.10101
001.01110
≡
10101
101110
10101𝟎𝟎𝟎𝟎
101110
𝑄 = 111, 𝑅 = 1110
→ 𝑄𝑓 = 0.0111(𝑥 = 4)
Final result (2C):
0.101010
110.1001
= 2𝐶(0.0111) = 1.1001
0000111110
1001110000
1010
10011
1010
10010
1010
10000
1010
1100
1010
100
1010
000001111
101000000
10101
100110
10101
100010
10101
11010
10101
101
10101
000010100
110100000
10100
11000
10100
10000
10100
000000111
101010000
101110
1001100
101110
111100
101110
1110
101110

ARITHMETIC FX UNITS. TRUNCATION/ROUNDING/SATURATION
ARITHMETIC FX UNITS
 They are the same as those that operate on integer numbers. The main difference is that we need to know where to place
the fractional point. The design must keep track of the FX format at every point in the architecture.
 One benefit of FX representation is that we can perform truncation, rounding and saturation on the output results and the
input values. These operations might require the use of some hardware resources.
TRUNCATION
 This is a useful operation when less hardware is required in subsequent operations. However
this comes at the expense of less accuracy.
 To assess the effect of truncation, use PSNR (dB) or MSE with respect to a double floating
point result or with respect to the original [𝑛 𝑝] format.
 Truncation is usually meant to be truncation of the fractional part. However, we can also
truncate the integer part (chop off 𝑘 MSBs). This is not recommended as it might render the number unusable.
ROUNDING
 This operation allows for hardware savings in subsequent
operations at the expense of reduced accuracy. But it is
more accurate than simple truncation. However, it requires
extra hardware to deal with the rounding operation.
 For the number 𝑏𝑛−𝑝−1𝑏𝑛−𝑝−2 … 𝑏0. 𝑏−1𝑏−2 … 𝑏−𝑝, if we want
to chop 𝑘 bits (LSB portion), we use the 𝑏𝑘−𝑝−1 bit to
determine whether to round. If the 𝑏𝑘−𝑝−1 = 0, we just
truncate. If 𝑏𝑘−𝑝−1 = 1, we need to add ‘1’ to the LSB of
the truncated result.
SATURATION
 This is helpful when we need to restrict the number of integer bits. Here, we are asked to
reduce the number of integer bits by 𝑘. Simple truncation chops off the integer part by 𝑘
bits; this might completely modify the number and render it totally unusable. Instead, in
saturation, we apply the following rules:
 If all the 𝑘 + 1 MSBs of the initial number are identical, that means that chopping by 𝑘
bits does not change the number at all, so we just discard the 𝑘 MSBs.
 If the 𝑘 + 1 MSBs are not identical, chopping by 𝑘 bits does change the number. Thus, here, if the MSB of the initial
number is 1, the resulting (𝑛 − 𝑘)-bit number will be −2𝑛−𝑘−𝑝−1
= 10 … 0 (largest negative number). If the MSB is 0, the
resulting (𝑛 − 𝑘)-bit number will be 2𝑛−𝑘−𝑝−1 − 2−𝑝 = 011 …1 (largest positive number).
Examples: Represent the following signed FX numbers in the signed fixed-point format: [8 7]. You can use rounding or
truncation for the fractional part. For the integer part, use saturation.
 1,01101111:
To represent this number in the format [8 7], we keep the integer bit, and we can only truncate or round the last LSB:
After truncation: 1,0110111
After rounding: 1,0110111 + 1 = 1,0111000
 11,111010011:
Here, we need to get rid of on MSB and two LSBs. Let’s use rounding (to the next bit).
Saturation in this case amounts to truncation of the MSB, as the number won’t change if we remove the MSB.
After rounding: 11,1110100 + 1 = 11,1110101
After saturation: 1,1110101
 101,111010011:
Here, we need to get rid of two MSB and two LSBs.
Saturation: Since the three MSBs are not the same and the MSB=1 we need to replace the number by the largest negative
number (in absolute terms) in the format [8 7]: 1,0000000
 011,1111011011:
Here, we need to get rid of two MSB and three LSBs.
Saturation: Since the three MSBs are not identical and the MSB=0, we need to replace the number by the largest positive
number in the format [8 7]: 0,1111111
n-p p
n-p p-k
k
n-p p
n-p p-k
k
0 n-p p
n-p p-k
k
1
1
+
n-p+1 p-k
n-p
k
n-p-k p
p
n-k

FLOATING POINT REPRESENTATION
 There are many ways to represent floating numbers. A common way is:
𝑋 = ±𝑠𝑖𝑔𝑛𝑖𝑓𝑖𝑐𝑎𝑛𝑑 × 2𝑒
 Exponent 𝑒: Signed integer. It is common to encode this field using a bias: 𝑒 + 𝑏𝑖𝑎𝑠. This facilitates zero detection (𝑒 +
𝑏𝑖𝑎𝑠 = 0). Note that the exponent of the actual number is always 𝑒 regardless of the bias (the bias is just for encoding).
𝑒 ∈ [−2𝐸−1
, 2𝐸−1
− 1 ]
 Significand: Unsigned fixed point number. Usually normalized to a particular range, e.g.: [0, 1), [1,2).
Format (unsigned): [𝑚 𝑝]. Range: [0,
2𝑚−1
2𝑝 ] = [0, 2𝑚−𝑝
− 2−𝑝], 𝑘 = 𝑚 − 𝑝
If 𝑘 = 0  Significand ∈ [0,1 − 2−𝑝] = [0,1)
If 𝑘 = 𝑚  Significand ∈ [0, 2𝑚 − 1]. Integer significand.
Another common representation of the significand is using 𝑘 = 1 and setting that bit (the MSB) to 1. Here, the range of the
significand would be [0, 21
− 2−𝑝], but since the integer bit is 1, the values start from 1, which result in the following
significand range: [1, 21
− 2−𝑝]. This is a popular normalization, as it allows us to drop the MSB in the encoding.
IEEE-754 STANDARD
 The representation is as follows:
𝑋 = ±1. 𝑓 × 2𝑒
 Significand: Unsigned FX integer. The representation is normalized to 𝑠 = 1. 𝑓, where 𝑓 is the mantissa. There is always
an integer bit 1 (called hidden 1) in the representation of the significand, so we do not need to indicate in the encoding.
Thus, we only use 𝑓 the mantissa in the significant field.
Significand range: [1,2 − 2−𝑝] = [1,2)
 Biased exponent: Unsigned integer with 𝐸 bits. 𝑏𝑖𝑎𝑠 = 2𝐸−1
− 1. Thus, 𝑒𝑥𝑝 = 𝑒 + 𝑏𝑖𝑎𝑠 → 𝑒 = 𝑒𝑥𝑝 − 𝑏𝑖𝑎𝑠. We just subtract
the 𝑏𝑖𝑎𝑠 from the exponent field in order to get the exponent value 𝑒.
 𝑒𝑥𝑝 = 𝑒 + 𝑏𝑖𝑎𝑠 ∈ [0, 2𝐸
− 1 ]. 𝑒𝑥𝑝 is represented as un unsigned integer number with 𝐸 bits. The bias makes sure that
𝑒𝑥𝑝 ≥ 0. Also note that 𝑒 ∈ [−2𝐸−1 + 1, 2𝐸−1 ].
 The IEEE-754 standard reserves the following cases: i) 𝑒𝑥𝑝 = 2𝐸
− 1 (𝑒 = 2𝐸−1
) to represent special numbers (𝑁𝑎𝑁 and
±∞), and ii) 𝑒𝑥𝑝 = 0 to represent the zero and the denormalized numbers. The remaining cases are called ordinary
numbers.
 Ordinary numbers:
Range of 𝑒: [−2𝐸−1
+ 2, 2𝐸−1
− 1].
Max number:𝑙𝑎𝑟𝑔𝑒𝑠𝑡 𝑠𝑖𝑔𝑛𝑖𝑓𝑖𝑐𝑎𝑛𝑑 × 2𝑙𝑎𝑟𝑔𝑒𝑠𝑡 𝑒𝑥𝑝𝑜𝑛𝑒𝑛𝑡
𝑚𝑎𝑥 = 1.11 … 1 × 22𝐸−1−1
= (2 − 2−𝑝) × 22𝐸−1−1
Min. number: 𝑠𝑚𝑎𝑙𝑙𝑒𝑠𝑡 𝑠𝑖𝑔𝑛𝑖𝑓𝑖𝑐𝑎𝑛𝑑 × 2𝑠𝑚𝑎𝑙𝑙𝑒𝑠𝑡 𝑒𝑥𝑝𝑜𝑛𝑒𝑛𝑡
𝑚𝑖𝑛 = 1.00 … 0 × 2−2𝐸−1+2 = 2−2𝐸−1+2
𝐷𝑦𝑛𝑎𝑚𝑖𝑐 𝑅𝑎𝑛𝑔𝑒 =
𝑚𝑎𝑥
𝑚𝑖𝑛
=
(2 − 2−𝑝) × 22𝐸−1−1
2−2𝐸−1+2
= (2 − 2−𝑝) × 22𝐸−3
𝐷𝑦𝑛𝑎𝑚𝑖𝑐 𝑅𝑎𝑛𝑔𝑒 (𝑑𝐵) = 20 × log10{(2 − 2−𝑝) × 22𝐸−3
}
 Plus/minus Infinite: ±∞
The 𝑒𝑥𝑝 field is a string of 1’s. This is a special case
where 𝑒𝑥𝑝 = 2𝐸
− 1. (𝑒 = 2𝐸−1
)
±∞ = ±22𝐸−1
 Not a Number: 𝑁𝑎𝑁
The 𝑒𝑥𝑝 field is a strings of 1’s. 𝑒𝑥𝑝 = 2𝐸 − 1. This is a
special case where 𝑒𝑥𝑝 = 2𝐸
− 1 (𝑒 = 2𝐸−1
). The only
difference with ±∞ is that 𝑓 is a nonzero number.
e significand
E m
k p
m
e+bias[1,2E-2] f
E p
biased exponent significand
e+bias = 2E-1 f=0
E p
e+bias = 2E-1 f0
E p
e+bias f
E p
sign bit

 Zero:
Zero cannot be represented with a normalized
significand 𝑠 = 1.00 … 0 since 𝑋 = ±1. 𝑓 × 2𝑒
cannot be
zero. Thus, a special code must be assigned to it, where
𝑠 = 0.00 … 0 and 𝑒𝑥𝑝 = 0. Every single bit (except for the
sign) is zero. There are two representations for zero.
The number zero is a special case of the denormalized numbers, where 𝑠 = 0. 𝑓 (see below).
 Denormalized numbers: The implementation of these numbers is optional in the standard (except for the zero). Certain
small values that are not representable as normalized numbers (and are rounded to zero), can be represented more precisely
with denormals. This is a “graceful underflow” provision, which leads to hardware overhead.
These numbers have the 𝑒𝑥𝑝 field equal to zero. The
tricky part is that 𝑒 is set to −2𝐸−1
+ 2 (not −2𝐸−1
+ 1,
as the 𝑒 + 𝑏𝑖𝑎𝑠 formula states). The significand is
represented as 𝑠 = 0. 𝑓. Thus, the floating point number
is 𝑋 = ±0. 𝑓 × 2−2𝐸−1+2
. These numbers can represent
numbers lower (in absolute value) than 𝑚𝑖𝑛 (the
number zero is a special case).
Why is 𝑒 not −2𝐸−1 + 1? Note that the smallest ordinary number is 2−2𝐸−1+2.
The largest denormalized number with 𝑒 = −2𝐸−1
+ 1 is: 0.11 … 1 × 22𝐸−1−1
= (1 − 2−𝑝) × 2−2𝐸−1+1
.
The largest denormalized number with 𝑒 = −2𝐸−1
+ 2 is: 0.11 … 1 × 22𝐸−1−2
= (1 − 2−𝑝) × 2−2𝐸−1+2
.
By picking 𝑒 = −2𝐸−1
+ 2, the gap between the largest denormalized number and the smallest normalized is smaller. Though
this specification makes the formula 𝑒 + 𝑏𝑖𝑎𝑠 = 0 inconsistent, it helps in accuracy.
 Depiction of the range of values:
 The IEEE-754-2008 (revision of IEEE-754-1985) standard defines several representations: half (16 bits, E=5, p=10), single
(32 bits, E = 8, p = 23) and double (64 bits, E = 11, p = 52). There is also quadruple precision (128 bits) and octuple
precision (256 bits). You can define your own representation by selecting a particular number of bits for the exponent and
significand. The table lists various parameters for half, single and double FP arithmetic (ordinary numbers):
Ordinary numbers Exponent
bits (E)
Range of 𝒆 Bias
Dynamic
Range (dB)
Significand
range
Significand
bits (p)
Min Max
Half 2−14 (2 − 2−10)2+15
5 [−14,15] 15 180.61 dB [1,2 − 2−10
] 10
Single 2−126 (2 − 2−23)2+127
8 [−126,127] 127 1529 dB [1,2 − 2−23
] 23
Double 2−1022 (2 − 2−52)2+1023
11 [−1022,1023] 1023 12318 dB [1,2 − 2−52] 52
 Rules for arithmetic operations:
 𝑂𝑟𝑑𝑖𝑛𝑎𝑟𝑦 𝑛𝑢𝑚𝑏𝑒𝑟 ÷ (+∞) = ±0
 𝑂𝑟𝑑𝑖𝑛𝑎𝑟𝑦 𝑛𝑢𝑚𝑏𝑒𝑟 ÷ (0) = ±∞
 (+∞) × 𝑂𝑟𝑑𝑖𝑛𝑎𝑟𝑦 𝑛𝑢𝑚𝑏𝑒𝑟 = ±∞
 𝑁𝑎𝑁 + 𝑂𝑟𝑑𝑖𝑛𝑎𝑟𝑦 𝑛𝑢𝑚𝑏𝑒𝑟 = 𝑁𝑎𝑁
 (0) ÷ (0) = 𝑁𝑎𝑁 (±∞) ÷ (±∞) = 𝑁𝑎𝑁
 (0) × (±∞) = 𝑁𝑎𝑁 (∞) + (−∞) = 𝑁𝑎𝑁
Examples:
 F43DE962 (single): 1111 0100 0011 1101 1110 1001 0110 0010
𝑒 + 𝑏𝑖𝑎𝑠 = 1110 1000 = 232 → 𝑒 = 232 − 127 = 105
𝑀𝑎𝑛𝑡𝑖𝑠𝑠𝑎 = 1.011 1101 1110 1001 0110 0010 = 1.4837
𝑋 = − 1.4837 × 2105
= −6.1085 × 1031
 007FADE5 (single): 0000 0000 0111 1111 1010 1101 1110 0101
𝑒 + 𝑏𝑖𝑎𝑠 = 0000 0000 = 0 → 𝐷𝑒𝑛𝑜𝑟𝑚𝑎𝑙 𝑛𝑢𝑚𝑏𝑒𝑟 → 𝑒 = − 126
𝑀𝑎𝑛𝑡𝑖𝑠𝑠𝑎 = 0.111 1111 1010 1101 1110 0101 = 0.9975
𝑋 = 0.9975 × 2−126
= 1.1725 × 10−38
e+bias = 0 f=0
E p
e+bias = 0 f0
E p
...
- +
... ...
...
Underflow region
(or denormal numbers)
Overflow region

𝑏1 = ±𝑠12𝑒1, 𝑠1 = 1. 𝑓1 𝑏2 = ±𝑠22𝑒2, 𝑠1 = 1. 𝑓2
→ 𝑏1 + 𝑏2 = ±𝑠12𝑒1 ± 𝑠22𝑒2
If 𝑒1 ≥ 𝑒2, we simply shift 𝑠2 to the right by 𝑒1 − 𝑒2 bits. This step is referred to as alignment shift.
𝑠22𝑒2 =
𝑠2
2𝑒1−𝑒2
2𝑒1
→ 𝑏1 + 𝑏2 = ±𝑠12𝑒1 ±
𝑠2
2𝑒1−𝑒2
2𝑒1 = (±𝑠1 ±
𝑠2
2𝑒1−𝑒2
) × 2𝑒1 = 𝑠 × 2𝑒
→ 𝑏1 − 𝑏2 = ±𝑠12𝑒1 ∓
𝑠2
2𝑒1−𝑒2
2𝑒1 = (±𝑠1 ∓
𝑠2
2𝑒1−𝑒2
) × 2𝑒1 = 𝑠 × 2𝑒
 Normalization: Once the operators are aligned, we can add. The result might not be in the format 1. 𝑓, so we need to
discard the leading 0’s of the result and stop when a leading 1 is found. Then, we must adjust 𝑒1 properly, this results in 𝑒.
 For example, for addition, when the two operands have similar signs, the resulting significand is in the range [1,4), thus
a single bit right shift is needed on the significant to compensate. Then, we adjust 𝑒1 by adding 1 to it (or by left shifting
everything by 1 bit). When the two operands have different signs, the resulting significand might be lower than 1 (e.g.:
0.000001) and we need to first discard the leading zeros and then right shift until we get 1. 𝑓. We then adjust 𝑒1 by
adding the same number as the number of shifts to the right on the significand.
Note that overflow/underflow can occur during the addition step as well as due to normalization.
Example: 𝑠3 = (±𝑠1 ±
𝑠2
2𝑒1−𝑒2
) = 00011.1010
First, discard the leading zeros: 𝑠3 = 11.1010
Normalization: right shift 1 bit: 𝑠 = 𝑠3 × 2−1
= 1.11010
Now that we have the normalized significand 𝑠, we need to adjust the exponent 𝑒1 by adding 1 to it: 𝑒 = 𝑒1 + 1:
(𝑠3 × 2−1) × 2𝑒1+1 = 𝑠 × 2𝑒 = 1.1101 × 2𝑒1+1
Example: 𝑏1 = 1.0101 × 25
, 𝑏2 = −1.1110 × 23
𝑏 = 𝑏1 + 𝑏2 = 1.0101 × 25
−
1.1110
22
× 25
= (1.0101 − 0.011110) × 25
1.0101 − 0.011110 = 0.11011. To get this result, we convert the operands to the 2C representation (you can also do
unsigned subtraction if the result is positive). Here, the result is positive. Finally, we perform normalization:
→ 𝑏 = 𝑏1 + 𝑏2 = (0.11011) × 25 = (0.11011 × 21) × 25 × 2−1 = 1.1011 × 24
 Subtraction: This operation is very similar.
Example: 𝑏1 = 1.0101 × 25
, 𝑏2 = 1.111 × 25
𝑏 = 𝑏1 − 𝑏2 = 1.0101 × 25
− 1.111 × 25
= (1.0101 − 1.111) × 25
To subtract, we convert to 2C representation: 𝑅 = 01.0101 − 01.1110 = 01.0101 + 10.0010 = 11.0111. Here, the result
is negative. So, we get the absolute value (|𝑅| = 2𝐶(1.0111) = 0.1001) and place the negative sign on the final result:
→ 𝑏 = 𝑏1 − 𝑏2 = −(0.1001) × 25
Example:
 𝑋 = 50DAD000 – D0FAD000:
50DAD000: 0101 0000 1101 1010 1101 0000 0000 0000
𝑒 + 𝑏𝑖𝑎𝑠 = 10100001 = 161 → 𝑒 = 161 − 127 = 34 𝑀𝑎𝑛𝑡𝑖𝑠𝑠𝑎 = 1.10110101101
50DAD000 = 1.10110101101 × 234
D0FAD000: 1101 0000 1111 1010 1101 0000 0000 0000
𝑒 + 𝑏𝑖𝑎𝑠 = 10100001 = 161 → 𝑒 = 161 − 127 = 34 𝑀𝑎𝑛𝑡𝑖𝑠𝑠𝑎 = 1.11110101101
D0FAD000 = −1.11110101101 × 234
𝑋 = 1.10110101101 × 234
+ 1.11110101101 × 234
(unsigned addition)
𝑋 = 11.1010101101 × 234
= 1.11010101101 × 235
𝑒 + 𝑏𝑖𝑎𝑠 = 35 + 127 = 162 = 10100010
𝑋 = 0101 0001 0110 1010 1101 0000 0000 0000 = 516AD000
1.1 0 1 1 0 1 0 1 1 0 1 +
1.1 1 1 1 0 1 0 1 1 0 1
1 1.1 0 1 0 1 0 1 1 0 1 0
c
12
=1
c
11
=1
c
10
=1
c
9
=1
c
8
=1
c
7
=0
c
6
=1
c
5
=0
c
4
=1
c
3
=1
c
2
=0
c
1
=1
c
0
=0

Example:
 𝑋 = 60A10000 + C2F97000:
60A10000: 0110 0000 1010 0001 0000 0000 0000 0000
𝑒 + 𝑏𝑖𝑎𝑠 = 11000001 = 193 → 𝑒 = 193 − 127 = 66 𝑀𝑎𝑛𝑡𝑖𝑠𝑠𝑎 = 1.0100001
60A10000 = 1.0100001 × 266
C2F97000: 1100 0010 1111 1001 0111 0000 0000 0000
𝑒 + 𝑏𝑖𝑎𝑠 = 10000101 = 133 → 𝑒 = 133 − 127 = 6 𝑀𝑎𝑛𝑡𝑖𝑠𝑠𝑎 = 1.11110010111
C2F97000 = −1.11110010111 × 26
𝑋 = 1.0100001 × 266
− 1.11110010111 × 26
𝑋 = 1.0100001 × 266
−
1.11110010111
260
× 266
Representing the division by 260 requires more than 𝑝 + 1 = 24 bits. Thus, we can approximate the 2nd
operand with 0.
𝑋 = 1.0100001 × 266
𝑋 = 0110 0000 1010 0001 0000 0000 0000 0000 = 60A10000
MULTIPLICATION
𝑏1 = ±𝑠12𝑒1, 𝑏2 = ±𝑠22𝑒2
→ 𝑏1 × 𝑏2 = (±𝑠12𝑒1) × (±𝑠22𝑒2) = ±(𝑠1 × 𝑠2)2𝑒1+𝑒2
Note that 𝑠 = (𝑠1 × 𝑠2) ∈ [1,4).
Example:
𝑏1 = 1.100 × 22
, 𝑏2 = −1.011 × 24
,
𝑏 = 𝑏1 × 𝑏2 = −(1.100 × 1.011) × 26
= −(10,0001) × 26
,
Normalization of the result:
𝑏 = −(10,0001 × 2−1) × 27 = −(1,00001) × 27.
Note that if the multiplication requires more bits than allowed by the representation (32, 64 bits), we have to do truncation
or rounding. It is also possible that overflow/underflow might occur due to large/small exponents and/or multiplication of
large/small numbers.
Example:
 𝑋 = 7A09D300  0BEEF000:
7A09D300: 0111 1010 0000 1001 1101 0011 0000 0000
𝑒 + 𝑏𝑖𝑎𝑠 = 11110100 = 244 → 𝑒 = 244 − 127 = 117 𝑀𝑎𝑛𝑡𝑖𝑠𝑠𝑎 = 1.00010011101001100000000
7A09D300 = 1.000100111010011 × 2117
0BEEF000: 0000 1011 1110 1110 1111 0000 0000 0000
𝑒 + 𝑏𝑖𝑎𝑠 = 00010111 = 23 → 𝑒 = 23 − 127 = −104 𝑀𝑎𝑛𝑡𝑖𝑠𝑠𝑎 = 1.11011101111000000000000
0BEEF000 = 1.11011101111 × 2−104
𝑋 = 1.000100111010011 × 2117
× 1.11011101111 × 2−104
𝑋 = 10.00000010100011010111111101 × 213
= 1.000000010100011010111111101 × 214
= 1.6466 × 104
𝑒 + 𝑏𝑖𝑎𝑠 = 14 + 127 = 141 = 10001101
𝑋 = 0100 0110 1000 0000 1010 0011 0101 1111 = 4680A35F (four bits were truncated)
 

DIVISION
𝑏1 = ±𝑠12𝑒1, 𝑏2 = ±𝑠22𝑒2
→
𝑏1
𝑏2
=
±𝑠12𝑒1
±𝑠22𝑒2
= ±
𝑠1
𝑠2
2𝑒1−𝑒2
Note that 𝑠 = (
𝑠1
𝑠2
) ∈ (1/2,2)
Here, the result might require normalization.
Example:
𝑏1 = 1.100 × 22, 𝑏2 = −1.011 × 24
→
𝑏1
𝑏2
=
1.100 × 22
−1.011 × 24
= −
1.100
1.011
2−2
1.100
1.011
: unsigned division, here we can include as many fractional bits as we want.
With 𝑥 = 4 (and 𝑎 = 0) we have:
1100𝟎𝟎𝟎𝟎
1011
 1100𝟎𝟎𝟎𝟎 = 10101(1011) + 11
𝑄𝑓 = 1,0101, 𝑅𝑓 = 00,0011
If the result is not normalized, we need to normalized it. In this example, we do not need to do this.
→
𝑏1
𝑏2
=
1.100 × 22
−1.011 × 24
= −1.0101 × 2−2
Example
 𝑋 = 49742000  40490000:
49742000: 0100 1001 0111 0100 0010 0000 0000 0000
𝑒 + 𝑏𝑖𝑎𝑠 = 10010010 = 146 → 𝑒 = 146 − 127 = 19 𝑀𝑎𝑛𝑡𝑖𝑠𝑠𝑎 = 1.11101000010000000000000
497420000 = 1.1110100001 × 219
40490000: 0100 0000 0100 1001 0000 0000 0000 0000
𝑒 + 𝑏𝑖𝑎𝑠 = 10000000 = 128 → 𝑒 = 128 − 127 = 1 𝑀𝑎𝑛𝑡𝑖𝑠𝑠𝑎 = 1.10010010000000000000000
0BEEF000 = 1.1001001 × 21
𝑋 =
1.1110100001 × 219
1.1001001 × 21
Alignment:
1.1110100001
1.1001001
=
1.1110100001
1.1001001000
=
11110100001
11001001000
11110100001𝟎𝟎𝟎𝟎𝟎𝟎𝟎𝟎
11001001000
Integer division
𝑄 = 100110110, 𝑅 = 1011101000 → 𝑄𝑓 = 1.00110110
Thus: 𝑋 =
1.1110100001×219
1.1001001×21 = 1.0011011 × 218
= 1.2109375 × 218
= 317440
𝑒 + 𝑏𝑖𝑎𝑠 = 18 + 127 = 145 = 10010001
𝑋 = 0100 1000 1001 1011 0000 0000 0000 0000 = 489B0000
0000000000100110110
1111010000100000000
11001001000
101011001000
11001001000
100100000000
11001001000
101011100000
11001001000
100100110000
11001001000
10111010000
11001001000

Notes unit 2

Recommended

More Related Content

What's hot (19)

Similar to Notes unit 2 (20)

Recently uploaded (20)

Notes unit 2