Circular convolution
From Wikipedia, the free encyclopedia
Discrete Fourier transform and Convolution. And we note that circular boundary conditions are merely one possible boundary condition for convolution. One can also have e.g. even/odd boundary conditions of various types. (For example, every type of discrete cosine transform and discrete sine transform corresponds to convolutions with a different distinct boundary condition.)
Depending on the application, circular convolution can be a useful operation or an unwanted side-effect. The intent of this article is to document specific applications and issues.
Contents |
[edit] Filtering
[edit] Fast convolution
Convolution of time-domain functions is equivalent to multiplication of their Fourier transforms. Due to the efficiencies of the fast Fourier transform algorithm, the latter is often done (in digital signal processing) to maximize the speed of a signal filtering task. In the time domain, convolution filtering is inherently a continuous streaming process. But in the frequency domain, block-processing is required. The time-domain signal is divided into segments (blocks) and processed piecewise. Then the filtered segments are carefully pieced back together, mindful of edge effects, which means that a portion of each output segment must be discarded. Data loss is avoided by overlapping the initial input segments.
If linear convolution were performed on each block, the discarded data would represent the start-up transient (or latency) of the filter. When the DFT or FFT is used, the edge-effect has the same duration, just different values. During the start-up transient, the convolution is actually using data from both the beginning and the end of the block, as if the data were periodic or circular. To illustrate this, the fourth frame of the figure depicts a block that has been periodically 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 added blocks overlap the contributions from the original block. The last frame is the composite output, and the portion colored green represents the unadulterated output from the original input block.
[edit] Test signal generation
Sometimes it is useful to generate a periodic test signal/sequence. If one cycle of the test signal is synthesized and then simply repeated indefinitely, there might be a harsh discontinuity where one cycle ends and the next begins. One way to mitigate that is to filter the repeating sequence, but that requires a dedicated, real-time filter component. So another way is to circularly filter the synthesized segment [once] before repeating it indefinitely.
