Discrete Fourier Transform¶

High-performance FFT, convolution, and spectral analysis routines.

A¶

variable dft_plan<T>::all_stages Internal data.
variable dft_plan<T>::arblen True if Bluestein's FFT algorithm is selected.
function autocorrelate(const univector<T, Tag1> &) Computes the auto-correlation of a real or complex signal.

B¶

typedef dft_plan<T>::bitset
variable convolve_filter<T>::block_size
variable dft_stage<T>::blocks Number of independent blocks processed by the stage.
enum constant dft_type::both Both direct and inverse transforms.

C¶

function dft_plan<T>::calc_disposition() Internal function
variable dft_stage<T>::can_inplace Whether the stage can operate in-place.
enum constant dft_pack_format::CCs Conjugate-symmetric format: {DC, 0}, X[1], X[2], ..., X[N/2-1], {Nyquist, 0} The number of complex samples is
typedef cdirect_t Tag type selecting the direct (forward) DFT direction.
typedef cinvert_t Tag type selecting the inverse DFT direction.
function dft_cache_impl<int>::clear()
function dft_plan_real<T>::complex_size() Returns the number of complex samples produced/consumed.
function dft_plan_md_real<T, Dims>::complex_size() Returns the shape of the complex (packed) spectrum.
function dft_plan_md_real<T, Dims>::complex_size_for(shape<Dims>) Returns the complex spectrum shape for a given real shape.
function dft_plan_real<T>::complex_size_for(size_t, dft_pack_format) Returns the number of complex samples for a given real size and format.
function dft_resampler<T>::compute_block_size(size_t, T, T) Computes the minimal power-of-two block size required for the given filter parameters (Kaiser formula).
class convolve_filter<T> Streaming convolution filter using the overlap-add (block convolution) method.
constructor convolve_filter<T>::convolve_filter<T>(const univector_ref<const T> &, size_t) Constructs a filter and initializes its kernel from data .
constructor convolve_filter<T>::convolve_filter<T>(size_t, size_t) Constructs a filter with a kernel of the given length (initially zero).
function convolve(const univector<T1, Tag1> &, const univector<T2, Tag2> &) Computes the linear convolution of two real or complex signals.
function dft_stage<T>::copy_input(bool, complex<T> *, const complex<T> *, size_t) Copies the input into the stage's working buffer.
function correlate(const univector<T1, Tag1> &, const univector<T2, Tag2> &) Computes the linear correlation of two real or complex signals.
variable convolve_filter<T>::cscratch
variable dft_resampler_params::cutoff Normalised cutoff frequency (0..1], where 1.0 = Nyquist of the output rate.

D¶

variable dft_stage<T>::data Pointer to the stage's internal data buffer.
variable dft_plan<T>::data Internal data.
variable dft_stage<T>::data_size Size in bytes of the stage's internal data (e.g. twiddles).
variable dft_plan<T>::data_size Internal data size.
variable convolve_filter<T>::data_size
class dct_plan<T> Plan for computing the Discrete Cosine Transform (DCT type 2, unscaled).
constructor dct_plan<T>::dct_plan<T>(size_t) Constructs a DCT plan for the given size.
variable default_dft_algorithm
enum dft_algorithm Concrete DFT/FFT algorithm selection.
typedef dft_cache
class dft_cache_impl<int>
enum dft_decomp Decomposition direction for a butterfly pass.
enum dft_family Family of DFT algorithms (groups related algorithms).
macro DFT_MAX_STAGES
enum dft_order Specifies the desired order for DFT output (and IDFT input).
enum dft_pack_format Specifies the packing format for real DFT output data. See https://www.kfr.dev/docs/latest/dft_format/ for details
class dft_plan_md_real<T, Dims> Multidimensional real-to-complex / complex-to-real DFT plan.
constructor dft_plan_md_real<T, Dims>::dft_plan_md_real<T, Dims>(const dft_plan_md_real<T, Dims> &)
constructor dft_plan_md_real<T, Dims>::dft_plan_md_real<T, Dims>(dft_plan_md_real<T, Dims> &&)
constructor dft_plan_md_real<T, Dims>::dft_plan_md_real<T, Dims>(shape<Dims>, bool) Constructs a multidimensional real DFT plan.
class dft_plan_md<T, Dims> Multidimensional complex DFT plan.
constructor dft_plan_md<T, Dims>::dft_plan_md<T, Dims>(const dft_plan_md<T, Dims> &)
constructor dft_plan_md<T, Dims>::dft_plan_md<T, Dims>(dft_plan_md<T, Dims> &&)
constructor dft_plan_md<T, Dims>::dft_plan_md<T, Dims>(shape<Dims>) Constructs a multidimensional DFT plan for the given shape.
typedef dft_plan_ptr
typedef dft_plan_real_ptr
class dft_plan_real<T> Real-to-complex and complex-to-real 1D DFT plan.
constructor dft_plan_real<T>::dft_plan_real<T>() Constructs an empty (uninitialized) real DFT plan.
constructor dft_plan_real<T>::dft_plan_real<T>(const dft_plan_real<T> &)
constructor dft_plan_real<T>::dft_plan_real<T>(dft_plan_real<T> &&)
constructor dft_plan_real<T>::dft_plan_real<T>(size_t, dft_pack_format, bool) Constructs a real DFT plan.
class dft_plan<T> Class for performing 1D DFT/FFT.
constructor dft_plan<T>::dft_plan<T>() Constructs an empty DFT plan.
destructor dft_plan<T>::~dft_plan<T>() Destructor.
constructor dft_plan<T>::dft_plan<T>(const dft_plan<T> &) Copy constructor (deleted).
constructor dft_plan<T>::dft_plan<T>(dft_plan<T> &&) Move constructor.
constructor dft_plan<T>::dft_plan<T>(noinit, size_t, dft_order, bool)
constructor dft_plan<T>::dft_plan<T>(size_t, dft_order, bool) Constructs a DFT plan with the specified size and order.
struct dft_resampler_params Parameters for constructing a dft_resampler .
constructor dft_resampler_params::dft_resampler_params(int, fbase, fbase, fbase) Constructs resampler parameters.
class dft_resampler<T> FFT-based sample-rate converter and FIR filter using overlap-save.
constructor dft_resampler<T>::dft_resampler<T>(const dft_resampler_params &) Constructs the resampler from the given parameters.
typedef dft_stage_ptr
class dft_stage<T> Base structure representing a single DFT stage.
destructor dft_stage<T>::~dft_stage<T>() Destructor.
enum dft_type Direction(s) of DFT computation requested for a plan.
function dft(const univector<complex<T>, Tag> &) Performs the direct (forward) complex DFT using a cached plan.
enum constant dft_decomp::dif Decimation-in-frequency
enum constant dft_type::direct Only the direct (forward) transform.
variable dft_plan<T>::disposition_inplace Internal data.
variable dft_plan<T>::disposition_outofplace Internal data.
enum constant dft_decomp::dit Decimation-in-time
function dft_stage<T>::do_execute(cdirect_t, complex<T> *, const complex<T> *, u8 *) Performs the direct stage execution (implemented by derived stages).
function dft_stage<T>::do_execute(cinvert_t, complex<T> *, const complex<T> *, u8 *) Performs the inverse stage execution (implemented by derived stages).
function dft_stage<T>::do_initialize(size_t) Initializes the stage's internal data for the given DFT size.
function dft_stage<T>::dump() Prints the stage parameters to stdout for debugging.
function dft_plan<T>::dump() Dumps details of the DFT plan to stdout for inspection.
function dft_plan_md<T, Dims>::dump() Dumps details of the underlying per-axis plans to stdout.
function dft_plan_md_real<T, Dims>::dump() Dumps details of the underlying per-axis plans to stdout.

I¶

function idft(const univector<complex<T>, Tag> &) Performs the inverse complex DFT using a cached plan.
function dft_stage<T>::initialize(size_t)
function convolve_filter<T>::input_block_size() Returns the processing block size.
variable dft_resampler_params::input_block_size Computed FFT block size (power of two) satisfying the overlap-save constraint.
function dft_resampler<T>::input_block_size() Returns the input FFT block size \(N\) .
function dft_resampler<T>::input_hop() Returns the number of new input samples consumed per frame.
variable convolve_filter<T>::input_position
function dft_cache_impl<int>::instance()
enum constant dft_order::internal Possibly bit/digit-reversed, implementation-defined, may be faster to compute
enum constant dft_type::inverse Only the inverse transform.
variable convolve_filter<T>::ir_segments
function irealdft(const univector<complex<T>, Tag> &) Performs the inverse complex-to-real DFT using a cached plan.
function dft_resampler_params::is_downsampling() Returns true if this is a downsampling configuration.
function dft_resampler<T>::is_downsampling() Returns true if this resampler downsamples by factor() .
function dft_plan<T>::is_initialized() Checks whether the plan is non-empty.
function dft_plan_real<T>::is_initialized() Checks whether the plan is non-empty.
function dft_plan_md<T, Dims>::is_initialized() Checks whether the plan is non-empty.
function dft_plan_md_real<T, Dims>::is_initialized() Checks whether the plan is non-empty.

K¶

function dft_resampler<T>::kaiser_beta_from_attenuation(T) Computes the Kaiser window beta from a desired stopband attenuation.
macro KFR_DFT_ALGO_SWITCH
macro KFR_DFT_SUPPORTS_ODD_REAL

L¶

variable ngfft_plan<T>::l2fftsize Log2 of the FFT size (e.g. 16 means a 65536-point FFT).
function library_version_dft() Returns the full version string of the KFR DFT module.

N¶

variable dft_stage<T>::name Human-readable name of the stage (for
variable dft_stage<T>::need_reorder Whether the stage output requires bit-reversal reordering.
function ngfft_execute(const ngfft_plan<T> &, bool, complex<T> *, const complex<T> *, dft_algorithm) Executes the FFT with separate input and output buffers, runtime direction and algorithm.
function ngfft_execute(const ngfft_plan<T> &, bool, complex<T> *, dft_algorithm) Executes the FFT in-place with runtime direction and algorithm.
function ngfft_execute(const ngfft_plan<T> &, cbool_t<inverse>, complex<T> *, const complex<T> *, dft_algorithm) Executes the FFT with separate input and output buffers, a compile-time direction and runtime algorithm.
function ngfft_execute(const ngfft_plan<T> &, cbool_t<inverse>, complex<T> *, dft_algorithm) Executes the FFT in-place with a compile-time direction and runtime algorithm.
function ngfft_initialize(ngfft_plan<T> &, dft_algorithm) Initializes the plan's twiddles for a runtime algorithm value.
class ngfft_plan_real<T>
constructor ngfft_plan_real<T>::ngfft_plan_real<T>()
constructor ngfft_plan_real<T>::ngfft_plan_real<T>(uint8_t)
class ngfft_plan<T> Plan structure for the ng FFT algorithms (new in KFR 7.1).
function ngfft_real_execute(const ngfft_plan<T> &, complex<T> *, const T *, dft_algorithm) Executes the forward real-to-complex FFT with a runtime algorithm.
function ngfft_real_execute(const ngfft_plan<T> &, T *, const complex<T> *, dft_algorithm) Executes the inverse complex-to-real FFT with a runtime algorithm.
function ngfft_twiddle_count(ngfft_plan<T> &, dft_algorithm) Returns the twiddle-factor count for a runtime algorithm value.
struct dft_plan<T>::noinit
enum constant dft_order::normal Normal order

O¶

function dft_plan_md_real<T, Dims>::operator=(const dft_plan_md_real<T, Dims> &)
function dft_plan_md<T, Dims>::operator=(const dft_plan_md<T, Dims> &)
function dft_plan_real<T>::operator=(const dft_plan_real<T> &)
function dft_plan<T>::operator=(const dft_plan<T> &) Copy assignment operator (deleted).
function dft_stage<T>::operator
function dft_stage<T>::operator
function dft_plan_md_real<T, Dims>::operator=(dft_plan_md_real<T, Dims> &&)
function dft_plan_md<T, Dims>::operator=(dft_plan_md<T, Dims> &&)
function dft_plan_real<T>::operator=(dft_plan_real<T> &&)
function dft_plan<T>::operator=(dft_plan<T> &&) Move assignment operator.
function dft_stage<T>::operator
function dft_stage<T>::operator
variable dft_stage<T>::out_offset Offset (in complex elements) between successive recursive outputs.
function dft_resampler<T>::output_block_size() Returns the output FFT block size \(M\) .
function dft_resampler<T>::output_hop() Returns the number of valid output samples produced per frame.
variable convolve_filter<T>::overlap

P¶

enum constant dft_pack_format::Perm Packed format: {DC, Nyquist}, X[1], X[2], ..., X[N/2-1] For even N, the number of complex samples is
typedef convolve_filter<T>::plan_t
variable convolve_filter<T>::position
function dft_plan<T>::precompute_disposition(int, bitset, bool) Internal function
variable convolve_filter<T>::premul
function convolve_filter<T>::process_buffer(T *, const T *, size_t)
function convolve_filter<T>::process_expression(T *, const expression_handle<T> &, size_t)
function dft_resampler<T>::process_frame(const T *) Processes one frame in-place and returns a pointer to the valid output.
function dft_resampler<T>::process_frame(T *, const T *) Processes one frame via overlap-save and writes normalised output.
function dft_resampler<T>::process(std::span<T>, std::span<const T>) Processes an arbitrary-length input stream and writes the resampled output.
variable dft_plan<T>::progressive_optimized True if the plan is for progressive execution of the DFT.

R¶

variable dft_stage<T>::radix Radix of the stage (number of butterfly arms).
variable convolve_filter<T>::real_fft
variable dft_plan_md_real<T, Dims>::real_out_is_enough If true, the inverse transform may write directly into the real output buffer without an extra complex working region.
function dft_plan_md_real<T, Dims>::real_out_size() Returns the number of real elements needed to hold the inverse output.
function dft_plan_md_real<T, Dims>::real_out_size_for(shape<Dims>) Returns the real output element count for a given real shape.
function realdft(const univector<T, Tag> &) Performs the direct (forward) real-to-complex DFT using a cached plan.
variable dft_stage<T>::recursion Whether the stage uses recursive execution.
function reference_dft_md(complex<T> *, const complex<T> *, shape<dynamic_shape>, bool, size_t, size_t) Performs Multidimensional Complex DFT using reference implementation (slow, used for testing)
function reference_dft_md(complex<T> *, const T *, shape<dynamic_shape>, bool, size_t, size_t) Performs Multidimensional Direct Real DFT using reference implementation (slow, used for testing)
function reference_dft_md(T *, const complex<T> *, shape<dynamic_shape>, bool, size_t, size_t) Performs Multidimensional Inverse Real DFT using reference implementation (slow, used for testing)
function reference_dft(complex<T> *, const complex<T> *, size_t, bool, size_t, size_t) Performs Complex DFT using reference implementation (slow, used for testing)
function reference_dft(complex<T> *, const T *, size_t, size_t, size_t) Performs Direct Real DFT using reference implementation (slow, used for testing)
function reference_dft(T *, const complex<T> *, size_t, size_t, size_t) Performs Inverse Real DFT using reference implementation (slow, used for testing)
variable dft_stage<T>::repeats Number of recursive repetitions used during execution.
function convolve_filter<T>::reset() Resets the filter state (clears input history and overlap buffers).
function dft_resampler<T>::reset() Resets the resampler to its freshly-constructed state, clearing all buffered input without changing filter parameters.

S¶

variable convolve_filter<T>::saved_input
variable convolve_filter<T>::scratch1
variable convolve_filter<T>::scratch2
variable convolve_filter<T>::segments
function convolve_filter<T>::set_data(const univector_ref<const T> &) Sets (replaces) the filter kernel.
variable dft_resampler_params::shift Resampling factor as a power of 2 (e.g. 1 for 2x, -1 for 0.5x, 0 for filter-only).
variable dft_plan<T>::size The size of the DFT as passed to the constructor.
variable dft_plan_real<T>::size Number of real samples in the transform.
variable dft_plan_md<T, Dims>::size Per-dimension sizes of the transform.
variable dft_plan_md_real<T, Dims>::size Per-dimension sizes of the real transform.
typedef convolve_filter<T>::ST
function dft_resampler_params::stage_factor() Returns the per-stage conversion ratio (>1 for upsampling, <1 for downsampling).
variable dft_stage<T>::stage_size Number of complex elements processed by this stage.
variable dft_plan<T>::stages Internal data.
variable dft_resampler_params::stopband_atten_db Desired stopband attenuation in dB (e.g. 144). Controls Kaiser beta.

T¶

variable convolve_filter<T>::temp
variable dft_stage<T>::temp_size Size in bytes of scratch buffer required by this stage.
variable dft_plan<T>::temp_size The temporary (scratch) buffer size for the DFT plan.
variable dft_plan_md<T, Dims>::temp_size Scratch buffer size in bytes required by
variable dft_plan_md_real<T, Dims>::temp_size Scratch buffer size in bytes required by
variable dft_resampler_params::transition_width Transition bandwidth normalised to the lower-rate Nyquist (0..1].
variable ngfft_plan<T>::twiddles User-allocated pointer to twiddle factors. The required element count is obtained from ngfft_twiddle_count(); the buffer must be cache-line aligned. Initialise via ngfft_initialize() before first use.

U¶

variable dft_stage<T>::user Stage-specific user value (e.g. log2 of the stage size).

This file was generated by cxxdox, a C++ documentation generator based on MkDocs Material and libclang.

Discrete Fourier Transform¶

A¶

B¶

C¶

D¶

E¶

F¶

G¶

I¶

K¶

L¶

N¶

O¶

P¶

R¶

S¶

T¶

U¶