Patent ID: 7685220

Claim:
A Decimation In Frequency (DIF) Fast Fourier Transform (FFT) stage for use in an N bin Fourier transform, wherein N is an integer, the DIF FFT stage comprising: swap logic that receives a first input sample, x(v), and a second input sample, x(v+N/2), and selectively supplies either the first and second input samples at respective first and second swap logic output ports or alternatively the second and first input samples at the respective first and second swap logic output ports, wherein 0≦v<N/2; a summing unit for adding values supplied by the first and second swap logic output ports; a differencing unit for subtracting values supplied by the first and second swap logic output ports; and twiddle factor logic that multiplies a value supplied by the differencing unit by a twiddle factor, W N (v+s)mod(N/2) , where s is an integer representing an amount of circular shift of N input samples.