Method and Apparatus for Fast Multiplication Including Conversion of Operand Format

1. Field of the Invention

This invention relates to a fast digital multiplier adapted to multiply two binary numbers together. The invention also relates to digital adder-multipliers which can calculate functions of the kind y.sub.o = A.sub.1.sup.. y.sub.1 + A.sub.2.sup.. y.sub.2 + . . . + A.sub.i.sup.. y.sub.i + . . . + A.sub.n.sup.. y.sub.n, formed by the sum of n products of two numbers A.sub.i and y.sub.i, i being a whole number between 1 and n. The invention also relates to digital filters comprising such adder-multipliers.

2. Description of the Prior Art

The number of digits or bits in a binary number may of course be very considerable and the time taken for a multiplication operation in known multiplier circuits is greater in proportion as the number of digits or bits of the values to be multiplied together is higher. Also, if high accuracy is required the values must have a large number of digits. The known multiplier circuits therefore operate fairly slowly because of the large number of digits in the values.

It is an object of this invention to obviate the disadvantage and to provide a fast multiplier.

The basic idea of the invention is to provide a very considerable reduction in the number of bits in the values to be multiplied together yet to retain a satisfactory relative accuracy; accordingly, the least significant bits -- i.e., of low weight -- and the most significant bits -- i.e., of high weight -- which are equal to zero and whose weight is greater than the first digit of high weight equal to 1, are eliminated. Of course, an indication of how many insignificant bits or digits of the low-weight items have been eliminated from the new representation of the value must be given, so that the weight of the various digits can be known. Each value therefore presents in the form:

OF A NUMBER WITH ITS SIGN, COMPRISING THE MAIN SIGNIFICANT DIGITS OF WHICH THE FIRST HAS THE HIGHEST WEIGHT AND IS OTHER THAN ZERO, SUCH NUMBER REPRESENTING THE AMPLITUDE OF THE VALUE, AND

A NUMBER WITH ITS SIGN, INDICATING THE WEIGHT OF THE NEW UNIT RELATIVELY TO THE ORIGINAL VALUE. The sign indicates whether the weight of the new unit in the new form or representation is greater or less than the weight of the unit in the former representation. The number indicates the multiplying factor for changing from one unit to the other -- i.e., the weight shift between the new unit and the former unit. In other words, the number and its sign are a proportional indication of the amplitude and shift direction needed to place the various digits of a value in the column representing their own weight. Such number will hereinafter be called the "shift number".

According to the invention, therefore, in a process for fast multiplication of two binary values each in the form of a number of digits, each of the two values is so converted as to be in a new form excluding all the high-weight zero digits whose weight is greater than the first high-weight 1 digit and some of the lowest-weight digits, so that after conversion each value is represented by a first amplitude number with its sign, such representation comprising the main significant digits of which the first, which now has the highest weight, is different from zero, and by a second shift number whose amplitude indicates the weight shift between the units of the original and new representations of the value and whose sign represents the direction of the shift, whereafter the amplitude numbers of the two values are multiplied in known manner whereas the shift numbers are added algebraically, the result of the latter multiplication then being shifted towards either the low weights or the high weights, in agreement with the information given by the algebraic sum of the shift number, to provide a result in normal representation or form of the multiplication of the original two values.

Clearly, the invention leads to much faster multiplication of two values when reduced accuracy can be tolerated; for instance, the invention makes it possible to reduce values containing 12 or 16 bits to 8 bits.

To carry out the method according to the invention, a fast digital multiplier of two binary values each having a number of bits or digits is distinguished in that it comprises provision for converting each of the two values into a first amplitude number with a sign, such number comprising the main significant digits, the first of which has the highest weight and is different from zero, and into a second shift number whose amplitude indicates the weight shift between the units of the value before and after conversion and whose sign indicates the direction of the latter weight shift, the system also having provision for multiplying the amplitude numbers of the two values, provision for algebraically adding the shift numbers of the two values, and provision for shifting the result of multiplying the two amplitude numbers towards either the low weights or high weights, in agreement with the information given by the algebraic sum of the shift numbers.

The provision for converting such a value to be multiplied can comprise a detector and a router each receiving such value simultaneously, the detector determining by comparison the weight of the first high-weight digit of the value which is other than zero and so controlling the router that at the output thereof such weight represents the highest weights of the converted value. For instance, if the router is designed to process values of a particular bit number of format, there is automatic removal of the lowest-weight digits, the number of low-weight digits which are removed being equal to the difference between the initial number of digits or bits of the value and the router format, less the shift arising from suppression of the high weights. Such a router can be embodied by a shift register or by a multiplexer. Similar considerations apply to the provision for shifting the result of the multiplication of the two amplitude numbers of the values.

This invention is of use more particularly in fast digital adder-multipliers serving to calculate functions of the type:

In known adder-multipliers of such kind the various products A.sub.i .sup.. y.sub.i are calculated simultaneously by n separate multiplication circuits whereafter the n results are added together in an n-input adder which outputs the required result y.sub.o. This invention helps to speed up the operation of a known adder-multiplier of such kind, subject to the n multipliers calculating the A.sub.i .sup.. y.sub.i products being of the kind hereinbefore described.

Also of course, such an adder-multiplier is appropriate more particularly but not exclusively for use in the construction of digital filters in which the signal filtering effect is produced by sampling of the signal at a particular frequency, whereafter some fractions of previous samples are added to an existing sample. Such digital filters are described e.g. in the paper "Recent Advances in the Synthesis of Comb Filters" (1957 I.R.E. Nat. Conv. Rec., pages 186 to 199) and in a paper entitled "Digital Filter Design Techniques in the Frequency Domain" by Charles M. RADER and Bernard GOLD (Proceedings of the I.E.E.E. February 1967). Digital filters of this kind are very useful, particularly in radar and information transmission techniques, e.g. in telephony.

The known digital filters have basically the same design as the adder-multipliers referred to, with the addition, however, that their output is looped to an input of each separate multiplication circuit by delay facilities, such as shift stores, for the various values y.sub.1.sup.. y.sub.2, . . . y.sub.n are the values of y.sub.o at the instant of time -T, -2T, . . . -nT, respectively, T denoting the sampling period of the signal to be filtered. Consequently, it is sufficient to provide common conversion means, which are disposed in the loop, for all the values y.sub.o, y.sub.1 . . . ,y.sub.n. Associated with the values A.sub.1, A.sub.2 . . . A.sub.n are conversion means similar to those provided in the adder-multipliers according to the invention.

The figures of the accompanying drawings will show how the invention can be carried into effect. In the drawings:

FIG. 1 is a block schematic view of a multiplier according to the invention;

FIG. 2 is a block schematic view of the provision according to the invention for converting the values which it is required to multiply together;

FIG. 3 is an overall block schematic view of an adder-multiplier according to the invention; and

FIG. 4 shows a digital frequency filter according to the invention.

Like references denote like elements throughout the drawings.

The multiplier according to the invention which is shown in FIG. 1 comprises a store M (X) and a store M (Y) storing the values X and Y respectively which it is required to multiply together. Each such value takes the form of a first number with its sign, representing the amplitude of the corresponding value, and a second number with its sign, indicating the shift experienced by the value. A description will be given hereinafter with reference to FIG. 2 of how the values X and Y can be converted so as to be represented by an amplitude number and by a shift number.

The multiplier of FIG. 1 also has a multiplication unit M which can be of any known kind and which has applied to its multiplicand and multiplier inputs the amplitude numbers of the values X and Y respectively from the stores M (X) and M (Y). The multiplication unit M therefore outputs the product of the two amplitude numbers, the product going to a router A G R.

The multiplier of FIG. 1 also has a sign calculation unit S which receives signs Sx and Sy respectively of the values X and Y respectively from the stores M (X) and M (Y) respectively. The sign arising from multiplication of the values X and Y is output by unit S at a terminal s.

The stores M (X) and M (Y) also supply a calculating unit F with the shift numbers and their signs of the values X and Y. The two shift numbers are added algebraically in unit F and the addition results indicate by its amplitude the resulting shift and by its sign the direction of the shift. The router A G R receives the sum and its sign and shifts the product X.sup.. Y coming from the multiplication unit M in the direction indicated by the sign and by the number of bits or digits indicated by such sum. Consequently, the timed product of the values X and Y appears at router output e.

The system shown in FIG. 1 is therefore a means for multiplying the values X and Y in their simplified form (amplitude numbers), so that multiplication is speeded up, yet outputs the correct results of the calculated products with some loss of accuracy. There is therefore a floating-point multiplication of the values X and Y.

Conversion of each of the two values X and Y into two numbers, viz. an amplitude number and a shift number as hereinbefore defined, can be provided by means of the system shown in FIG. 2 and comprising a detector DT and a router A G T. The values to be converted and their signs are stored in a store M.sub.m, whereas the converted values -- i.e., the amplitude and shift numbers and their signs -- are stored once obtained in the store M (X) or M (Y) for further use.

The amplitude of a value to be convered, e.g. X, stored in the store M.sub.m is applied to the detector DT and router A G T simultaneously whereas the sign of the corresponding value is transferred directly to the store M (X). The detector DT determines by comparison the highest-weight bit of the value X which is different from O and transmits to the router A G T an address or shift number corresponding to the weight of such bit. The value X is shifted in the router A G T in accordance with such address, so that the amplitude number arises. The detector DT and router A G T then transmit the shift number and amplitude number respectively to the store M (X) which already contains the sign of X.

If the maximum number of bits which the router A G T can give the numbers it processes is less than the number of bits making up each number coming from the store M.sub.m, there is automatic elimination of the lowest-weight bits. Also, assuming either that the numbers are integers or that they have a decimal point but are greater than 1, the shift is always in the same direction and so the sign of the shift number is of no importance.

FIG. 3 shows a possible construction of an adder-multiplier according to the invention. The same comprises: an adding assembly AD having n signal input groups e.sub.1 to e.sub.n, one sign input s.sub.1 to s.sub.n being associated with each group e.sub.1 to e.sub.n ; and n identical multiplication assemblies E.sub.1 to E.sub.n. The groups e.sub.1 to e.sub.n receive the output signals of the assemblies E.sub.1 to E.sub.n respectively, the signs of the latter output signals being applied to the inputs s.sub.1 to s.sub.n respectively.

Consequently, if it is required to obtain a function of the kind:

the inputs e.sub.1 and s.sub.1 receive the amplitude and sign respectively of the product A.sub.1.sup.. y.sub.1, the inputs e.sub.2 and s.sub.2 receive the amplitude and sign respectively of the product A.sub.2.sup.. y.sub.2 and so on, and the inputs e.sub.n and s.sub.n receive the amplitude and sign respectively of the product A.sub.n.sup.. y.sub.n.

Since all the multiplication assemblies E.sub.1 to E.sub.n are identical and of similar construction to the multiplier shown in FIG. 1, only a single such assembly will be described, e.g. the assembly of rank i.

Each multiplication assembly E.sub.i has a store M (y.sub.i) and a store M (A.sub.i) storing the values A.sub.i and y.sub.i respectively. The latter values are presented in the form hereinbefore described -- i.e., each such value comprises a first number with its sign, representing the amplitude of the value, and a second number with its sign, indicating the shift. The values A.sub.i and y.sub.i have been entered in the stores M (y.sub.i) and M (A.sub.i) e.g. through the agency of the system shown in FIG. 2.

The multiplication assembly E.sub.i has a multiplication unit M.sub.i receiving the number representing the amplitude of y.sub.i at its multiplicand inputs and the number representing the amplitude A.sub.i at its multiplier inputs. The unit M.sub.i therefore outputs the result of the products of the two numbers y.sub.i and A.sub.i.

The multiplication units M.sub.l and M.sub.n can in known manner be embodied by elementary multiplication circuits enabling a p-digit multiplicand to be multiplied by a q-digit multiplier and making it possible to add to the result the value of a number which is applied to inputs known as "constant" inputs. Since the numbers p and q are fixed and therefore limited, grouping a number of multiplication circuits of such a kind is a means of increasing the number of bits of the inputs until it becomes possible for all the bits of the multiplicand and multiplier to be applied to the respective inputs of the group. The multiplicand and multiplier are therefore subdivided into respective blocks or portions of p and q digits, each such portion being applied to a number of elementary multiplication circuits. Each such circuit outputs a partial result of which the unit is the product of those units of the multiplicand portion and multiplier portion which are applied at the input. The various partial results are added together with regard to their respective weights. To this end, each of the partial products is applied to the constant inputs of another elementary multiplier whose output digit weight is equal to the digit weight of the number applied to the input of the constant. Each elementary multiplication circuit therefore multiplies together the two numbers applied to the multiplicand and multiplier inputs and adds to the result the value of the number applied to the constant input. Multiplications and additions therefore proceed simultaneously.

Each multiplication assembly E.sub.i comprises a sign-calculating unit s.sub.i for product amplitude, such unit receiving from the stores M (y.sub.i) and M (A.sub.i) the respective signs for the amplitudes of y.sub.i and A.sub.i.

A calculating unit F.sub.i receives from the store M (y.sub.i) and M (A.sub.i) the shift numbers of y.sub.i and A.sub.i respectively and summates them algebraically to obtain the resulting shift number and its sign.

Consequently, the sign, the shift number and the amplitude number of the product A.sub.i.sup.. y.sub.i appear at the outputs of S.sub.i, F.sub.i and M.sub.i respectively.

The n results of the multiplications must be added together through the agency of the assembly AD. The n products must therefore be restored to a single unit -- i.e., the formats must be uniform. Accordingly, each assembly E.sub.i has a router A Gi for shifting each product A.sub.i.sup.. y.sub.i in the direction indicated by the sign of its shift number and with a shift amplitude equal to the latter number. The routers A Gi have their input connected to the output of the corresponding multiplication unit M.sub.i and their output (which forms the output of the corresponding assembly E.sub.i) connected to the associated input e.sub.i of the adding assembly AD. The routers A Gi also have a control input connected to the output of the corresponding calculating unit F.sub.i. Consequently, each router A Gi can apply to the assembly AD, in correspondence with its weight, each of the digits of the product it receives from the associated unit M.sub.i.

Each router A Gi can take the form of a shift register which can shift the bits of the product applied to it in the direction and by an amount indicated by the shift number of such product. The router can also take the form of a multiplexing circuit enabling each input of a group of inputs e.sub.i of the adding assembly AD to select from the bits of the product applied to the group the bit corresponding to the weight of the particular input concerned. In this case the various multiplexer outputs to which the bits of the products A.sub.i.sup.. y.sub.i are routed can be fixedly connected to the inputs of the corresponding input groups e.sub.i of the assembly AD. Of course, routing within the multiplexer is also controlled by the corresponding shift number; for instance, a shift number of zero causes the lowest-weight digit of the output of the multiplication unit M.sub.i to be applied to the unit input of the input group e.sub.i, all the other digits undergoing a similar shift. A shift number of -1 causes the second bit of the low weights of the output of the multiplication unit Mi to be applied to the same unit input of the group e.sub.i. A shift number of +1 causes a shift of the same amplitude but in the opposite direction.

The adding assembly AD therefore receives the various products A.sub.i.sup.. y.sub.i, brought to the same format, at its various inputs and therefore adds the n values together in the light of their signs and delivers at its outputs the product y.sub.o (outputs a and b) and its sign (output c), the high-weight bits appearing at a and the low-weight bits at b.

For some uses, such as the use of the value y.sub.o in circuits similar to those hereinbefore described, it may be advantageous to convert y.sub.o, as described in respect of A.sub.i and y.sub.i, into two numbers: a number representing the value of y.sub.o with its sign, and a number indicating the shift (and its sign) of y.sub.o. Such conversion can be performed similarly to what is shown in FIG. 1.

For this purpose the high-weight digits or bits of y.sub.o are applied to a detector circuit DT determining which is the highest-weight bit which is different from zero. The detector circuit DT then compares the highest-weight digit of y.sub.o with zero; if the result of the comparison shows that there is a difference, the detector DT stops its comparison and transmits to a router AG and to a store M (y) an address or shift number denoting the weight of such bit. If the result of the comparison indicates that the highest weight bit is equal to zero, the detector circuit DT compares the digit of the next lowest weight with zero, and so on. If k denotes the number of fixed-point digits and h denotes the number of floating point digits, the comparison is proceeded with in respect of the highest weight k - h bits.

The detector DT therefore indicates the weight of the highest weight bit of y.sub.o which is different from zero. If the detector finds no such weight, it delivers an address equal to the rank of the last digit analyzed plus 1.

In the router AG to which all the bits of y.sub.o are transmitted, y.sub.o undergoes a shift controlled by the address just calculated by the detector DT, so that the router AG delivers the amplitude number of y.sub.o. The shift number, amplitude number and sign of y.sub.o are then stored in the store M (y).

As in the previous case the router AG can be a shift register or a multiplexer.

FIG. 4 shows how the adder-multiplier according to the invention can be used in the construction of a two-stage fast digital filter. The same comprises two assemblies E.sub.1 and E.sub.2 which are identical to the assemblies E.sub.i hereinbefore described and which are connected to the input groups s.sub.1, e.sub.1 and S.sub.2, e.sub.2 of an adding assembly AD having three input groups. The third input groups s.sub.o, e.sub.o is connected to a store M.sub.o containing a value x.sub.o. Downstream of the adding assembly AD there is the facility DT, AG and M (y).

The filter shown in FIG. 4 also comprises two shift stores MD1 and MD2 so devised that MD1 receives the data contained in M (y) and can transfer its own data both to M (y.sub.1) and to MD2. The same can also transmit its data to M (y.sub.2).

On the basis of amplitude signal samples x.sub.o reaching M.sub.o at a periodicity T, a filter of such a kind can calculate the function:

y.sub.1 and y.sub.2 denoting the values of y.sub.o at the instant of time -T and -2T respectively if y.sub.o is calculated at the time O, A.sub.1 and A.sub.2 being coefficients.

The values y.sub.1 and y.sub.2 appear at the output of the stores MD1 and MD2 respectively, the former receiving at its input the value y.sub.o from the store M (y). Each of the stores MD1 and MD2 performs a complete shift cycle in the time T.

As previously described, the coefficients A.sub.1 and A.sub.2 appear, in their converted form just described, at the output of the permanent stores M (A.sub.1) and M (A.sub.2) belonging to the assemblies E.sub.1 and E.sub.2 respectively; and on the one hand the values y.sub.1 and A.sub.1 and the values y.sub.2 and A.sub.2 are applied to the multiplicand and the multiplier inputs of their respective multiplication unit M.sub.1, M.sub.2. The signals output by the latter units are applied to the inputs of the two routers AG1 and AG2 whose routing is controlled by the shift number of each product A.sub.1.sup.. y.sub.1 and A.sub.2.sup.. y.sub.2 (through the agency of the calculator units F.sub.1 and F.sub.2). The three values x.sub.o, A.sub.1.sup.. y.sub.1 and A.sub.2.sup.. y.sub.2 are added together in the adding assembly AD, with due regard to their sign. The result y.sub.o is then analyzed by the detector DT determining the rank of the highest-weight bit different from zero and hence determining the shift to be applied. The value y.sub.o then goes through the routing circuit AG, which is controlled by the value of the previously determined shift and whose outputs are applied via the store M (y) to the input of the shift store MD1 outputting the value y.sub.1. The value of the shift is present in the shift store MD1.

So that the operation of the digital filter shown in FIG. 3 may be understood readily, the following assumptions will be made:

a. at the output of AD the value y.sub.o comprises 16 value bits and 1 sign bit, in which event a requirement for accuracy to 8 digits or bits calls for a maximum shift of 8 bits;

b. at the output of M.sub.o the value x.sub.o contains 10 bits plus 1 sign bit;

c. at the output of the stores MD1 and MD2 the values y.sub.1 and y.sub.2 each comprise 12 bits -- i.e., 8 bits for the amplitude number, 1 bit for the sign and 3 bits for the shift number.

The direction of the shift is assumed always to be the same, A.sub.1 is less than 2 and A.sub.2 is between 0.5 and 1.

The eight digits of y.sub.1 and y.sub.2, coming from MD1 and MD2 respectively through M (y.sub.1) and M (y.sub.2), are applied to the associated multiplication unit M.sub.1 and M.sub.2 which also receives A.sub.1 or A.sub.2, the same also taking the form of an eight-bit word or less if accuracy remains satisfactory.

If A.sub.2 can be quantized and written in the form:

where m is a positive integer .gtoreq.1, the assembly E.sub.2 can be simplified and the multiplication of y.sub.2 by A.sub.2 can become a subtraction:

For instance, if A.sub.2 = 0.984, it is possible to write:

so that A.sub.2.sup.. y.sub.2 = y.sub.2 - y.sub.2 /64. This comes to subtracting from y.sub.2, y.sub.2 itself after a shift of m times towards low weights (in the example m = 6) and therefore after having been divided by 2.sup.m = 2.sup.6 = 64.

Since y.sub.2 is represented by 8 digits, there remain in this example only 8 - 6 = 2 digits or bits, the first of which can be 0 (see hereinafter), to represent y.sub.2 /64; there is therefore a loss of low weights and a reduction of the latter number. A fraction smaller than y.sub.2 /64 is therefore subtracted from y.sub.2, and the coefficient A.sub.2 therefore acquires a value slightly closer to 1 than the theoretical value taken as an example.

The product A.sub.2.sup.. y.sub.2 therefore appears very rapidly, so that such product can be added after routing to the value x.sub.o which has been available since the beginning of the calculation.

Consequently, when the result of the multiplication of A.sub.1 by y.sub.1 appears at the output of E.sub.1, y.sub.o can be found by adding such result to the result of the previous addition.

To simplify equipment, the routers AG1 and AG2 can perform five possible shifts, viz. 0 or 2 or 4 or 6 or 8 digits, quantized in 2-steps. The latter routers also make it possible for each of the bits at the inputs of the adder AD to be chosen as "one amongst five" bits of the outputs of the multiplication units M.sub.1 and M.sub.2.

Since the shifts are quantized by 2-bit groups, the higher-weight bit considered in floating point operation can be 0 if the next bit is a 1, for a further shift of 2 bits would eliminate such second bit. If the number is small (zero shift), there can of course be a number of zeros on the high-weight-digit side.

If the adder input groups e.sub.1 and e.sub.2 have e.g. 16 bits each, the routers AG1 and AG2 have 32 routing circuits each making a "one amongst five" selection. The adder AD outputs a 16-bit representation of the value y.sub.o.

The 8 higher-weight bits of y.sub.o are applied to the detector DT, which outputs 3 address bits (shift number) to the router AG whose input receives y.sub.o. The router AG makes a "one amongst five" selection, giving a shift which can vary from zero to 8 bits.

The 8 bits representing the value of y.sub.o at the output of the router AG, the sign bit of y.sub.o and the three shift bits are then placed in the shift store MD1.

In the embodiment shown in FIG. 4 the store M (y) may not exist physically, the 12 bits of y.sub.o possibly being introduced directly into the store MD1 from the output of detector DT, from the output of the router AG and from the sign output b of the adder AD.

It may be useful if the filter shown in FIG. 4 can accept numbers whose digit count (or format) is greater than the output format of the adder AD, as for instance, if in the example just given it is required to process numbers having 18 bits instead of 16.

There are no difficulties with the multiplication units M.sub.1 and M.sub.2 since the same operate on a floating point basis. It is sufficient to have available a shift of adequate amplitude -- in the present case of 18 - 8 = 10 bits -- i.e., an extra 2-bit shift. In the adder AD which normally operates on a normal format, a residual 2-bit shift must be retained for the three numbers x.sub.o, A.sub.1.sup.. y.sub.1 and A.sub.2.sup.. y.sub.2, so that 2 low-weight digits can be removed from the 18 bits or digits. For instance, in the case of numbers, e.g. y.sub.1 and y.sub.2, which exceed the format receivable by the adder AD (16 bits), the timing amplitude provided by the routers AG1 and AG2 is so chosen that such numbers have the receivable format -- i.e., that the amplitude of such timing is less than the amplitude of the readjustment which should normally be made and that the lowest weight of the readjusted number corresponds not to the weight of the units but to a greater weight. For instance, and as seen in the foregoing example, in the case of 18-bit numbers a readjustment of 10 bits could normally be provided. Actually, they will be readjusted by only 8 bits and the lowest weight will be equal to a weight of 2.sup.2 = 4. Conversely, in the case numbers e.g. x.sub.o, not exceeding the format receivable by the adder AD, a shift is made (by means of a router which is not shown) of an amplitude such that the lowest-weight bit of such number corresponds to the same weight as the lowest-weight bit of numbers exceeding the format. For instance, in the previous example x.sub.o would be given a 2-bit adjustment so that its lowest-weight bit takes the weight 4.

Of course, the two multiplication assemblies E.sub.1 and E.sub.2 can be coupled together so that the readjustments of the routers AG1 and AG2 are the same.