Multiplier (digital technology)

from Wikipedia, the free encyclopedia

In digital technology, a multiplier is an electrical circuit that uses the mathematical operation of multiplication to determine the product of two or more digital numbers . In processors, the multiplier is part of the arithmetic-logic unit (ALU) and occurs there as a multiplication accumulator (MAC), but can also be implemented as an independent functional unit in programmable digital circuits such as FPGAs .

In addition to the addition , which is implemented in digital circuits with less circuitry complexity in the form of adders , a fast, hardware-based multiplication is essential, especially in the field of digital signal processing . The multiplier is therefore used in signal processing such as image processing or in the field of digital filters . But it is also used in digital control technology . One of the first areas of application was digital signal processors (DSP).

species

Multiplier 16x16 = 32 bit

Multipliers are differentiated based on the number formats processed:

The effort is essentially determined by the number of bits to be multiplied (increases quadratically). Floating point multipliers need some additional logic:

  • An adder for the exponents that can work in parallel
  • An XOR gate for the sign
  • Treatment of the loss of the MSB (highest bit, most significant bit) after multiplication: decrement and shift.
  • Treatment for NANs and INFs at the entrance or for overflow and underflow.

When using parallel multipliers in modern CPUs and graphics cards, the main effort (double: approx. 97 percent, float: approx. 92 percent) lies in the multiplier network.

Fixed point multiplier

Parallel multiplier for 4 bits. = Summands = carry output = input enable


The binary multiplication is analogous to that in the decimal system and can be implemented in digital circuits as a sequence of additions and shift operations. The adjacent circuit shows an unsigned, parallel multiplier (MAC) for two four-bit numbers X and Y and the addend K with full adders. The eight output bits P are formed in the combinational logic with the following equation:

The process of multiplication is designed according to the following scheme, the four input bits K are set to 0 for the sake of simplicity: 

      1011   (X, entspricht dezimal der Zahl 11)
    · 1110   (Y, entspricht dezimal der Zahl 14)
    ------
 +    0000   (1011 · 0)
 +   1011    (1011 · 1, um eine Stelle nach links verschoben)
 +  1011     (1011 · 1, um zwei Stellen nach links verschoben)
 + 1011      (1011 · 1, um drei Stellen nach links verschoben)
 ---------
  10011010   (P, entspricht dezimal 154)

This simple multiplier can be implemented from individual full adders and the shift operation through direct interconnection. The binary digits of the product P are equal to the sum of digits of the two factors X and Y . A decimal point fixed in the position is generally not mapped in the circuit, but the position of the decimal point in the product results from the sum of the places after the decimal point of the two input factors. In the example above, the number of digits after the decimal point is zero for both factors, which means that the decimal point is to the right of the last digit in the product.

In the case of signed numbers, which are usually represented as two's complement in digital circuits , a corresponding circuit extension of the multiplier is necessary. The correctly signed multiplication of two four-digit binary numbers is designed according to the following scheme, whereby it should be noted that the last line must be subtracted due to the negative factor: 

       1001   (entspricht dezimal der Zahl -7)
     · 1101   (entspricht dezimal der Zahl -3)
     ------
 + 11111001   (1001 · 1, mit Vorzeichenerweiterung)
 + 0000000    (1001 · 0, um eine Stelle nach links verschoben und mit Vorzeichenerweiterung)
 + 111001     (1001 · 1, um zwei Stellen nach links verschoben und mit Vorzeichenerweiterung)
 - 11001      (1001 · 1, um drei Stellen nach links verschoben und mit Vorzeichenerweiterung)
 ----------
   00010101   (entspricht dezimal +21)

In terms of circuitry, the subtraction in the last line can be implemented using extended full adders, which, in addition to addition, can also handle subtraction.

The parallel multiplier, in which the computing speed only depends on the maximum gate delay , is, however, expensive to implement for larger bit widths. Another method is the serial multiplier, in which one bit (one digit) of the result is calculated per cycle at the expense of throughput with less hardware outlay. Furthermore, there are methods based on tables with values ​​that have already been calculated in advance (English look-up tables ). There are also efficient algorithms with which fast multipliers can be implemented with moderate circuitry complexity. Examples are the Wallace tree multiplier or the Booth algorithm .

Floating point multiplier

Any floating point number x is formed from the sign bit s (± 1), the mantissa m and an exponent e , with an arbitrarily chosen and fixed base b :

The IEEE 754 standard for the representation of floating point numbers, which is common in computer technology, uses a base b  = 2 and mantissas and exponents of different widths, depending on the required resolution.

The multiplication of two floating point numbers can always be reduced to a multiplication of the two mantissas and an addition of the two exponents with fixed point arithmetic. The addition and multiplication can be done in parallel with separate circuit parts for speed reasons. The individual steps

  • Splitting the factors into signs, exponents and mantissas. The leading 1 for normalized mantissas (exponent> 1) and the leading zero for denormalized mantissas (mantissa = 0) must be added.

The following steps can be carried out in parallel:

  • Multiplication of the mantissas: M = M 1 × M 2
  • Addition of the exponents: E = E 1 + E 2 - bias
  • Xor operation of the signs: S = S 1 + S 2

Now follows:

  • Determination of the MSBs that are 0. In the case of normalized factors this can be 0 or 1, in the case of denormalized factors larger numbers are possible (double to 106): L

Case distinction:

  • If E - L ≤ −24 or −53, the result is zero. The sign is retained, however.
  • If E - L ≤ 0, the result is a denormalized number.
  • If 0 <E - L <MaxBias, the result is a normalized number.
  • If MaxBias ≤ E - L, the result is infinite.

In addition, there are control logics with floating point multipliers that form the correct sign of the result and handle certain special cases of the IEEE 754 floating point format, such as "No number" ( NaN , English for Not-A-Number ).

Hardware implementation and temporal behavior

All logic components have a signal delay. As the bit width of the multiplier increases, the number of logic components that are connected in parallel and / or in series increases. As the number of logic components increases, the total signal propagation time of the multiplier increases.

literature

  • Jean-Michel Muller: Elementary Functions - Algorithms and Implementation . 2nd Edition. Birkhäuser, Lyon 2006, ISBN 0-8176-4372-9 .

Web links