Multidimensional discrete convolution: Difference between revisions

Revision as of 04:36, 11 December 2015

Revision as of 04:40, 11 December 2015

Line 7:

Similar to the one-dimensional case, an asterisk is used to represent the convolution operation. The number of dimensions in the given operation is reflected in the number of asterisks. For example, an ''M''-dimensional convolution would be written with ''M'' asterisks. The following represents a ''M''-dimensional convolution of discrete signals:

<math>y(n_1,n_2,...,n_M)=x(n_1,n_2,...,n_M)*... \overset{M}{\cdots} *h(n_1,n_2,...,n_M)</math>

For discrete-valued signals, this convolution can be directly computed via the following:

Line 110:

This conclusion can then be extended to the convolution of two separable ''M''-dimensional signals as follows:

<math>x(n_1,n_2,...,n_M)*... \overset{M}{\cdots} *h(n_1,n_2,...,n_M)=\bigg[x(n_1)*h(n_2)\bigg]\bigg[x(n_2)*h(n_2)\bigg]...\bigg[x(n_M)*h(n_M)\bigg]</math>

So, when the two signals are separable, the multidimensional convolution can be computed by computing <math>n_M</math> one-dimensional convolutions.

Line 141:

===Convolution Theorem in Multiple Dimensions===

For one-dimensional signals, the [[Convolution theorem|Convolution Theorem]] states that the [[Fourier transform]] of the convolution between two signals is equal to the product of the Fourier Transforms of those two signals. Thus, convolution in the time ___domain is equal to multiplication in the frequency ___domain. Mathematically, this principle is expressed via the following:<math display="block">y(n)=h(n)*x(n)\longleftrightarrow Y(\omega)=H(\omega)X(\omega)</math>This principle is directly extendable to dealing with signals of multiple dimensions.<math display="block">y(n_1,n_2,...,n_M)=h(n_1,n_2,...,n_M)*...\overset{M}{\cdots}*x(n_1,n_2,...,n_M) \longleftrightarrow Y(\omega_1,\omega_2,...,\omega_M)=H(\omega_1,\omega_2,...,\omega_M)X(\omega_1,\omega_2,...,\omega_M)</math>This property is readily extended to the usage with the [[Discrete Fourier transform]] (DFT) as follows (note that linear convolution is replaced with circular convolution where <math>\otimes</math> is used to denote the circular convolution operation of size <math>N</math>):

<math>y(n)=h(n)\otimes x(n)\longleftrightarrow Y(k)=H(k)X(k)</math>

When dealing with signals of multiple dimensions:<math display="block">y(n_1,n_2,...,n_M)=h(n_1,n_2,...,n_M)\otimes...\overset{M}{\cdots}\otimes(n_1,n_2,...,n_M) \longleftrightarrow Y(k_1,k_2,...,k_M)=H(k_1,k_2,...,k_M)X(k_1,k_2,...,k_M)</math>The circular convolutions here will be of size <math>N_1, N_2,...,N_M</math>.

===Circular Convolution Approach===