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

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.