"CS" multipliers |
Partial product of "CS" operands |
Multiplier X and multiplicand A are both in "CS" notation,
i.e. with digits values Î {'0', '1',
'2'}. An array of "xCS" cells output a set of bits whose weighted sum is the product A × X in constant time (no propagation). To make sure that the "xCS" cells never overflow, it is necessary that either in A or in X every digit value '2' is preceded by a '0' at its right. Either A or X requires a rewriting. In the applet the double arrow at right shows or hides the wires distributing A and X through the "xCS" cells. |
Partial products reduction |
The partial product of two "CS" digits is a simple bit, reduced by Wallace trees in the very same way as conventional binary fast multiplication. |
The "xCS" cell computes the product of two digits "a" and "x" in "CS" notation and gives a bit "i". Its arithmetic equation is "2 × b + 2 × y + i = a × x + z + c". Furthermore the outputs "b" and "y" does not depend on "c" or "z" (no propagation). Actually "c + z" takes only the values '0' or '1' (it is impossible that "c + z" be 2) and "a × x" takes the values 0, 1, 2 or 4. Only the value 1 might cause a propagation but this value is only possible when "a" and "x" are both '1' implying that "c" and "z" are both '0'. |
The transcoder "CS2CS" rewrites from "CS" to "CS" while making sure that in the output with value '2' is always preceded (at the right) by a '0'. |
Coding circuit "CS2BC" |
The transcoder "CS2BC" passes from "CS" to "BC", that is from the "Carry-Save" code to the "Booth Code" ( symmetric minimally redundant radix-4 code ). |
Integer constant multiplication |
Multiplication of a number by a series of constants |
The discrete Fourier transform, the discrete cosine transform or inverse, digital filters, and so on all contains
the multiplication of a variable X by several constants C1, C2, .. Cn. The factorization of those constants permits
a dramatic reduction of the number of additions/subtractions demanded by those multiplications. The following applet
computes Y1 = X × C1, Y2 = X × C2, .. Yn = X × Cn. |