Cyclic folding

The cyclic convolution , also known as circular convolution or periodic convolution , is a form of discrete convolution in functional analysis . Here are sequences of length periodically continued, which arise from the cyclic shift of the sequence. Cyclic convolution is primarily used in digital signal processing , for example to implement digital filters . ${\ displaystyle N}$

General

Compare discrete aperiodic convolution, left column, and right discrete cyclic convolution

In combination with the discrete Fourier transformation (DFT), in particular the fast Fourier transformation (FFT), the cyclic convolution can be used to replace the computationally intensive discrete aperiodic convolution operation in the time domain with a more efficient multiplication in the spectral domain . The periodic convolution has its origin in the block-based structure of the FFT algorithm.

To form the fast convolution , the cyclic convolution is expanded by fast Fourier transformation and methods such as the overlap-save method or overlap-add method , with the aim of efficiently realizing higher-order non-recursive digital filters (FIR filters). Conventional FIR filters in the direct normal form immediately carry out the aperiodic convolution operation, which is more inefficient than fast convolution from approx. 50 filter orders.

The cyclical shift by places in a sequence of length can be expressed with the modulo operation: ${\ displaystyle m}$ ${\ displaystyle x [n]}$ ${\ displaystyle N}$

{\ displaystyle {\ tilde {x}} [nm] = x [(nm) {\ bmod {N}}]}

periodically continued sequences are marked with the tilde symbol. In the figure on the left, two exemplary sequences and the length and their aperidoic convolution result are shown. Right to the periodically-continued effects and and the cyclic convolution product formed therefrom . ${\ displaystyle x_ {1}}$ ${\ displaystyle x_ {2}}$ ${\ displaystyle N = 4}$ ${\ displaystyle {\ tilde {x}} _ {1}}$ ${\ displaystyle {\ tilde {x}} _ {2}}$ ${\ displaystyle {\ tilde {x}} _ {1} * {\ tilde {x}} _ {2}}$

literature

Alan V. Oppenheim, Ronald W. Schafer: Discrete-time signal processing . 3. Edition. Oldenbourg, 1999, ISBN 3-486-24145-1 .