TFFTStorageFormat Type

Summary

Type used to define the storage format for FFT operations.

Declaration

TFFTStorageFormat = (fsfCCS, fsfPack, fsfPerm);

Value	Description
fsfCCS	This is the "natural" FFT storage format. It's main disadvantages are: 1.) you can not perform an inverse FFT to real, without telling the routine of what length should the result be: odd or even. 2.) When performing real to complex FFT, the size of the result is bigger than the size of the source data. This requires that the initial data is stored in to an array which allocates more memory then occupied by the source (2 real numbers more)
fsfPack	Pack's the complex numbers together. The side effect of this is that each complex number is now no longer alligned with the complex array. The Re(1) is now stored at position of Im(0), Im(1) at position of Re(1) and so on. The advantages of this format are: 1.) the inverse is uniformly defined, even for odd length FFT. If the source data was odd in length, so will be the result also. If the (real) source data was even in length, the result will also require an even number of (real) array elements. 2.) The storage requirements before and affter the FFT will remain the same. There is no need for a memory resize. The complex array missalignment can be worked around with the help of the SetSubRange method.
fsfPerm	Stores the Re(d) element at position of Im(0). The side effect is that for even length real source, the complex numbers will be alligned with the complex array, but for odd length FFT they will be not. The advantages of this format are: 1.) the inverse is uniformly defined, even for odd length FFT. If the source data was odd in length, so will be the result also. If the (real) source data was even in length, the result will also require an even number of (real) array elements. 2.) The storage requirements before and after the FFT will remain the same. There is no need for a memory resize. The complex array missalignment can be worked around with the help of the SetSubRange method.

Value

Description

fsfCCS

This is the "natural" FFT storage format. It's main disadvantages are:

1.) you can not perform an inverse FFT to real, without telling the routine of what length should the result be: odd or even.
2.) When performing real to complex FFT, the size of the result is bigger than the size of the source data. This requires that the initial data is stored in to an array which allocates more memory then occupied by the source (2 real numbers more)

fsfPack

Pack's the complex numbers together. The side effect of this is that each complex number is now no longer alligned with the complex array. The Re(1) is now stored at position of Im(0), Im(1) at position of Re(1) and so on. The advantages of this format are:

1.) the inverse is uniformly defined, even for odd length FFT. If the source data was odd in length, so will be the result also. If the (real) source data was even in length, the result will also require an even number of (real) array elements.
2.) The storage requirements before and affter the FFT will remain the same. There is no need for a memory resize.

The complex array missalignment can be worked around with the help of the SetSubRange method.

fsfPerm

Stores the Re(d) element at position of Im(0). The side effect is that for even length real source, the complex numbers will be alligned with the complex array, but for odd length FFT they will be not. The advantages of this format are:

1.) the inverse is uniformly defined, even for odd length FFT. If the source data was odd in length, so will be the result also. If the (real) source data was even in length, the result will also require an even number of (real) array elements. 2.) The storage requirements before and after the FFT will remain the same. There is no need for a memory resize.

The complex array missalignment can be worked around with the help of the SetSubRange method.

Description

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:


  (Re(0), Im(0)), (Re(1), Im(1)),...,(Re(d), Im(d)), ... , (Re(N-1), Im(N-1))

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


  (Re(0), Im(0)), (Re(1), Im(1)),...,(Re(d), Im(d))

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)


    Re(1,1)     0         Re(1,2)     Im(1,2)     ... Re(1,k)     Im(1,k)     Re(1,k+1)     0
    0           0         0           0           ... 0           0           0             0
    Re(2,1)     Re(2,2)   Re(2,3)     Re(2,4)     ... Re(2,n-1)   Re(2,n)     n/u         n/u
    Im(2,1)     Im(2,2)   Im(2,3)     Im(2,4)     ... Im(2,n-1)   Im(2,n)     n/u         n/u
    ...         ...       ...         ...         ... ...         ...         n/u         n/u
    Re(m/2,1)   Re(m/2,2) Re(m/2,3)   Re(m/2,4)   ... Re(m/2,n-1) Re(m/2,n)   n/u         n/u
    Im(m/2,1)   Im(m/2,2) Im(m/2,3)   Im(m/2,4)   ... Im(m/2,n-1) Im(m/2,n)   n/u         n/u
    Re(m/2+1,1) 0         Re(m/2+1,2) Im(m/2+1,2) ... Re(m/2+1,k) Im(m/2+1,k) Re(m/2+1,k+1) 0
    0           0         0           0           ... 0           0           n/u         n/u

Odd length (m = s*2+1)


    Re(1,1)     0           Re(1,2)     Im(1,2)     ...   Re(1,k)       Im(1,k)     Re(1,k+1) 0
    0           0           0           0           ...   0             0           0         0
    Re(2,1)     Re(2,2)     Re(2,3)     Re(2,4)     ...   Re(2,n-1)     Re(2,n)     n/u     n/u
    Im(2,1)     Im(2,2)     Im(2,3)     Im(2,4)     ...   Im(2,n-1)     Im(2,n)     n/u     n/u
    ...         ...         ...         ...         ...   ...           ...         n/u     n/u
    Re(s,1)     Re(s,2)     Re(s,3)     Re(s,4)     ...   Re(s,n-1)     Re(s,n)     n/u     n/u
    Im(s,1)     Im(s,2)     Im(s,3)     Im(s,4)     ...   Im(s,n-1)     Im(s,n)     n/u     n/u

PACK format, m x n matrix

Even length (m = s*2)


    Re(1,1)     Re(1,2)     Im(1,2)     Re(1,3)     ...   Im(1,k)     Re(1,k+1)
    Re(2,1)     Re(2,2)     Re(2,3)     Re(2,4)     ...   Re(2,n-1)   Re(2,n)
    Im(2,1)     Im(2,2)     Im(2,3)     Im(2,4)     ...   Im(2,n-1)   Im(2,n)
    ...         ...         ...         ...         ...   ...         ...
    Re(m/2,1)   Re(m/2,2)   Re(m/2,3)   Re(m/2,4)   ...   Re(m/2,n-1) Re(m/2,n)
    Im(m/2,1)   Im(m/2,2)   Im(m/2,3)   Im(m/2,4)   ...   Im(m/2,n-1) Im(m/2,n)
    z(m/2+1,1)  Re(m/2+1,2) Im(m/2+1,2) Re(m/2+1,3) ...   Im(m/2+1,k) z(m/2+1,k+1)

Odd length (m = s*2+1)


    Re(1,1) Re(1,2) Im(1,2) Re(1,3) ... Im(1,k)   Re(1,n/2+1)
    Re(2,1) Re(2,2) Re(2,3) Re(2,4) ... Re(2,n-1) Re(2,n)
    Im(2,1) Im(2,2) Im(2,3) Im(2,4) ... Im(2,n-1) Im(2,n)
    ... ... ... ... ... ... ...
    Re(s,1) Re(s,2) Re(s,3) Re(s,4) ... Re(s,n-1) Re(s,n)
    Im(s,1) Im(s,2) Im(s,3) Im(s,4) ... Im(s,n-1) Im(s,n)

PERM Format, m x n matrix

Even length (m = s*2)


    Re(1,1)     Re(1,k+1)     Re(1,2)       Im(1,2)     ... Re(1,k)     Im(1,k)
    Re(m/2+1,1) Re(m/2+1,k+1) Re(m/2+1,2)   Im(m/2+1,2) ... Re(m/2+1,k) Im(m/2+1,k)
    Re(2,1)     Re(2,2)       Re(2,3)       Re(2,4)     ... Re(2,n-1)   Re(2,n)
    Im(2,1)     Im(2,2)       Im(2,3)       Im(2,4)     ... Im(2,n-1)   Im(2,n)
    ...         ...           ...           ...         ... ...         ...
    Re(m/2,1)   Re(m/2,2)     Re(m/2,3)     Re(m/2,4)   ... Re(m/2,n-1) Re(m/2,n)
    Im(m/2,1)   Im(m/2,2)     Im(m/2,3)     Im(m/2,4)   ... Im(m/2,n-1) Im(m/2,n)

Odd length (m = s*2+1)


    Re(1,1)     Re(1,k+1)     Re(1,2)       Im(1,2)     ... Re(1,k)     Im(1,k)
    Re(2,1)     Re(2,2)       Re(2,3)       Re(2,4)     ... Re(2,n-1)   Re(2,n)
    Im(2,1)     Im(2,2)       Im(2,3)       Im(2,4)     ... Im(2,n-1)   Im(2,n)
    ...         ...           ...           ...         ... ...         ...
    Re(s,1)     Re(s,2)       Re(s,3)       Re(s,4)     ... Re(s,n-1)   Re(s,n)
    Im(s,1)     Im(s,2)       Im(s,3)       Im(s,4)     ... Im(s,n-1)   Im(s,n)