There are other uses for 3× function; typically it is used in the Partial Product Generator (PPG) for Radix-8 Booth multipliers. For performing a radix-8 Booth Multiplication, one of the input terms that the partial product generator needs is 3 times the value of the multiplicand or 3× of the multiplicand. Other terms needed by the PPG are 0, ±1×, ±2×, ±4×, but these can be generated very easily.
Although 0, ±1×, ±2×, ±3×, ±4× values of the multiplicand are needed by the PPG, only the positive values need to be created, i.e. only 1×, 2×, 3×, 4×s are needed. To create the negative values, the corresponding positive value is inverted and +1 is added to it in the later stages of the compressor tree. The 3× term generation needs some extra logic. Typically, as shown in FIG. 1 depicting a flowchart of a current 3× generation method 10 using a prior art multiplier circuit, this 3× term is generated by adding 2× of the multiplicand together with itself.
That is, in the prior art method 10, to evaluate an expression out=3*in, at 12, the method implements an adder using a Parallel Prefix addition algorithm, to add 2× the “in” multiplicand with itself to produce 3× value as indicated at 20. However, first, at 15, the 2× of the multiplicand is easily obtained by shifting the input multiplicand bits left by 1 bit position (i.e., in<<1) to produce a binary multiplication of the input by 2 using a 1-bit fixed amount shifter circuit. Thus, to evaluate the product out=3*in, i.e., obtain the multiplication of 3*in at 25, the 2*in result from the 1-bit shifter is added together with the in multiplicand using a 2-input full adder circuit. Thus the 3× partial product output is: 3× multiplicand={multiplicand<<1}+multiplicand and is available for use in the next step in the radix-8 multiplication.
FIG. 2 is a block diagram illustrating a radix-8 multiplication system 50 according to the prior art. In this embodiment, a register file 52 contains 128 n-bit wide integer words. Under the control circuitry 60 through control line 66 an integer word is loaded into the n-bit multiplicand operand latch 70. Likewise, the contents of the multiplier operand latch 65 are also loaded. The contents of the multiplier operand latch 70 are provided to a shifter 72 with a fixed shift amount of 1-bit left shift and a padding block 75 to add a bit “0” in front of the most significant bit of the output of the operand latch 70. As a result of the shifting and padding operations performed by shifter 72 and padding block 75, their corresponding outputs 76 and 78 are now n+1 bit wide data buses. For example, given a 16 bit input multiplicand, processing results in seventeen bits where the Pad 0 on MSB {1′b0,in} is such that the input is padded with a zero (bit) on the MSB side which does not change the value of the number. To multiply by two, Pad 0 on the LSB so that the input is padded with a zero on the LSB side {in, 1′b0} such that it equals 2*in.
The 2-input n+1 bit full adder 80 receives the outputs 76 and 78 from the shifter 72 and padding block 75 respectively. The full adder 80 produces the sum of the two n+1 bit input buses 76 and 78 and produces an n+1 bit sum. This sum from adder 80 is input into the radix-8 multiplier circuit 90. The radix-8 multiplier 90 also receives the contents of the multiplier operand latch 65. The radix-8 multiplier 90 performs multiplication and produces a 2*n-bit result on data bus 62. This output 62 is provided back to the register file 52 for a next operation.
But creating a 3× of the multiplicand in this way introduces a 2-input full adder whose 2 inputs are: 2× multiplicand and the multiplicand itself. Unfortunately, use of a full adder in implementing 3× is not an optimal design. For example, use of this adder, or any type of adder, e.g., a Sklansky adder, that produces the 3×=2×+1×, this calculation becomes a critical timing path.
It is desirable to speed up the 3× term generation, because the earlier it is available, the sooner the multiplication can start. The delay incurred in generating the 3× term is also dependent upon the size of the multiplicand. The 3× generation for a 64-bit multiplicand will take longer than a 32-bit multiplicand. Basically, current devices are limited by the speed of the adder. For a parallel prefix adder, such as the Sklansky adder 85 shown in FIG. 3, the delay increases as log2 (width (in bits 87) of multiplicand), i.e. delay ˜O(log2 n) with multiplicand[n−1:0]. Typically, in the prior art, the adder used is a general purpose adder 85, i.e., if this adder circuitry were to be detached from the multiplier, it can still work standalone as an adder.
Typically, the full Adder such as the Sklansky adder 85 conceptually shown in FIG. 3, has following levels of logic (assuming a 16-bit multiplicand): a first level of Propagate/Generate logic 82; an amount (log2 n)−1 levels 84 of carry tree at which a carry look-ahead is performed to predict what the carry will look like; a third level of buffering 86 for a final multiplexer; and, a final level of logic 88 for final multiplexing. Thus, a total levels of logic for increment operation=3+(log2 n)−1=2+log2 n, where “n” is the width (in bits) of the multiplicand. The amount of levels is determined by the number of bits of the multiplicand. FIG. 3 also shows the critical path 92 in which processing at the four (4) logic levels occur for a 16-bit multiplicand. The amount of logic levels will increase as dependent upon the number of multiplicand bits.
FIG. 3 further shows the adder's known propagate and generate cell block 95 employed along the critical path, that includes respective logic circuits 91, 93 for providing respective Generate and Propagate values at each level with “k” representing the level, e.g., Gk, k=1 is the first level generate. The numbers in the parenthesis [ ] represent the bit numbers, e.g., Gk[1], Gk[2], for i=0, 1, . . . , n−1. As known, the Generate represents AND functionality where a carry is always generated, and Propagate represents an OR functionality where a carry propagated from previous stage would be propagated to next stage. For example, in FIG. 3, the iG5 Generate term is the carry that is highlighted as the critical path 92.
In the typical n-bit adder, such as the 3×-Generation Adder according to the prior art depiction shown in FIG. 7A employing a parallel prefix adder carry tree 400, where n=16, as the adder receives two n-bit inputs a[n−1:0], b[n−1:0] and results in a sum=a[n−1:0]+b[n−1:0]. For such an adder, the internal carry tree 400 providing iG1[i], G2[i], iG3[i], iP1[i], P2[i], iP3[i] are expressed in terms inputs a[i], b[i] where “i” is each bit.
For example:
                    iG        ⁢                                  ⁢                  1          ⁡                      [            i            ]                              =              !                              (                                          a                ⁡                                  [                  i                  ]                                            &&                              b                ⁡                                  [                  i                  ]                                                      )                    ⁢                      :                    ⁢                                          ⁢          These          ⁢                                          ⁢          are          ⁢                                          ⁢          the          ⁢                                          ⁢          internal          ⁢                                          ⁢          inverted          ⁢                                          ⁢          Generate          ⁢                                          ⁢          terms                      ;                      iP        ⁢                                  ⁢                  1          ⁡                      [            i            ]                              =              !                              (                                          a                ⁡                                  [                  i                  ]                                            ⁢                                                                          ⁢                              b                ⁡                                  [                  i                  ]                                                      )                    ⁢                      :                    ⁢                                          ⁢          These          ⁢                                          ⁢          are          ⁢                                          ⁢          the          ⁢                                          ⁢          internal          ⁢                                          ⁢          inverted          ⁢                                          ⁢          Propagate          ⁢                                          ⁢          terms                      ;              G      ⁢                          ⁢              2        ⁡                  [          i          ]                      =                  !                  (                                    (                              iG                ⁢                                                                  ⁢                                  1                  ⁡                                      [                    i                    ]                                                  ⁢                                                                                    ⁢                iP                ⁢                                                                  ⁢                                  1                  ⁡                                      [                                          i                      +                      1                                        ]                                                              )                        &&                          iG              ⁢                                                          ⁢                              1                ⁡                                  [                                      i                    +                    1                                    ]                                                              )                    =              !                  (                                                    (                                  !                                                            (                                                                        a                          ⁡                                                      [                            i                            ]                                                                          &&                                                  b                          ⁡                                                      [                            i                            ]                                                                                              )                                        ⁢                                                                                                                                      !                                        ⁢                                          (                                                                        a                          ⁡                                                      [                                                          i                              +                              1                                                        ]                                                                          ⁢                                                                                                                            ⁢                                                  b                          ⁡                                                      [                                                          i                              +                              1                                                        ]                                                                                              )                                                                      )                            &&                              (                                  !                                      (                                                                  a                        ⁡                                                  [                                                      i                            +                            1                                                    ]                                                                    &&                                              b                        ⁡                                                  [                                                      i                            +                            1                                                    ]                                                                                      )                                                  )                                      ;                                          and                ⁢                                                                  ⁢                P                ⁢                                                                  ⁢                                  2                  ⁡                                      [                    i                    ]                                                              =                                                !                                      (                                                                  (                                                  iP                          ⁢                                                                                                          ⁢                                                      1                            ⁡                                                          [                              i                              ]                                                                                ⁢                                                                                                                                      ⁢                                                      iP                            ⁢                                                                                                                  [                                                          i                              +                              1                                                        ]                                                                          )                                            &&                                              iG                        ⁢                                                                                                  ⁢                                                  1                          ⁡                                                      [                                                          i                              +                              1                                                        ]                                                                                                                )                                                  =                                  !                                      (                                                                                            (                                                      !                                                                                          (                                                                                                      a                                    ⁡                                                                          [                                      i                                      ]                                                                                                        ⁢                                                                                                                                                                              ⁢                                                                      b                                    ⁡                                                                          [                                      i                                      ]                                                                                                                                      )                                                            ⁢                                                                                                                                                                                                  !                                                            ⁢                                                              (                                                                                                      a                                    ⁡                                                                          [                                                                              i                                        +                                        1                                                                            ]                                                                                                        ⁢                                                                                                                                                                              ⁢                                                                      b                                    ⁡                                                                          [                                                                              i                                        +                                        1                                                                            ]                                                                                                                                      )                                                                                                              )                                                &&                                                  (                                                      !                                                          (                                                                                                a                                  ⁡                                                                      [                                                                          i                                      +                                      1                                                                        ]                                                                                                  &&                                                                  b                                  ⁡                                                                      [                                                                          i                                      +                                      1                                                                        ]                                                                                                                              )                                                                                )                                                                    ;                                                                                                              where the “i” in front of iG1 represents an INVERT, ! represents a logic INVERT operation, && represents an AND logic operation and ∥ represents an OR logic operation.
In FIG. 7A, first level AND and OR gate processing 405 provides first level Generate terms iG1[ ] and first level Propagate terms iP1[ ] based on the two received inputs a[ ] and b[ ] (processing shows only first 4 bits being processed). The first level Generate terms iG1[ ] and first level Propagate terms iP1[ ] proceed as inputs to the next level of the carry tree where second level AND and OR gate processing 410 provides second level Generate terms G2[ ] and second level Propagate terms P2[ ] associated with the G2[i] and P2[i] calculations above. The process continues through third level processing 415 and fourth level processing 420 until final level Generate terms G4[ ] and Propagate terms P4[ ] are output.
By using this full adder in partial product generation, the prior art also exhibits increased area, power and wiring resources. Overall, the use of a 2-input full adder in the prior art does not result in an optimized implementation.
USPTO Backgrounds
USPTO Backgrounds