Algorithms and Data Structures in C++:Algorithms for Computer Arithmetic







Algorithms and Data Structures in C++

by Alan Parker

CRC Press, CRC Press LLC

ISBN: 0849371716   Pub Date: 08/01/93  


















Previous
Table of Contents
Next




An example of booth recoding is illustrated in Table 4.5. In the worst case the Booth algorithm requires that n operations be performed to compute the product. This is illustrated in the last entry in Table 4.5. As a result the recoding operation for this operand has not simplified the problem. The average number of operations for a random operand by the algorithm is determined in Problem 4.10. Due to the average and worst-case complexity of the Booth algorithm a better solution is sought to find the product.


Figure 4.14  Booth Algorithm

Table 4.5 Booth Recoding 8-Bit Example

Original Number
Booth Recode

0
0
0
0
0
1
1
1
0
0
0
0
1
0
0
-1

0
0
0
0
1
1
0
0
0
0
0
1
0
-1
0
0

0
0
0
1
1
0
1
0
0
0
1
0
-1
1
-1
0

0
1
0
1
0
1
0
1
1
-1
1
-1
1
-1
1
-1




Table 4.6 Booth Recoding

Bit Pattern
Operation

0
0
product unchanged

0
1
product += a

1
0
product -=a

1
1
product unchanged


Code List 4.11 Booth Algorithm



Code List 4.12 Output of Program in Code List 4.11


4.3.3 Bit-Pair Recoding
The Bit-Pair recoding technique is a technique which recodes the bits by considering three bits at a time. This technique will require n/2 additions or subtractions to compute the product. The recoding is illustrated in Table 4.7. The bits after recoding are looked at two at a time and the respective operations are performed. The higher order bit is weighted twice as much as the lower order bit. The C++ program to perform bit-pair recoding is illustrated in Code List 4.13. The output is shown in Code List 4.14.
The bit pair recoding algorithm is shown in Figure 4.14. The algorithm is analogous to the Booth recoding except that it investigates three bits at a time while the Booth algorithm looks at two bits at a time. The bit-pair recoding algorithm needs to have access to A, -A, 2A, and -2A and as a result needs another additional 1-bit register to the left of P which is initialized to zero.
Table 4.7 Bit-Pair Recoding

BitPattern
Operation




0

0

0

0

1

1

1

1




0

0

1

1

0

0

1

1




0

1

0

1

0

1

0

1




no operation

1×a
prod = prod + a;

2×a-a


prod = prod + a

2×a
prod = prod + 2a

-2×a

prod = prod - 2a

-2×a + a



prod = prod - a

-1×a

prod = prod - a

no operation



Figure 4.15  Bit Pair Recoding Algorithm
Code List 4.13 Bit-Pair Recoding Program



Code List 4.14 Output of Program in Code List 4.13




Previous
Table of Contents
Next




Copyright © CRC Press LLC