METHOD AND CIRCUIT FOR MULTIPLICATION USING BOOTH ENCODING AND ITERATIVE ADDITION TECHNIQUES

摘要

A multiplier circuit for use with large numbers is presented. The circuit accepts two large numbers and segments the second number into a number of segments each of a known size. The unsegmented number is multiplied using Booth Encoding by the lowest order segment to form two partial products which are added to form a partial product and an associated carry value. The partial product is shifted right one segment and the result is padded. The next segment is then multiplied by the unsegmented number usi ng Booth Encoding to provide two further partial products for summation. Summation of the three values results in a partial product and an associated carry value. And so th e process is iterated until all segments have been multiplied by the unsegmented number. Padding of each partial product is performed based on a flag which is set when a negati ve encoded number is generated by the Booth Encoding and when a carry out from the sum is not fully resolved. When the flag is not set, the padding is with zeros; when th e flag is set, the padding is with ones.