When is the second iteration at BITS

EP0825523A1 - Method and circuit for multiplying a multiplicand and a multiplier according to the Booth method in iterative steps - Google Patents

Method and circuit for multiplying a multiplicand and a multiplier according to the Booth method in iterative steps Download PDF

info

Publication number
EP0825523A1
EP0825523A1EP97111341AEP97111341AEP0825523A1EP 0825523 A1EP0825523 A1EP 0825523A1EP 97111341 AEP97111341 AEP 97111341AEP 97111341 AEP97111341 AEP 97111341AEP 0825523 A1EP0825523 A1
Authority
EP
European Patent Office
Prior art keywords
multiplier
multiplicand
bits
result
partial
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
EP97111341A
Other languages
English (en)
French (fr)
Other versions
EP0825523B1 (de
Inventor
Ulrich Dr. Little ones
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Infineon Technologies AG
Original assignee
Siemens AG
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Family has litigation
Priority to DE19632246ApriorityCriticalpatent / DE19632246C1 / de
Priority to DE19632246priority
Application filed by Siemens AGfiledCriticalSiemens AG
Publication of EP0825523A1publicationCriticalpatent / EP0825523A1 / de
Application granted granted Critical
Publication of EP0825523B1publicationCriticalpatent / EP0825523B1 / de
First worldwide family litigation filedlitigationCriticalhttps: //patents.darts-ip.com/? Family = 7802278 & utm_source = google_patent & utm_medium = platform_link & utm_campaign = public_patent_search & patent = EP0825523 (A1) "Global patent litigation dataset" by Darts-ip is licensed under Creative 4.0 License.
Anticipated expirationlegal-statusCritical
Expired - Lifetimelegal-statusCriticalCurrent

Left

  • 238000009825accumulationMethods0.000claimsdescription8
  • 101710088044SHE3Proteins0.000claimsdescription7
  • 230000001419dependentEffects0.000claimsdescription2
  • RXRGZNYSEHTMHC-RNFRBKRXSA-N4-amino-1 - [(2R, 4R) -2- (hydroxymethyl) -1,3-dioxolan-4-yl] pyrimidin-2-oneChemical compoundO = C1N = C (N) C = CN1 [ C @@ H] 1O [C @ H] (CO) OC1RXRGZNYSEHTMHC-RNFRBKRXSA-N0.000claims1
  • 239000001981lauryl tryptose brothSubstances0.000claims1
  • 238000010586diagramsMethods0.000description7
  • 230000000875correspondingEffects0.000description5
  • 101710007782MYO4Proteins0.000description2
  • 101710088029SHE1Proteins0.000description2
  • 101710088041SHE2Proteins0.000description2
  • 230000000295complementEffects0.000description2
  • 281999990866 International Society for Computer Aided Surgerycompanies0.000description1
  • 238000004364calculation methodsMethods0.000description1
  • 230000018109developmental processEffects0.000description1
  • 239000000284extractsSubstances0.000description1
  • 239000000203mixturesSubstances0.000description1
  • 230000002441reversibleEffects0.000description1
  • 238000001356 surgical procedureMethods0.000description1

Images

Classifications

    • G — PHYSICS
    • G06-COMPUTING; CALCULATING; COUNTING
    • G06F — ELECTRIC DIGITAL DATA PROCESSING
    • G06F7 / 00 — Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7 / 38 — Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
    • G06F7 / 48 — Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
    • G06F7 / 52-Multiplying; Dividing
    • G06F7 / 523 — Multiplying only
    • G06F7 / 533 — Reduction of the number of iteration steps or stages, e.g. using the Booth algorithm, log-sum, odd-even
    • G06F7 / 5334 — Reduction of the number of iteration steps or stages, e.g. using the Booth algorithm, log-sum, odd-even by using multiple bit scanning, i.e. by decoding groups of successive multiplier bits in order to select an appropriate precalculated multiple of the multiplicand as a partial product
    • G06F7 / 5336 — Reduction of the number of iteration steps or stages, e.g. using the Booth algorithm, log-sum, odd-even by using multiple bit scanning, i.e. by decoding groups of successive multiplier bits in order to select an appropriate precalculated multiple of the multiplicand as a partial product overlapped, i.e. with successive bitgroups sharing one or more bits being recoded into signed digit representation, e.g. using the Modified Booth Algorithm
    • G06F7 / 5338 — Reduction of the number of iteration steps or stages, e.g. using the Booth algorithm, log-sum, odd-even by using multiple bit scanning, i.e. by decoding groups of successive multiplier bits in order to select an appropriate precalculated multiple of the multiplicand as a partial product overlapped, i.e. with successive bitgroups sharing one or more bits being recoded into signed digit representation, e.g. using the Modified Booth Algorithm each bitgroup having two new bits, e.g. 2nd order MBA

Abstract

Description

From US Pat. No. 5,457,804 a multiplication circuit is known in which the multiplication time for multiplications with double precision is shortened, either a more significant half or a less significant half of an input word of the multiplication circuit being fed to a conventional Booth decoder via a multiplexer.
There are numerous algorithms for the accelerated calculation of a multiplication. In the classic Booth algorithm, two bits of the multiplier are always considered at the same time and a factor is formed from this, with which the multiplicand is multiplied, and this product is added to the partial product in each case. This method works with n-uniform shift operations by one bit position to the right (division by 2) and n / 2 additions, where n is the word length of the multiplier. No sign corrections are required for two's complement representations.
A faster modified method has been proposed in [1], [2]. With this method, three bits of the multiplier are considered simultaneously, which are decoded into 5 different factors (0; + -1; + -2; see table 1). For this algorithm only n / 2 shift operations by two bit positions to the right (division by 4) and n / 2 additions are required. With both of the methods mentioned, decoding can be started either with the LSB (Least Significant Bit) or with the MSB (Most Significant Bit); special handling of the signs is not necessary. Decoding starting with the LSB has the advantage [3] that the word length of the product is limited to the word length of the multiplicand by using the Horn scheme. The result obtained in this way agrees with the first m-bits of the exact n + n-bit wide product. The modified Booth algorithm is described in somewhat more detail below, since it serves as the starting point for the invention.
The multiplier Y and the multiplicand X are given by their two's complement representation. with yi ∈ {0,1}, for i = 0, 1, 2, ..., n-1 and xj ∈ {0,1},
for j = 0, 1, 2, ..., m-1
By combining two successive summation steps, the multiplier Y in can be calculated for i = 1, 3, 5, ..., n-1 and yn = 0
be reshaped.
The product of the multiplication P is thus obtained with the multiplicant X for i = 1, 3, 5, ..., n-1, with yn = 0
and with for i = 1, 3, 5, ..., n-1
In Fig. 1, the basic processing of the multiplier X with the modified Booth decoder is shown. Starting at the LSB side, three bits are always decoded at the same time and then the decoding window is shifted two bit positions to the left. The bit yn is set to 0, and if the word length n is odd, an additional bit is generated by doubling the multiplier MSB's. The corresponding decoding table can be found in Table 1. This does not have to be explained further because it results from [3].
Control signals, namely the factor signal C and the shift signal K, are generated in accordance with the coding rules in Table 10 and the sign signal Si. The control signals control the specific sequence of the individual multiplication cycles. 2 shows a block diagram of a typical Booth multiplier architecture. At the beginning of a multiplication, the multiplicand X is first loaded into the register REGX and the accumulation register ACCU is set to 0 and initialized. According to the value of the multiplier Y and the corresponding result of the Booth decoding according to Table 1, the individual partial products are generated in n / 2 steps according to Equation 6. To do this, the multiplicand X must be multiplied by 0, 1 or 2 in each iteration. The sliding unit SHE1 is used for this in FIG. 2. The multiplication by the factor 2 means that a left shift operation of the multiplicand by one bit position must be carried out. The partial product PP is calculated in each iteration with the aid of a shift unit SHE2, which divides the partial product of the previous iteration by 4 (shift to the right by two bit positions). After n / 2 iterations, the product is available in the ACCU accumulation register. It should be noted that the multiplicand X must have a doubled MSB so that no overflow can occur during the execution of the additions or subtractions. With the aid of the multiplier according to FIG. 2, the equations given in Table 1 under the heading "Operation" are thus implemented. The factor signal C is used to let the multiplicand X through to the shift unit SHE1 or to set it to 0. Such an operation is required according to the first and last lines of Table 1. A multiplication by 2 is required for the multiplicand X according to Table 1 in the 4th and 5th lines. The addition or subtraction takes place in an arithmetic logic unit ALU as a function of the sign signal S.i. The last column of Table 1 shows when the multiplicand X to the previous partial product PPi + 2 must be added or subtracted. The partial product PPi + 2 is in the accumulation register ACCU and is multiplied by 0.25 in the shift unit SHE2 and then to form the next partial product PPi fed back to the ALU. The assignment of the multiplier bits yi-1, yi, yi + 1 Table 1 shows the individual operations.
The aim of the invention is to modify the Booth algorithm explained above in order to achieve a simplification of the multiplier. This goal is achieved according to the features of claim 1.
A further object is to provide a Booth multiplier which works according to the modified Booth algorithm.
Finally, the object is to provide a decoding circuit with which the control signals for the multiplier are generated.
Developments of the invention emerge from the dependent claims.
Fig. 1
the decoding window of the multiplier according to the known methods,
Fig. 2
the well-known Booth multiplier,
Fig. 3
a block diagram of the modified Booth multiplier,
Fig. 4
the decoding window of the multiplier according to the modified Booth algorithm,
Fig. 5
a block diagram of the Booth decoding circuit,
Fig. 6
a realization of the Booth decoder.
The block diagram according to FIG. 3 shows, in comparison to the block diagram of FIG. 2, that there is no longer a shift unit SHE in the left branch of the ALU. In this left branch only a multiplication by 0 or 1 and a sign reversal is carried out. For this, however, a variable right shift operation is carried out in the accumulator loop (right ALU branch). The rest of the structure of the multiplier according to FIG. 3 corresponds to that of the multiplier according to FIG. 2.
The multiplicand X is stored in the REGX register. This is either let through or set to 0 via the MULT unit, which is controlled by the factor signal C. For this purpose, the factor signal C is generated from the multiplier signal Y in a circuit C-ERZ in accordance with the operations in Table 1. The multiplier Y also becomes that
Sign signal Si generated in the circuit S-ERZ. The shift of the partial product is carried out in the shift unit SHE3, a multiplication by 1/2, 1/4 or 1/8 being carried out by shifting to the right, depending on the operations to be carried out.
A possible coding of the multiplier Y is given in Table 2. As can be seen from Table 2, an expansion of the decoding size to 5 bits is necessary, as is also described in [3]. The sign signal Si indicates whether the multiplicand adds X (pi= 0) or subtracted (pi= 1), the factor signal C indicates the factor with which the multiplicand X is weighted (C = 1 multiplication by 1, C = 0 multiplication by 0), and the control signals K.1 (Shift right operation by one bit position if K1= 1) and K2 (Shift right operation by two bit positions if K2= 1) define the slide vector for the slide unit SHE3. The value of the control signals K1 and K2 and the multiplication of the shift unit SHE3 to be carried out accordingly can also be taken from table 3. As in the previous algorithm, the bit yi represents the current position. The bits yn, yn + 1 and yn + 2 are initially set to 0 (see FIG. 4) and if the word length n is odd, an additional bit is generated by doubling the multiplier MSB's.
The multiplication proceeds similarly to the modified Booth algorithm with a constant shift vector (FIG. 2). First, the multiplicand is loaded into the REGX register and the ACCU accumulation register is initialized. Starting at the LSB side, the 5-bit wide decoding window is placed over the two least significant bits of the multiplier Y (see FIG. 4) and shifted to the left by 2 bit positions after each iteration. The result of the decoding determines the actual execution of the operations during an iteration. The partial product PPi is calculated with the help of the variable shift unit SHE3, which allows shifts to the right by 1, 2 or 3 bit positions. After n / 2 iterations, the product is available in the ACCU accumulation register. So that no overflow can occur during the execution of the additions or subtractions, the multiplicand X must have a doubled MSB.
The correctness of Table 2 can be checked using Table 1. With the logical link H1 it is detected whether a multiplication by 2 has to be carried out in the original coding according to Table 1, and with the corresponding logical link H2 it is detected whether a multiplication by 2 was carried out in the previous cycle. With the multiplier according to FIG. 3, a multiplication by 2 is implemented by an additional right shift operation of the partial product by one bit position. The partial product then no longer has to be shifted to the right by 2, but by only one bit position in the next iteration. The operations described can be carried out with the logical functions H.1 and H2 can be detected. The control signals K1 and K2 for the sliding unit SH3 can be determined as follows:
Since the sign of the multiplicand Y is doubled (y0= y1), the condition is H1 never fulfilled in the last iteration, and no additional cycle is necessary for a further shift operation, so that n / 2 shift operations and n / 2 additions or subtractions are also necessary for the modified Booth algorithm with variable shift vectors.
The control signals Si and C can be generated as follows:
Table 2 shows the 5 bits of the multiplier Y, which are detected by the decoding window, as well as the factor signal C and the sign signal S, as well as the results of the H operations1 and H2 or K1 and K2. The control signals K1 and K2 are framed when the control signal K2 is binary 1. Table 3 extracts the different cases from Table 2 and indicates which multiplication is to be carried out in the shift unit SHE3. If both the control signal K1 as well as K2 is binary 1, then it is multiplied by 1/8 by three shift operations to the right.
When the control signal K1 is binary 1 and the control signal K2 binary 0, then only a shift operation or a multiplication by 1/2 takes place. If the control signal is K1 binary 0 and the control signal K2 binary 1, then two shift operations or a multiplication by 1/4 take place.
5 shows the block diagram of the Booth decoding circuit DEKOY with a variable shift vector. The multiplier Y is stored in an n-bit wide latch LA with the aid of the transfer signal Ü. The decoding window function is formed with the aid of 5 multiplexers MUX1 to MUX5, each with 8 inputs.The inputs are selected one after the other via the control lines S1 to S8. The control signals S are generated from the 5 bits of the current decoding window with the aid of the actual Booth decoder B-DOCi, C, K1 and K2 generated according to equations 7 to 12.
6 shows the block diagram of the Booth decoder B-DOC. Since the logical functions H1 and H2 are identical, they can, as shown in FIG. 6, be combined into a function by storing the results from the previous cycle. The result of the function H1 is stored in the register REG with the transfer signal CL and corresponds to the result of the function H in the next clock period2. At the beginning of Booth decoding, the register content must be set to logic 0. Since the function H2 the only one that got the signals yi + 2 and yi + 3 required, the multiplexers MUX1 and MUX2 in FIG. 5 can be dispensed with.
The individual circuits of FIG. 6 are illustrated by the symbols corresponding to those of equations 7-12. Corresponding circuits are known in the literature.
  • [1] O. L. MacSorley, High-Speed ​​arithmetic in binary computers, Proc. IRE, Vol. 49, pp. 67-91, 1961
  • [2] L. P. Rubinfield, A Proof of the Modified Booth's Algorithm for Multiplication, IEEE Trans. Computers, pp. 1014-1015, October 1975
  • [3] A. Stölzle, A. Rainer and W. Ulbrich, Parallel-Serial Multiplication Using Booth's Algorithm and Horner Scheme, Proc. ISCAS'85, pp. 1389-1390, May 1985
  • Claims (6)

    1. Method for a multiplication circuit for multiplying a multiplicand (X) and a multiplier (Y) according to the Booth method in iterative steps,
      in which, starting with the LSB, three multiplier bits (yi-1, yi, yi + 1; i = 1, 2 ...) and iteratively, depending on the decoding result, a partial product (PPi) from the previous partial product (PPi + 2) and the multiplicand, where the partial product (PPi + 2) is set to 0 at the beginning,
      in which the decoding window is then shifted two bits to the left in the next iteration using the multiplier (Y),
      in which the multiplicand is multiplied by 0 or 1 to obtain a first intermediate result as a function of a factor signal (C) obtained from the bits to be decoded,
      in which the first intermediate result and one from the partial product (PPi + 2) the second intermediate result obtained from the previous iteration is added or subtracted as a function of a sign signal (S) obtained from the bits to be decoded,
      in the case of the control signals (K1, K2) the partial product (PPi + 2) of the previous iteration is multiplied by 1/2, 1/4, or 1/8, where
      a multiplication by 1/4 takes place if the decoding result of the current iteration shows that the multiplicand (X) is in simple form with the previous partial product (PPi + 2) is linked,
      a multiplication by 1/8 takes place if the decoding result of the current iteration shows that the multiplicand is linked in 2-fold form with the previous partial product,
      a multiplication by 1/2 takes place if the decoding result of the previous iteration shows that the multiplicand was to be linked in 2-fold form.
    2. Method according to claim 1,
      in which the sign signal (S) according to the formula
      is won.
    3. Method according to claim 1 or 2,
      where the factor signal (C) according to the formula
      is won.
    4. Method according to one of the preceding claims,
      in which the control signals (K1, K2) is obtained from the following formulas:
      e
    5. Multiplier circuit for carrying out the method according to one of the preceding claims,
      in which a multiplicand register (REGX) is provided which stores the multiplicand (X),
      in which a multiplier (MULT) is provided at the output of the multiplicand register which, depending on the factor signal (C), multiplies the multiplicand by 0 or 1,
      in which an arithmetic logic unit (ALU) is provided which, depending on the sign signal (S), adds or subtracts the result given at the output of the multiplier (MULT) to the second intermediate result present at the other input,
      in which an accumulation register is arranged at the output of the ALU,
      In which a shift unit (SHE3) is provided at the output of the accumulation register, with which the content of the accumulation register is multiplied by 1/2, 1/4 or 1/8 depending on the control signals (K) to generate the second intermediate result,
      and in which the output of the shift unit (SHE3) is connected to the ALU.
    6. Multiplier circuit according to Claim 5,
      in which a decoding circuit is provided for generating the control signals (K) of the factor signal (C) and the sign signal (S),
      with a latch memory (LA) for storing the multiplier (Y),
      with multiplexers (MUX) connected to the output of the latch memory, which select the bits of the decoding window from the multiplier bits at the output,
      with a decoder (D-DOC), which generates the control signals (K, S, C) from the bits of the decoding window.
    EP97111341A1996-08-091997-07-04 Method and circuit for multiplying a multiplicand and a multiplier according to the Booth method in iterative steps Expired - LifetimeEP0825523B1 (de)

    Priority Applications (2)

    Application NumberPriority DateFiling dateTitle
    DE19632246ADE19632246C1 (de) 1996-08-091996-08-09Method for a multiplication circuit for multiplying a multiplicand and a multiplier according to the Booth method in iterative steps
    DE196322461996-08-09

    Publications (2)

    ID = 7802278

    Family Applications (1)

    Application NumberTitlePriority DateFiling date
    EP97111341AExpired - LifetimeEP0825523B1 (de) 1996-08-091997-07-04Method and circuit for multiplying a multiplicand and a multiplier according to the Booth method in iterative steps

    Country Status (3)

    Families Citing this family (3)

    Publication numberPriority datePublication dateAssigneeTitle
    US6684236B1 (en) *2000-02-152004-01-27Conexant Systems, Inc.System of and method for efficiently performing computations through extended booth encoding of the operands
    US20030088407A1 (en) *2001-04-022003-05-08Yi HuCodec
    US8082699B1 (en) *2009-01-222011-12-27Kychelhahn Jerry AModular structure

    Citations (1)

    Publication numberPriority datePublication dateAssigneeTitle
    EP0144568A2 (de) *1983-09-291985-06-19Siemens AktiengesellschaftMultiplier and procedure for its operation

    Family Cites Families (4)

    Publication numberPriority datePublication dateAssigneeTitle
    JPH0831025B2 (yes) *1986-03-291996-03-27株式会社 東芝乗 算 回路
    JP2597736B2 (yes) *1990-07-171997-04-09株式会社 東芝高速 乗 算 器
    US5220525A (en) *1991-11-041993-06-15Motorola, Inc.Recoded iterative multiplier
    JPH0612229A (yes) *1992-06-101994-01-21Nec Corp乗 累 算 回路