Transcript Integer Arithmetics: Part 1

Fixed-Point Arithmetics: Part I
Binary Representation



Unsigned Magnitude
Signed Magnitude
Two’s Complement
Ira Fulton School of Engineering
Electrical Department
EEE404/591 – Real Time DSP
Unsigned Magnitude




Only positive number are presented
No sign bit
For N bits we can represent the signed
integers between 0 and 2N -1
Example: 111 ->7
Ira Fulton School of Engineering
Electrical Department
EEE404/591 – Real Time DSP
Signed Magnitude



The most significant bit is used to
represent the sign: “1” means negative,
“0” means positive
For positive numbers the result is the
same as unsigned magnitude
representation
For N bits we can represent the signed
integers between -2(N-1) +1 and +2(N-1)-1
Ira Fulton School of Engineering
Electrical Department
EEE404/591 – Real Time DSP
Disadvantage of Signed Magnitude


Two encoding for the zero ‘0’.
Addition of two numbers of opposite sign will not yield
0!!



-5 + 5 = (85)H + (05)
H
= (8A)
H
= -10!!
Arithmetic operations of numbers with unlike sign and
with same sign must be handled differently (subtracter
needed with unlike signs)
A – B ≠ A + (-B)
Example: 3 – 2
Addition Operation 3 + (-2)
0011 (+3)
+ 1010 (-2)
------1100 (-5) WRONG!

Ira Fulton School of Engineering
Electrical Department
EEE404/591 – Real Time DSP
Subtraction Operation (3-2)
0011 (+3)
- 0010 (+2)
------0001 (+1) CORRECT!
Disadvantage of Signed Magnitude


A hardware adder and subtracter needed
Special treatment also for A – B if B>A


Example 3 – 2 & 2 – 3
Subtraction Operation 3 - 2
0011 (3)
- 0010 (2)
------0001 (1) CORRECT

Solution:



Subtraction Operation 2 - 3
0010 (+2)
- 0011 (+3)
-----1111 (-7) WRONG
Switch order of operands (3 – 2 instead of 2 – 3)
Perform subtraction (Result = 1)
attach the minus sign (Result = -1)
Ira Fulton School of Engineering
Electrical Department
EEE404/591 – Real Time DSP
Two’s Complement example





1 = 0001 −1 = 1110 + 1 = 1111
2 = 0010 −2 = 1101 + 1 = 1110
6 = 0110 −6 = 1001 + 1 = 1010
8 = 1000 −8 = 0111 + 1 = 1000
Note that the max positive number that can be
represented is 7! Since to get the negative of -8 we
need:
-8 = 1000
To bitwise invert : 0111
Add +1 to LSB:
+1
Result:
1000
So –(-8) = -8 (abnormal result)  8 cannot be represented

For N bits, the max number is 2(N-1)-1 while the min
number is -2(N-1)
Ira Fulton School of Engineering
Electrical Department
EEE404/591 – Real Time DSP
Geometric Depiction of Twos Complement
Integers
Ira Fulton School of Engineering
Electrical Department
EEE404/591 – Real Time DSP
Benefits of 2’s Complement

One unique representation of the number 0:







0=
0000
Complement: 1111
Add +1 to LSB: +1
Result:
0000 (Ignoring carry bit)
-0 = +0
Negation: take complement and add +1
Extending word length:

For positive number pack with leading zeros



+3 =011
+3 = 000011
For negative numbers pack with leading ones


-4=100
-4 =111000
Ira Fulton School of Engineering
Electrical Department
EEE404/591 – Real Time DSP
Benefits of 2’s Complement

Subtraction Rule: to subtract ‘b’ from ‘a’, take the 2’s
complement of ‘b’ and add it to ‘a’: a – b = a + (-b)
b
a
a
2’s
Signed Mag
Compare signs bits
Equal??
Adder
If Subtraction
enable
2’s Comp
b
No
Yes
Adder: a + b
Yes
Result
Sub: a - b
Ira Fulton School of Engineering
Electrical Department
EEE404/591 – Real Time DSP
Is a > b
No
Swap Operand
Sub: a – b
Negate
Benefits of 2’s Complement

Overflow Rule: if two numbers with same sign
are added and overflow occurs the result
number has different sign:



Addition: 011 + 011 = 110
3 + 3 = -2
Subtraction: 110 – 011 = 011
-2 - 3 = 3
Multiplication: 011 * 010 = 110
3 * 2
Ira Fulton School of Engineering
Electrical Department
EEE404/591 – Real Time DSP
= -2
What to Do In case of Overflow


Prevention rule: design your code with minimal possible
overflows
DSP can be configured to saturate the number at
overflow (N=4):



5 x 2 = 0010 Overflow
5 x 2 = 0111 Saturate
Guard bits in accumulator could be useful for
intermediate results


Example: 5 x 2 - 1 x 4 = 10 – 4 = 6
If accumulator has one extra bit called “guard bit” the final
result will not overflow!
Ira Fulton School of Engineering
Electrical Department
EEE404/591 – Real Time DSP
Multiplication Example








1011 Multiplicand (11 dec)
x 1101 Multiplier
(13 dec)
1011 Partial products
0000
Note: if multiplier bit is 1 copy
1011
multiplicand (place value)
1011
otherwise zero
10001111 Product (143 dec)
Note: need double length result
Ira Fulton School of Engineering
Electrical Department
EEE404/591 – Real Time DSP
Unsigned Binary Multiplication
Ira Fulton School of Engineering
Electrical Department
EEE404/591 – Real Time DSP
Execution of Example
Ira Fulton School of Engineering
Electrical Department
EEE404/591 – Real Time DSP
Flowchart for Unsigned Binary
Multiplication
Ira Fulton School of Engineering
Electrical Department
EEE404/591 – Real Time DSP
Problem: Multiplication & 2’s Complement
Addition and Subtraction can be treated as
unsigned integer

1001 (+9)
Unsigned
1001 (-7)
+0011 (+3)
+ 0011 (+3)
1100 (+12)
1100 (-4)
What about multiplication??

x
1010
(10)
1110
(14)
0000
Unsigned
x
1010
(-6)
1110
(-2)
0000
1010
1010
1010
2’s Complement
1010
1010
10001100
2’s Complement
1010
(140)
Ira Fulton School of Engineering
Electrical Department
EEE404/591 – Real Time DSP
10001100
(-116) Wrong Result!!!
Problem: Multiplication & 2’s Complement
Addition and Subtraction can be treated as
unsigned integer

1001 (+9)
Unsigned
1001 (-7)
+0011 (+3)
+ 0011 (+3)
1100 (+12)
1100 (-4)
What about multiplication??

x
1010
(10)
1110
(14)
0000
Unsigned
x
1010
(-6)
1110
(-2)
0000
1010
2’s Complement
1010
1010
1010
1010
10001100
2’s Complement
Need to sign extend partial products
1010
(140)
Ira Fulton School of Engineering
Electrical Department
EEE404/591 – Real Time DSP
10001100
(-116) Wrong Result!!!
Problem: Multiplication & 2’s Complement
Addition and Subtraction can be treated as
unsigned integer

1001 (+9)
Unsigned
1001 (-7)
+0011 (+3)
+ 0011 (+3)
1100 (+12)
1100 (-4)
What about multiplication??

x
1010
(10)
1110
(14)
0000
Unsigned
x
1010
(-6)
1110
(-2)
00000000
1010
2’s Complement
1111010
1010
111010 Need to sign extend partial products
1010
10001100
2’s Complement
11010
(140)
Ira Fulton School of Engineering
Electrical Department
EEE404/591 – Real Time DSP
000101100
(44)
Still Wrong Result!!!
Multiplying Negative Numbers


This does not work!
Solution 1




Convert to positive if required
Multiply as above
If signs were different, negate answer
Solution 2

Booth’s algorithm
Ira Fulton School of Engineering
Electrical Department
EEE404/591 – Real Time DSP
Solution 1

Solution 1 is as follows:



If either multiplicand or multiplier is negative
convert it to positive
Do the multiplication operation
Check the signs of the multiplicand and
multiplier if different negate the result
Adds Hardware
Complexity
Ira Fulton School of Engineering
Electrical Department
EEE404/591 – Real Time DSP
Solution 2: Booth Algorithm (1951)

Booth starts from the fact that a series
can be represented as:
K 1
2n  2n1    2n K

1

1  
2
K


1
1
1
2
 
 
 2n 1            2n  
1
 2 
 2  2
1
2
 2n1  2n K
Suppose that we have to perform the following
multiplication:


M*30 ->M * (00011110) = M * (24+23+22+21)
From series the multiplication can be written as:
M * (00011110) = M * (25 – 21) Savings on computations
Ira Fulton School of Engineering
Electrical Department
EEE404/591 – Real Time DSP
Booth Algorithm:



Multiply the multiplicand by -2n-K when a
transition from 0 to 1 (0-1) is encountered
going from right to left.
Multiply the multiplicand by 2n+1
whenever an transition from 1-0 is
encountered
Add the partial products obtained.
Ira Fulton School of Engineering
Electrical Department
EEE404/591 – Real Time DSP
Booth Algorithm:

When multiplying 2n-bit numbers, form 22n-bit partial
products as follows:





When the first 1 of a block is encountered (1-0), partial
product is formed by negating the multiplicand and
appropriately shifting the negated multiplicand
When the last 1 of a block is encountered (0-1), partial
product is formed by taking the multiplicand and
appropriately shifting it
When either 0-0 or 1-1 is encountered, partial product is all
zeros
Sign-extend all partial products
Add the partial products to obtain the multiplication
result.
Ira Fulton School of Engineering
Electrical Department
EEE404/591 – Real Time DSP
Booth Algorithm: Example 1

Multiplying: -6 x -2
1010
X 1110 (0)
00000000 0-0
0000110 1-0
000000
1-1
00000
1-1
00001100
Ira Fulton School of Engineering
Electrical Department
EEE404/591 – Real Time DSP
-6
-2
(Subtract multiplicand)
(Shift)
(Shift)
Multiplication: Why MSB is Redundant?






Assume that we have a number represented by 4 bits
(N = 4)
2’s complement range is from -8 to +7.
The min/max number obtained from multiplication is
-56/+64  7 bits are enough to represent the result.
In general: 2N-1 bits are needed if NxN multiplication is
performed
The additional MSB is a “sign extension bit” and can be
removed
Another way to interpret it is that if converted to
unsigned the multiplication result will be (N-1) + (N-1)
+ 1 sign bits giving 2N – 1.
Ira Fulton School of Engineering
Electrical Department
EEE404/591 – Real Time DSP