METHOD AND APPARATUS FOR FFT COMPUTATION
The invention relates to a method and apparatus for computing a 2N-point Fourier transform, direct or inverse, out of a 2N-sample input sequence. According to the invention, a signal processing method and apparatus is provided that makes use of an existing N-point FFT processor as well as other blocks such as a CORDIC or a filter to compute the 2N-point FFT.
1 . A method for computing a 2N-point Fourier transform, direct or inverse, out of a 2N-sample input sequence S, characterized in that an N-point Fourier transform, direct or inverse, is used.
2 . The method of claim 1 , characterized in that N is a power of 2.
3 . The method of claim 1 , characterized in that the N-point Fourier transform is a discrete Fourier transform (DFT), direct or inverse.
4 . The method of claim 1 , characterized in that the N-point Fourier transform is a fast Fourier transform (FFT), direct or inverse.
5 . The method of claim 1 , characterized in that the 2N-sample input sequence S is equally divided into two contiguous N-sample subsequences S lower and S upper .
6 . The method of claim 5 , characterized in that each subsequence S lower and S upper is rotated by a phase sequence:
exp
(
-
j
2
n
2
N
)
with nε0 . . . N−1 and
exp
(
-
j
2
n
2
N
)
with nεN . . . 2N−1, respectively, to produce rotated sequences S lower(bis) and S upper(bis) , respectively.
7 . The method of claim 6 , characterized in that the sequences S lower , S upper , S lower(bis) and S upper(bis) undergo, successively or in parallel, an N-point Fourier transform, direct or inverse, to respectively produce sequences F lower , F upper , F lower (bis) and F upper(bis) .
8 . The method of claim 7 , characterized in that F lower and F upper are added to produce F even which comprises the even-numbered samples of the 2N-point Fourier transform spanning 0 through 2N−2, and that F lower(bis) and F upper(bis) are added to produce F odd which comprises the odd-numbered samples of the 2N-point Fourier transform spanning 1 through 2N−1.
9 . The method of claim 1 , characterized in performing a frequency filtering on the sequences to solely compute a direct 2N-point Fourier transform.
10 . The method of claim 9 , characterized in that the input signal is frequency translated so as to center the middle, as expressed in terms of subcarriers, of its lower half on DC.
11 . The method of claim 10 , characterized in that the resulting signal is low-pass filtered to produce the samples, i.e. subcarriers, numbered 0 through N−1of the 2N-point Fourier transform.
12 . The method of claim 9 , characterized in that the input signal is frequency translated so as to center the middle, as expressed in terms of subcarriers, of its upper half on DC.
13 . The method of claim 12 , characterized in that the resulting signal is high-pass filtered to produce the samples, i.e. subcarriers, numbered respectively N through 2N−1 of the 2N-point Fourier transform.
14 . An apparatus for computing a 2N-point Fourier transform, direct or inverse, of a 2N-sample input sequence S, characterized in that it comprises at least one signal processing unit for performing a N-point Fourier transform.
15 . The apparatus of claim 14 , characterized in that it comprises means for equally dividing the 2N-sample input sequence S into two contiguous N-sample subsequences S lower and S upper .
16 . The apparatus of claim 14 , characterized in that it further comprises a phase rotator for phase rotating the subsequences S lower and S upper to produce rotated subsequences S lower(bis) and S upper(bis) , respectively.
17 . The apparatus of claim 16 , characterized in that the phase rotator is a Coordinate Rotation Digital Computer, CORDIC.
18 . The apparatus of claim 14 , characterized in that it further comprises a digital structure implementing a frequency domain filter coupled to the output of the FFT signal processor.
19 . The apparatus of claim 14 , characterized in that it further comprises an adder/subtractor for adding/subtracting the input sequences S lower and S upper from each other before they are inputted to the FFT signal processor.
20 . The apparatus of claim 14 , characterized in that it further comprises an adder for adding sequences F lower and F upper outputted from the FFT signal processor.