Impementing SlidingDFTs

SlidingDFTs provides an interface to define new methods to compute Sliding Discrete Fourier Transforms (SDFT), which can be implemented in pull requests to this package, but also in independent packages.

Theoretical basis

An SDFT is generally implemented as a recursive equation, such that if $X_{i}[k]$ is the DFT of $x[j]$ for $j = i, \ldots, i+n$ at frequency $k$, the next iteration is:

\[X_{i+1}[k] = f(k, X_{1}[k], \ldots, X_{i}[k], x[i], \ldots x[i+n], x[i+n+1])\]

Such an equation depends on:

The frequency $k$
The values of the DFT in one or more previous iterations, $X_{p}[k]$ for $p = 1, \ldots, i$.
The values of the data series used in the most recent iteration, $x[j]$ for $j = i, \ldots, i+n$.
The next value of the data series after the fragment used in the most recent iteration, $x[i+n+1]$.

For instance, the basic definition of the SDFT uses the following formula:

\[X_{i+1}[k] = W[k] \cdot (X_{i}[k] + x[i+n] - x[i]),\]

which depends only on the most recent DFT ($X_{i}[k]$), the first data point of the fragment used in that DFT ($x[i]$), and the next data point after that fragment ($x[i+n+1]$), plus a "twiddle" factor $W[k]$ that only depends on the frequency $k$, equal to $\exp(j2{\pi}k/n)$. Other variations of the SDFT may use formulas that depend on previous iterations or other values of the data series in that fragment.

Implementation in Julia object types

A method to compute an SDFT is defined by three kinds of object types:

One for the method, which contains the fixed parameters that are needed by the algorithm to compute the SDFT.
Another for the iterator created by the function sdft, which binds a method with the target data series.
And yet another for the state of the iterator, which holds the information needed by the algorithm that depends on the data series and changes at each iteration.

The internals of SlidingDFTs take care of the design of the iterator and state types, and of the creation of their instances. The only thing that has to be defined to create a new kind of SDFT is the struct of the method with the fixed parameters, and a few function methods dispatching on that type. One of those functions is the one that implements the recursive formula, using also the information stored in the state.

Extract information from the state of SDFT iterators

Before explaining how to define a new type for SDFTs, it is convenient to know the functions that can be used to extract the information that is stored in the state of SDFT iterators. There is a function for each of the three kinds of variables used in the general recursive equation presented above.

SlidingDFTs.previousdft — Function

previousdft(state[, back=0])

Return the DFT computed in the most recent iteration of the sliding DFT represented by state, or in a number of previous iterations equal to back.

If the DFT computed in the most recent iteration corresponds to the fragment of the data series between its positions i and i+n, then this function returns its DFT for the fragment between i-back and i+n-back.

source

SlidingDFTs.previousdata — Function

previousdata(state[, offset=0])

Return the first value of the fragment of the data series that was used in the most recent iteration of the sliding DFT represented by state, or at offset positions after the beginning of that fragment.

If the DFT computed in the most recent iteration corresponds to the fragment of the data series between its positions i and i+n, then this function returns the i+offset-th value.

source

SlidingDFTs.nextdata — Function

nextdata(state)

Return the next value after the fragment of the data series that was used in the most recent iteration of the sliding DFT represented by state.

If the DFT computed in the most recent iteration corresponds to the fragment of the data series between its positions i and i+n, then this function returns the i+n+1-th value.

There is no defined behavior if such value does not exist (i.e. if the end of a finite data series was reached).

source

For instance, the values used in the formula of the basic SDFT may be obtained from a state object as:

SlidingDFTs.previousdft(state, 0) for $X_{i}$.
SlidingDFTs.previousdata(state, 0) for $x[i]$.
SlidingDFTs.nextdata(state) for $x[i+n+1]$.

Notice that the second arguments of previousdft and previousdata might have been ommited in this case, since they are zero by default.

For methods that need to know how many steps of the SDFT have been done, this can also be extracted:

SlidingDFTs.iterationcount — Function

iterationcount(state)

Return the number of iterations done for the sliding DFT represented by state.

If the DFT computed in the most recent iteration corresponds to the fragment of the data series between its positions i and i+n, then this function returns the number i.

source

Definition of new SDFT types

The design of the struct representing a new SDFT type is free, but it is required to implement the following methods dispatching on that type:

SlidingDFTs.windowlength — Function

SlidingDFTs.windowlength(method)

Return the length of the window used by method.

source

SlidingDFTs.updatedft! — Function

updatedft!(dft, x, method, state)

Update the values of a sliding Discrete Fourier Transform (DFT) of a data series, according to the algorithm of the provided method, for a given state of the sliding DFT.

dft is a mutable collection of complex values with length equal to windowlength(method), containing the value returned by the last iteration of the sliding DFT.

x is the data series for which the sliding DFT is computed, at least as long as windowlength(method).

method is the object that defines the method to compute the sliding DFT.

state is an object generated automatically at each iteration of an object created by sdft(method, x), containing the information that is needed to compute the new values of the sliding DFT, together with x. That information can be extracted from state with the following functions:

SlidingDFTs.previousdft to get the DFTs of previous iterations.
SlidingDFTs.previousdata to get a previous value of the data series.
SlidingDFTs.nextdata to get the next value of the data series.

source

The formula of the basic SDFT formula could be implemented for a type MyBasicSDFT as follows:

import SlidingDFTs: updatedft!, windowlength, nextdata, previousdata

function udpatedft!(dft, x, method::MyBasicSDFT, state)
    n = windowlength(method)
    for k in eachindex(dft)
        X_i = dft[k]
        x_iplusn = nextdata(state)
        x_i = previousdata(state)
        Wk = exp(2π*im*k/n)
        dft[k] = Wk * (X_i + x_iplusn - x_i)
    end
end

(The type SDFT implemented in SlidingDFTs actually has as a similar, but not identic definition.)

Notice that it was not necessary to use previousdft to retrieve the most recent iteration of the DFT, since that is assummed to be already contained in the first argument dft.

Depending on the functions that are used in the particular implementation of updatepdf! for a given type, the following methods should be defined too:

SlidingDFTs.dftback — Function

dftback(method)

Return an integer or a vector of positive integers with the indices of the previous iterations that are needed by the given method to compute a sliding DFT.

If the code of SlidingDFTs.updatepdf! for the type of method uses the function SlidingDFTs.previousdft, this function must return the integers that are used as the third argument (back) of that function.

If that function is not needed, this one may return nothing to reduce memory allocations.

source

SlidingDFTs.dataoffsets — Function

dataoffsets(method)

Return an integer or a vector of integers with the offsets of data samples that are needed by the given method to compute a sliding DFT.

If the code of SlidingDFTs.updatepdf! that dispatches on the type of method uses the function SlidingDFTs.previousdata, this function must return the integers that are used as the third argument (offset) of that function.

If that function is not needed (no past samples are used), this one may return nothing to reduce memory allocations.

source

The fallback methods of those functions return nothing, as if neither previousdata or previousdft had to be used.

The implementation of updatepdf! given in the previous example does use previousdata - with the default offset value, equal to zero - so the following is required in this case:

SlidingDFTs.dataoffsets(::MyBasicSDFT) = 0

On the other hand there is no need to define SlidingDFTs.dftback in this case, since as it has been noted above, the interface of of updatedft! assumes that the most recent DFT is already contained in its first argument, so it is not necessary to use the function previousdft to get it.