FR2475250A1 - Fast multiplier for long binary numbers - uses multiple and=gates to multiply one bit of first number simultaneously with every bit of second number and groups like weighted bits - Google Patents

Abstract

THE MULTIPLIER DEVICE OF THE INVENTION INCLUDES ELEMENTARY MULTIPLIERS 5 ACHIEVING ALL THE POSSIBLE COMBINATIONS OF EACH TIME ONE OF THE BINARY ELEMENTS OF ONE OF THE NUMBERS A0-A63, WITH ONE OF THE BINARY ELEMENTS OF THE OTHER NUMBER B0-B63, AND SEVERAL PROCESSING STAGES 6, 7, 8 DETERMINING THE NUMBER OF 1 OF EACH WEIGHT OF BINARY ELEMENTS OF THE PREVIOUS STAGE BY WEIGHING, BY WIRING, THE BINARY ELEMENTS OF THIS NUMBER 1, A FINAL ADDITIONER STAGE 9 REALIZING THE ADDITION OF TWO BINARY NUMBERS FORMED BY THE RESULTS PROVIDED BY THE LAST PROCESSING STAGE 8. APPLICATION: DIGITAL FILTERS.

Description

The present invention relates to a method for rapid multiplication of two binary numbers and to a fast numerical multiplier for the implementation of this method
Currently known digital multipliers are of the "serial-parallel" type, and their operating speed is sufficiently high for most applications. However, when one must multiply between them two very long binary numbers in a very short time, as is the case for example for some digital filters, these known multipliers are not fast enough, which forces to reduce the performances systems in which they must be used.

 The subject of the present invention is a method of multiplying two binary numbers faster than known methods, and a numerical multiplier making it possible to obtain the result of the multiplication of two binary numbers of great length much more rapidly than with multipliers of the prior art.

 The method for multiplying two binary numbers according to the present invention consists, after having multiplied, in a manner known per se, each of the binary elements of one of the numbers by each of the binary elements of the other number, preferably simultaneously, to group together the results of the multiplication of each two bits according to the respective weights of these results, then for each result weight to count and to memorize the number of "1", to be assigned to each number of "1" thus obtained a weight which is equal to the weight of the corresponding results, to group the same weighted binary elements of the weighted numbers, to count and to store the number of "I" of each weight of the weighted numbers, and so on to obtain for each weight of binary elements of weighted numbers a number of "1" equal to at most two, and finally to add in a manner known per se weighted numbers.

The multiplier device for implementing the method according to the present invention is connected to the different outputs of two registers in each of which is stored one of the two numbers to be multiplied between them, and comprises - a multiplication stage comprising AND gates to two
each entry and whose number equals the total number of
possible combinations of each time one of the binary elements
of one of the numbers with one of the binary elements of the other
number, one of the inputs of each door being connected to one
outputs of the first of the two aforesaid registers, and the other
input being connected to an output of the other of these two registers,
in order to obtain all of these combinations, these doors
being preferably grouped according to the sum of the weights of the
two corresponding bits, - one or more processing stages each comprising several
number determination blocks of "I" to each of which one
assigns weight from zero to maximum weight
necessary, these blocks each having a register or
output, the cells of this register or the output terminals being
assigned a weight equal to their own weight plus weight
-assigned to their determination blocks, the different inputs
of these blocks being each time connected, for the first floor,
at the outputs of all AND gates receiving two elements
binaries whose sum of weights is the same, and for the
following stages, at the outputs of all the cells or at the terminals
of the previous stage and having, after weighting, the
same weight, the determination blocks of the last milking stage
with a maximum of two output terminals or a two-digit
maximum cells, the outputs of the last treatment stage
being connected to corresponding inputs of an adder
quick.

According to a preferred embodiment of the invention, each number determination block has a transcoding circuit having a multi-stage pyramidal processing structure, the input stage, at the base of the pyramid, comprising in parallel a plurality of elementary transcoder circuits each providing on its different outputs the value, in pure binary, of the number of 11 1I for each bit weight of the numbers or parts of numbers arriving on all its inputs, the outputs of at least two
different transcoder circuits being grouped each time at
the input of an adder circuit, several stages of such
adding circuits being arranged in cascade, the last stage,
at the top of the pyramid, with only one addi
tionneur.

The present invention will be better understood by means of the
detailed description of an embodiment and then as a non
limiting and illustrated by the attached drawing, in which
Figure I is a simplified diagram of a compliant multiplier
to the present invention,
FIG. 2 is a block diagram of a transcoder of the multi
Folder of Figure i, and,
FIG. 3 is a partial diagram of a variant of the device
of Figure 1.

The multiplier shown schematically and partially on
FIG. 1 is intended for the multiplication of two binary words
A and B each having 64 bits respectively referenced
A0 to A63 and BO to B63. It is understood, however, that
the invention is not limited to words of 64 bits
each, and that words of any length can be
multiplied between them, one of them may even be longer than
the other, the multiplier device then being modified accordingly
quence, in a manner obvious to those skilled in the art on reading
the description below. To simplify Figure I, neither the
clock inputs of the various registers, or the links
such inputs to an appropriate clock signal source, or
this source have been represented.

The two numbers A, BF are available in registers 1,
2, these two registers could for example be the
output registers of read / write memories. Each of the cells of the registers I and 2 is connected to a corresponding wire of a
matrix 3, 4 respectively, of parallel wires. However,
matrices of any other appropriate conformation can be used
lisées. Each time a wire of the matrix 3 and a wire of the
matrix 4 is connected to an input of an AND gate with two inputs of
in order to obtain all possible combinations of each of the bits of the number A with each of the bits of the number B. In the case where the numbers A and B have 64 bits each, there are therefore 4096 possible combinations. These different combinations and their respective weights can for example be determined from Table 1 below, in which N denotes the number of combinations by weight. In this table 1, the first column contains all the combinations of BO with each of the bits of A, from AOBO to A63BO, the second column contains all the combinations of B1 with each of the bit elements of
A, and so on until the 64th column which contains all the combinations of B63 with each of the binary elements of A.

These combinations are arranged from top to bottom in ascending order of their respective weights. Thus, for weight 0, there is only one combination: AOBO, which is therefore the only combination of the first row. For weight 1, (second row) there are two combinations: AIBO and AOB1, and so on until the 127th row which contains only A63B63, TABLE I

<SEP><SEP> Weights of <SEP> Binaries <SEP> N
<tb> 0 <SEP> A0B0 <SEP> 1
<tb> 1 <SEP> A1B0 <SEP> A0B1 <SEP> 2
<tb> 2 <SEP> A2B0 <SEP> A1B1 <SEP> A0B2 <SEP> 3
<tb> 3 <SEP> A3B0 <SEP> A2B1 <SEP> A1B2 <SEP> A0B3 <SEP> 4
<tb> ............................................... .................................................
<tb> ............................................... .................................................
<tb> 59 <SEP> A59B0 <SEP> A58B1 <SEP> .................... <SEP> A0B59 <SEP> 60
<tb> 60 <SEP> A60B0 <SEP> A59B1 <SEP> ......................... <SEP> A0B60 <SEP> 61
<tb> 61 <SEP> A61B0 <SEP> A60B1 <SEP> A59B2 <SEP> ......................... <SEP> A0B61 <SEP > 62
<tb> 62 <SEP> A62B0 <SEP> A61B1 <SEP> A60B2 <SEP> ......................... <SEP> A1B61 <SEP > A0B62 <SEP> 63
<tb> 63 <SEP> A63B0 <SEP> A62B1 <SEP> A61B2 <SEP> ............................... <SEP> A1B62 <SEP> A0B63 <SEP> 64
<tb> 64 <SEP> A63B1 <SEP> A62B2 <SEP> ................................ <SEP> A2B62 <SEP> A1B63 <SEP> 63
<tb> 65 <SEP> A63B2 <SEP> ................................ <SEP> A3B62 <SEP> A2B63 <SEP> 62
<tb> 66 <SEP> A63B3 <SEP> .......................... <SEP> A4B62 <SEP> A3B63 <SEP> 61
<tb> 67 <SEP> A63B4 <SEP> .................... <SEP> A5B62 <SEP> A4B63 <SEP> 60
<tb> ............................................... .................................................
<tb> ............................................... .................................................
<tb> 124 <SEP> A63B61 <SEP> A62B62 <SEP> A61B63 <SEP> 3
<tb> 125 <SEP> A63B62 <SEP> A62B63 <SEP> 2
<tb> 126 <SEP> A63B63 <SEP> 1
<Tb>

 The different AND gates thus connected to the various wires of the matrices 3 and 4 form a multiplication stage 5. For the clarity of the drawing, the different doors of the stage 5 have been grouped by weight successively increasing from top to bottom, since the weight Zero to weight 126. It is thus determined that from zero weight to weight 63 the number of combinations of bits per weight varies from one to a maximum of 64, and that this number regularly decreases to a combination for weight. 126, the weights being referenced p, from p = 0 to p = 126.

 The multiplication stage 5 is followed by a first processing stage 6 consisting of transcoders, an exemplary embodiment of which is shown in FIG. 2. Each of these transcoders is assigned a weight, from 0 to 126, and is connected to the outputs of all AND gates corresponding to bit combinations of the same weight. Transcoders of stage 6 therefore have sizes corresponding to the number of combinations for each weight considered. Thus, for the zero weight, the transcoder may be a simple flip-flop, since it has only one input, while the assigned one of the weight 63 has 64 inputs.

 Since, as explained below, the transcoders comprise an output register whose number of cells is equal to the maximum number of bits of the number, expressed in binary notation, of bits "1" present on its various inputs. , the number of cells of the output registers of the different transcoders of the processing stage 6 varies from 1 to 7, a register cell being sufficient for the zero and 126 weights, and seven cells being necessary for the transcoder corresponding to the 63. Determining the number of cells in each output register of the transcoders of stage 6 being as easy as determining the number of combinations of bits by weight, it will not be explained in more detail below. It will be noted simply that the stage 6 comprises 127 transcoders, the transcoders assigned to the zero weights and 126 can be simple flip-flops.

 The first processing stage 6 is followed by a second processing stage 7 also composed of transcoders similar to those of the stage 6, but smaller than the latter, apart from the transcoder corresponding to the zero weight, which remains the same size and can be a flip-flop.

 The transcoders of stage 7 are connected to the outputs of the cells of the output registers of the transcoders of stage 6 in the following manner. The cells of the output registers of each transcoder of stage 6 are weighted by assigning each cell containing the least significant bit the same weight as that assigned to this transcoder. Of course, in each output register of the transcoders of the stage 6, the cells assigned to the binary elements of higher weight are weighted accordingly: thus, for an affected transcoder of the weight n, the cell containing the binary element of weight the the lower of the output register is assigned the weight n, the next cell of the same register is assigned weight n + 1, and so on.

 The outputs of the cells of the output registers of the transcoders of the stage 6 are then grouped according to their respective weights, and they are connected to the inputs of the transcoders of corresponding weight of the stage 7, each transcoder of the stage 7 being equally assigned a weight.

 It can easily be verified that the processing stage 7 comprises 127 transcoders, the first two transcoders, assigned weights zero and 1, having a single input and a single output each, and therefore can also be simple flip-flops. It can also be easily verified that, since the transcoders of the stage 7 have at most 7 inputs, their output registers comprise a maximum of three cells. It will be noted in particular that in the processing stage 7, the weighted transcoder 126 has two inputs, and therefore its output register must comprise two cells.

 In the same way as for the output registers of the transcoders of the stage 6, the cells of the output registers of the transcoders of the stage 7 are weighted. The outputs of the cells of the output registers of the stage 7 are then connected to corresponding inputs of transcoders of a processing stage 8, these transcoders of the stage 8 are also each assigned a different bit weight. Since in stage 7 the output register of the weight assigned transcoder 126 has two cells, the cell has the weight bit.

the highest will, after weighting, the bit weight 127, and therefore the stage 8 must include a transcoder assigned the weight p = 127. Consequently, the processing stage 8 comprises 128 transcoders respectively assigned weights zero to 127. It will be noted that in the stage 8, the first three transcoders assigned weight zero to 2, and the last transcoder assigned to the weight 127, do not have only one entry and one exit each,
The outputs of the different output registers of the processing stage 8 are connected to a last processing stage 9 in the following manner.

The output cells of the first three least significant transcoders of the processing stage 8 are connected to a register 10, while the output registers of all the other transcoders of the processing stage 8 are connected to an adder 11. The three outputs of the register 10, corresponding to its three inputs, are referenced S0 to S2, and the 125 outputs of the fast adder 11 are respectively referenced S3 to 8127,
On the outputs S0 to S127, the result of the multiplication of A by B is collected, the weight of the bits of the result corresponding to the numbers of each of the aforementioned outputs S0 to 8127. It will be noted that the AND gates can be replaced by any circuit performing the same function, for example registers or PLA circuits
With reference to FIG. 2, the structure of the largest transcoder circuit used in the multiplier represented in FIG. 1, namely the transcoder of the processing stage 6 assigned to the bit weight 63 and comprising 64 inputs, the structure of other transcoders, having a lower number of inputs, deduced in a manner obvious to those skilled in the art of the structure of the transcoder shown in Figure 2 and described below.

The transcoder 11 represents in FIG. 2, comprises 64 inputs respectively referenced E0 to E63. The transcoder 11 comprises a first processing stage 12 comprising four converter circuits respectively referenced 13, 14, 15 and 16
The converter circuits 13 to 16 each have 16 inputs, and are, for example, logic circuits known under the designation PLA (programmable logic array), that is to say programmable logic circuits. Logic circuits 13 to 16 are implemented, in a manner known per se, to present on their outputs the value, in pure binary notation, of the total "1" present on all their inputs, Since each of the circuits 13 to 16 has 16 inputs, there is a maximum of 16 " 1 "present on their inputs at a given time, and these circuits must have 5 outputs each because it takes 5 bits to represent all the numbers from 0 to 16.

 The outputs of the converter circuits 13 and 14 are connected to a register 17 to 10 cells, and the outputs of the converter circuits 15 and 16 are connected to corresponding inputs of a register 18 to 10 cells. The ten outputs of the register 17 are connected to corresponding inputs of an adder 19, while the ten outputs of the register 18 are connected to corresponding inputs of another adder 20, the adder 19 and 20 forming an addition stage 21.

 Since the adders 19 and 20 are each connected to 2 converter circuits of the input stage 12, they must each be able to present on their outputs a number at most equal to 32, that is to say a number represented on 6 significant bits at most. The adders 19 and 20 must therefore each have 6 outputs, the 6 outputs of the adder 19 are connected to corresponding inputs of a flip-flop register 22, while the 6 outputs of the adder 20 are connected to inputs The six outputs of each of the two registers 22 and 23 are connected to corresponding inputs of an adder 24.

Since the adder 24 must have at its outputs a number at most equal to 64, that is to say the maximum number of inputs of the transcoder 11, this adder 24 must have seven outputs. The seven outputs of the adder 24 are connected, by means of a bassinet register 25 to seven output terminals respectively referenced S0 to S6 forming the seven outputs of the transcoder device 11.

 The clock signal inputs CK of the registers 17, 18, 22, 23 and 25 are all connected to a common terminal 26 which is itself connected to a clock signal generator (not shown).

 It is understood that the transcoder device shown in FIG. 2 could be constituted differently if other circuits were available: in particular if there were programmable logic circuits with 64 inputs, the circuit of FIG. 2 would be reduced to a single such circuit whose seven outputs would be connected directly or possibly via a register terminals S0 to S6, which would of course increase the processing speed of the transcoder circuit.

 We will now explain the operation of the multiplier described above It is known that an AND gate allows for the multiplication of two bits each arriving on one of its two inputs Since all possible combinations have been considered of each of the binary elements of the number A with each of the binary elements of the number B, and that each of these combinations is realized in the form of a multiplication by a corresponding AND gate, it is necessary and sufficient to obtain the product AB, -de sum all the partial results available at the exit of the AND gates of the stage 5, taking into account, of course, the weight of each of the partial results.

For this purpose, for each of the weights of multiplication results, all corresponding partial multiplication results are grouped together. The processing stages 6, 7, 8 and 9 of FIG. 1 are intended to produce, as quickly as possible, the sum of all the partial results, given their respective weights.

 We will now explain using a simplified example of multiplication how the processing stages 6 to 9 work.

For example, we take two numbers A and B such that A = 311 and
B = 249 is, in binary notation: A = 100110111, B = 011111001.

 The multiplication of A by B can be written in a manner known per se as shown below (Table 2) but, instead of determining column by column, the result by referring to the next column all the possible detentions determined. , for each column, the number of "1" appearing there without taking care of possible deductions, this number of "1" being written in the last row of table 2, in decimal notation.

TABLE 2
100110111 100110111
100110111
100110111
100110111 100110111
1112323543431111
Table 3 below is then obtained by converting the number, expressed in decimal notation, of "1" for each column in binary notation, and weighting each of these numbers according to its column, that is, say by assigning to each of these numbers the weight of the corresponding column, the rightmost column having of course the weight 0, which is the weight of the least significant bit of the number A. This gives the table 3 below, noting that the highest number of "1" is five, that is, only three bits are required to represent all of these "1" numbers.

TABLE 3
001
001
001
001
011
100
011
100
101
011
010
011
010
001 001
-001
001121222121111111
In the last row of this table 3, the number of "1" for each corresponding column has been reported in decimal notation.
From Table 3 * the weighting of the result of the count of "1" of each column is restarted, and then Table 4 below is obtained, in which the first row of the result indicates, in decimal notation, the number of "1" in each column, and the second line is the result of the addition of two fictitious binary numbers that would be obtained by placing Table 4 on two lines
TABLE 4 Ol
01
01
01
01
01
01
10
01
10
10
10
01
10
01
'01 -
01202110201111111
10010111001111111
It can be seen that the result of addition in the last row of Table 4 is equal to the result of the multiplication of A by B. Starting from Table 4, the weighting of the number "1" can be repeated and we obtain Table 5 below, in which the result, in binary notation, of the addition, column by column, of the binary elements is directly transferred to the result line.
TABLE 5
01
01
01
01
01
01 01
00
10
00
01
01
10
00
10 01
10010111001111111
It is found that the addition result of Table 5 is also equal to the result of the multiplication of A by B. Therefore, the result of the multiplication of A by B can be obtained from any one of Tables 2 to 5. 5. In practice, it is preferable to use Table 4, in which each column has at most two bits "1" The result of the multiplication of A by B is then obtained by a conventional binary adder, preferably an adder fast binary.

 Tables 4 and 5 show that, by a series of weights and counting of bits by column, we obtain a table in which each column has only one binary element "1". then even more to use adder, but to detect the presence or absence of a binary element "1". However, it will be noted that the example described above relates to relatively short binary numbers.

If we are dealing with much longer binary numbers, for example with several hundred bits, we can check that obtaining a table similar to Table 5, that is to say a table in which each column has at most a single binary element "1", may require a large number of weighting cycles and element counts "1", while obtaining a table similar to Table 4, c that is, a table in which each column has a maximum of two bits, is relatively fast.

 One can easily check that, when multiplying two binary numbers between them, considering one of these two numbers if they are of the same length, or considering the longest of them if they are of lengths different, we obtain a table similar to Table 4, that is to say a table in which each column has not more than two bits "1", directly from a table similar to Table 2 if the number considered has not more than three bits, after a weighting step (performed by stage 7) if the number considered comprises from 4 to 7 bits, after two weighting steps (performed by stages 7 and 8) if the number considered comprises from 8 to 127 bits, and after three weighting steps (performed by stages 7 and 8 and by an additional processing stage inserted between stages 8 and 9) if the number considered has from 128 to 2127- 1 element binary ts.

From the table similar to Table 4, it is only necessary to perform the addition of two binary numbers, and even if these two binary numbers are very long, the adder usually known are fast enough for most applications. .

 Therefore, thanks to the treatment method described above, two very long binary numbers can be multiplied between them in a relatively short time.

 FIG. 3 partially shows an alternative embodiment of the device of FIG. 1 to perform the multiplication AB. Instead of producing the converter circuits as explained above with reference to FIG. 2, the adders such as the adders are omitted. 19, 20 and 24, the outputs of the registers such as 17 and 18 are directly weighted, and the thus weighted outputs of the registers such as 17 and 18 are connected to the corresponding weight entries of the second treatment stage which is produced in the same way. than the first treatment stage, that is to say without adders.

 In the partial diagram of FIG. 3, for the first eight weights, referenced p = 0 to p = 7, the beginning of the multiplication stage 5 with AND gates is represented, this stage remaining unchanged with respect to that represented by FIG. in FIG. 1, as well as the first eight circuits of weight p = 0 to p = 7 of the four processing stages 27, 28, 29 and 30 respectively. Indeed, it can easily be demonstrated that for the device of FIG. 3, one more processing stage is necessary than for the device of FIG. 1, but each of these treatment stages no longer comprises adders. Each processing stage comprises only a converter circuit such as the circuits 13 to 16 of FIG. 2, each of the converter circuits having a number of appropriate inputs and outputs. Each converter circuit is followed by a register having a corresponding number of cells. However, in some cases, particularly if the converter circuits have few outputs, these registers which are intended only to present the information of output of a whole treatment stage. In the device of FIG. 3, the last processing stage, referenced 30, is followed by a stage 31, similar to the stage 9 of the device of FIG. 1 and comprising a simple register for the weights 0 to 3, and an adder for the other weights.

 It can easily be verified, by drawing up tables similar to Tables 2 to 5 described above, that the operation of the device of FIG. 3 implements the same method as the device of FIG. 1, with the only difference that in these new tables several successive rows may have the same weight since there are no more adders themselves carrying the sum of the binary elements of the same weight.

 It should be noted that the above method can also be applied if one or both of the numbers A, B and B are completely or partially in series, the weights and groupings then being obvious for the those skilled in the art in the light of the example described above.

The implementation device is then reduced accordingly, and the adder of the stage 9 or 31 is replaced by an accumulator-adder
All the circuits described above may be partially or totally integrated, and transcoders may be grouped on the same integrated circuit in an order different from that shown in the figures.

Claims (4)

 1. A method of rapid multiplication of two binary numbers in which each of the binary elements of one of the numbers is multiplied, in a manner known per se, by each of the binary elements of the other number, preferably simultaneously, charac terized by the that the results of the multiplication of each two bits are grouped according to the respective weights of these results, that, for each weight of result, the number "1" is counted and stored, that each weight is weighed number of "1" thus obtained by assigning it a weight which is equal to said corresponding result weight, which is grouped together the binary elements of the same weight of the numbers thus weighted, which are counted and stored the number of "I" of each weight of bits of the weighted numbers, which is then carried out until, for each weight of weighted number bits, a number of "1" equal to at most two is obtained, and that we ad finally, in a manner known per se, the last weighted numbers.  2. Multiplier device for implementing the method according to claim 1, connected to the different parallel outputs of two registers in which are stored the two numbers to be multiplied between them, characterized in that it comprises: - a multiplication stage comprising AND gates with two inputs  each and whose number is equal to the total number of combi  possible each time one of the binary elements of one  numbers with one of the binary elements of the other number,  one of the inputs of each AND gate being connected to one of the  outputs of the first of the two aforesaid registers, and the other input  being connected to an output of the other of these two registers,  way to get all the said combinations, these doors being,  preferably grouped according to the sum of the weights of the two  corresponding binary elements, - one or more treatment stages each comprising several  number determination blocks of "1" to each of which one  assigns a weight from weight 0 to maximum weight  necessary, these determination blocks each having a register  or output terminals; the cells of this register or the output terminals being assigned a weight equal to their own weight plus the weight assigned to their determination blocks, the different inputs of these determination blocks being each time connected, for the first stage, at the outputs of all the AND gates receiving two bits whose sum of weights is the same, and for the next stage or stages, to the outputs of all the cells or to the output terminals of the preceding stage and having, after weighting, the same weight, the determination blocks of the last processing stage having a maximum of two output terminals or a maximum two-cell register, - a fast adder whose different inputs are connected to the corresponding outputs of the last processing stage.  3. Multiplier device according to claim 2, characterized in that each number determination block of "1" comprises a transcoding circuit having a pyramidal structure with several stages of treatment, the input stage, at the base of the pyramid, comprising in parallel a plurality of elementary transcoder circuits each providing on its different outputs the value, in pure binary, of the number "1" for each bit weight of the numbers or parts of numbers arriving on all its inputs, the outputs of at least two different transcoder circuits being grouped each time at the input of an adder circuit, several stages of such adder circuits being arranged in cascade, the last stage at the top of the pyramid comprising only one adder circuit.  4. Multiplier device according to claim 2, characterized in that each number determination block of "1" comprises a transcoding circuit, for example a read-only memory or a programmable logic circuit, optionally followed by a register.