Circular convolution

• categories: Definition, Functional analysis, Signal processing

Circular Convolution

Definition

The circular convolution of two discrete sequences $f[n]$ and $g[n]$ of length $N$ is defined as:

$$(f⊛g)[n]=\sum _{k=0}^{N-1}f[k]g[(n-k)\mathrm{mod}N],$$

where the indices wrap around using modulo $N$, making the sequences periodic.

Key Intuition

1. Wrapping Behavior:
   Unlike linear Convolution, circular convolution treats the sequences as periodic, meaning the summation “wraps around” when indices go out of bounds.

2. Frequency Domain Relationship:
   Circular convolution corresponds to pointwise multiplication of the discrete Fourier transforms (DFTs) of the sequences:

   $$\text{DFT}(f⊛g)=\text{DFT}(f)\cdot \text{DFT}(g).$$

---

Properties

1. Commutativity:

   $$f⊛g=g⊛f.$$

2. Associativity:

   $$(f⊛g)⊛h=f⊛(g⊛h).$$

3. Distributivity:

   $$f⊛(g+h)=(f⊛g)+(f⊛h).$$

4. Connection to Linear Convolution:
   When $f[n]$ and $g[n]$ are zero-padded to length $2N-1$ before computing circular convolution, the result matches the linear convolution of the original sequences.

---

Applications

1. Fast Convolution via FFT:
   Circular convolution allows efficient computation of convolution using the Fast Fourier Transform (FFT), as:

   $$f⊛g=\text{IFFT}(\text{FFT}(f)\cdot \text{FFT}(g)).$$

2. Digital Signal Processing:
   Used in systems where periodic signals or wrapping behavior is natural, such as in discrete-time Fourier analysis.

3. Image Processing:
   Circular convolution handles edge effects in periodic image filtering.