Write Booth's algorithm. Also explain floating point arithmetic operation. Describe signal addition and subtraction in detail.
Q.) Write Booth's algorithm. Also explain floating point arithmetic operation. Describe signal addition and subtraction in detail.
Subject: Computer Organization and ArchitectureBooth's Algorithm
Booth's algorithm is a multiplication algorithm that multiplies two signed binary numbers in two's complement notation. The algorithm is efficient because it reduces the number of additions required to calculate the product. Here's a step-by-step approach to Booth's algorithm:
Step 1: Initialization
- Let
multiplicand
be the number that we are going to multiply andmultiplier
be the number with which we are going to multiply. - Convert both numbers to binary (if they are not already in binary).
- Initialize two registers:
Accumulator (A)
andQ
. SetA
to 0 andQ
to themultiplier
. - Add an extra bit
Q-1
to the right ofQ
for the algorithm to work properly. Initially, setQ-1
to 0. - Set a
count
variable to the number of bits in themultiplier
.
Step 2: Checking and Operations
- Check the two least significant bits of
Q
andQ-1
. - Perform the following operations based on the value of these bits:
Q |
Q-1 |
Operation |
---|---|---|
0 | 0 | No operation (skip to step 3) |
0 | 1 | Add multiplicand to A |
1 | 0 | Subtract multiplicand from A |
1 | 1 | No operation (skip to step 3) |
Step 3: Arithmetic Shift Right
- Perform an arithmetic right shift on the combined
A
,Q
, andQ-1
registers. This means that you shift all bits one position to the right, and the leftmost bit ofA
remains unchanged (to preserve the sign).
Step 4: Loop or Terminate
- Decrease the
count
by 1. - If
count
is not zero, go back to step 2. - If
count
is zero, the algorithm terminates, and the combinedA
andQ
registers contain the product.
Example
Let's multiply 3 (0011 in binary) by -2 (using 4-bit representation, -2 is 1110 in two's complement).
Step | A | Q | Q-1 | Operation | Comment |
---|---|---|---|---|---|
1 | 0000 | 1110 | 0 | Initialize | Initial values |
2 | 0000 | 1110 | 0 | 0 0 | No operation |
3 | 0000 | 1111 | 0 | Shift | Arithmetic shift right |
4 | 0000 | 1111 | 0 | 1 0 | Subtract multiplicand |
5 | 1101 | 1111 | 0 | Update A | A = A - multiplicand |
6 | 1101 | 1111 | 0 | Shift | Arithmetic shift right |
7 | 1110 | 1111 | 1 | 1 1 | No operation |
8 | 1110 | 1111 | 1 | Shift | Arithmetic shift right |
9 | 1111 | 0111 | 1 | 0 1 | Add multiplicand |
10 | 0010 | 0111 | 1 | Update A | A = A + multiplicand |
11 | 0010 | 0111 | 1 | Shift | Arithmetic shift right |
12 | 0001 | 0011 | 1 | End | Result in A and Q |
The result is 0001 0011, which is 19 in decimal. Since we were multiplying 3 by -2, the expected result is -6. In binary, -6 using 8-bit two's complement is 1111 1010, which is equivalent to our result when considering only the least significant 8 bits.
Floating Point Arithmetic Operation
Floating point arithmetic operations are used to handle real numbers that require a fractional part. The IEEE 754 standard is a widely used format for representing floating point numbers. Here's a brief overview of the format and how operations are performed:
IEEE 754 Floating Point Format
A floating point number in IEEE 754 format consists of three parts:
- Sign bit (S): 1 bit that determines the sign of the number (0 for positive, 1 for negative).
- Exponent (E): A fixed number of bits that represent the exponent, biased by a certain value.
- Mantissa (M) or Significand: The significant digits of the number.
Floating Point Addition/Subtraction
To add or subtract two floating point numbers, follow these steps:
- Align the decimal points (or binary points) by adjusting the exponent of the smaller number.
- Add or subtract the mantissas.
- Normalize the result, if necessary, so that there is only one non-zero digit to the left of the decimal point.
- Round the result, if necessary, to fit within the mantissa size.
- Adjust the exponent to reflect any changes made during normalization.
Example
Add 3.25 and 2.125 in IEEE 754 single-precision format:
- Convert to binary: 3.25 (11.01) and 2.125 (10.001).
- Normalize: 1.101 x 2^1 and 1.0001 x 2^1 (same exponent, no need to adjust).
- Add mantissas: 1.101 + 1.0001 = 10.1011.
- Normalize result: 1.01011 x 2^2 (shift one position to the right, increase exponent by 1).
- Round, if necessary (not needed in this example).
- Convert to IEEE 754 format (assuming no rounding is needed):
S | Exponent (8 bits) | Mantissa (23 bits) |
---|---|---|
0 | 10000001 | 01011000000000000000000 |
The exponent is 1 + bias (127 for single-precision), so the stored exponent is 128, which is 10000001 in binary.
Signal Addition and Subtraction
Signal addition and subtraction involve combining or removing signal amplitudes at each point in time. This is commonly used in signal processing and audio engineering.
Signal Addition
To add two signals, simply add their amplitudes at each point in time.
Signal Subtraction
To subtract one signal from another, subtract the amplitudes of the second signal from the first at each point in time.
Example
Consider two signals A and B, where A(t) = 2sin(t) and B(t) = sin(2t).
- To add the signals: C(t) = A(t) + B(t) = 2sin(t) + sin(2t).
- To subtract the signals: D(t) = A(t) - B(t) = 2sin(t) - sin(2t).
The resulting signals C(t) and D(t) are new waveforms that represent the combined or differential effect of the original signals.