Circular convolution: Difference between revisions

Revision as of 17:08, 1 July 2020

Latest revision as of 12:26, 17 December 2024

(25 intermediate revisions by 12 users not shown)

Line 1:

{{Short description|Mathematical operation}}

The '''circular convolution''', also known as '''cyclic convolution''', of two aperiodic functions (i.e. [[Schwartz functions]]) occurs when one of them is [[convolution|convolved in the normal way]] with a [[periodic summation]] of the other function. That situation arises in the context of the [[Discrete Fourier transform#Circular convolution theorem and cross-correlation theorem|circular convolution theorem]]. The identical operation can also be expressed in terms of the periodic summations of ''both'' functions. That situation arises in the context of the [[discrete-time Fourier transform]] (DTFT) and is also called '''periodic convolution'''. In particular, the DTFT of the product of two discrete sequences is the periodic convolution of the DTFTs of the individual sequences. And each DTFT is a periodic summation of a continuous Fourier transform function. (See [[Discrete-time Fourier transform#Definition]].)

'''Circular convolution''', also known as '''cyclic convolution''', is a special case of '''periodic convolution''', which is the [[convolution]] of two periodic functions that have the same period. Periodic convolution arises, for example, in the context of the [[discrete-time Fourier transform]] (DTFT). In particular, the DTFT of the product of two discrete sequences is the periodic convolution of the DTFTs of the individual sequences. And each DTFT is a [[periodic summation]] of a continuous Fourier transform function (see {{slink|Discrete-time Fourier transform|Relation to Fourier_Transform}}). Although DTFTs are usually continuous functions of frequency, the concepts of periodic and circular convolution are also directly applicable to discrete sequences of data. In that context, circular convolution plays an important role in maximizing the efficiency of a certain kind of common filtering operation.

==Definitions==

The ''periodic convolution'' of two T-periodic functions, <math>h_Th_{_T}(t)</math> and <math>x_Tx_{_T}(t)</math> can be defined as''':'''

:<math>\int_{t_o}^{t_o+T} h_Th_{_T}(\tau)\cdot x_Tx_{_T}(t - \tau)\,d\tau,</math> &nbsp; <ref name=Jeruchim/><ref name=Udayashankara/>

where ''t''<submath>ot_o</submath> is an arbitrary parameter.&nbsp; An alternative definition, in terms of the notation of normal ''linear'' or ''aperiodic'' convolution, follows from expressing <math>h_Th_{_T}(t)</math> and <math>x_Tx_{_T}(t)</math> as [[periodic summation|periodic summations]] of aperiodic components <math>h</math> and <math>x</math>, i.e.''':'''

:<math>h_Th_{_T}(t) \ \triangleq \ \sum_{k=-\infty}^\infty h(t - kT) = \sum_{k=-\infty}^\infty h(t + kT).</math>

Then''':'''

{{Equation box 1

:<math>\int_{t_o}^{t_o+T} h_T(\tau)\cdot x_T(t - \tau)\,d\tau = \int_{-\infty}^\infty h(\tau)\cdot x_T(t - \tau)\,d\tau\ \triangleq\ (h *x_T)(t) = (x * h_T)(t).</math>{{efn-ua

|indent=:|cellpadding=0|border=0|background colour=white

|Proof:

|equation={{NumBlk||

<math>

:<math>\int_{t_o}^{t_o+T} h_Th_{_T}(\tau)\cdot x_Tx_{_T}(t - \tau)\,d\tau = \int_{-\infty}^\infty h(\tau)\cdot x_Tx_{_T}(t - \tau)\,d\tau\ \triangleq\ (h *x_Tx_{_T})(t) = (x * h_Th_{_T})(t).</math>{{efn-ua &nbsp; &nbsp;

|{{EquationRef|Eq.1}} }} }}

{{Collapse top|title=Derivation of Eq.1}}

:<math>\begin{align}

&\int_{-\infty}^\infty h(\tau)\cdot x_Tx_{_T}(t - \tau)\,d\tau \\

&={} &\sum_{k=-\infty}^\infty \left[\int_{t_o+kT}^{t_o+(k+1)T} h(\tau)\cdot x_Tx_{_T}(t - \tau)\ d\tau\right] \quad t_0 \text{ is an arbitrary parameter}\\

&=\sum_{k=-\infty}^\infty \left[\int_{t_o}^{t_o+T} h(u + kT)\cdot \underbrace{x_{_T}(t-u-kT)}_{x_{_T}(t-u), \text{ by periodicity}}\ du\right] \quad \text{substituting } u\triangleq \tau-kT\\

\stackrel{\tau \rightarrow \tau+kT}{=}{}

&=\int_{t_o}^{t_o+T} \left[\sum_{k=-\infty}^\infty \left[\int_{t_o}^{t_o+T} h(\tauu + kT)\cdot x_Tx_{_T}(t - \tau -kTu)\ d\tau\right]\ du\\

&={} &\int_{t_o}^{t_o+T} \underbrace{\left[\sum_{k=-\infty}^\infty h(\tauu + kT)\cdotright]}_{\triangleq \underbrace h_{x_T_T}(t - \tau-kTu)}_\cdot x_{X_T_T}(t - \tauu), \text{ by periodicity}}\right]\ d\taudu\\

&={} &\int_{t_o}^{t_o+T} \underbraceh_{\left[\sum_{k=-\infty_T}^\infty h(\tau + kT)\right]}_cdot x_{\triangleq \ h_T(\tau)_T}\cdot x_T(t - \tau)\ d\tau \quad \text{substituting } \tau \triangleq u

\end{align}</math>

{{Collapse bottom}}<br>

}}

Both forms can be called ''periodic convolution''.{{efn-la

Line 31 ⟶ 37:

}}, which can also be expressed as a ''circular function''''':'''

:<math>x_Tx_{_T}(t) = x(t_{\mathrm{mod}\ T}), \quad t\in\mathbb{R}\,</math> ([[Number#Real_numbers|any real number]]){{efn-la

|[[#Oppenheim|Oppenheim and Shafer]], p 559 (8.59)

}}

Line 37 ⟶ 43:

And the limits of integration reduce to the length of function <math>h</math>''':'''

:<math>(h *x_Tx_{_T})(t) = \int_{0}^{T} h(\tau)\cdot x((t - \tau)_{\mathrm{mod}\ T})\ d\tau.</math>{{efn-la

|[[#Oppenheim|Oppenheim and Shafer]], p 571 (8.114), shown in digital form

}}{{efn-la

Line 69 ⟶ 75:

== See also ==

*[[Convolution theorem#Functions of discrete variable sequences|Convolution theorem]]

*[[Hilbert transform#Discrete Hilbert transform|Discrete Hilbert transform]]

*[[Circulant matrix]]

*[[Hilbert transform#Discrete Hilbert transform|Discrete Hilbert transform]]

== Notes ==

{{notelist-ua}}

== Page citations ==

Line 88 ⟶ 92:

|year=1975

|publisher=Prentice-Hall

|___location=Englewood Cliffs, N.J.

|isbn=0-13-914101-4

|url-access=registration

Line 104 ⟶ 108:

|volume=6

|date=July 1991

|___location=Teaneck, N.J.

|url=https://books.google.com/books?id=QBT7nP7zTLgC&printsec=frontcover&dqq=Priemer,+Roland

|isbn=9971-50-919-9

}}</ref>

Line 111 ⟶ 115:

<ref name=Jeruchim>

{{cite book

|lastlast1=Jeruchim

|firstfirst1=Michel C.

|last2=Balaban

|first2=Philip

Line 141 ⟶ 145:

#<li value="5">{{cite book

|ref=Oppenheim

|lastlast1=Oppenheim

|firstfirst1=Alan V.

|authorlink=Alan V. Oppenheim

|last2=Schafer

Line 153 ⟶ 157:

|year=1999

|publisher=Prentice Hall

|___location=Upper Saddle River, N.J.

|isbn=0-13-754920-2

|edition=2nd

|url-access=registration

|url=https://archive.org/details/discretetimesign00alan

}}

}}&nbsp; Also available at https://d1.amobbs.com/bbs_upload782111/files_24/ourdev_523225.pdf

#{{cite book

|ref=McGillem

Line 171 ⟶ 175:

|isbn=0-03-061703-0

}}

</li>

== Further reading ==