Method and apparatus for digital multiplication based on sums and differences of finite sets of powers of two

A multiples generating apparatus for generating signals representing multiples of a value A represented by a received multiplicand signal (A), the apparatus comprising:

• (a) a plurality of partial result generating modules where each module includes:
• (a.1) plural shifting means, each receiving said multiplicand signal (A) and each receiving one of plural shift control signals, each of the shifting means being for shifting the received multiplicand signal (A) and producing therefrom, in response to the corresponding shift control signal, a term signal either representative of the multiplicand (A) multiplied by a power of two or representative of a nullity;
• and
• (a.2) first-level summing means, operatively coupled for receiving term signals from two or more of said plural shifting means and for producing a partial result signal representing a sum or difference of the received term signals;
• (b) second-level summing means, operatively coupled for receiving partial result signals from two or more of said plural modules and for producing a second-level result signal representing a sum or difference of the received partial result signals;
• and
• (c) mapping control means, operatively coupled to the plural plurality of partial result generating modules and to the second-level summing means, for receiving a supplied index signal (B), for responsively outputting the shift control signals to each of the plural shifting means in each module, and for responsively outputting sign select signals to each of the firstlevel and second-level summing means, such that the second-level result signal produced by the second-level summing means represents a multiple of the received multiplicand signal (A) having the form, A.multidot.P/Q, where Q is an integer equal to two raised to an integer power (Q=2.sup.j ) and P is an integer selected from a series of integers in accordance with a predefined mapping of B to P.

A multiples generating circuit for generating electrical signals representing rational multiples (A.multidot.P/Q) of a value A represented by a received, binary-coded multiplicand signal (A), the circuit comprising:

• (a) a plurality of or-constant shifters, each receiving said multiplicand signal (A) and each receiving one of plural, or-constant control signals, each of the or-constant shifters including circuitry, responsive to a corresponding or-constant control signal for either shifting the received multiplicand signal (A) and producing therefrom a term signal representative of the multiplicand (A) multiplied by two raised to an integer power or producing a term signal representative of a predefined constant;
• (b) a summing circuit, operatively coupled to the or-constant shifters for receiving term signals from two or more of said plurality of or-constant shifters and for producing a result signal representing a sum or difference of the received term signals;
• and
• (c) mapping control means, operatively coupled to the plurality of or-constant shifters, for receiving a supplied index signal (B) and responsively outputting the or-constant control signals to each of the plurality of or-constant shifters such that the result signal produced by the summing means represents a multiple of the received multiplicand signal (A) having the form, A.multidot.P/Q, where Q is an integer equal to two raised to an integer power (Q=2.sup.j) and P is an integer selected from a series of integers in accordance with a predefined mapping of B to P.

A multiples generating apparatus for generating a succession of physical signals representing a succession of rational multiples of a value A, where the value A is represented by a received, binary-coded multiplicand signal (A), said apparatus comprising:

• (a) a plurality of or-constant shifting means, each or-constant shifting means receiving said multiplicand signal (A) and each receiving one of plural shift or-constant control signals,
• (a.1) each of the or-constant shifting means including shift means for shifting the received multiplicand signal (A), and
• (a.2) each of the or-constant shifting means further including term-producing means, operatively coupled to the corresponding shift means, for producing, in response to a corresponding shift or-constant control signal, a term signal either representative of the multiplicand (A) multiplied by two raised to an integer power or representative of a predefined constant;
• (b) summing means, operatively coupled for receiving term signals from two or more of said plural or-constant shifting means and for producing a physical result signal representing a sum or difference of the received term signals;
• and
• (c) mapping control means, operatively coupled to the plural or-constant shifting means, for outputting a succession of the shift or-constant control signals to the or-constant shifting means such that the result signal produced by the summing means represents a succession of rational multiples of the value A of the received multiplicand signal (A), each of said multiples having the form, A.multidot.P/Q, where Q is an integer equal to two raised to an integer power (Q=2.sup.j) and P is a corresponding one of a succession of integers selected from a predefined series of integers.

A multiples generating circuit for generating electrical signals representing rational multiples of a value A, where the value A is defined by a supplied, binary-coded multiplicand signal (A), the circuit comprising:

• (a) a plurality of or-constant shifters, each receiving said multiplicand signal (A) and each receiving one of plural, or-constant control signals, each of the or-constant shifters including circuitry, responsive to a corresponding or-constant control signal for either shifting the received multiplicand signal (A) and producing therefrom a term signal representative of the multiplicand (A) multiplied by two raised to an integer power or producing a term signal representative of a predefined constant;
• (b) a summing circuit, operatively coupled to the or-constant shifters for receiving term signals from two or more of said plurality of or-constant shifters and for producing a result signal representing a sum or difference of the received term signals;
• and
• (c) an inferential mapping means, operatively coupled to the plurality of or-constant shifters, for outputting the or-constant control signals to each of the plurality of or-constant shifters such that the result signal produced by the summing means represents a multiple of the received multiplicand signal (A) having the form, A.multidot.P/Q, where Q is an integer equal to two raised to an integer power (Q=2.sup.j) and P is an integer selected from a series of integers in accordance with a predefined mapping of an inferentially defined variable, B, to P.

A multiples generating apparatus for generating physical signals representing a succession of rational multiples of a value A, where the value A is represented by a received, binary-coded multiplicand signal (A), said apparatus comprising:

• (a) a plurality of or-constant shifting means, each or-constant shifting means receiving said multiplicand signal (A) and each receiving one of plural shift or-constant control signals, each of the or-constant shifting means being for shifting the received multiplicand signal (A) and producing therefrom, in response to a corresponding shift or-constant control signal, a term signal either representative of the multiplicand (A) multiplied by two raised to an integer power or representative of a predefined constant;
• (b) summing means, operatively coupled for receiving term signals from two or more of said plural or-constant shifting means and for producing a physical result signal representing a sum or difference of the received term signals;
• and
• (c) inferential mapping means, operatively coupled to the plural or-constant shifting means, for outputting a succession of shift or-constant control signals to each of the plurality of or-constant shifting means such that the result signal produced by the summing means represents a succession of multiples of the received multiplicand signal (A), each multiple having the form, A.multidot.P/Q, where Q is an integer equal to two raised to an integer power (Q=2.sup.j) and p is a corresponding integer selected from a succession of integers within a predefined range of integers, in accordance with a predefined mapping to P of an inferentially-defined, time-varying signal, B.

An integrated circuit comprising:

• (a) a substrate;
• (b) a first bus having at least n+1 lines extending along said substrate where n is greater than three, at least one of the n+1 lines being a constant-maintaining line for maintaining a constant logic level, and at least n others of the lines being multiplicand-carrying lines for carrying in parallel, n bits of a supplied, n-bit wide digital multiplicand signal (A.sub.0:(n-1)) that represents a succession of multiplicand values over time;
• (c) a second bus having at least six control lines extending along said substrate substantially parallel to the lines of the first bus, the at least six control lines being for carrying in parallel a corresponding set of at least six control signals (I.sub.a:c,J.sub.a:c);
• (d) first and second pluralities of multiplexer cells, each multiplexer cell including:
• (d.1) an output node, and
• (d.2) at least three switching devices respectively controlled by control signals on a corresponding at least three control lines of the second bus, the at least three switching devices having inputs respectively coupled to two or more lines of the first bus, one of said two or more lines being a constant-maintaining line and another of said two or more lines being a multiplicand-carrying line, the at least three switching devices further having outputs commonly coupled to the cell output node;
• (e) an adder/subtractor unit having a first term receiving port operatively coupled to the output nodes of the first plurality of multiplexer cells, a second term receiving port operatively coupled to the output nodes of the second plurality of multiplexer cells, and a sign-defining input, the adder/subtractor unit outputting a result signal representing, for a first state of the sign-defining input, a sum of first and second term signals respectively output by said pluralities of multiplexer cells, and representing, for a second state of the sign-defining input, a difference between the first and second term signals;
• and
• (f) a mapping control unit, operatively coupled to the at least six control lines and to the sign-defining input, for defining states of the corresponding at least six control signals (I.sub.a:c,J.sub.a:c) and the sign-defining input so that the result signal output by the adder/subtractor unit represents a succession over time of rational multiples of the succession of multiplicand values represented by the supplied, n-bit wide digital multiplicand signal (A.sub.0:(n-1)).

A circuit for carrying out machine-implemented multiplication of respective values represented by a supplied, n-bits wide, multiplicand signal (A) and by a physically real or inferentially defined multiplier signal (B), said circuit comprising:

• (a) a plurality of barrel shifting units for providing bit significance translation of the multiplicand signal (A);
• (b) a summing unit operatively coupled to the barrel shifting units for adding or subtracting output signals of the barrel shifting units to each other or to a supplied constant in accordance with a supplied control signal;
• and
• (c) a mapping control unit operatively coupled to the barrel shifting units and the summing unit for controlling the barrel shifting units and the summing unit such that the summing unit produces a result signal that is at least approximately representative of the value of the multiplicand signal (A) multiplied by the value of the multiplier signal (B).

A function generating apparatus for generating an output signal (C) that at least approximately represents a function output value C=f(A,B) taken out of a predefined range of output magnitudes, where f(A,B) represents a predefined function of first and second input values, A and B, said apparatus comprising:

• (a) first signal receiving means for receiving a first digital signal (A) representing the first input value, A;
• (b) first approximating-term generating means, operatively coupled to the first signal receiving means and responsive to a supplied first control signal, for generating in response to the first digital signal (A) and the first control signal, a first term signal representing either a predefined constant or one of a first finite set of values distributed across said predefined range of output magnitudes, said first finite set of values being distributed such that the gap between any two adjacent ones of the distributed first finite set of values is no more than a first predefined maximum gap amount;
• (c) second approximating-termgenerating means, operatively coupled to the first signal receiving means and responsive to a supplied second control signal, for generating in response to the first digital signal (A) and the second control signal, a second term signal representing either a predefined constant or one of a second finite set of values distributed across a predefined second range of magnitudes, said second range being approximately at least as wide as said first predefined maximum gap amount;
• (d) term combining means, operatively coupled to the first and second approximating-term generating means, and responsive to a supplied third control signal, for combining the first and second term signals and producing therefrom, in response to the third control signal, a result signal representative of one of a third finite set of values distributed across said predefined range of output magnitudes, the third finite set of values being distributed such that the gap between any two adjacent ones of the distributed third finite set of values is substantially less than the first predefined maximum gap amount and such that, for a majority of the values in the first finite set, each of the same values found in the third finite set is surrounded in a generally symmetric fashion by neighboring other values of the third finite set;
• and
• (e) mapping means, operatively coupled to the first approximating-term generating means, and to the second approximating-term generating means, and to the term combining means, for respectively supplying said first, second, and third control signals such that the result signal is at least approximately representative of the function output value C=f(A,B) for the case where the second input value B is either defined by second digital signal (B) applied to the mapping means, or inferred from the first, second, and third control signals supplied by the mapping means.