Method for Reduction of High Speed Multipliers Minimizing the Number of Half Adders Required

Background There have been tremendous advancements in the field of microprocessors and digital signal processors, marked by an increasing demand for high-speed arithmetic circuits. In particular, the demand for high-speed multiplier circuits with reduced complexity has increased. To meet this demand, the common method set that is being used in current implementations of multipliers is the Wallace methods.

Wallace multipliers use full adders and half adders in the tree reduction tiers. Half adders do not contribute to the array reduction; they only shift partial products. Therefore, minimizing the number of half adders used in a multiplier reduction is beneficial, especially if it can be achieved without significantly adding to the number of full adders. Wallace tree multiplier analysis, especially for large data word sizes can be very cumbersome and difficult to reduce without error. Moreover, for an n-bit by n-bit Wallace multiplier, the number of half-adders is at least n. More often the number of half adders is significantly larger than n, resulting in Wallace multipliers that are unnecessarily complex. There have been only a few innovations in topological manipulation of high speed multipliers that simplify analysis and reduce errors.

Invention Description This technology defines a reduction method or process that ensures that the number of reduction stages is the same as when using the classic Wallace technique; hence, the resulting multiplier performance is equivalent to conventional Wallace multipliers. This technique emphasizes the use of full adders and greatly reduces the number of half-adders, allowing implementations with 47% fewer (for 8x8 bit multipliers) to 85% fewer (for 64x64 bit multipliers) half-adders than standard Wallace multipliers with only approximately 0.1% increase in the number of full adders.

Benefits

Allows development of smaller and less complex multipliers, allowing for about 7.5% fewer (for 8 by 8 bit multipliers) to 4.5% fewer (for 64 by 64 bit multipliers) total gate count compared to conventional Wallace multipliers. The cost (both the area required and the power dissipation) for these multipliers is roughly proportional to the total gate count. Therefore, both area and power are lowered by roughly 5% with no degradation in performance.

Features

Greatly reduces the number of half-adders to implement a high-speed Wallace multiplier without decreasing the speed

Market Potential/Applications High performance microprocessors and digital signal processors

Development Stage Proof of concept

IP Status One U.S. patent application filed

UT Researcher Earl E. Swartzlander, Jr., Ph.D., Electrical and Computer Engineering, The University of Texas at Austin Ron S. Waters, Electrical and Computer Engineering, The University of Texas at Austin Whitney J. Townsend, Electrical and Computer Engineering, The University of Texas at Austin

Type of Offer: Licensing



« More Computer Science Patents

---