An Algorithm of Fast Interpolation

There are many approaches to realize interpolation. Padding zeros in the high frequency band of a real sequence results in interpolation in time domain. For the discrete frequency spectrum with high frequency band being zeros, this paper proposes a fast implementation method of inverse fast Fourier transform to reduce the computational cost. The proposed algorithm has a computational cost of (IN/2)(log₂ ^N- 1/2), while the computational cost of IFFT is (IN/2)(log₂ ^lN )(where N is the length of the original sequence, and l is the interpolation multiple). The stage of butterflies of the proposed method just depends on the length of the original sequence, and has nothing to do with the number of padded zeros.