Digital Signal Processing Reference
In-Depth Information
100001
011111
¼
100000
1
¼
Thus, equivalently, a string of 1s is replaced with 1 at the least significant 1 of the string,
and a 1 placed next to the the most significant 1 of the string, while all other bits are filled
with zeros.
We can trivially extend this transformation to any string of 1s in binary representation of a number.
The string property can be recursively applied on binary representations of a number. The
transformed number has minimum number of non-zero bits. The representation and its use in
digital design are further discussed in Chapter 6.
The example in Figure 5.46 shows how the string property can be recursively applied. The number
of non-zero digits in the example has reduced from 14 to 6.
5.9.4 Modified Booth Recoding Multiplier
The three basic building blocks of a multiplier are the generation of PPs, reduction of PPs to two
layers, and addition of these layers using a CSA. Section 5.8.3 has covered optimization techniques
for partial products reduction. Reducing the number of PPs is yet another optimization technique
that can be exploited in many design instances. 'Modified Booth recoding' (MBR) is one such
technique.
While multiplying two N-bit signed numbers a and b, the technique generates one PP each by
pairing all bits of b in 2-bit groups. The technique, while moving from LSB to MSB of b, pairs two
bits together to make a group for recoding using the MBR algorithm. The two bits in a group can
possibly be 00
2
,01
2
,10
2
and 11
2
. Multiplication by 00
2
,01
2
and 10
2
simply results in 0, a and
2a
1, respectively where each PP is appropriately computed as one number. The fourth
possibility of 11
2
¼
¼
a
1, and a simple shift would not generate the requisite PP; rather this
multiplication will results in two PPs and they are a and 2a. This means in the worst case the
multiplier ends up having N partial products.
This problem of 11
2
generating two PPs is resolved by using the Booth recoding algorithm. This
algorithm still works on groups of 2 bits each but recodes each group to use one of the five equivalent
values: 0, 1, 2,
1,
2. Multiplication by all these digits results in one PP each. These equivalent
values are coded by indexing into a look-up table. The look-up table is computed by exploiting the
string property of numbers (see Section 5.9.3). The string property is observed on each pair of two
bits while moving from LSB to MSB. To check the string property, the MSB of the previous pair is
also required along with the two bits of the pair under consideration. For the first pair a zero is
appended to the right. Table 5.4 shows the string property working on all possible 3-bit numbers for
generating a table that is then used for recoding.
3is2
þ
0
0
1
1
1
1
0
1
1
0
1
1
1
1
0
1
1
1
0
1
String
0
0
1
1
1
1
0
1
1
0
1
1
1
1
1
0
0
1
0
1
String
0
0
1
1
1
1
0
1
1
1
0
0
0
0
1
0
0
1
0
1
String
0
0
1
1
1
1
1
0
0
1
0
0
0
0
1
0
0
1
0
1
String
0
1
0
0
0
0
1
0
0
1
0
0
0
0
1
0
0
1
0
1
Figure 5.46
Application of the string property
Search WWH ::
Custom Search