DSP-speak for the operation y ℋ x when ℋ is a circulant matrix corresponding to an LSI system (). Write out matrix multiply y ℋ x · ⋯ ⋯ ⋯ ⋯ → ⋮ ⋮ ⋮ ⋮ ↓ where the · is in the n th row. y n k 0 N 1 ℋ n k x k where ℋ is a circulant matrix and ℋ n k h n k N

ℋ is LSI. y n k 0 N 1 h n k N x k y h ⊛ N x y n h ⊛ N x n

Notation Since impulse response h completely describes ℋ, we often write: and .

Inner Product Interpretation of Circular Convolution Define the time reversal matrix ℛ as a matrix that reverses the time axis of a column vector (). ℛ h k h k N

h. flip h . flip h N i.e.: to periodize with a period of N. ℛ h . N 4 . h 0 N h -1 N h -2 N h -3 N h 0 N h 3 N h 2 N h 1 N 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 h 0 N h 1 N h 2 N h 3 N Given circulant ℋ 1 3 2 2 1 3 3 2 1 zeroth column h 0 c 1 2 3 zeroth row ℛ h 0 c 1 3 2 1 3 2 So circular convolution can be written as this y n inner product of row n of ℋ (turned into a column) x row n of ℋ tipped into a column but row n of ℋ tipped into a column vector is h n r C n h 0 C n ℛ h 0 c which is the circular shift of the zeroth row and where h 0 ℛ h 0 c and is the time reversed column. & so... y n x C n ℛ h 0 c for N ; put a * in second entry for N .

The Ring of Doom N operations are natural on a circle! Since they are naturally N -periodic ().

0 n N 1 . n . x 3 2 1 0 . We can put x on a circle/wheel ().

Time runs counter-clockwise. To do a circular shift by m , C m x : just spin the wheel counter-clockwise m units and read off the new signal. m 2 , C 2 ().

Spin two spots counter-clockwise then C 2 x x 2 x 3 x 0 x 1 . Time reversal, ℛ x : just read off wheel in clockwise direction ().

Read off in time reversed order then ℛ x x 0 x 3 x 2 x 1 .

"How to do" Cyclic Convolution Cyclic convolution works N is equivalent to "on the wheel," where the cylinder analogy is powerful. y n m 0 N 1 x m h n m N

Step 1 Plot x m ().

Step 2 Plot h m (backwards on cylinder) ().

Step 3 Spin h m n steps to implement h n m N anti-clockwise.

Step 4 Multiply pointwise x m wheel and h n m N wheel. The sum equals y n .

Step 5 Repeat steps 3 and 4 for all n .