The result of the forward transform (that is, in the frequency domain) of real data is represented in several possible packed formats: Pack, Perm, CCS, or CCE. The data can be packed due to the symmetry property of the FFT of real data.
Use the following non-default settings for real transforms of all ranks:
- The configuration parameter DFTI_CONJUGATE_EVEN_STORAGE has the value of DFTI_COMPLEX_COMPLEX.
- Elements of the result in the conjugate-even domain have a complex type.
- The configuration parameter DFTI_PACKED_FORMAT has the value of DFTI_CCE_FORMAT.
The following setting is the default for one-dimensional and two-dimensional real transforms:
- The configuration parameter DFTI_CONJUGATE_EVEN_STORAGE has the value of DFTI_COMPLEX_REAL.
- Data elements in the frequency domain have a real type.
- The value of DFTI_PACKED_FORMAT defines how real and imaginary parts of the data are laid out in the result.
Note
This setting does not apply to three-dimensional and higher-rank transforms. Though not recommended, it is the default for backward compatibility.
The CCE format stores the values of the first half of the output complex conjugate-even signal resulting from the forward FFT. For a multi-dimensional real transform, n1 * n2 * n3 * ... * nk the size of complex matrix in CCE format is (n1/2+1)* n2 * n3 * ... * nk for Fortran and n1 * n2 * ... * (nk/2+1) for C.
The CCS format is similar to the CCE format and is the same format for one-dimensional transform. It differs slightly for multi-dimensional real transforms. In CCS format, the output samples of the FFT are arranged as shown in Table "Packed Format Output Samples" for a one-dimensional FFT and in Table "CCS Format Output Samples (Two-Dimensional Matrix (m+2)-by-(n+2))" for a two-dimensional FFT.
The Pack format is a compact representation of a complex conjugate-symmetric sequence, but the elements are arranged intuitively for complex FFT algorithms rather than for real FFTs. In the Pack format, the output samples of the FFT are arranged as shown in Table "Packed Format Output Samples" for one-dimensional FFT and in Table "Pack Format Output Samples (Two-Dimensional Matrix m-by-n)" for two-dimensional FFT.
The Perm format is a permutation of the Pack format for even lengths and is the same as the Pack format for odd lengths. In Perm format, the output samples of the FFT are arranged as shown in Table "Packed Format Output Samples" for a one-dimensional FFT and in Table "Perm Format Output Samples (Two-Dimensional Matrix m-by-n)" for a two-dimensional FFT.
|
For n = 2*s |
|||||||||
|---|---|---|---|---|---|---|---|---|---|
|
FFT Real |
0 |
1 |
2 |
3 |
... |
n-2 |
n-1 |
n |
n+1 |
|
CCS |
R0 |
0 |
R1 |
I1 |
... |
Rn/2-1 |
In/2-1 |
Rn/2 |
0 |
|
Pack |
R0 |
R1 |
I1 |
R2 |
... |
In/2-1 |
Rn/2 |
|
|
|
Perm |
R0 |
Rn/2 |
R1 |
I1 |
... |
Rn/2-1 |
In/2-1 |
|
|
|
For n = 2*s + 1 |
|||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
|
FFT Real |
0 |
1 |
2 |
3 |
... |
n-4 |
n-3 |
n-2 |
n-1 |
n |
n+1 |
|
CCS |
R0 |
0 |
R1 |
I1 |
... |
Is-2 |
Rs-1 |
Is-1 |
Rs |
Is |
|
|
Pack |
R0 |
R1 |
I1 |
R2 |
... |
Rs-1 |
Is-1 |
Rs |
Is |
|
|
|
Perm |
R0 |
R1 |
I1 |
R2 |
... |
Rs-1 |
Is-1 |
Rs |
Is |
|
|
Note that Table "Packed Format Output Samples" uses the following notation for complex data entries:
Rj = Re zj
Ij = Im zj
See also Table "Comparison of the Storage Effects of Complex-to-Complex and Real-to-Complex FFTs for Forward Transform" and Table "Comparison of the Storage Effects of Complex-to-Complex and Complex-to-Real FFTs for Backward Transform".
|
For m = 2*s, n = 2*k |
||||||||
|---|---|---|---|---|---|---|---|---|
|
z(1,1) |
0 |
REz(1,2) |
IMz(1,2) |
... |
REz(1,k) |
IMz(1,k) |
z(1,k+1) |
0 |
|
0 |
0 |
0 |
0 |
... |
0 |
0 |
0 |
0 |
|
REz(2,1) |
REz(2,2) |
REz(2,3) |
REz(2,4) |
... |
REz(2,n-1) |
REz(2,n) |
n/u* |
n/u |
|
IMz(2,1) |
IMz(2,2) |
IMz(2,3) |
IMz(2,4) |
... |
IMz(2,n-1) |
IMz(2,n) |
n/u |
n/u |
|
... |
... |
... |
... |
... |
... |
... |
n/u |
n/u |
|
REz(m/2,1) |
REz(m/2,2) |
REz(m/2,3) |
REz(m/2,4) |
... |
REz(m/2,n-1) |
REz(m/2,n) |
n/u |
n/u |
|
IMz(m/2,1) |
IMz(m/2,2) |
IMz(m/2,3) |
IMz(m/2,4) |
... |
IMz(m/2,n-1) |
IMz(m/2,n) |
n/u |
n/u |
|
z(m/2+1,1) |
0 |
REz(m/2+1,2) |
IMz(m/2+1,2) |
... |
REz(m/2+1,k) |
IMz(m/2+1,k) |
z(m/2+1,k+1) |
0 |
|
0 |
0 |
0 |
0 |
... |
0 |
0 |
n/u |
n/u |
|
For m = 2*s+1, n = 2*k |
||||||||
|---|---|---|---|---|---|---|---|---|
|
z(1,1) |
0 |
REz(1,2) |
IMz(1,2) |
... |
REz(1,k) |
IMz(1,k) |
z(1,k+1) |
0 |
|
0 |
0 |
0 |
0 |
... |
0 |
0 |
0 |
0 |
|
REz(2,1) |
REz(2,2) |
REz(2,3) |
REz(2,4) |
... |
REz(2,n-1) |
REz(2,n) |
n/u |
n/u |
|
IMz(2,1) |
IMz(2,2) |
IMz(2,3) |
IMz(2,4) |
... |
IMz(2,n-1) |
IMz(2,n) |
n/u |
n/u |
|
... |
... |
... |
... |
... |
... |
... |
n/u |
n/u |
|
REz(s,1) |
REz(s,2) |
REz(s,3) |
REz(s,4) |
... |
REz(s,n-1) |
REz(s,n) |
n/u |
n/u |
|
IMz(s,1) |
IMz(s,2) |
IMz(s,3) |
IMz(s,4) |
... |
IMz(s,n-1) |
IMz(s,n) |
n/u |
n/u |
|
For m = 2*s, n = 2*k+1 |
|||||||
|---|---|---|---|---|---|---|---|
|
z(1,1) |
0 |
REz(1,2) |
IMz(1,2) |
... |
IMz(1,k-1) |
REz(1,k) |
IM z(1,k) |
|
0 |
0 |
0 |
0 |
... |
0 |
0 |
0 |
|
REz(2,1) |
REz(2,2) |
REz(2,3) |
REz(2,4) |
... |
REz(2,n-1) |
REz(2,n) |
n/u* |
|
IMz(2,1) |
IMz(2,2) |
IMz(2,3) |
IMz(2,4) |
... |
IMz(2,n-1) |
IMz(2,n) |
n/u |
|
... |
... |
... |
... |
... |
... |
... |
n/u |
|
REz(m/2,1) |
REz(m/2,2) |
REz(m/2,3) |
REz(m/2,4) |
... |
REz(m/2,n-1) |
REz(m/2,n) |
n/u |
|
IMz(m/2,1) |
IMz(m/2,2) |
IMz(m/2,3) |
IMz(m/2,4) |
... |
IMz(m/2,n-1) |
IMz(m/2,n) |
n/u |
|
z(m/2+1,1) |
0 |
REz(m/2+1,2) |
IMz(m/2+1,2) |
... |
IMz(m/2+1,k-1) |
REz(m/2+1,k) |
IMz(m/2+1,k) |
|
0 |
0 |
0 |
0 |
... |
0 |
0 |
n/u |
|
For m = 2*s+1, n = 2*k+1 |
|||||||
|---|---|---|---|---|---|---|---|
|
z(1,1) |
0 |
REz(1,2) |
IMz(1,2) |
... |
IMz(1,k-1) |
REz(1,k) |
IMz(1,k) |
|
0 |
0 |
0 |
0 |
... |
0 |
0 |
0 |
|
REz(2,1) |
REz(2,2) |
REz(2,3) |
REz(2,4) |
... |
REz(2,n-1) |
REz(2,n) |
n/u |
|
IMz(2,1) |
IMz(2,2) |
IMz(2,3) |
IMz(2,4) |
... |
IMz(2,n-1) |
IMz(2,n) |
n/u |
|
... |
... |
... |
... |
... |
... |
... |
n/u |
|
REz(s,1) |
REz(s,2) |
REz(s,3) |
REz(s,4) |
... |
REz(s,n-1) |
REz(s,n) |
n/u |
|
IMz(s,1) |
IMz(s,2) |
IMz(s,3) |
IMz(s,4) |
... |
IMz(s,n-1) |
IMz(s,n) |
n/u |
Note that in the Table "CCS Format Output Samples (Two-Dimensional Matrix (m+2)-by-(n+2))", (n+2) columns are used for even n = k*2, while n columns are used for odd n = k*2+1.
|
For m = 2*s, n = 2*k |
||||||
|---|---|---|---|---|---|---|
|
z(1,1) |
REz(1,2) |
IMz(1,2) |
REz(1,3) |
... |
IMz(1,k) |
z(1,k+1) |
|
REz(2,1) |
REz(2,2) |
REz(2,3) |
REz(2,4) |
... |
REz(2,n-1) |
REz(2,n) |
|
IMz(2,1) |
IMz(2,2) |
IMz(2,3) |
IMz(2,4) |
... |
IMz(2,n-1) |
IMz(2,n) |
|
... |
... |
... |
... |
... |
... |
... |
|
REz(m/2,1) |
REz(m/2,2) |
REz(m/2,3) |
REz(m/2,4) |
... |
REz(m/2,n-1) |
REz(m/2,n) |
|
IMz(m/2,1) |
IMz(m/2,2) |
IMz(m/2,3) |
IMz(m/2,4) |
... |
IMz(m/2,n-1) |
IMz(m/2,n) |
|
z(m/2+1,1) |
REz(m/2+1,2) |
IMz(m/2+1,2) |
REz(m/2+1,3) |
... |
IMz(m/2+1,k) |
z(m/2+1,k+1) |
|
For m = 2*s+1, n = 2*k |
||||||
|---|---|---|---|---|---|---|
|
z(1,1) |
REz(1,2) |
IMz(1,2) |
REz(1,3) |
... |
IMz(1,k) |
z(1,n/2+1) |
|
REz(2,1) |
REz(2,2) |
REz(2,3) |
REz(2,4) |
... |
REz(2,n-1) |
REz(2,n) |
|
IMz(2,1) |
IMz(2,2) |
IMz(2,3) |
IMz(2,4) |
... |
IMz(2,n-1) |
IMz(2,n) |
|
... |
... |
... |
... |
... |
... |
... |
|
REz(s,1) |
REz(s,2) |
REz(s,3) |
REz(s,4) |
... |
REz(s,n-1) |
REz(s,n) |
|
IMz(s,1) |
IMz(s,2) |
IMz(s,3) |
IMz(s,4) |
... |
IMz(s,n-1) |
IMz(s,n) |
|
For m = 2*s, n = 2*k+1 |
||||||
|---|---|---|---|---|---|---|
|
z(1,1) |
z(1,k+1) |
REz(1,2) |
IMz(1,2) |
... |
REz(1,k) |
IMz(1,k) |
|
z(m/2+1,1) |
z(m/2+1,k+1) |
REz(m/2+1,2) |
IMz(m/2+1,2) |
... |
REz(m/2+1,k) |
IMz(m/2+1,k) |
|
REz(2,1) |
REz(2,2) |
REz(2,3) |
REz(2,4) |
... |
REz(2,n-1) |
REz(2,n) |
|
IMz(2,1) |
IMz(2,2) |
IMz(2,3) |
IMz(2,4) |
... |
IMz(2,n-1) |
IMz(2,n) |
|
... |
... |
... |
... |
... |
... |
... |
|
REz(m/2,1) |
REz(m/2,2) |
REz(m/2,3) |
REz(m/2,4) |
... |
REz(m/2,n-1) |
REz(m/2,n) |
|
IMz(m/2,1) |
IMz(m/2,2) |
IMz(m/2,3) |
IMz(m/2,4) |
... |
IMz(m/2,n-1) |
IMz(m/2,n) |
|
For m = 2*s+1, n = 2*k+1 |
||||||
|---|---|---|---|---|---|---|
|
z(1,1) |
z(1,k+1) |
REz(1,2) |
IMz(1,2) |
... |
REz(1,k) |
IMz(1,k) |
|
REz(2,1) |
REz(2,2) |
REz(2,3) |
REz(2,4) |
... |
REz(2,n-1) |
REz(2,n) |
|
IMz(2,1) |
IMz(2,2) |
IMz(2,3) |
IMz(2,4) |
... |
IMz(2,n-1) |
IMz(2,n) |
|
... |
... |
... |
... |
... |
... |
... |
|
REz(s,1) |
REz(s,2) |
REz(s,3) |
REz(s,4) |
... |
REz(s,n-1) |
REz(s,n) |
|
IMz(s,1) |
IMz(s,2) |
IMz(s,3) |
IMz(s,4) |
... |
IMz(s,n-1) |
IMz(s,n) |
The tables for two-dimensional FFT use Fortran-interface conventions. For C-interface specifics in storing packed data, see DFTI_COMPLEX_STORAGE, DFTI_REAL_STORAGE, DFTI_CONJUGATE_EVEN_STORAGE. See also Table "Fortran-interface Data Layout for a 6-by-4 Matrix" and Table "C-interface Data Layout for a 6-by-4 Matrix" for examples of Fortran-interface and C-interface formats.
To better understand packed formats for two-dimensional transforms, refer to these examples in your Intel MKL directory:
C: |
./examples/dftc/source/config_conjugate_even_storage.c |
Fortran: |
./examples/dftf/source/config_conjugate_even_storage.f90 |