Real Time Domain#

Real time domain, complex frequency domain

Background#

If $x_0, x_1, \ldots , x_{N-1}$ are real numbers and $\mathbf{X} = \mathcal{F}(\mathbf{x})$ , then

$X_k = X^*_{-k \bmod N} \quad \forall\, k \in \{0, 1, \ldots , N-1\}$

where the star denotes complex conjugation.

As a special case, note that

$X_0 = X^*_0 \quad\Rightarrow\quad X_0 \mathrm{\ is \ real.}$

Also, if $N$ is even,

$-N\!/2 \,\equiv\, N\!/2 \!\!\pmod{N} \quad\Rightarrow\quad X_{N\!/2} = X^*_{N\!/2} \quad\Rightarrow\quad X_{N\!/2} \mathrm{\ is \ real.}$

For the multidimensional case, the conjugate symmetry is similar:

$X_{k_0,k_1,\ldots ,k_{d-1}} = X^*_{-k_0,-k_1,\ldots ,-k_{d-1}} \quad \forall\, k_l \in \{0, 1, \ldots , N_l-1\}$

where each $-k_l$ above is understood to be modulo $N_l$ . That is,

$-k_l \,\equiv\, N_l - k_l \!\!\pmod{N_l} \quad \forall\, l \in \{0, 1, \ldots , d-1\}\mathrm{.}$

Examples:

1. Consider the following sequence of six complex numbers whose imaginary parts all happen to be zero:

$\mathbf{x} = \big\langle(4.667,0),\,(-2.643,0),\,(2.821,0),\,(1.667,0),\, (0.512,0),\,(1.976,0)\big\rangle$

Then we can use a complex FFT to compute

$\mathcal{F}(\mathbf{x}) \approx \big\langle(9,0),\,(1,2),\,(5,6),\,(7,0),\,(5,-6),\,(1,-2)\big\rangle$

Note that $X_0$ and $X_3$ are real and that $X_1 = X^*_5$ and $X_2 = X^*_4$ .

2. Consider the following sequence of seven complex numbers whose imaginary parts are all zero:

$\mathbf{x} = \big\langle(5.000,0),\,(-3.766,0),\,(3.156,0),\,(0.338,0),\, (2.610,0),\,(-0.792,0),\,(2.454,0)\big\rangle$

Then,

$\mathcal{F}(\mathbf{x}) \approx \big\langle(9,0),\,(1,2),\,(5,6),\,(7,8),\, (7,-8),\,(5,-6),\,(1,-2)\big\rangle$

Note that $X_0$ is real, $X_1 = X^*_6$ , $X_2 = X^*_5$ , and $X_3 = X^*_4$ .

3. Consider a three-dimensional FFT of real data having 9 slabs, each of which has 7 rows and 6 columns. That is,

$N_0 = 9,\; N_1 = 7,\; N_2 = 6$

Then

$\begin{array}{cl} X_{0,0,0}\!\! &= X^*_{0, 0, 0} \mathrm{\ (i.e., real)} \\[1ex] X_{0,0,1}\!\! &= X^*_{0, 0, 5} \\[1ex] X_{0,0,3}\!\! &= X^*_{0, 0, 3} \mathrm{\ (i.e., real)} \\[1ex] X_{1,1,1}\!\! &= X^*_{8, 6, 5} \\[1ex] X_{1,2,3}\!\! &= X^*_{8, 5, 3} \\[1ex] &\;\vdots \end{array}$

Data Layout#

The data representation of points in the time domain is self-evident; each point is a single real value. Given an N-point FFT, there are N real numbers in the time domain. For a 1-dimensional FFT, the points must be adjacent, i.e., the timeStride should be 0 or explicitly set to 1. For a multidimensional FFT, the points in each row must be adjacent, but additional padding is allowed between rows, between slabs, etc. In other words, the timeStride for the last dimension must be 0 or 1 (these are equivalent).

The data representation for the frequency domain is complex. For out-of-place transforms, freqStride for the last dimension must be 0 or 2.

Given the mathematical symmetry of the frequency data, one does not wish to compute and store N complex frequency values when the time domain has only N real values. Therefore, we adopt the following policy: each row in the frequency domain will have the following number of complex values:

$\bigg\lfloor \frac{N}{2} \bigg\rfloor + 1$

and the rest of the row will be truncated (not found in memory). While this is not the most compact scheme one might invent, it is simple and eliminates nearly all of the redundancy. Note that the size of a row in the frequency domain is slightly larger than the size of a row in the time domain, for the total number of real or imaginary values in a frequency row is

$\left\{\begin{array}{ll} N + 2 & \quad \mathrm{if\ } N \mathrm{\ is\ even}\\ N + 1 & \quad \mathrm{if\ } N \mathrm{\ is\ odd}\\ \end{array}\right.$

As C++ expressions, the number of complex values per frequency row is

(N >> 1) + 1

and the number of real or imaginary values per frequency row is twice that, i.e.,

(N | 0x1) + 1

where N is the number of real values per row in the time domain.

For Inplace transforms, sufficient padding must follow each row in the time domain to account for the space needed to store the frequency values. If the timeStride between rows is set (or defaults) to 0, this necessary padding is assumed. This applies both to the stride between transforms in a batch of 1-dimensional FFTs as well as to the stride between rows of a multidimensional FFT.

For Ooplace transforms, no padding is needed. If the timeStride between rows is set (or defaults) to 0, no padding is assumed after each time row. If the freqStride between rows is set (or defaults) to 0, no padding is assumed after each frequency row. Note, however, that the frequency domain data is slightly larger than the time domain data, and memory must be allocated accordingly.

Examples:

For all the examples below, first make a FactoryRC<double>

std::unique_ptr factory =
        hpk::fft::makeFactory<double, double, std::complex<double>>();

then

Consider a 1-dimensional time sequence of six real numbers

std::vector<double> x{4.667, -2.643, 2.821, 1.667, 0.512, 1.976};

Ooplace

auto fft = factory->makeOoplace<1>({6});  // equivalently, {{6, 1, 2}}
std::vector<double> X(8);
fft->forwardCopy(x.data(), X.data());
// X is approximately {9.0, 0.0,  1.0, 2.0,  5.0, 6.0,  7.0, 0.0}

Inplace

auto fft = factory->makeInplace<1>({6});  // equivalently, {{6, 1}}
x.resize(8);
fft->forward(x.data());
// x is approximately {9.0, 0.0,  1.0, 2.0,  5.0, 6.0,  7.0, 0.0}

Consider a 1-dimensional time sequence of seven real numbers

std::vector<double> x{5.000, -3.766, 3.156, 0.338, 2.610, -0.792, 2.454};

Ooplace

auto fft = factory->makeOoplace<1>({7});  // equivalently, {{7, 1, 2}}
std::vector<double> X(8);
fft->forwardCopy(x.data(), X.data());
// X is approximately {9.0, 0.0,  1.0, 2.0,  5.0, 6.0,  7.0, 8.0}

auto fft = factory->makeOoplace<1>({7});  // equivalently, {{7, 1, 2}}
std::vector<std::complex<double>> X(4);
fft->forwardCopy(x.data(), X.data());
// X is approximately {{9.0, 0.0}, {1.0, 2.0}, {5.0, 6.0}, {7.0, 8.0}}

Inplace

auto fft = factory->makeInplace<1>({7});  // equivalently, {{7, 1}}
x.resize(8);
fft->forward(x.data());
// x is approximately {9.0, 0.0,  1.0, 2.0,  5.0, 6.0,  7.0, 8.0}

Consider a three-dimensional FFT of real data having 9 slabs, each of which has 7 rows and 6 columns.

Ooplace (no padding between rows, neither in time nor in frequency)

auto fft = factory->makeOoplace<3>({ 9         ,  7       ,  6       });
                  // equivalently, {{9, 42, 56}, {7, 6, 8}, {6, 1, 2}}
std::vector<double> x(378);
x[0] = 1.0;  // unit impulse
std::vector<double> X(504);
fft->forwardCopy(x.data(), X.data());

Inplace (2 real padding values at end of each time row)

auto fft = factory->makeInplace<3>({ 9     ,  7    ,  6    });
                  // equivalently, {{9, 56}, {7, 8}, {6, 1}}
std::vector<double> x(504);
x[0] = 1.0;  // unit impulse
fft->forward(x.data());

Additional real time domain examples are in fft_rc.cpp.