Real FFT transformation storage

An FFT transformation of a real vector of length N is a complex vector with conjugate symmetry. 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.

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-values.

Example 1:

for a vector of length 8, i = [0, 1, 2, 3, 4, 5, 6, 7] a = [1, 2, 3, 4, 5, 6, 7, 8] 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.

Example 2:

for a vector of length 7, i = [0, 1, 2, 3, 4, 5, 6] b = [1, 2, 3, 4, 5, 6, 7]

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.

see here for more about real FFT