# Packed formats

The result of the forward transform (i.e. 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 a real data.

The CCE format stores the values of the first half of the output complex conjugate-even signal resulted from the forward FFT. Note that the one-dimensional signal stored in CCE format is one complex element longer. For 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 looks like the CCE format. It is the same format as CCE for one-dimensional transform. The CCS format is slightly different for multi-dimensional real transform. In CCS format, the output samples of the FFT are arranged as shown in Table “Packed Format Output Samples” for one-dimensional FFT and in Table “CCS Format Output Samples (Two-Dimensional Matrix (m+2)-by-(n+2))” for two-dimensional FFT.

The Pack format is a compact representation of a complex conjugate-symmetric sequence. The disadvantage of this format is that it is not the natural format used by the real FFT algorithms ("natural" in the sense that array is natural for complex FFTs). In 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 an arbitrary permutation of the Pack format for even lengths and one 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 one-dimensional FFT and in Table “Perm Format Output Samples (Two-Dimensional Matrix m-by-n)” for two-dimensional FFT.

Packed Format Output Samples
For n = s*2
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 = s*2 + 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”.

CCS Format Output Samples (Two-Dimensional Matrix (m+2)-by-(n+2))
For m = s*2, n = k*2
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 = s*2+1, n = k*2
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 = s*2, n = k*2+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 = s*2+1, n = k*2+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

* n/u - not used.

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`. In the latter case, the first row is

`z(1,1) 0 REz(1,2) IMz(1,2) ... REz(1,k) IMz(1,k)`

If m is even, the (`m+1`)-th row is

`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)`

Pack Format Output Samples (Two-Dimensional Matrix m-by-n)
For m = s*2
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 = s*2+1
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)

Perm Format Output Samples (Two-Dimensional Matrix m-by-n)
For m = s*2
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 = s*2+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)

Note that in the Table “Pack Format Output Samples (Two-Dimensional Matrix m-by-n)” and Table “Perm Format Output Samples (Two-Dimensional Matrix m-by-n)”, for even number of columns `n = k*2`, while for odd number of columns `n = k*2+1` and the first row is

`z(1,1) REz(1,2) IMz(1,2) ... REz(1,k) IMz(1,k)`

If m is even, the last row in Pack format and the second row in Perm format is

`z(m/2+1,1) REz(m/2+1,2) IMz(m/2+1,2) ... REz(m/2+1,k) IMz(m/2+1,k)`

The tables for two-dimensional FFT use Fortran-interface conventions. For C-interface specifics in storing packed data, see Storage schemes. 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.

Parent topic: Configuration Settings