Rational arithmetic units in computer systems
Michael J. Flynn, Oskar Mencer · 2000
Computer arithmetic remains important as we move to systems-on-a-chip that dedicate large areas for special-purpose arithmetic units. System application areas such as signal processing, multimedia, and mobile computing require the evaluation of functions as fast as possible with as little power as possible. It is well known that rational approximations and continued fractions offer fast approximations and efficient algorithms to compute rational functions. Due to the difficulty of converting between continued fractions and binary numbers continued fractions have been impractical for the design of computer systems. Rational arithmetic is about division of two numbers, division of polynomials and/or division of digits. Continued fractions (CFs) enable the development of divide-add structures for digits of rational numbers. Continued fraction arithmetic deals with computing rational functions where input and output values are represented as simple continued fractions. The basic remaining problems of previous work are threefold: choosing the optimal CF-digit representation, converting between simple continued fractions and binary numbers, and error control. The M-log-Fraction Transform (MFT), introduced in this work, solves all three problems. Instant conversion is shown to be related to the distance between the '1's of the binary number. Applying M-log-Fractions to continued fraction arithmetic algorithms reduces the complexity of the implementation of the CF algorithm to shift-and-add structures, or more specifically, digit-serial arithmetic algorithms for computing rational functions. A multiplication-based scheme can be used to evaluate higher-degree rational approximations. This thesis demonstrates two applications of the MFT: (1) a rational arithmetic unit computing functions such as (ax+b)/(cx+d) in a shift-and-add-based structure. (2) the evaluation of rational approximations (continued fraction approximations in a multiplication-based structure. The MFT bridges the gap between continued fractions and the binary number representation, enabling the design of a new class of efficient rational arithmetic units and the efficient evaluation of rational approximations.