Low-error fixed-width modified booth multiplier

A fixed-width modified Booth multiplier, comprising:

• a module that encodes a W-bit multiplier using modified Booth coding;
• a module that processes the encoded multiplier and a multiplicand to generate partial products;
• and
• a module that accumulates the partial products to generate a W-bit product,
• wherein said module that accumulates comprises
• means for associating truncated bits with a major least significant bit group or a minor least significant bit group,
• means for generating an approximate carry value using the bits associated with the minor least significant bit group, and
• means for generating an exact carry value using the approximate carry value and the bits associated with the major least significant bit group.

A method for fixed-width multiplication, comprising:

• (a) processing a modified Booth encoded multiplier and a multiplicand to generate a first group of N partial products and a second group of N partial products;
• (b) associating each partial product of the first group of N partial products with a most significant bit group, a major least significant bit group, or a minor least significant bit group;
• (c) associating each partial product of the second group of N partial products with the most significant bit group or the major least significant bit group;
• (d) generating an approximate carry value for the minor least significant bit group;
• (e) generating an exact carry value for the major least significant bit group using the approximate carry value and the value of each partial product associated with the major least significant bit group;
• and
• (f) generating a product for the most significant bit group using the exact carry value and the value of each partial product associated with the most significant bit group.

A fixed-width multiplier, comprising:

• a module that processes a modified Booth encoded multiplier (Y) and a multiplicand (X) to generate a first group of N partial products and a second group of N partial products;
• a module that associates each partial product of the first group of N partial products with a most significant bit group, a major least significant bit group, or a minor least significant bit group;
• a module that associates each partial product of the second group of N partial products with the most significant bit group or the major least significant bit group;
• a module that generates an approximate carry value for the minor least significant bit group;
• a module that generates an exact carry value for the major least significant bit group using the approximate carry value and the value of each partial product associated with the major least significant bit group;
• and
• a module that generates a product for the most significant bit group using the exact carry value and the value of each partial product associated with the most significant bit group.

A method for designing a fixed-width multiplier, comprising:

• identifying a plurality of partial products formed for a W-bit multiplier and a W-bit multiplicand during modified Booth multiplication;
• associating each of the partial products with a most significant bit group, a major least significant bit group, or a minor least significant bit group;
• designing a circuit that generates an approximate carry value based on partial product values of the partial products associated with the minor least significant bit group;
• designing a circuit that generates an exact carry value based on partial product values of the partial products associated with the major least significant bit group and an output of the circuit that generates an approximate carry value;
• and
• designing a circuit that generates a product value based on partial product values of the partial products associated with the most significant bit group and an output of the circuit that generates an exact carry value.

A method for fixed-width modified Booth multiplication, comprising:

• encoding a W-bit multiplier using modified Booth coding;
• processing the encoded multiplier and a multiplicand to generate partial products;
• and
• accumulating the partial products to generate a P-bit product, P being greater than W, and
• wherein said accumulating step comprises
• dividing truncated bits into two groups, a major least significant bit group and a minor least significant bit group,
• generating an approximate carry value using the bits of the minor least significant bit group, and
• generating an exact carry value for the major least significant bit group using the approximate carry value and the bits of the major least significant bit group.