A Bound on the Output of a Circular Convolution with Application to Digital Filtering

When implementing a digital filter, it is important to utilize in the design a bound or estimate of the largest output value which will be obtained. Such a bound is particularly useful when fixed point arith-metic is to be used since it assists in determining register lengths necessary to prevent overflow. In this paper we consider the class of digital filters which have an impulse response of finite duration and are implemented by means of circular convolutions performed using the discrete Fourier transform. A least upper bound is obtained for the maximum possible output of a circular convolution for the general case of complex input sequences. For the case of real input sequences, a lower bound on the least upper bound is obtained. The use of these results in the implementation of this class of digital filters is discussed. Manuscript received November 26, 1968. This work was sponsored by the U. S. Air Force