-
Notifications
You must be signed in to change notification settings - Fork 85
Real FFT transformation storage
An FFT transformation of a real vector of length N is a complex vector with conjugate symmetry for a 1D vector. Like other major FFT libraries, e.g. FFTW, rocFFT only stores the first [1 + N/2] elements of the output complex vector, where N/2 is an integer division (round down).
More specifically, if N is even, we store elements at indices i=0, 1, ..., N/2-1, N/2, where elements at i=0 and i=N/2 are real-valued (have imaginary part = 0). If N is odd, we store elements at indices i=0, 1, ..., (N-1)/2, where element at i=0 is real-valued.
for a vector of length 8,
i = [ 0, 1, 2, 3, 4, 5, 6, 7]
a = [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0]
on Matlab, we getfft(a) = [36.0, -4.0+9.6569i, -4.0+4.0000i, -4.0+1.6569i, -4.0, -4.0-1.6569i, -4.0-4.0000i, -4.0-9.6569i]
where fft(a)[0] = sum(a[0]:a[7]) by FFT property, while fft(a)[1] and fft(a)[7] are complex conjugates of each other; similarly, fft(a)[2] & fft(a)[6], fft(a)[3] & fft(a)[5]. The elements at indices(i) 5,6,7 are redundant and thus need not be stores. So here N=8, we only store for i=0, 1, 2, 3, 4. Totally, 1 + 8/2 = 5 elements.
for a vector of length 7,
i = [ 0, 1, 2, 3, 4, 5, 6]
b = [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0]
on Matlab, fft(b) = [28.0, -3.5 + 7.2678i, -3.5 + 2.7912i, -3.5 + 0.7989i, -3.5 - 0.7989i, -3.5 - 2.7912i, -3.5 - 7.2678i]
where fft(b)[0] = sum(b[0]:b[6]), while fft(b)[1] and fft(a)[6] are complex conjugates of each other, similarly, fft(a)[2] & fft(a)[5], fft(a)[3] & fft(a)[4]. So here N=7, we only store for i=0, 1, 2, 3. Totally, 1 + 7/2 = 4 elements.
If the input vector is 2D or 3D. Only the inner most dimension is changed to (1+N/2). The other dimensions keeps the same.
This is because the FFT along the inner most dimension is computed first and is logically a real-to-hermitian transform. The FFTs along other dimensions are computed afterwards; they are simply 'complex-to-complex' transforms. For example, assuming Lengths[2] is used to set up a 2D real FFT, let N1 = Lengths[1], and N0 = Lengths[0]. The output FFT has N1*(1 + N0/2) complex elements. Similarly, for a 3D FFT with the output has N2N1(1 + N0/2) complex elements.