Circular convolution: Difference between revisions

Revision as of 20:59, 27 February 2020

Latest revision as of 12:26, 17 December 2024

(44 intermediate revisions by 14 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, if the infinite integration interval is reduced to just one period. 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.{{efn-ua

'''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.

|If a sequence, ''x''[''n''], represents samples of a continuous function, ''x''(''t''), with Fourier transform ''X''(ƒ), its DTFT is a periodic summation of ''X''(ƒ). (See [[Discrete-time Fourier transform#Definition]].)

}}

==Definitions==

Let ''x'' be a function with a well-defined periodic summation, ''x''_''T'', where:

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

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

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

If ''h'' is any other function for which the convolution ''x''_''T'' ∗ ''h'' exists, then the convolution ''x''_''T'' ∗ ''h'' is periodic and identical to''':'''

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

:<math>

\begin{align}

(x_T * h)(t)\quad &\triangleq \ \int_{-\infty}^\infty h(\tau)\cdot x_T(t - \tau)\,d\tau \\

&\equiv \int_{t_o}^{t_o+T} h_T(\tau)\cdot x_T(t - \tau)\,d\tau,

\end{align}

</math>{{efn-ua

|Proof:

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

Then''':'''

{{Equation box 1

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

|equation={{NumBlk||

<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> &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 \quadtext{substituting } \scriptstyle{(QED)}tau \triangleq u

\end{align}</math>

{{Collapse bottom}}<br>

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

|[[#McGillem|McGillem and Cooper]], p 172 (4-6)

}} The term ''circular convolution''<ref name=Udayashankara/><ref name=Priemer/> arises from the important special case of constraining the non-zero portions of both <math>h</math> and <math>x</math> to the interval <math>[0,T].</math> Then the periodic summation becomes a ''periodic extension''{{efn-la

|[[#McGillem|McGillem and Cooper]], p 183 (4-51)

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

:<math>x_{_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)

}}

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

where ''t''_o is an arbitrary parameter and ''h''_''T'' is a [[periodic summation]] of ''h''.

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

The second integral is called the '''periodic convolution'''<ref name=Jeruchim/><ref name=Udayashankara/> of functions ''x''_''T'' and ''h''_''T'' and is sometimes normalized by 1/''T''.<ref name=Oppenheim/> When ''x''_''T'' is expressed as the [[periodic summation]] of another function, ''x'', the same operation may also be referred to as a '''circular convolution'''<ref name=Udayashankara/><ref name=Priemer/> of functions ''h'' and ''x''.

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

}}{{efn-la

|[[#McGillem|McGillem and Cooper]], p 171 (4-22), shown in digital form

}}

== Discrete sequences ==

Line 35 ⟶ 53:

:<math>

(x_Nh * hx_{_N})[n] \ \triangleq \ \sum_{m=-\infty}^\infty h[m] \cdot \underbrace{x_Nx_{_N}[n-m]}_{\sum_{k=-\infty}^\infty x[n -m -kN]}

</math>

Line 41 ⟶ 59:

== Example ==

[[Image:Circular convolution example.svg|thumb|400px|Circular convolution can be expedited by the FFT algorithm, so it is often used with an FIR filter to efficiently compute linear convolutions. These graphs illustrate how that is possible. Note that a larger FFT size (N) would prevent the overlap that causes graph #6 to not quite match all of #3.]]

A case of great practical interest is illustrated in the figure. The duration of the '''x''' sequence is '''N''' (or less), and the duration of the '''h''' sequence is significantly less. Then many of the values of the circular convolution are identical to values of '''x∗h''',&nbsp; which is actually the desired result when the '''h''' sequence is a [[finite impulse response]] (FIR) filter. Furthermore, the circular convolution is very efficient to compute, using a [[fast Fourier transform]] (FFT) algorithm and the [[Discrete Fourier transform#Circular convolution theorem and cross-correlation theorem|circular convolution theorem]].

Line 57 ⟶ 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]]

== NotesPage citations ==

{{notelist-uala|1}}

== References ==

Line 67 ⟶ 86:

<ref name=Rabiner>

{{cite book

|author1=Rabiner, Lawrence R.

| ref=refRabiner

|author2=Gold, Bernard

| author1=Rabiner, Lawrence R.

|title=Theory and application of digital signal processing

| author2=Gold, Bernard

|pages=63–67

| title=Theory and application of digital signal processing

|year=1975

| pages=63-67

|publisher=Prentice-Hall

| year=1975

|___location=Englewood Cliffs, N.J.

| publisher=Prentice-Hall

|isbn=0-13-914101-4

| ___location=Englewood Cliffs, N.J.

|url-access=registration

| isbn=0-13-914101-4

|url=https://archive.org/details/theoryapplicatio00rabi/page/63

| pages=63–67

| url-access=registration

| url=https://archive.org/details/theoryapplicatio00rabi/page/63

}}</ref>

<ref name=OppenheimPriemer>

{{cite book

|last=Priemer

|ref=refOppenheim

|first=Roland

|last=Oppenheim

|title=Introductory Signal Processing

|first=Alan V.

|pages=286–289

|publisher=World Scientific Pub Co Inc.

|series=Advanced Series in Electrical and Computer Engineering

|volume=6

|date=July 1991

|___location=Teaneck, N.J.

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

|isbn=9971-50-919-9

}}</ref>

<ref name=Jeruchim>

{{cite book

|last1=Jeruchim

|first1=Michel C.

|last2=Balaban

|first2=Philip

|last3=Shanmugan

|first3=K. Sam

|title=Simulation of Communication Systems: Modeling, Methodology and Techniques

|pages=73–74

|publisher=Kluwer Academic Publishers

|edition=2nd

|date=October 2000

|___location=New York

|isbn=0-30-646267-2

}}</ref>

<ref name=Udayashankara>

{{cite book

|last=Udayashankara

|first=V.

|title=Real Time Digital Signal Processing

|page=189

|publisher=Prentice-Hall

|date=June 2010

|___location=India

|isbn=978-8-12-034049-7

}}</ref>

}}

{{refbegin}}

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

|ref=Oppenheim

|last1=Oppenheim

|first1=Alan V.

|authorlink=Alan V. Oppenheim

|last2=Schafer

Line 93 ⟶ 154:

|first3=John R.

|title=Discrete-time signal processing

|pages=[https://archive.org/details/discretetimesign00alan/page/548 548], 571

|pages=388-389

|year=1999

|publisher=Prentice Hall

Line 100 ⟶ 161:

|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>

|ref=McGillem

|last1=McGillem

<ref name=Priemer>

|first1=Clare D.

{{cite book

|last2=Cooper

| ref=refPriemer

|first2=George R.

| last =Priemer

|title=Continuous and Discrete Signal and System Analysis

| first =Roland

|publisher=Holt, Rinehart and Winston

| title =Introductory Signal Processing

|edition=2

| pages=286-289

|date=1984

| publisher =World Scientific Pub Co Inc.

|isbn=0-03-061703-0

| series =Advanced Series in Electrical and Computer Engineering

}}

| volume =6

| date =July 1991

| ___location =Teaneck, N.J.

| url =https://books.google.com/books?id=QBT7nP7zTLgC&printsec=frontcover&dq=Priemer,+Roland&hl=en&sa=X&ei=J2owUZzANIb_ygGex4HAAg&ved=0CC8Q6AEwAA

| isbn =9971-50-919-9

}}</ref>

<ref name=Jeruchim>

{{cite book

| ref=refJeruchim

| last =Jeruchim

| first =Michel C.

| last2 =Balaban

| first2 =Philip

| last3 =Shanmugan

| first3 =K. Sam

| title =Simulation of Communication Systems: Modeling, Methodology and Techniques

| pages=73-74

| publisher =Kluwer Academic Publishers

| edition =2nd

| date =October 2000

| ___location =New York

| isbn =0-30-646267-2

}}</ref>

== Further reading ==

<ref name=Udayashankara>

*{{cite book |author1=Oppenheim, Alan V. |author2=Willsky, with S. Hamid |title=Signals and Systems |publisher=Pearson Education |year=1998 |isbn=0-13-814757-4}}

{{cite book

| ref=refUdayashankara

| last =Udayashankara

| first =V.

| title =Real Time Digital Signal Processing

| page=189

| publisher =Prentice-Hall

| date =June 2010

| ___location =India

| isbn =8-12-034049-3

}}</ref>

}}

{{refbegin}}

#<li value="6">{{cite book |author1=Oppenheim, Alan V. |author2=Willsky, with S. Hamid | title=Signals and Systems | publisher=Pearson Education | year=1998 | isbn=0-13-814757-4}}

</li>

{{refend}}