Real FFT transformation storage

A FFT transformation of a real vector of length N is a complex vector with conjugate symmetry. Like other major FFT library, e.g. FFTW, rocFFT only store 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 element i=0,1,..., N/2-1, N/2, where element i=0, i=N/2 must be real.

If N is odd, we store element i=0,1,..., (N-1)/2, where only element i=0 be real.

Example 1, for a vector of length 8

a = [1, 2, 3, 4, 5, 6, 7, 8]

by 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 conjugate to each other, similarly, fft(a)[2] & fft(a)[6], fft(a)[3] & fft(a)[5]. The element 7, 6, 5 are redundant and thus not need to store.

So here N=8, we only store i=0, 1, 2, 3, 4. Totally 1 + N/2 = 5 elements.

Example 2: for a vector of length 7

b = [1, 2, 3, 4, 5, 6, 7]

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 conjugate to each other, similarly, fft(a)[2] & fft(a)[5], fft(a)[3] & fft(a)[4].

So here N=7, we only store i=0, 1, 2, 3. Totally 1 + N/2 = 1+ 7/2 = 4 elements.

see here for more about real FFT