PROJECT TITLE :

On the Systematic Creation of Faithfully Rounded Truncated Multipliers and Arrays (2014)

ABSTRACT :

Sometimes it is necessary to return a faithfully rounded result when performing fixed-point multiplication, i.e. the number representable by the computer either immediately above or below the arbitrary precision result, if the latter is not exactly representable. Faithfully rounded multipliers use substantially less silicon area, usually by applying a truncation scheme within the partial product array, compared to correctly rounded multipliers, i.e. those returning the nearest machine representative amount. In the literature, there are a variety of such heuristically inspired systems, but their use in industrial practice is hindered by the absence of verification, and exhaustive simulation is usually impossible, e.g. 264 simulations are necessary for a 32 bit multiplier. We present three truncated multiplier schemes that subsume most of the existing schemes and derive the necessary and adequate conditions for faithful rounding both in closed form. We include closed form expressions for the bit vectors for two of the schemes, giving rise to the worst-case error and the probability of encountering these inputs during the simulation of Monte-Carlo. From these expressions, we demonstrate how it is possible to build HDL code that performs faithfully rounded multiplication correct-by-construction. We also present a way to truncate an arbitrary array while preserving faithful rounding, generating in the process two new truncated multiplier schemes.