FACTOID # 14: North Carolina has a larger Native American population than North Dakota, South Dakota and Montana combined.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Multiplication ALU

In digital design, a multiplier or multiplication ALU is a hardware circuit dedicated to multiplying two binary values. Image File history File links Broom_icon. ... Digital circuits are electric circuits based on a number of discrete voltage levels. ... In mathematics, multiplication is an elementary arithmetic operation. ...


A variety of computer arithmetic techniques can be used to implement a digital multiplier. Most techniques involve computing a set of partial products, and then summing the partial products together. This process is similar to the method taught to primary schoolchildren for conducting long multiplication on base-10 integers, but has been modified here for application to a base-2 (binary) numeral system. The binary numeral system, or base-2 number system, is a numeral system that represents numeric values using two symbols, usually 0 and 1. ... This article is about different methods of expressing numbers with symbols. ...

Contents

An unsigned example

For example, suppose we want to multiply two unsigned eight bit integers together: a[7:0] and b[7:0]. We can produce eight partial products by performing eight one-bit multiplications, one for each bit in multiplicand a: Signedness is a property of an integer number used by a compiler to indicate if variables of a numeric type are capable of storing both positive and negative numbers, or just positive. ...

 p0[7:0] = a[0] × b[7:0] = {8{a[0]}} & b[7:0] p1[7:0] = a[1] × b[7:0] = {8{a[1]}} & b[7:0] p2[7:0] = a[2] × b[7:0] = {8{a[2]}} & b[7:0] p3[7:0] = a[3] × b[7:0] = {8{a[3]}} & b[7:0] p4[7:0] = a[4] × b[7:0] = {8{a[4]}} & b[7:0] p5[7:0] = a[5] × b[7:0] = {8{a[5]}} & b[7:0] p6[7:0] = a[6] × b[7:0] = {8{a[6]}} & b[7:0] p7[7:0] = a[7] × b[7:0] = {8{a[7]}} & b[7:0] 

where {8{a[0]}} means repeating a[0] (the 0th bit of a) 8 times (Verilog notation).


To produce our product, we then need to add up all eight of our partial products, as shown here:

 p0[7] p0[6] p0[5] p0[4] p0[3] p0[2] p0[1] p0[0] + p1[7] p1[6] p1[5] p1[4] p1[3] p1[2] p1[1] p1[0] 0 + p2[7] p2[6] p2[5] p2[4] p2[3] p2[2] p2[1] p2[0] 0 0 + p3[7] p3[6] p3[5] p3[4] p3[3] p3[2] p3[1] p3[0] 0 0 0 + p4[7] p4[6] p4[5] p4[4] p4[3] p4[2] p4[1] p4[0] 0 0 0 0 + p5[7] p5[6] p5[5] p5[4] p5[3] p5[2] p5[1] p5[0] 0 0 0 0 0 + p6[7] p6[6] p6[5] p6[4] p6[3] p6[2] p6[1] p6[0] 0 0 0 0 0 0 + p7[7] p7[6] p7[5] p7[4] p7[3] p7[2] p7[1] p7[0] 0 0 0 0 0 0 0 ------------------------------------------------------------------------------------------- P[15] P[14] P[13] P[12] P[11] P[10] P[9] P[8] P[7] P[6] P[5] P[4] P[3] P[2] P[1] P[0] 

In other words, P[15:0] is produced by summing p0, p1 << 1, p2 << 2, and so forth, to produce our final unsigned 16-bit product.


The impact of signed integers

If b had been a signed integer instead of an unsigned 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. Signedness is a property of an integer number used by a compiler to indicate if variables of a numeric type are capable of storing both positive and negative numbers, or just positive. ... Signedness is a property of an integer number used by a compiler to indicate if variables of a numeric type are capable of storing both positive and negative numbers, or just positive. ...


The above array multiplier can be modified to support two's complement notation signed numbers by inverting several of the product terms and inserting a one to the left of the first partial product term: Twos complement is the most popular method of signifying negative integers in computers. ...

 1 -p0[7] p0[6] p0[5] p0[4] p0[3] p0[2] p0[1] p0[0] -p1[7] +p1[6] +p1[5] +p1[4] +p1[3] +p1[2] +p1[1] +p1[0] 0 -p2[7] +p2[6] +p2[5] +p2[4] +p2[3] +p2[2] +p2[1] +p2[0] 0 0 -p3[7] +p3[6] +p3[5] +p3[4] +p3[3] +p3[2] +p3[1] +p3[0] 0 0 0 -p4[7] +p4[6] +p4[5] +p4[4] +p4[3] +p4[2] +p4[1] +p4[0] 0 0 0 0 -p5[7] +p5[6] +p5[5] +p5[4] +p5[3] +p5[2] +p5[1] +p5[0] 0 0 0 0 0 -p6[7] +p6[6] +p6[5] +p6[4] +p6[3] +p6[2] +p6[1] +p6[0] 0 0 0 0 0 0 1 +p7[7] -p7[6] -p7[5] -p7[4] -p7[3] -p7[2] -p7[1] -p7[0] 0 0 0 0 0 0 0 ------------------------------------------------------------------------------------------------------------ P[15] P[14] P[13] P[12] P[11] P[10] P[9] P[8] P[7] P[6] P[5] P[4] P[3] P[2] P[1] P[0] 

Do not be misled by the minus sign (-) notation above. It does not mean arithmetic negation ( -(7) = -7), but instead binary complementation, more commonly denoted x' (read x prime or x bar) or flipping all the bits. In two's complement to get the negation of a number, you complement the number then add 1, so they are NOT equivalent.


There are a lot of simplifications in the bit array above that are not shown and are not obvious, so I'll try to explain a few. The sequences of one complemented bit followed by noncomplemented bits are just 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 15 (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.


Implementations

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 Baugh-Wooley algorithm, Wallace trees, or Dadda multipliers to add the partial products together in a single cycle. The performance of the Wallace tree implementation is sometimes improved by modified Booth encoding one of the two multiplicands, which reduces the number of partial products that must be summed. Wallace tree is an efficient hardware implementation of multiplication of two integers. ... basic principle known from manual multiplication AND gate Would be used in reverse order Full adder, would in this case use only XOR The Dadda multiplier is a hardware multiplier design invented by computer scientist Luigi Dadda in 1965. ... Wallace tree is an efficient hardware implementation of multiplication of two integers. ... Booths multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in twos complement notation. ...


See also

Booths multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in twos complement notation. ... The multiply-accumulate operation computes a product and adds it to an accumulator. ... Wallace tree is an efficient hardware implementation of multiplication of two integers. ...

External links


  Results from FactBites:
 
Arithmetic logic unit - Wikipedia, the free encyclopedia (572 words)
The arithmetic logic unit/arithmetic-logic unit (ALU) of a computer's CPU is a part of the execution unit, a core component of all CPUs.
ALUs are capable of calculating the results of a wide variety of basic arithmetical computations.
The inputs to the ALU are the data to be operated on (called operands) and a code from the control unit indicating which operation to perform.
Multiplication ALU - Wikipedia, the free encyclopedia (586 words)
In digital design, a multiplier or multiplication ALU is a hardware circuit dedicated to multiplying two binary values.
A variety of computer arithmetic techniques can be used to implement a digital multiplier.
This process is similar to the method taught to primary schoolchildren for conducting long multiplication on base-10 integers, but has been modified here for application to a base-2 (binary) numeral system.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m