Content deleted Content added
add external link to a citation |
move citations from Notes to References |
||
Line 1:
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.
|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# }}
Let ''x'' be a function with a well-defined periodic summation, ''x''<sub>''T''</sub>, where:
Line 12 ⟶ 14:
&\equiv \int_{t_o}^{t_o+T} h_T(\tau)\cdot x_T(t - \tau)\,d\tau,
\end{align}
</math>
|Proof:
:<math>\begin{align}
Line 22 ⟶ 25:
={} &\int_{t_o}^{t_o+T} \underbrace{\left[\sum_{k=-\infty}^\infty h(\tau + kT)\right]}_{\triangleq \ h_T(\tau)}\cdot x_T(t - \tau)\ d\tau \quad \quad \scriptstyle{(QED)}
\end{align}</math>
}}
</ref>▼
where ''t''<sub>o</sub> is an arbitrary parameter and ''h''<sub>''T''</sub> is a [[periodic summation]] of ''h''.
The second integral is called the '''periodic convolution'''<ref
== Discrete sequences ==
Line 45 ⟶ 48:
=== Overlapping input blocks ===
This method uses a block size equal to the FFT size (1024). We describe it first in terms of normal or ''linear'' convolution. When a normal convolution is performed on each block, there are start-up and decay transients at the block edges, due to the filter ''latency'' (200-samples). Only 824 of the convolution outputs are unaffected by edge effects. The others are discarded, or simply not computed. That would cause gaps in the output if the input blocks are contiguous. The gaps are avoided by overlapping the input blocks by 200 samples. In a sense, 200 elements from each input block are "saved" and carried over to the next block. This method is referred to as '''[[Overlap-save method|overlap-save]]''',<ref
When an FFT is used to compute the 824 unaffected DFT samples, we don't have the option of not computing the affected samples, but the leading and trailing edge-effects are overlapped and added because of circular convolution. Consequently, the 1024-point inverse FFT (IFFT) output contains only 200 samples of edge effects (which are discarded) and the 824 unaffected samples (which are kept). To illustrate this, the fourth frame of the figure at right depicts a block that has been periodically (or "circularly") extended, and the fifth frame depicts the individual components of a linear convolution performed on the entire sequence. The edge effects are where the contributions from the extended blocks overlap the contributions from the original block. The last frame is the composite output, and the section colored green represents the unaffected portion.
Line 51 ⟶ 54:
=== Overlapping output blocks ===
This method is known as ''[[overlap-add method|overlap-add]]''.<ref
== See also ==
Line 58 ⟶ 61:
== Notes ==
{{
== References ==
{{reflist|refs=
<ref name=Rabiner>
| ref=refRabiner
| author1=Rabiner, Lawrence R.
| author2=Gold, Bernard
| title=Theory and application of digital signal processing
| pages=63-67
| year=1975
| publisher=Prentice-Hall
| ___location=Englewood Cliffs, N.J.
| isbn=0-13-914101-4
| pages=63–67
| url-access=registration
| url=https://archive.org/details/theoryapplicatio00rabi/page/63
}}</ref>
<ref name=Oppenheim>
{{cite book
|ref=refOppenheim
|last=Oppenheim
Line 73 ⟶ 93:
|first3=John R.
|title=Discrete-time signal processing
|pages=388-389
|year=1999
|publisher=Prentice Hall
Line 78 ⟶ 99:
|isbn=0-13-754920-2
|edition=2nd
|url-access=registration
|url=https://d1.amobbs.com/bbs_upload782111/files_24/ourdev_523225.pdf▼
|url=https://archive.org/details/discretetimesign00alan/
▲</ref>
<ref name=Priemer>
{{cite book
| ref=refPriemer
| last =Priemer
| first =Roland
| title =Introductory Signal Processing
| 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.
| 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>
<ref name=Udayashankara>
{{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}}
▲*Priemer, Roland (July 1991). ''Introductory Signal Processing (Advanced Series in Electrical and Computer Engineering) (v. 6)''. Teaneck, N.J.: World Scientific Pub Co Inc. [https://books.google.com/books?id=QBT7nP7zTLgC&printsec=frontcover&dq=Priemer,+Roland&hl=en&sa=X&ei=J2owUZzANIb_ygGex4HAAg&ved=0CC8Q6AEwAA {{isbn|9971509199}}.
</li>
{{refend}}
▲*{{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}}.
[[Category:Functional analysis]]
| |||