A parallel interpolation method for designing FIR digital filters by nonuniform frequency samples

A new class of interpolating polynomials which depend on the number of available processors is introduced and used to develop fast and accurate parallel algorithms for designing FIR (finite impulse response) digital filters using the frequency-sampling method. Based on these polynomials and on new suitable band or upper triangular matrices, efficient parallel algorithms and recursive relations to solve the design problem are developed. Given n samples at n frequencies and p available processors such that n=m*p, the proposed algorithm needs p*m/sup 2/ flops by each processor to compute the coefficients of the interpolating polynomials and 0.5n/sup 2/ flops to calculate the coefficients of the filter. In the progressive case where the samples appear sequentially, a fast algorithm, which needs only p*n flops by each processor, is developed; it updates the old filter coefficients and computes the new ones when the last mth group of samples appears.<>