Patent ID: 6195675
Filing Date: 2001-02-27
Classification: G06F,H04Q

Abstract:
A method of determining at least one frequency component of a sampled input signal using an N-point discrete Fourier transform (DFT), where N=2.sup.M and M is an integer greater than 1, the DFT comprising M stages of butterfly computations from at least one input for the successive samples of the input signal to a respective output for each frequency component, comprising the steps of:providing each of said stages with up to 2.sup.m-1 butterfly computations where m is a number of the stage from 1 to M from said at least one input to said respective output(s);determining said at least one frequency component at its respective output from the stage M; andfor each of the stages from 1 to M-1:determining 1 to 2.sup.m intermediate results using the respective butterfly computation(s) and storing the determined intermediate result(s); andderiving 1 to 2.sup.m intermediate results required, in addition to the 1 to 2.sup.m intermediate results determined in respect of a current sample of the input signal, for butterfly computation(s) in the next subsequent stage from the stored intermediate result(s) determined in respect of preceding sample(s) of the input signal.