Abstract:
High speed digital multiply-by-three device comprising a sum generation unit associated with a carry look-ahead unit, the latter comprising means for generating the carry bit C k   +1  to be fed to the (k+1) th  stage of said sum generation unit by performing the logic function 
     
       C.sub.k.sub.+1 =X.sub.k.sup.. X.sub.k.sub.-1 +(X.sub.k.sub.-1.sup.. 
     
      X K   -2  + . . . + X k   -1 .sup.. X k   -3 .sup.. X k   -5  . . . X 1 ) + (X k .sup.. X k   -2 .sup.. X k   -3  + . . . + X k .sup.. X k   -2 .sup.. X k   -4  . . . X 0 )

Description:
BACKGROUND OF THE INVENTION 
     This invention relates to a high-speed digital device for multiplying any binary number by three. 
     In many computing devices, and particularly in digital multiplier devices, it is often necessary to multiply a given number x by three. One of the more attractive prior art methods of performing multiplications consists in dividing the multiplier term into groups of bits of constant length and in analyzing such groups to determine a multiple of the multiplicand to be used in order to carry out the desired multiplication as a sequence of accumulations. Once this multiple has been determined, means for generating same must of course be provided. 
     More specifically, let us assume that, in a multiplication XY to be performed, the multiplier Y is divided into several groups of three bits each, beginning with the lowest-order bit, plus one of the bits of the preceding group. For example, if ##EQU1## Groups g1, g2, g3 and g4 are successively analyzed. To each configuration of a group g corresponds a contribution which is a multiple of X to be added to the contributions of the previous groups to finally provide, after group g4 has been processed, the desired product of XY. The following table summarizes the contributions associated with the various configurations of g. 
     
         ______________________________________      Bit of         Multiple ofg          preceding g    X______________________________________000        0              0000        1              +X001        0              +X001        1              +2X010        0              +2X010        1              +3X011        0              +3X011        1              +4X100        0              -4X100        1              -3X101        0              -3X101        1              -2X110        0              -2X110        1              -X111        0              -X111        1              0______________________________________ 
    
     The above method makes it possible to find a compromise between the number of adders required to build the multiplier device and the speed of the latter. However, it will be seen that the speed of the device is dependent, in particular, upon the time required to determine the multiples of X. This is especially troublesome where the device must perform successive multiplications XY, X&#39;Y&#39;, X&#34;Y&#34;, etc., at a rate which should be as fast as possible and in any event faster than that at which the operands X, Y, X&#39;, Y&#39;, etc., are received. In such cases, the so-called pipelining technique is sometimes used. That is, as soon as group g1 of Y has been processed, the associated circuits start processing group g1 of Y&#39;, thereby initiating the computation of X&#39;Y&#39;, then of X&#34;Y&#34;, etc., before the computation of XY is completed. It is clear, therefore, that a device capable of generating the multiples of terms X, X&#39;,X&#34;, etc., as quickly as possible would be quite useful. Multiples such as X, 2X, 4X, that is, multiples belonging to the family 2 N  X, can readily be generated from X. All that is required to do so is to shift X N bit positions toward the higher-order positions. However, this does not apply when 3X or one of its multiples is required. 
     In a prior art device designed to multiply binary numbers by means of analyses of the groups of bits g that comprise the multiplier, 3X is obtained by adding X to 2X in two successive operations. Two basic cycles of operation instead of one are therefore required. Such a process is too slow and does not permit maintaining an operating cycle of constant duration regardless of the configuration of the groups of bits. 
     Alternatively, 3X can be generated using an additional device. In that case, the additional device should be inexpensive and capable of operating at high speed. 
     Accordingly, it is an object of the present invention to provide a high-speed device for multiplying any binary number X by three. 
     Another object of the invention is to implement such a device using a limited number of circuits, thereby reducing the size of the device. 
     The foregoing and other objects, features and advantages of the invention will be apparent from the following more particular description of preferred embodiments of the invention, as illustrated in the accompanying drawings. 
    
    
     THE DRAWINGS 
     FIGS. 1 and 1A represent an implementation of the carry look-ahead unit of the present invention. 
     FIG. 2 illustrates an implementation of the multiplier device of the invention. 
     FIG. 3 is an implementation of another multiplier device realized in accordance with the invention. 
     FIGS. 4 and 5 show circuits associated with the device of FIG. 3. These features show the circuitry for providing an adder that performs the operation X + 2X, the adder being divided into a number of sub-adders. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The multiplier device of the present invention provides 3X by adding X to 2X in accordance with the well-known carry look-ahead technique, but is characterized in that it includes a carry look-ahead unit that feeds the inputs of a sum generation unit, with the carry look-ahead unit providing the carry bit intended for the stage of order (k+1) of the sum generation unit by means of the following logic combinations of the bits of X: 
     
         x.sub.k. X.sub.k.sub.-1 + (X.sub.k.sub.-1. X.sub.k.sub.-2 + . . . + X.sub.k.sub.-l. X.sub.k.sub.-3. X.sub.k.sub.-5 . . . X.sub.1) + (X.sub.k. X.sub.k.sub.-2. X.sub.K.sub.-3 + . . . + X.sub.k. .X.sub.k.sub.-2. X.sub.k.sub.-4 . . . X.sub.0) 
    
     an adder comprising a basic carry look-ahead unit and a basic sum generation unit is described in an article entitled &#34;High-Speed Arithmetic in Binary Computers&#34; by O. L. McSorley in &#34;Proceedings of the IRE, &#34; January 1961. The carry look-ahead unit, by logically combining the bits of the words to be added together, supplies a carry bit to each stage of the sum generation unit. This arrangement could be used to generate the multiple of X being sought here, but would require the provision of an excessive number of circuits for the carry look-ahead unit. 
     The present invention enables a simple carry generator to be realized. If the bits of X are designated X 0 , X 1 , . . . , X k , the carry bits, C 0 , C 1 , . . . , C k , and the sum bits, S 0 , . . . , S k , and if the so-called two&#39;s complement code is used and if X n  is assumed to be the sign bit order, the addition X+2X can be written: 
     
         ______________________________________Order n+2     n+1     n     n-1   ... k    ... 1   0______________________________________Carries       C.sub.n+1                 C.sub.n                       C.sub.n-1                             ... C.sub.k                                      ... C.sub.1                                              C.sub.0X             X.sub.n+1                 X.sub.n                       X.sub.n+1 X.sub.k  X.sub.1                                              X.sub.02X            X.sub.n X.sub.n-1                       X.sub.n-2 X.sub.k-1                                          X.sub.0                                              .Sums  S.sub.n+2         S.sub.n+1                 S.sub.n                       S.sub.n-1                             ... S.sub.k                                      ... S.sub.1                                              S.sub.0______________________________________ 
    
     The only possible combinations of X k  and X k   -1  are: 
     
         ______________________________________X.sub.k          X.sub.k-1______________________________________0                00                11                01                1______________________________________ 
    
     In the first case, no carry bit C k-1  intended for column &#34;k+1&#34; of the above table can be generated in column &#34;k&#34;  regardless of the value of C k  since X k  = 0 and X k   -1  = 0. 
     In the second case (X k  = 0 and X k   -1  = 1), the generation of a carry bit depends on the value of C k . Thus, C k   +1  = 1 where a carry bit is generated in column &#34;k-1&#34; or any of the preceding columns. This is summarized by the formula 
     
         C.sub.k.sub.+1 =  X.sub.k.sub.-1. X.sub.k.sub.-2 +X.sub.k.sub.-1. X.sub.k.sub.-3. X.sub.k.sub.-4 + . . . +  X.sub.k.sub.-1. X.sub.k.sub.-3. X.sub.k.sub.-5 . . . X.sub.1                              (1) 
    
     in the third case (X k  = 1 and X k   -1  = 0), a carry bit for column &#34;k+1&#34; is generated if a carry bit has been generated in columns &#34;k-2&#34; and &#34;k-3&#34; or any of the preceding columns. Thus, 
     
         C.sub.k.sub.+1 =  X.sub.k. .X.sub.k.sub.-2.X.sub.k.sub.-3+ . . . + X.sub.k. X.sub.k.sub.-2. X.sub.k.sub.-4 . . . X.sub.0     (2) 
    
     lastly, in the fourth case (X k  = 1 and X k   -1  = 1), a carry bit is always generated, so that 
     
         C.sub.k.sub.+1 =  X.sub.k. X.sub.k.sub.-1.                 (3) 
    
     Formulas (1), (2) and (3) show that all cases where a carry bit intended for column &#34;k+1&#34; is generated are derived from the general logic formula 
     
         C.sub.k.sub.+1 =  X.sub.k. .X.sub.k.sub.-1 +(X.sub.k-1. X.sub.k.sub.-2 + X.sub.k.sub.-1.X.sub.k.sub.-3. X.sub.k.sub.-4 . . . +  X.sub.k.sub.-1. .X.sub.k.sub.-3. X.sub.k.sub.-5 . . . X.sub.1) + (X.sub.k. X.sub.k.sub.-2.X.sub.k.sub.-3 + . . . +  X.sub.k. X.sub.k.sub.-2. X.sub.k.sub.-4 . . . X.sub.0)                             (4) 
    
     the carry generator of the multiplier device of the present invention can be implemented in various manners depending upon the technology the designer proposes to utilize, but is in no way restricted to the use of a particular technology. It must only be such as to satisfy formula (4) or any equivalent logic formula while allowing the size of the multiplier device and the power consumption to be minimized. 
     FIGS. 1 and 1A illustrate a carry generator implemented, in accordance with the invention, with NOR circuits for an 8-bit work X written X 7  . . . X 3  X 2  X 1  X 0 . The generator includes a first stage comprising 16 NOR circuits N1-N16, and a second stage comprising six NOR circuits N17-N22. The inputs of these NOR circuits are connected to the points shown in the following table: 
     
         ______________________________________Circuit Input Connected to:Circuit Inputs of*       Outputs of______________________________________N1  ##STR1##N2  ##STR2##N3  ##STR3##N4  ##STR4##N5  ##STR5##N6  ##STR6##N7  ##STR7##N8  ##STR8##N9  ##STR9##N10  ##STR10##N11  ##STR11##N12  ##STR12##N13  ##STR13##N14  ##STR14##N15  ##STR15##N16  ##STR16##N17                  N1, N2N18                  N2, N3, N4N19                  N3, N4, N5, N6N20                  N5, N6, N7, N8, N9N21                  N7, N8, N9, N10, N11, N12N22                  N10,N11,N12,N13,N14,N15,N16______________________________________  *the bars above the X&#39;s mean that the inverted logic values of X bits ar used (1= 0,0= 1) 
    
     The outputs from the NOR circuits of the second stage provide the inverted values of the desired carry bits, i.e. C3, C4, C5, C6, C7 and C8. The other bits are obtained more simply since co=., c1= 0 and C2=X1.X0. 
     Accordingly, the multiplier device of the invention can be implemented in accordance with the diagram of FIG. 2. This device includes a carry generator (GR) which is similar to that of FIG. 1 and provides carry bits C3-C8 to a sum generator (GS). Where the arrangement of FIG. 1 is used to determine the carry bits, bit inverters are required for the inputs and the outputs of generator GR. The sum generator supplies S0=X0 directly. Bit S1 is obtained by means of an Exclusive OR Invert circuit XOR1 the inputs of which receive X1 and X0. Bit S2 is supplied by an Exclusive OR Invert circuit XOR2 which receives X2 and the output of an AND circuit A1, which itself receives X0, as inverted by an inverter 1, and X1. Bits S3-S7 are respectively provided by a pair of Exclusive OR Invert circuits XOR3, XOR3&#39; - XOR7, XOR7&#39;. If we call XORp and XORp&#39; the pair of order p, we may say that the inputs of XORp receive Xp and X p   -1  while the inputs of XORp&#39;  receive the carry bit Cp and output from XORp. The bit Sp is obtained at the output of XORp&#39;. If X7 is the sign bit S8 is directly obtained from C8 and bit S9 is directly provided by X7. It will be appreciated that if X7 were not the sign bit S8 would be obtained from X7 exclusive OR C8 and S9 would be X7.C8. 
     The outputs from the NOR circuits of the second stage provide the inverted values of the desired carry bits, i.e. C3, C4, C5, C6, C7 and C8. The other bits are obtained more simply since CO=0, C1=0 and C2=X1.X0. 
     Accordingly, the multiplier device of the invention can be implemented in accordance with the diagram of FIG. 2. This device includes a carry generator (GR) which is similar to that of FIG. 1 and provides carry bits C3-C8 to a sum generator (GS). Where the arrangement of FIG. 1 is used to determine the carry bits, bit inverters are required for the inputs and the outputs of generator GR. The sum generator supplies S0=X0 directly. Bit S1 is obtained by means of an Exclusive OR Invert circuit XOR1 the inputs of which receive X1 and X0. Bit S2 is supplied by an Exclusive OR Invert circuit XOR2 which receives X2 and the output of an AND circuit A1, which itself receives X0, as inverted by an inverter 1, and X1. Bits S3-S7 are respectively provided by a pair of Exclusive OR Invert circuits XOR3, XOR3&#39; - XOR7, XOR7&#39;. If we call XORp and XORp&#39; the pair of order p, we may say that the inputs of XORp receive Xp and X p   -1  while the inputs of XORp&#39;  receive the carry bit Cp and output from XORp. The bit Sp is obtained at the output of XORp&#39;. If X7 is the sign bit S8 is directly obtained from C8 and bit S9 is directly provided by X7. It will be appreciated that if X7 were not the sign bit S8 would be obtained from X7 exclusive OR C8 and S9 would be X7.C8. 
     This architecture of the proposed multiplier device is valid regardless of the number of bits of X but does not necessarily represent the best solution considering the size of the integrated circuit that would be required to implement it. An alternative solution would consist in dividing the adder that performs the operation X+2X into a number of sub-adders. FIG. 3 illustrates a means for processing a 16-bit word X as two words of eight bits each. The lower-order bits (2 0  to 2 7 ) are processed in a first adder ADD1 and the higher-order bits (2 8  to 2 15 ) in a second adder ADD2. Both of these adders use the technique described earlier and are identical with the adder of FIG. 2 except that in ADD1 X7 is not the sign bit so that, as mentioned previously, S8 would be provided by X7 exclusive OR C8 and S9 would be X7.C8. ADD1 provides bits S0-S7 of the result as well as two bits of weights 2 8  and 2 9  which will be added to the two lowest-order bits supplied by ADD2. Bits 2 8  and 2 9  may be regarded as carries which must be allowed to propagate through the bits of ADD2. A circuit designated PROPAG is provided for this purpose. Assuming that the sum bits supplied by ADD2 are designated A0-A9, the PROPAG circuit must in effect add bits S8&#39;-S9&#39; of ADD1 to the word comprised of bits A0-A9 to finally provide bits S8-S17 of 3X. 
     Referring now to FIG. 4, bit S8 is obtained by means of a simple Exclusive OR Invert circuit 0 which receives as inputs S8&#39; and A0. However, the combination of these inputs will also yield a carry bit if they both have a logical 1 value. This carry bit is therefore obtained by means of an AND circuit, the output of which is fed to the carry input of a full-adder stage FA. The latter, which also receives as input S9&#39; and A1, provides bit S9 and a carry bit C02 which must be allowed to propagate through bits A2-A9. This is done using the carry lookahead technique. A carry generator such as that shown in FIG. 5 is therefore required. This generator is comprised of seven NOR circuits designated N23-N29 which generate carry bits C&#39;3-C&#39;9. The bits shown in the right-hand column of the following table are applied to the respective inputs of N23-N29. 
     
         ______________________________________N23 ##STR17##N24 ##STR18##N25 ##STR19##N26 ##STR20##N27 ##STR21##N28 ##STR22##N29 ##STR23##______________________________________ 
    
     bits S10-S17 are obtained by Exclusive OR&#39;ing bits C02, C&#39;3, C&#39;4, . . . , C&#39;9 and A2, A3, A4, . . . , A9, respectively. Bit S18 is obtained by AND&#39;ing C&#39;9 and A9. 
     While the invention has been particularly shown and described with reference to preferred embodiments thereof, it will be understood by those skilled in the art that the foregoing and other changes in form and detail may be made therein without departing from the spirit and scope of the invention.