Bit Serial Multiplier

Shift the multiplier one bit to the right and multiplicand one bit to the left. Stop when all bits of the multiplier are zero. From above it is clear that the multiplication has been changed to addition of numbers. If the Partial Products are added serially then a serial adder is used with least hardware. (16 BIT X 16 BIT) BOOTH MULTIPLIER USING VHDL MUHAMMAD SYAFIQ BIN NORASHID UNIVERSITI MALAYSIA PAHANG “I hereby acknowledge that the scope and quality of this thesis is qualified for the award of the Bachelor Degree of Electrical Engineering (Electronics)”.

1. Booth, A.D.: A signed binary multiplication technique. Q. J. Mech. Appl. Math. 4, part-2, 236–240 (1951)MathSciNetCrossRefGoogle Scholar
2. Chen, T.C.: A binary multiplication scheme based on squaring. IEEE Tans. C-20, 678–680 (1971)Google Scholar
3. Wallace, C.S.: A suggestion for a fast multiplier. IEEE Trans. EC-13, 14–17 (1964)Google Scholar
4. Braun, E.L.: Digital computer design. Academic Press, New York (1963)zbMATHGoogle Scholar
5. Baugh, C.R., Wooley, B.A.: A two’s complement parallel array multiplication algorithm. IEEE Trans. C-22(1-2), 1045–1047 (1973)Google Scholar
6. Nayak, S.S., Meher, P.K.: High throughput VLSI implementation of discrete orthogonal transforms using bit-level vector - matrix multiplier. IEEE Trans. Circuits Syst. II. Analog and Digital Signal Processing 46(5), 655–658 (1999)CrossRefGoogle Scholar
7. Nayak, S.S., Murty, M.N., Panda, H.: Bit - level systolic implementation of discrete orthogonal transforms. Signal Processing 81, 2437–2443 (2001)zbMATHCrossRefGoogle Scholar
8. Amira, A., Bouridane, A., Milligan, P., Belatreche, A.: Design of efficient architectures for discrete orthogonal transforms using bit level systolic structures. IEE Proc. - Comput. Digit. Tech. 149(1), 17–24 (2002)CrossRefGoogle Scholar

Mpeg4 satellite receiver software. A binary multiplier is an electronic circuit used in digital electronics, such as a computer, to multiply two binary numbers. It is built using binary adders.

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.

History[edit]

Between 1947-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.[3]However, until the late 1970s, most minicomputers did not have a multiply instruction, and so programmers used a 'multiply routine'^[1][2]which repeatedly shifts and accumulates partial results,often written using loop unwinding. Mainframe computers had multiply instructions, but they did the same sorts of shifts and adds as a 'multiply routine'.

Early microprocessors also had no multiply instruction. Though the multiply instruction is usually associated with the 16-bit microprocessor generation,^[3] at least two 'enhanced' 8-bit micro have a multiply instruction: the Motorola 6809, introduced in 1978,^[4][5] and Intel MCS-51 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 a lot of 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.

Basics[edit]

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):

Binary numbers[edit]

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):

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 take a lot of time. 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.^{[citation needed]}

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 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, sign-and-magnitude, IEEE-754 or other binary representations require specific adjustments to the multiplication process.

Unsigned numbers[edit]

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:

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:

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.

Signed integers[edit]

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.

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:

Where ~p represents the complement (opposite value) of p.

There are a lot of 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.^[6]

Floating point numbers[edit]

A binary floating number contains a sign bit(s) significant bit (s) and exponent bit (e) [ for simplicity we don't consider bais and combination field]. Two signed ar XOR'd to get the sign of the answer. Then two exponents are added to get the exponent of the result. Finally, the result multiplication significant is the result of tow fixed point significand multiplication. However, if the result of binary multiplication is higher then the total number of bit for a specific precision (32,64,128) rounding is required and the exponent is further required to adjust.

Implementations[edit]

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,^{[7][8][9][10]}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 modifiedBooth encoding one of the two multiplicands, which reduces the number of partial products that must be summed.

Example circuits[edit]

See also[edit]

• BKM algorithm for complex logarithms and exponentials
• Kochanski multiplication for modular multiplication

References[edit]

1. ^'The Evolution of Forth' by Elizabeth D. Rather et al.[1][2]
2. ^'Interfacing a hardware multiplier to a general-purpose microprocessor'
3. ^M. Rafiquzzaman (2005). Fundamentals of Digital Logic and Microcomputer Design. John Wiley & Sons. p. 251. ISBN978-0-47173349-2.
4. ^Krishna Kant (2007). Microprocessors and Microcontrollers: Architecture, Programming and System Design 8085, 8086, 8051, 8096. PHI Learning Pvt. Ltd. p. 57. ISBN9788120331914.
5. ^Krishna Kant (2010). Microprocessor-Based Agri Instrumentation. PHI Learning Pvt. Ltd. p. 139. ISBN9788120340862.
6. ^Parhami, Behrooz, Computer Arithmetic: Algorithms and Hardware Designs, Oxford University Press, New York, 2000 (ISBN0-19-512583-5, 490 + xx pp.)
7. ^Baugh, Charles Richmond; Wooley, Bruce A. (December 1973). 'A Two's Complement Parallel Array Multiplication Algorithm'. IEEE Transactions on Computers. C-22 (12): 1045–1047. doi:10.1109/T-C.1973.223648.
8. ^Hatamian, Mehdi; Cash, Glenn (1986). 'A 70-MHz 8-bit×8-bit parallel pipelined multiplier in 2.5-µm CMOS'. IEEE Journal of Solid-State Circuits. 21 (4): 505–513. doi:10.1109/jssc.1986.1052564.
9. ^Gebali, Fayez (2003). 'Baugh–Wooley Multiplier'(PDF). University of Victoria, CENG 465 Lab 2. Archived(PDF) from the original on 2018-04-14. Retrieved 2018-04-14.
10. ^Reynders, Nele; Dehaene, Wim (2015). Written at Heverlee, Belgium. Ultra-Low-Voltage Design of Energy-Efficient Digital Circuits. Analog Circuits And Signal Processing (ACSP) (1 ed.). Cham, Switzerland: Springer International Publishing AG Switzerland. doi:10.1007/978-3-319-16136-5. ISBN978-3-319-16135-8. ISSN1872-082X. LCCN2015935431.

• Hennessy, John L.; Patterson, David A. (1990). 'Section A.2, section A.9'. Computer Architecture: A quantitative Approach. Morgan Kaufmann Publishers, Inc. pp. A–3.A–6, A–39.A–49. ISBN978-0-12383872-8.

External links[edit]

• Multiplier Designs targeted at FPGAs