Circular convolution

The circular convolution \( \mathbf{z} = \mathbf{x} \circledast \mathbf{y} \) between two vectors \(\mathbf{x}\) and \(\mathbf{y}\) in \(\mathbf{C}^N\) is defined by: \[z_n = \sum_{k=0}^{N-1} x_{(k - n\ \mathrm{mod. } N)} y_k\] for \( 0 \leq n < N\).

It can be interpreted as the product of a circular matrix and a vector. With \(N = 4\) : \[ \left( \begin{array}{c} z_0 \\ z_1 \\ z_2 \\ z_3 \end{array} \right) = \left( \begin{array}{cccc} x_0 & x_{3} & x_2 & x_1 \\ x_1 & x_0 & x_3 & x_2 \\ x_2 & x_1 & x_0 & x_3 \\ x_3 & x_2 & x_1 & x_2 \end{array} \right) \left( \begin{array}{c} y_0 \\ y_1 \\ y_2 \\ y_3 \end{array} \right) \] or equivalently, using the commutativity of the convolution: \[ \left( \begin{array}{c} z_0 \\ z_1 \\ z_2 \\ z_3 \end{array} \right) = \left( \begin{array}{cccc} y_0 & y_{3} & y_2 & y_1 \\ y_1 & y_0 & y_3 & y_2 \\ y_2 & y_1 & y_0 & y_3 \\ y_3 & y_2 & y_1 & y_2 \end{array} \right) \left( \begin{array}{c} x_0 \\ x_1 \\ x_2 \\ x_3 \end{array} \right) \]

Consequence : coefficients in the tails of the input signals will influence the head of the result.