Advances in bit width selection methodology

We describe a method for the formal determination of signal bit width in fixed point VLSI implementations of signal processing algorithms containing loop nests. The main contribution of this paper is the use of results of the (max, +) algebraic theory to find the integral bit width of algorithms containing loop nests whose bound parameters are not statically known. Combined with recent results on fractional bit width determination, this can be used for 1-dimensional systolic-like arrays implementing linear signal processing algorithms. Although this technique is presented in the context of a specific high level design methodology (based on systems of affine recurrence equations), it can be used in many high level design environments.