# Real Time Domain#

Real time domain, complex frequency domain

## Background#

If are real numbers and , then

where the star denotes complex conjugation.

As a special case, note that

Also, if is even,

For the multidimensional case, the conjugate symmetry is similar:

where each above is understood to be modulo . That is,

**Examples:**

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

Then we can use a complex FFT to compute

Note that and are real and that and .

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

Then,

Note that is real, , , and .

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

Then

## 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:

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

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}

or

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.