Spelling suggestions: "subject:"multiplicationand processing"" "subject:"multiplicationwith processing""
1 |
Improving the Karatsuba-Ofman multiplication algorithm for special applicationsErdem, Serdar S. 08 November 2001 (has links)
In this thesis, we study the Karatsuba-Ofman Algorithm (KOA), which is a
recursive multi-precision multiplication method, and improve it for certain special
applications. This thesis is in two parts.
In the first part, we derive an efficient algorithm from the KOA to multiply the
operands having a precision of 2[superscript m] computer words for some integer m. This new
algorithm is less complex and three times less recursive than the KOA. However, the
order of the complexity is the same as the KOA.
In the second part of the thesis, we introduce a novel method to perform fast
multiplication in GF(2[superscript m]), using the KOA. This method is intended for software
implementations and has two phases. In the first phase, we treat the field elements
in GF(2[superscript m]) as polynomials over GF(2) and multiply them by a technique based on
the KOA, which we call the LKOA (lean KOA). In the second phase, we reduce the
product with an irreducible trinomial or pentanomial.
The LKOA is similar to the KOA. However, it stops the recursions early and
switches to some nonrecursive algorithms which can efficiently multiply small polynomials
over GF(2). We derive these nonrecursive algorithms from the KOA, by
removing its recursions. Additionally, we optimize them, exploiting the arithmetic
of the polynomials over GF(2). As a result, we obtain a decrease in complexity, as
well as a reduction in the recursion overhead. / Graduation date: 2002
|
2 |
Truncated multiplications and divisions for the negative two's complement number systemPark, Hyuk, 1973- 28 August 2008 (has links)
In the design of digital signal processing systems, where single-precision results are required, the power dissipation and area of parallel multipliers can be significantly reduced by truncating the less significant columns and compensating to produce an approximate rounded product. This dissertation presents the design of truncated multiplications of signed inputs utilizing a new number system, the negative fractional two's complement number system which solves an inherent problem of the conventional two's complement number system. This research also presents a new truncated multiplication method to reduce the errors with only slightly more hardware. Error, area, delay and dynamic power estimates are performed at the structural HDL level. The new method is also applied to various conventional number systems. For division, which is the slowest and most complex of the arithmetic operations, a new truncated division method is described that yields the same errors as those of true rounding without additional execution time that is normally required for true rounding. The new method is also applied to various conventional number systems.
|
Page generated in 0.1462 seconds