Patent ID: 7562106

Claim:
Apparatus for performing a multiplication operation of a multiplicand A having at least radix-n digits a0 and a1 with and a multiplier B having at least radix-n digits b0 and b1, with n>2 and each of the radix-n digits a0, a1, b0 and b1 not being zero, comprising: a first circuit in a first plurality of circuits, the first circuit implementing a table that determines a residue of a sum of a product of a0 and b1 and a product of a1 and b0, the first circuit having a first and a second input and an output, wherein: a residue of the product of a0 and b1 and a residue of the product of a1 and b0 have an identical radix-n position; the output of the first circuit provides a signal representing the residue of the sum when the first input receives a signal representing a0 and the second input receives a signal representing a1; the first circuit is selected from the first plurality of circuits based on b0 and b1; and no signal representing the residue of the first product is generated to determine the residue of the sum; a second circuit in a second plurality of circuits, the second circuit having a first and a second input and an output, the second circuit implementing a table that determines a carry of the sum of the product of a0 and b1 and the product of a1 and b0-wherein: the output of the second circuit in the second plurality of circuits provides a signal representing the carry of the sum when the first input of the second circuit receives the signal representing a1 and the second input of the second circuit receives the signal representing a1 and the second circuit is selected from the second plurality of circuits based on b0 and b1; means for determining the first circuit from the first plurality of circuits based on the value of b0 and b1; and means for determining the second circuit from the second plurality of circuits based on the value of b0 and b1.