Binary multiplier
A multiplier, an electric circuit which determines two or more digital numbers to the mathematical operation of multiplication of the product of the digital technology. Of the multiplier in the sub- processor arithmetic logic unit (ALU ), and there is as Multiplikationsakkumulator (MAC) before, but can be implemented in programmable digital circuits, such as FPGAs, also known as an independent functional unit.
Besides the addition, which is implemented in digital circuits with low circuit complexity in the form of adders, a fast, hardware-based multiplication in particular in the field of digital signal processing is essential. Therefore, applications of the multiplier are in signal processing, such as image processing or in the area of digital filters. But he also finds application in digital control engineering. One of the first areas of application were digital signal processors ( DSP).
Species
Multipliers are due to the different number formats that can process them, differed. The based on fixed-point arithmetic multipliers are characterized by lower circuit complexity, but are not as flexible as the more sophisticated, based on floating point multiplier.
Festkommamultiplizierer
Binary multiplication is analogous as in the decimal system and can be implemented in digital circuitry as a series of additions and sliding operations. In the adjacent circuit, an unsigned, parallel multiplier ( MAC) for each pair of four-bit full adders is shown by broad numbers X and Y and the summand K. The eight output bits P are formed in the combinational logic with the following equation:
The process of multiplication designed do so according to the following scheme, the four input bits K are due to the simplicity set to 0:
1011 ( X corresponds to the decimal number 11) · 1110 ( Y corresponds to the decimal number 14) ====== 0000 (1011 · 0 ) 1011 (1011 · 1, shifted by one position to the left) 1011 (1011 · 1, moved two places to the left) 1011 (1011 · 1, moved three places to the left) ========= 10011010 (P, corresponds to decimal 154) This simple multiplier can be realized from individual full adders and the shift operation by direct interconnection. The binary digits of the product P is equal to the sum of the digits of the two factors X and Y. A fixed in position comma point is generally not mapped circuitry, but the position of the decimal point in the product is derived from the sum of digits after the decimal point of the two input factors. In the above example, the number of digits after the decimal point zero, so that the last digit is right to lie in the product of decimal point in both factors.
With signed numbers, which are usually represented in digital circuits as two, an appropriate extension of the multiplier circuitry is needed. The correct sign multiplication of two four-digit binary numbers designed according to the following scheme, bearing in mind that the last line must be subtracted due to the negative factor:
1001 ( decimal equals the number -7) · 1101 ( decimal equals the number -3) ====== 11111001 (1001 · 1, with sign extension ) 0000000 (1001 · 0, shifted by one position to the left, with sign extension ) 111001 (1001 * 1, shifted two places to the left and with sign extension ) - 11001 (1001 x 1, shifted three places to the left, with sign extension ) ========== 00010101 ( decimal equals 21) Circuitry, the subtraction can be realized in the last line of advanced full adder, which dominate in addition to the addition and the subtraction.
The parallel multipliers, where the processing speed depends only on the maximum gate delay is, however, expensive to implement for larger bit widths. Another method is the serial multiplier, in which at the expense of throughput with lower hardware cost per clock a bit is calculated (one digit ) of the result. Furthermore, procedures that ( engl. look- up tables ) are based on tables with already pre-calculated values exist. There are also efficient algorithms, which can be realized fast multiplier with moderate circuit complexity. Examples include the Wallace tree or Booth's algorithm multiplier.
A floating point
Any floating-point number x is generated from the sign bit s ( ± 1 ) of the mantissa and an exponent e m with an arbitrary fixed base, and B:
In the usual in computer technology the IEEE 754 standard for the representation of floating point numbers is a base b = 2 and worked according to the required resolution of various widths mantissa and exponent.
The multiplication of two floating-point numbers can always be traced back 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 for reasons of speed parallel circuit with separate parts. To get correct results in over-or underruns of Festkommamultiplizierers, another logic is present at the output, which ensures by additional addition of ± 1 in the exponent and shift by ± one digit of the mantissa a correct result. In addition, still exist in Gleitkommamultiplizierern control logics, which form the correct sign of the result, and special cases of the IEEE -754 Gleitkommaformates as " Not a number " (NaN, Eng. Emergency for A- Number), treat.
Hardware implementation and temporal behavior
All logic components have a signal propagation time. By increasing the bit width of the multiplier, the number of logic devices, which are connected in parallel and / or in series, too. Ideally, the complete calculation step is performed within a single system clock. As the number of logic components, the total signal delay time of the multiplier is increased. However, you must not exceed the length of a clock cycle.
This problem can be solved in two different ways. In the first case we extended the system clock ( = reduction of the clock frequency ). This is exactly what is not desired, because a computer with a larger bit width is thereby forcibly slower.
In the second case, compensates for the signal transit time extended by distributing the computational process, for example, two clock cycles. Therefore one must divide the hardware circuit into two separate circuits. In the first system clock, the first part of the calculation is carried out and the results are stored in a buffer memory ( eg, registers, flip-flop) is stored. In the second system clock then the cached values are passed to the second circuit part which carries out the further processing of intermediate results to the overall result. In this solution, a subsequent multiplication operation can be edited in the first part of the circuit already again, while the currently running calculation process is completed in the second part of the circuit. A division of the multiplication to more than two clocks is also possible. This technique is called pipelining.