A new Fourier-transform algorithm using Walsh functions

This paper presents a new computational algorithm for the discrete Fourier transform. In an algorithm proposed here, first the discrete Walsh transform of sampled data is evaluated and then using these results Fourier coefficients can be computed. The number of multiplications in the algorithm can be expressed by approximately NL/6 for N data points and L Fourier coefficients to be calculated. On the other hand, the fast Fourier transform must compute all of Fourier coefficients independently of L. This algorithm is useful in the case where the number of L is not very large, or Walsh coefficients and Fourier coefficients are both calculated.