A binary multiplier is an
electronic circuit used in
digital electronics
Digital electronics is a field of electronics involving the study of digital signals and the engineering of devices that use or produce them. This is in contrast to analog electronics and analog signals.
Digital electronic circuits are usual ...
, such as a
computer, to
multiply
Multiplication (often denoted by the cross symbol , by the mid-line dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four elementary mathematical operations of arithmetic, with the other ones being additi ...
two
binary numbers.
A variety of
computer arithmetic
In computing, an arithmetic logic unit (ALU) is a combinational digital circuit that performs arithmetic and bitwise operations on integer binary numbers. This is in contrast to a floating-point unit (FPU), which operates on floating point numb ...
techniques can be used to implement a digital multiplier. Most techniques involve computing the set of ''partial products,'' which are then summed together using
binary adder
Binary may refer to:
Science and technology Mathematics
* Binary number, a representation of numbers using only two digits (0 and 1)
* Binary function, a function that takes two arguments
* Binary operation, a mathematical operation that ta ...
s. This process is similar to
long multiplication
A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are more efficient than others. Efficient multiplication algorithms have existed since the advent of the d ...
, except that it uses a base-2 (
binary
Binary may refer to:
Science and technology Mathematics
* Binary number, a representation of numbers using only two digits (0 and 1)
* Binary function, a function that takes two arguments
* Binary operation, a mathematical operation that ta ...
)
numeral system
A numeral system (or system of numeration) is a writing system for expressing numbers; that is, a mathematical notation for representing numbers of a given set, using digits or other symbols in a consistent manner.
The same sequence of symbo ...
.
History
Between 1947 and 1949 Arthur Alec Robinson worked for English Electric Ltd, as a student apprentice, and then as a development engineer. Crucially during this period he studied for a PhD degree at the University of Manchester, where he worked on the design of the hardware multiplier for the early
Mark 1 computer.
However, until the late 1970s, most
minicomputers
A minicomputer, or colloquially mini, is a class of smaller general purpose computers that developed in the mid-1960s and sold at a much lower price than mainframe and mid-size computers from IBM and its direct competitors. In a 1970 survey, ...
did not have a multiply instruction, and so programmers used a "multiply routine"
which repeatedly
shifts and accumulates partial results,
often written using
loop unwinding
Loop unrolling, also known as loop unwinding, is a loop transformation technique that attempts to optimize a program's execution speed at the expense of its binary size, which is an approach known as space–time tradeoff. The transformation ...
.
Mainframe computers had multiply instructions, but they did the same sorts of shifts and adds as a "multiply routine".
Early
microprocessor
A microprocessor is a computer processor where the data processing logic and control is included on a single integrated circuit, or a small number of integrated circuits. The microprocessor contains the arithmetic, logic, and control circ ...
s also had no multiply instruction. Though the multiply instruction became common with the 16-bit generation,
at least two 8-bit processors have a multiply instruction: the
Motorola 6809
The Motorola 6809 ("''sixty-eight-oh-nine''") is an 8-bit computing, 8-bit microprocessor with some 16-bit computing, 16-bit features. It was designed by Motorola's Terry Ritter and Joel Boney and introduced in 1978. Although source compatible wi ...
, introduced in 1978, and
Intel MCS-51
The Intel MCS-51 (commonly termed 8051) is a single chip microcontroller (MCU) series developed by Intel in 1980 for use in embedded systems. The architect of the Intel MCS-51 instruction set was John H. Wharton. Intel's original versions were po ...
family, developed in 1980, and later the modern
Atmel AVR 8-bit microprocessors present in the ATMega, ATTiny and ATXMega microcontrollers.
As more
transistors per chip became available due to larger-scale integration, it became possible to put enough adders on a single chip to sum all the partial products at once, rather than reuse a single adder to handle each partial product one at a time.
Because some common
digital signal processing algorithms spend most of their time multiplying,
digital signal processor designers sacrifice considerable chip area in order to make the multiply as fast as possible; a single-cycle
multiply–accumulate unit often used up most of the chip area of early DSPs.
Binary long multiplication
The method taught in school for multiplying decimal numbers is based on calculating partial products, shifting them to the left and then adding them together. The most difficult part is to obtain the partial products, as that involves multiplying a long number by one digit (from 0 to 9):
123
x 456
=
738 (this is 123 x 6)
615 (this is 123 x 5, shifted one position to the left)
+ 492 (this is 123 x 4, shifted two positions to the left)
=
56088
A binary computer does exactly the same multiplication as decimal numbers do, but with binary numbers. In binary encoding each long number is multiplied by one digit (either 0 or 1), and that is much easier than in decimal, as the product by 0 or 1 is just 0 or the same number. Therefore, the multiplication of two binary numbers comes down to calculating partial products (which are 0 or the first number),
shifting them left, and then adding them together (a binary addition, of course):
1011 (this is binary for decimal 11)
x 1110 (this is binary for decimal 14)
0000 (this is 1011 x 0)
1011 (this is 1011 x 1, shifted one position to the left)
1011 (this is 1011 x 1, shifted two positions to the left)
+ 1011 (this is 1011 x 1, shifted three positions to the left)
=
10011010 (this is binary for decimal 154)
This is much simpler than in the decimal system, as there is no table of multiplication to remember: just shifts and adds.
This method is mathematically correct and has the advantage that a small CPU may perform the multiplication by using the shift and add features of its arithmetic logic unit rather than a specialized circuit. The method is slow, however, as it involves many intermediate additions. These additions are time-consuming. Faster multipliers may be engineered in order to do fewer additions; a modern processor can multiply two 64-bit numbers with 6 additions (rather than 64), and can do several steps in parallel.
The second problem is that the basic school method handles the sign with a separate rule ("+ with + yields +", "+ with − yields −", etc.). Modern computers embed the sign of the number in the number itself, usually in the
two's complement
Two's complement is a mathematical operation to reversibly convert a positive binary number into a negative binary number with equivalent (but negative) value, using the binary digit with the greatest place value (the leftmost bit in big- endian ...
representation. That forces the multiplication process to be adapted to handle two's complement numbers, and that complicates the process a bit more. Similarly, processors that use
ones' complement
The ones' complement of a binary number is the value obtained by inverting all the bits in the binary representation of the number (swapping 0s and 1s). The name "ones' complement" (''note this is possessive of the plural "ones", not of a sin ...
,
sign-and-magnitude
In computing, signed number representations are required to encode negative numbers in binary number systems.
In mathematics, negative numbers in any base are represented by prefixing them with a minus sign ("−"). However, in RAM or CPU regist ...
,
IEEE-754
The IEEE Standard for Floating-Point Arithmetic (IEEE 754) is a technical standard for floating-point arithmetic established in 1985 by the Institute of Electrical and Electronics Engineers (IEEE). The standard addressed many problems found in ...
or other binary representations require specific adjustments to the multiplication process.
Unsigned integers
For example, suppose we want to multiply two
unsigned
Unsigned can refer to:
* An unsigned artist is a musical artist or group not attached or signed to a record label
** Unsigned Music Awards, ceremony noting achievements of unsigned artists
** Unsigned band web, online community
* Similarly, the c ...
eight bit integers together: ''a''
:0and ''b''
:0 We can produce eight partial products by performing eight one-bit multiplications, one for each bit in multiplicand ''a'':
p0 :0= a × b :0= & b :0 p1 :0= a × b :0= & b :0 p2 :0= a × b :0= & b :0 p3 :0= a × b :0= & b :0 p4 :0= a × b :0= & b :0 p5 :0= a × b :0= & b :0 p6 :0= a × b :0= & b :0 p7 :0= a × b :0= & b :0/nowiki>
where means repeating a (the 0th bit of a) 8 times (Verilog
Verilog, standardized as IEEE 1364, is a hardware description language (HDL) used to model electronic systems. It is most commonly used in the design and verification of digital circuits at the register-transfer level of abstraction. It is als ...
notation).
In order to obtain our product, we then need to add up all eight of our partial products, as shown here:
p0 p0 p0 p0 p0 p0 p0 p0 + p1 p1 p1 p1 p1 p1 p1 p1 0
+ p2 p2 p2 p2 p2 p2 p2 p2 0 0
+ p3 p3 p3 p3 p3 p3 p3 p3 0 0 0
+ p4 p4 p4 p4 p4 p4 p4 p4 0 0 0 0
+ p5 p5 p5 p5 p5 p5 p5 p5 0 0 0 0 0
+ p6 p6 p6 p6 p6 p6 p6 p6 0 0 0 0 0 0
+ p7 p7 p7 p7 p7 p7 p7 p7 0 0 0 0 0 0 0
-------------------------------------------------------------------------------------------
P 5P 4P 3P 2P 1P 0 P P P P P P P P P P
In other words, ''P'' 5:0is produced by summing ''p''0, ''p''1 << 1, ''p''2 << 2, and so forth, to produce our final unsigned 16-bit product.
Signed integers
If ''b'' had been a signed integer instead of an unsigned
Unsigned can refer to:
* An unsigned artist is a musical artist or group not attached or signed to a record label
** Unsigned Music Awards, ceremony noting achievements of unsigned artists
** Unsigned band web, online community
* Similarly, the c ...
integer, then the partial products would need to have been sign-extended up to the width of the product before summing. If ''a'' had been a signed integer, then partial product ''p7'' would need to be subtracted from the final sum, rather than added to it.
The above array multiplier can be modified to support two's complement notation
Two's complement is a mathematical operation to reversibly convert a positive binary number into a negative binary number with equivalent (but negative) value, using the binary digit with the greatest place value (the leftmost bit in big- endian ...
signed numbers by inverting several of the product terms and inserting a one to the left of the first partial product term:
1 ~p0 p0 p0 p0 p0 p0 p0 p0 ~p1 +p1 +p1 +p1 +p1 +p1 +p1 +p1 0
~p2 +p2 +p2 +p2 +p2 +p2 +p2 +p2 0 0
~p3 +p3 +p3 +p3 +p3 +p3 +p3 +p3 0 0 0
~p4 +p4 +p4 +p4 +p4 +p4 +p4 +p4 0 0 0 0
~p5 +p5 +p5 +p5 +p5 +p5 +p5 +p5 0 0 0 0 0
~p6 +p6 +p6 +p6 +p6 +p6 +p6 +p6 0 0 0 0 0 0
1 +p7 ~p7 ~p7 ~p7 ~p7 ~p7 ~p7 ~p7 0 0 0 0 0 0 0
------------------------------------------------------------------------------------------------------------
P 5 P 4 P 3 P 2 P 1 P 0 P P P P P P P P P P
Where ~p represents the complement (opposite value) of p.
There are many simplifications in the bit array above that are not shown and are not obvious. The sequences of one complemented bit followed by noncomplemented bits are implementing a two's complement trick to avoid sign extension. The sequence of p7 (noncomplemented bit followed by all complemented bits) is because we're subtracting this term so they were all negated to start out with (and a 1 was added in the least significant position). For both types of sequences, the last bit is flipped and an implicit -1 should be added directly below the MSB. When the +1 from the two's complement negation for p7 in bit position 0 (LSB) and all the -1's in bit columns 7 through 14 (where each of the MSBs are located) are added together, they can be simplified to the single 1 that "magically" is floating out to the left. For an explanation and proof of why flipping the MSB saves us the sign extension, see a computer arithmetic book.
Floating point numbers
A binary floating number contains a sign bit, significant bits (known as the significand) and exponent bits (for simplicity, we don't consider base and combination field). The sign bits of each operand are XOR'd to get the sign of the answer. Then, the two exponents are added to get the exponent of the result. Finally, multiplication of each operand's significand will return the significand of the result. However, if the result of the binary multiplication is higher than the total number of bits for a specific precision (e.g. 32, 64, 128), rounding is required and the exponent is changed appropriately.
Hardware implementation
The process of multiplication can be split into 3 steps:[
][
]
* generating partial product
* reducing partial product
* computing final product
Older multiplier architectures employed a shifter and accumulator to sum each partial product, often one partial product per cycle, trading off speed for die area. Modern multiplier architectures use the (Modified) Baugh–Wooley algorithm, Wallace tree
A Wallace multiplier is a hardware implementation of a binary multiplier, a digital circuit that multiplies two integers. It uses a selection of full and half adders (the Wallace tree or Wallace reduction) to sum partial products in stages unti ...
s, or Dadda multiplier
The Dadda multiplier is a hardware binary multiplier design invented by computer scientist Luigi Dadda in 1965. It uses a selection of full and half adders to sum the partial products in stages (the Dadda tree or Dadda reduction) until two numbers ...
s to add the partial products together in a single cycle. The performance of the Wallace tree
A Wallace multiplier is a hardware implementation of a binary multiplier, a digital circuit that multiplies two integers. It uses a selection of full and half adders (the Wallace tree or Wallace reduction) to sum partial products in stages unti ...
implementation is sometimes improved by ''modified'' Booth encoding
Booth's multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in two's complement notation. The algorithm was invented by Andrew Donald Booth in 1950 while doing research on crystallography at Birkbeck ...
one of the two multiplicands, which reduces the number of partial products that must be summed.
For speed, shift-and-add multipliers require a fast adder (something faster than ripple-carry).
A "single cycle" multiplier (or "fast multiplier") is pure combinational logic
In automata theory, combinational logic (also referred to as time-independent logic or combinatorial logic) is a type of digital logic which is implemented by Boolean circuits, where the output is a pure function of the present input only. This ...
.
In a fast multiplier,
the partial-product reduction process usually contributes the most to the delay, power, and area of the multiplier.
For speed, the "reduce partial product" stages are typically implemented as a carry-save adder composed of compressors and the "compute final product" step is implemented as a fast adder (something faster than ripple-carry).
Many fast multipliers use full adders as compressors ("3:2 compressors") implemented in static CMOS.
To achieve better performance in the same area or the same performance in a smaller area, multiplier designs may use higher order compressors such as 7:3 compressors;
implement the compressors in faster logic (such transmission gate logic, pass transistor logic, domino logic
Domino logic is a CMOS-based evolution of the dynamic logic techniques based on either PMOS or NMOS transistors. It allows a rail-to-rail logic swing. It was developed to speed up circuits, solving the premature cascade problem, typically by in ...
);[
Peng Chang]
"A Reconfigurable Digital Multiplier and 4:2 Compressor Cells Design"
2008.
connect the compressors in a different pattern; or some combination.
Example circuits
See also
* Booth's multiplication algorithm
Booth's multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in two's complement notation. The algorithm was invented by Andrew Donald Booth in 1950 while doing research on crystallography at Birkbeck ...
* Fused multiply–add
* Wallace tree
A Wallace multiplier is a hardware implementation of a binary multiplier, a digital circuit that multiplies two integers. It uses a selection of full and half adders (the Wallace tree or Wallace reduction) to sum partial products in stages unti ...
* BKM algorithm
The BKM algorithm is a shift-and-add algorithm for computing elementary functions, first published in 1994 by Jean-Claude Bajard, Sylvanus Kla, and Jean-Michel Muller. BKM is based on computing complex logarithms (''L-mode'') and exponentials ( ...
for complex logarithms and exponentials
* Kochanski multiplication Kochanski multiplication is an algorithm that allows modular arithmetic (multiplication or operations based on it, such as exponentiation) to be performed efficiently when the modulus is large (typically several hundred bits). This has particular ap ...
for modular
Broadly speaking, modularity is the degree to which a system's components may be separated and recombined, often with the benefit of flexibility and variety in use. The concept of modularity is used primarily to reduce complexity by breaking a s ...
multiplication
* Logical shift left
References
*
External links
Multiplier Designs
targeted at FPGAs
Binary Multiplier circuit using Half -Adders and digital gates.
{{DEFAULTSORT:Binary Multiplier
Arithmetic logic circuits
Binary arithmetic
Multiplication