1D fast convolution

Collaboration diagram for 1D fast convolution:

Modules
	Convolution methods

Macros
#define	MUFFT_CONV_BLOCK_FIRST   0
	The first block. More...
#define	MUFFT_CONV_BLOCK_SECOND   1
	The second block. More...

Typedefs
typedef struct mufft_plan_conv	mufft_plan_conv
	Opaque type representing a plan to convolve data. More...
typedef void(*	mufft_convolve_func) (void *output, const void *a, const void *b, float normalization, unsigned samples)
	Vector complex multiply routine signature. More...

Functions
mufft_plan_conv *	mufft_create_plan_conv (unsigned N, unsigned flags, unsigned method)
	Create a plan to convolve zero-padded input data of length N with zero-padded input data of length N. More...
void	mufft_execute_conv_input (mufft_plan_conv *plan, unsigned block, void *output, const void *input)
	Applies forward FFT of either first or second input block. More...
size_t	mufft_conv_get_transformed_block_size (mufft_plan_conv *plan)
	Queries the buffer size for intermediate FFT blocks. More...
void	mufft_execute_conv_output (mufft_plan_conv *plan, void *output, const void *input_first, const void *input_second)
	Multiply together FFTs of the two input arrays obtained from mufft_execute_conv_input and perform a normalized inverse FFT. More...
void	mufft_free_plan_conv (mufft_plan_conv *plan)
	Free a previously allocated convolution plan obtained from mufft_create_plan_conv. More...
mufft_convolve_func	mufft_get_convolve_func (unsigned flags)
	Gets a function pointer which implements complex multiplication (convolution in frequency domain). More...

Detailed Description

Macro Definition Documentation

MUFFT_CONV_BLOCK_FIRST

#define MUFFT_CONV_BLOCK_FIRST   0

The first block.

MUFFT_CONV_BLOCK_SECOND

#define MUFFT_CONV_BLOCK_SECOND   1

The second block.

Typedef Documentation

mufft_convolve_func

typedef void(* mufft_convolve_func) (void *output, const void *a, const void *b, float normalization, unsigned samples)

Vector complex multiply routine signature.

mufft_plan_conv

typedef struct mufft_plan_conv mufft_plan_conv

Opaque type representing a plan to convolve data.

Function Documentation

mufft_conv_get_transformed_block_size()

size_t mufft_conv_get_transformed_block_size

(

mufft_plan_conv *

plan

)

Queries the buffer size for intermediate FFT blocks.

Parameters

plan	Convolution instance

Returns

The number of bytes required to hold the output of mufft_execute_conv_input. Can be passed directly to Memory allocation.

mufft_create_plan_conv()

mufft_plan_conv* mufft_create_plan_conv	(	unsigned	N,
		unsigned	flags,
		unsigned	method
	)

Create a plan to convolve zero-padded input data of length N with zero-padded input data of length N.

Due to use of the FFT to perform convolution, this convolution is circular and to obtain proper convolution, the user must ensure that both input arrays are properly zero-padded at the end of each array. The length of a convolution is equal to K + L - 1, where K and L are the lengths of the two input arrays which are to be convolved. If the output array is overrun, the results will spill into the start of the output array which is rarely a desirable result. A very common approach when convolving two arrays of size N in filtering applications is to use an FFT of length N * 2, which can perfectly contain the result of the convolution with just outputing a single redundant value since we need an array of N * 2 - 1. Linear phase FIR filters tend to be of odd length, and we can e.g. implement a 33-tap FIR filter by convolving 32 input samples with 33 FIR samples to form a 64 sample result.

Parameters

N	the number of samples in the FFT. N must be at least 4 and power-of-two.
flags	Flags to be passed to the FFT planning. See Planning options.
method	The convolution method to use. See Convolution methods. Stereo convolution is supported as well as zero-padding the input data without extra memory copies.

Returns

An instance of a convolution plan, or NULL if failed.

mufft_execute_conv_input()

void mufft_execute_conv_input	(	mufft_plan_conv *	plan,
		unsigned	block,
		void *	output,
		const void *	input
	)

Applies forward FFT of either first or second input block.

When doing block-based overlap-add convolution with FFTs the filter generally stays constant over many transforms. We can do the forward transform of the filter input once and cache the FFT of the filter. Only the FFT of the input blocks have to be performed in this case.

Parameters

plan	Convolution instance
block	Which block to forward FFT transform. MUFFT_CONV_BLOCK_FIRST or MUFFT_CONV_BLOCK_SECOND are accepted. Which input is first and second is arbitrary and up to the API user.
output	The FFT of input. Its required buffer size can be queried with mufft_conv_get_transformed_block_size.
input	Input data to be transformed. Must be aligned to a boundary which matches with the SIMD instruction set used by your hardware, typically 16 or 32 bytes. Use Memory allocation to allocate properly aligned memory. Depending on the convolution method used, this input array is either treated as a complex array or real array with length either N or N / 2 if zero padding is used.

mufft_execute_conv_output()

void mufft_execute_conv_output	(	mufft_plan_conv *	plan,
		void *	output,
		const void *	input_first,
		const void *	input_second
	)

Multiply together FFTs of the two input arrays obtained from mufft_execute_conv_input and perform a normalized inverse FFT.

A convolution in the time domain happens by multiplying together the frequency response of them. The convolved output is obtained with an inverse transform. Unlike the regular 1D FFT interface, this inverse transform is normalized.

Parameters

plan	Convolution instance
output	Output data. Must be aligned to a boundary which matches with the SIMD instruction set used by your hardware, typically 16 or 32 bytes. Use Memory allocation to allocate properly aligned memory. Depending on the convolution method used, the type of output is either treated as a complex array or real array of length N.
input_first	The output obtained earlier by mufft_execute_conv_input for MUFFT_CONV_BLOCK_FIRST.
input_second	The output obtained earlier by mufft_execute_conv_input for MUFFT_CONV_BLOCK_SECOND.

mufft_free_plan_conv()

void mufft_free_plan_conv

(

mufft_plan_conv *

plan

)

Free a previously allocated convolution plan obtained from mufft_create_plan_conv.

mufft_get_convolve_func()

mufft_convolve_func mufft_get_convolve_func

(

unsigned

flags

)

Gets a function pointer which implements complex multiplication (convolution in frequency domain).

Parameters

flags

See Planning options.

Returns

A function which can multiply complex numbers, or NULL if failed.