# Convolution (G Dataflow)

Version:
Last Modified: January 9, 2017

Computes the convolution of two sequences.  ## x

The first input sequence.

This input accepts the following data types:

• 1D array of double-precision, floating-point numbers
• 1D array of complex double-precision, floating-point numbers
• 2D array of double-precision, floating-point numbers
• 2D array of complex double-precision, floating-point numbers ## y

The second input sequence.

This input accepts the following data types:

• 1D array of double-precision, floating-point numbers
• 1D array of complex double-precision, floating-point numbers
• 2D array of double-precision, floating-point numbers
• 2D array of complex double-precision, floating-point numbers ## algorithm

The convolution method to use.

If x and y are small, the direct method typically is faster. If x and y are large, the frequency domain method typically is faster. Additionally, slight numerical differences can exist between the two methods.

Name Description
frequency domain

Computes the convolution using an FFT-based technique.

direct

Computes the convolution using the direct method of linear convolution.

Computing 1D Convolution with the Frequency Domain Method

When algorithm is frequency domain, this node completes the following steps to compute the linear convolution:

1. Pads the end of x and y with zeros to make their lengths M + N - 1, as shown in the following equations.
${x\prime }_{i}=\left\{\begin{array}{cc}{\begin{array}{c}x\end{array}}_{i}& i=0,\text{\hspace{0.17em}}1,\text{\hspace{0.17em}}...,\text{\hspace{0.17em}}N-1\\ 0& i=N,\text{\hspace{0.17em}}...,\text{\hspace{0.17em}}M+N-2\end{array}$
${y\prime }_{i}=\left\{\begin{array}{cc}{y}_{i}& i=0,\text{\hspace{0.17em}}1,\text{\hspace{0.17em}}...,\text{\hspace{0.17em}}M-1\\ 0& i=M,\text{\hspace{0.17em}}...,\text{\hspace{0.17em}}M+N-2\end{array}$
2. Calculates the Fourier transform of x' and y' according to the following equations.
$x\prime \left(f\right)=FFT\left(x\prime \right)$
$y\prime \left(f\right)=FFT\left(y\prime \right)$
3. Multiplies x'(f) by y'(f) and calculates the inverse Fourier transform of the product. The result is the linear convolution of x and y, as shown in the following equation.
$x*y=IFFT\left(x\prime \left(f\right)\cdot y\prime \left(f\right)\right)$

Computing 2D Convolution with the Frequency Domain Method

When algorithm is frequency domain, this node completes the following steps to compute the two-dimensional convolution:

1. Pads the end of x and y with zeros to make their sizes (M1 + M2 - 1)-by-(N1 + N2 - 2), as shown in the following equations.
${x\prime }_{ij}=\left\{\begin{array}{cc}{\begin{array}{c}x\end{array}}_{ij}& i=0,\text{\hspace{0.17em}}1,\text{\hspace{0.17em}}...,\text{\hspace{0.17em}}{M}_{1}-1,\text{\hspace{0.17em}}j=0,\text{\hspace{0.17em}}1,\text{\hspace{0.17em}}...,\text{\hspace{0.17em}}{N}_{1}-1\\ 0& i={M}_{1},\text{\hspace{0.17em}}...,\text{\hspace{0.17em}}{M}_{1}+{M}_{2}-2,\text{\hspace{0.17em}}j={N}_{1},\text{\hspace{0.17em}}...,\text{\hspace{0.17em}}{N}_{1}+{N}_{2}-2\end{array}$
${y\prime }_{ij}=\left\{\begin{array}{cc}{\begin{array}{c}y\end{array}}_{ij}& i=0,\text{\hspace{0.17em}}1,\text{\hspace{0.17em}}...,\text{\hspace{0.17em}}{M}_{2}-1,\text{\hspace{0.17em}}j=0,\text{\hspace{0.17em}}1,\text{\hspace{0.17em}}...,\text{\hspace{0.17em}}{N}_{2}-1\\ 0& i={M}_{2},\text{\hspace{0.17em}}...,\text{\hspace{0.17em}}{M}_{1}+{M}_{2}-2,\text{\hspace{0.17em}}j={N}_{2},\text{\hspace{0.17em}}...,\text{\hspace{0.17em}}{N}_{1}+{N}_{2}-2\end{array}$
2. Calculates the Fourier transform of x' and y' according to the following equations.
$x\prime \left(f\right)=FFT\left(x\prime \right)$
$y\prime \left(f\right)=FFT\left(y\prime \right)$
3. Multiplies x'(f) by y'(f) and calculates the inverse Fourier transform of the product. The result is the two-dimensional convolution of x and y, as shown in the following equation.
$x*y=IFFT\left(x\prime \left(f\right)\cdot y\prime \left(f\right)\right)$

Computing 1D Convolution with the Direct Method

When algorithm is direct, this node uses the following equation to perform the discrete implementation of the linear convolution and obtain the elements of x * y.

${h}_{i}=\underset{k=0}{\overset{N-1}{\sum }}{x}_{k}\cdot {y}_{i}-k$

for i = 0, 1, 2, ... , M+N-2

where

• h is x * y
• N is the number of elements in x
• M is the number of elements in y
• the indexed elements outside the ranges of x and y are equal to 0, as shown in the following relationships:
${x}_{j}=0,\text{\hspace{0.17em}}j<0,\text{\hspace{0.17em}}\mathrm{or}\text{\hspace{0.17em}}j\ge N$

and

${y}_{j}=0,\text{\hspace{0.17em}}j<0,\text{\hspace{0.17em}}\mathrm{or}\text{\hspace{0.17em}}j\ge M$

Computing 2D Convolution with the Direct Method

When algorithm is direct, this node uses the following equation to compute the two-dimensional convolution of the input matrices x and y.

$h\left(i,j\right)=\underset{m=0}{\overset{{M}_{1}-1}{\sum }}\underset{n=0}{\overset{{N}_{1}-1}{\sum }}x\left(m,n\right)\cdot y\left(i-m,j-n\right)-k$

for i = 0, 1, 2, ... , M1+M2-2 and j = 0, 1, 2, ... , N1+N2-2

where

• h is x * y
• M1 is the number of rows of matrixx
• N1 is the number of columns of matrix x
• M2 is the number of rows of matrixy
• N2 is the number of columns of matrix y
• the indexed elements outside the ranges of x and y are equal to 0, as shown in the following relationships:
$x\left(m,n\right)=0,\text{\hspace{0.17em}}m<0,\text{\hspace{0.17em}}\mathrm{or}\text{\hspace{0.17em}}m\ge {M}_{1}\text{\hspace{0.17em}}\mathrm{or}\text{\hspace{0.17em}}n<0\text{\hspace{0.17em}}\mathrm{or}\text{\hspace{0.17em}}n\ge {N}_{1}$

and

$y\left(m,n\right)=0,\text{\hspace{0.17em}}m<0,\text{\hspace{0.17em}}\mathrm{or}\text{\hspace{0.17em}}m\ge {M}_{2}\text{\hspace{0.17em}}\mathrm{or}\text{\hspace{0.17em}}n<0\text{\hspace{0.17em}}\mathrm{or}\text{\hspace{0.17em}}n\ge {N}_{2}$

Default: frequency domain ## error in

Error conditions that occur before this node runs. The node responds to this input according to standard error behavior.

Default: No error ## x * y

The convolution of the two input sequences. ## error out

Error information. The node produces this output according to standard error behavior.

## Algorithm for Calculating the 1D Convolution

The linear convolution of the signals x(t) and y(t) is defined as:

$h\left(t\right)=x\left(t\right)*y\left(t\right)={\int }_{-\infty }^{\infty }x\left(\tau \right)\cdot y\left(t-\tau \right)d\tau$

where the symbol * denotes linear convolution.

This node computes the linear convolution, not the circular convolution. However, because $x\left(t\right)*{y\left(t\right)}_{N}⇔X\left(f\right)Y\left(f\right)$ is a Fourier transform pair, where $x\left(t\right)*{y\left(t\right)}_{N}$ is the circular convolution of x(t) and y(t), you can create a circular version of the convolution.

Where This Node Can Run:

Desktop OS: Windows

FPGA: Not supported