Math387

Defines the storage format used when performing forward and inverse FFT's. The result of a forward FFT operation is an array of complex numbers. Notation:

• Re(0) is the real part of the complex number stored at index 0.
• Im(0) is the imaginary part of the complex number stored at index 0.

The length of the FFT is N and d = N/2. N is an even value. For these parameters the complex to complex FFT returns the following complex array:

If the source was real, the real to complex FFT computes only the first half of that table, namely:

That is because beyond index d, all elements are conjugate symmetric part of elements below index d. For example, it is possible to compute the upper half of the array doing operation's like this: (Re(d+1), Im(d+1)) = (Re(d-1), - Im(d-1)) 

The storage format that stores the FFT result as presented here is called the CCS format. 

A speciallity of the FFT result is that Im(0) and Im(d) are always zero. Because these two values are implicitely known in advance, they do not have to be stored. This is exploited by two other storage formats: pack and perm. The pack format simply leaves out the zeros and pushes the elements together and the perm format stores the Re(d) value at the position of Im(0) and pushes the elements together. 

If the length of the FFT N is odd, then everything remains the same, except that the center element at index d is absent. This means that pack and perm have the same storage format in this case. 

For a 2D FFT similar rules apply and the storage formats layout is as follows: 

CCS format, m x n matrix 

Even length (m = s*2)

Odd length (m = s*2+1)

PACK format, m x n matrix 

Even length (m = s*2)

Odd length (m = s*2+1)

PERM Format, m x n matrix 

Even length (m = s*2)

Odd length (m = s*2+1)

Structs, Records, Enums