JPH02115929A - Multiplier - Google Patents

Abstract

PURPOSE:To simplify and miniaturize a multiplexer by multiplying plural multiplication coefficients whose minimum weight are displayed decided in advance by input data by controlling a selector, an inverter, and the carry input of an adder. CONSTITUTION:The selector 200 selects the left shift data of multiplication input corresponding to a term coefficient which becomes the most significant non-zero of the multiplication coefficient, and the selectors 201 and 202 select the left shift data of respective multiplication input corresponding to the term coefficients which become the non-zeros of residual multiplication coefficients by a selection signal SEL, respectively. The inverters 203 and 204 execute the bit inversion of data when the complement control signals IVT(1) and IVT(2) of 2 go to 1s when the term coefficients of the multiplication coefficients to which the selectors 201 and 202 correspond are set at -1. The arithmetic operation of the complement of 2 is performed by inputting 1 to the carry input(CI) of the adders 205 and 206. The adders 205 and 206 execute the multiplication of multiplication input data X by the absolute value of the multiplication coefficient after adding the output data of the selector 200 on that of the inverters 203 and 204.

Description

Detailed Description of the Invention (Field of Industrial Application) The present invention relates to a multiplier that multiplies multiplication input data in two's complement representation by a multiplication coefficient in minimum weight representation and outputs the multiplication result in two's complement representation. It is something.

(Prior Art) A conventional multiplier that multiplies two's complement input data by a multiplication coefficient uses Booth's algorithm and the carry look-ahead method (
Multipliers combined with adders (hereinafter referred to as CLA) are often used. FIG. 3 shows an example of a Booth multiplier. FIG. 3 shows a multiplier that achieves high speed by replacing the multiplication in which the multiplication input data X is 4 bits and the multiplication coefficient Y is 2 bits with CLA addition/subtraction of ±X and ±2X. The operation of the multiplier shown in FIG. 3 will be explained. The logic circuit 301 of Booth's algorithm generates control signals A, B, and C in the figure from the multiplication coefficient Y, the control signal A represents the selection of X, the control signal B represents the selection of 2x, and the control signal A represents the selection of 2x. , B, a circuit 302 executes the selection of X and 2X, a circuit 303 performs addition/subtraction switching control using the control signal C, and a CLA adder 304 performs high-speed addition with the input to obtain a multiplication output S. ing. Generally, unit multiplication circuits of about (2×4) bits are connected to form a larger multiplication array.

(Problem to be solved by the invention) However, the multiplier of Booth's algorithm is
It requires a logic circuit for Booth's algorithm, a switching circuit for The disadvantage is that the circuit scale becomes large.

An object of the present invention is to eliminate the above-mentioned drawbacks and provide a multiplier that can realize multiplication of multiplication input data in two's complement representation and a pre-limited number of multiplication coefficients with a simple configuration and small circuit scale. It's about doing.

(Means to solve the problem) FIG. 1 is a diagram showing the general configuration of the present invention.

The present invention provides multiplication input data X in two's complement representation and M predetermined multiplication coefficients Y in minimum weight representation of (n+1) bits with a radix of 2, = (1-2y,''):E, yiJ・21
(0≦j<M) (ys. is a polar sign, a positive number when yj=Q, and a positive number when ysi=1)
” represents a negative number. The term coefficients y and j of the multiplication coefficients are either 0 or 1° -1, however, the value of the non-zero term coefficient of the highest multiplication coefficient is 1. The number of non-zero term coefficients of the multiplication coefficient is m≦
((n/2) + 1)), and the multiplication result P in two's complement representation is: = X-Y, = (1-2y3S)・Σyij
-X・2I (0≦j<M)J In a multiplier that outputs 1 tomium O, when the non-zero term coefficient of the multiplication coefficient is in the i-bit position, the multiplication input data is shifted to the left by i bits. Shift data is prepared for each non-zero term coefficient of the multiplication coefficient, and the shift data for the highest non-zero term coefficient of the M multiplication coefficient term coefficients is input, and a multiplication coefficient selection signal (SEL) is used. The first selector selects and outputs one, and the non-zero term coefficients below the highest order of the multiplication coefficients are similarly selected. The second. inputs the shift data for the coefficients and selects and outputs one by the multiplication coefficient selection signal. Third. . . , the m-th selector, and the second . Third. . . . (m-1) 2 inputs connected to the m-th selector one by one and input to each of the (m-1) switch control inverters described below.
Complement calculation control signals IVT(1), IVT(2),
・, When IVT (m-1) is 11111, bit inversion is performed, and when IVT (m-1) is +101), bit inversion is not performed. Second. ..., the (m-1)th switch control inverter, and the two's complement control signals IVT(1), IVT(2
), ... IVT (m-1) is carry input (CI)
1. Second. -... an adder circuit that adds a total of m pieces of data, that is, the output data of the (m-1)th switch control inverter and the output data of the ``th'' selector, and a two's complement operation using the output data of the adder circuit as input. Control signal IVT (
When m) is "1", bit inversion is performed ((If 011, bit inversion is not performed) and the two's complement arithmetic control signal IVT(m) is connected to the carry input (CI). This multiplier is composed of an adder that performs addition with the output data of the switch control inverter m and uses the output data as a multiplication result.

(Operation) In order to explain the present invention in detail, the minimum weight display will be briefly explained. For details, please refer to the literature: Takashi, Tokura, Iwadare, and Inagaki, Coding Theory J, pages 426 to 433 (published by Corona Publishing).

For the integer N (< 2n), the base is set to 2, and the term coefficient of each term is 0, +1. If -1 is allowed, N=bo20+b121+b222+...bn-12
n-1<1)b, ((-1,0,+1), i=0.
1, 2. -, (n-1),
Among the representations of equation (1), the representation in which the number of non-zero term coefficients is the smallest is called the minimum weight representation. In order for Equation (1) to be the minimum weight representation of the integer N, there must be no adjacent non-zero term coefficients in Equation (1), that is, bibi+1''0(t==0,1,2.-・, n 2
) (2> only needs to be satisfied, and conversely, the display where equation (2) is satisfied is the minimum weight display,
And there are - minimum weight expressions that satisfy the condition of equation (2). Furthermore, in the minimum weight representation, the number of bits in the minimum weight representation that satisfies the condition of equation (2) for the n-bit binary number N is (n+1), and the number of non-zero term coefficients is ((n/2).
)+1). In the present invention, the absolute value is represented by the above-mentioned minimum weight representation, and a polarity code is added to this to represent a positive or negative integer such that if the polarity code is 0, it represents a positive integer, and if it is 1, it represents a negative integer.

Next, a method of configuring the multiplier will be explained.

The absolute value IY, 1 of the multiplier coefficient Y indicated with the minimum weight is expressed by Equation 1. The product Q of the multiplication input data X and the above IYI is expressed by Equation (4).

Q7shi"°2"(OSj<M) From equation (4), if the values of y and i are 1, the multiplication input data
If the value of y and i is -1, the data shifted to the left by i bits is multiplied by the data shifted to the left by i bits of the input data
The product Q of the above-mentioned X and the above-mentioned blank is obtained by obtaining data obtained by performing the complement operation for i from 0 to n and calculating the sum of these data. Next, if the polarity sign of Y is 1, a two's complement operation is performed on Q to obtain a multiplication result P of X and Y. To realize a plurality of multiplication coefficients, the left shift data of the multiplication input data may be switched using a selector. In this configuration, when a two's complement arithmetic circuit is realized by a switch-controlled inverter and a carry input of an adder, the maximum number of term coefficients that are non-zero in the multiplication coefficient is m = ((n/2
) + 1), it can be realized by m switch-controlled inverters with m selectors, m (m-1) input adder circuits with carry inputs, and one adder with carry input, and can be realized using conventional technology. Compared to the Booth multiplier described in 2.1, the logic circuit of the Booth algorithm and the switching circuits for X and 2X are not required, so the configuration can be made smaller with a simpler configuration.

(Example) Next, an example of the present invention will be described with reference to the drawings. FIG. 2 shows an embodiment of the multiplier of the present invention. In this example, 2
This is an example of a multiplier that takes three multiplication coefficients and has a maximum of three non-zero term coefficients.

The selector 200 shifts left shift data of the multiplication input corresponding to the most significant non-zero term coefficient of the multiplication coefficients to the selector 200.
1.202 corresponds to the non-zero term coefficients of the remaining multiplication coefficients, and the left shift data of the multiplication input data is selected by the coefficient selection signal SEL. However, if the term coefficient of the multiplication coefficient corresponding to each selector is O, 0 is selected. Inverters 203 and 204 perform bit inversion of data when the term coefficient of the multiplication coefficient corresponding to selectors 201 and 202 is -1, two's complement control signals IVT(1) and IVT(2) become "1", At the same time, the two's complement control signal IVT (
1), IVT (2) &: adder 205.206 input (CI) receives "1" and performs two's complement operation, and at the same time adder 205.206 selector 200 and the output data of inverters 203 and 204 to obtain the multiplication input data X and the absolute value of the multiplication coefficient IYI
Performs the multiplication of When the multiplication coefficient is negative, the two's complement control signal IVT(3) becomes "1" and the inverter 207
bit inversion is performed at the same time as the two's complement control signal IVT (
3), ““ is input to the carry input (cr) of the adder 208.
1'' is input and performs two's complement operation.Adder 208
can also be used to add the addition input from the outside and the multiplication result.

(Effects of the Invention) According to the present invention, by controlling the carry inputs of the selector, inverter, and adder, the multiplication of input data by a plurality of predetermined minimum weight multiplication coefficients can be easily realized. Multipliers with limited capacity can be simplified and miniaturized.

[Brief explanation of drawings]

FIG. 1 is a diagram showing the configuration of a multiplier according to the present invention, FIG. 2 is a diagram showing an embodiment of the present invention, and FIG. 3 is a diagram showing an example of a conventional multiplier. In the figure, 100-1.100-2. =・、10
0-m is a selector, 101-1.101-2. ...,
101-m is a switch control inverter, 102 is an adder, 103 is an adder, 200.201.202 is a selector, 203.204.207 is a switch control inverter, 205, 206.208 is an adder with carry input, and 301 is an adder with carry input. Booth's algorithm logic circuit, 30
2 is an X, 2X switching circuit, 303 is an addition/subtraction switching circuit, 304 is a carry look-ahead method (CLA) addition circuit, 3
05 is a most significant bit (MSB) processing circuit.

Claims (1)

[Claims] Multiplication input data X in two's complement representation and 2 as a base (n
+1) M predetermined multiplication coefficients that represent the minimum weight of bits ▲ There are mathematical formulas, chemical formulas, tables, etc. ▼ (0≦j<M) (y^s_j is the polarity sign and if y^s_j = 0 A positive number is expressed as a negative number when y^s_j=1.The term coefficient y_j^i of the multiplication coefficient is 0, 1, or -1, but the value of the non-zero term coefficient of the highest multiplication coefficient is 1.The number of non-zero term coefficients in the multiplication coefficient is m≦((n/2)+1)), and the multiplication result is expressed in two's complement ▲There are mathematical formulas, chemical formulas, tables, etc.▼ In a multiplier that outputs (0≦j<M), when a non-zero term coefficient of the multiplication coefficient is in the i-bit position, shift data obtained by shifting the multiplication input data to the left by i bits is used as the non-zero term coefficient of the multiplication coefficient. A first step that prepares each zero term coefficient, receives the shift data for the most significant non-zero term coefficient of the M multiplication coefficient term coefficients, and selects and outputs one by a multiplication coefficient selection signal (SEL). Similarly, for the selector 1 and the non-zero term coefficients below the highest order of the multiplication coefficients, input the shift data for the non-zero term coefficients below the highest order of the term coefficients of each of the M multiplication coefficients. A second, a third, . (m-1) two's complement arithmetic control signals IVT(1), IVT(2), .
..., when IVT (m-1) is "1", the bit is inverted, and when it is "0", the bit is not inverted, the first, second, etc.
, the (m-1)th switch-controlled inverter, and the second
complement control signals IVT(1), IVT(2),...
IVT (m-1) is carry input (CI) and the first
, second, . . . , an adder circuit that adds a total of m pieces of data, that is, the output data of the (m-1)th switch control inverter and the output data of the first selector, and inputs the output data of the adder circuit. Then, the two's complement arithmetic control signal IVT(m) becomes “1”.
an m-th switch control inverter that performs bit inversion when the value is "0" and does not perform bit inversion when the value is "0"; A multiplier comprising an adder that performs addition with output data of a control inverter and uses the output data as a multiplication result.