Try
Place four samples around a circle: x=(1,2,0,−1), with indices 0,1,2,3. A two-tap filter h=(1,1,0,0) adds the current sample to the previous one. “Previous” at index 0 means index 3. Predict the output at index 0 before checking the table: it is 1+(−1)=0, not 1.
| Output index j | Current x(j) | Previous index modulo 4 | Previous value | Output y(j) |
|---|
| 0 | 1 | 3 | −1 | 0 |
| 1 | 2 | 0 | 1 | 3 |
| 2 | 0 | 1 | 2 | 2 |
| 3 | −1 | 2 | 0 | −1 |
The output is y=(0,3,2,−1). In general, for vectors of length n≥1, define circular convolution by y(j)=Σ over ℓ of h(ℓ)x(j−ℓ), with every subscript reduced modulo n. All sums have exactly n terms. The minus sign is part of the definition, not an interchangeable drawing convention.
Predict
Can this filter be inverted? Try adding the alternating vector v=(1,−1,1,−1) to x. Each filtered adjacent pair receives one plus and one minus, so the output stays unchanged. A filter can lose information even though it produces a perfectly well-defined output at every position.
We use the forward-transform convention ω=exp(−2πi/n) and X(k)=Σ over j of x(j)ω^(jk). Inversion uses x(j)=(1/n)Σ over k of X(k)ω^(−jk). These definitions fix both the sign and the normalization. At n=4, ω=−i and the filter transform is H=(2,1−i,0,1+i). Its zero at k=2 is the alternating direction just discovered on paper.
The input transform is X=(2,1−3i,0,1+3i). Predict the output transform by multiplying the corresponding filter entries. You obtain Y=(4,−2−4i,0,−2+4i). Directly transforming the output table gives the same result. The next proof explains why this agreement holds for every input, including complex-valued ones.
Experiment
Write the matrix C_h that maps x to y. Its entry in row j and column a is h(j−a). Thus column a is h shifted by a positions. For our filter the rows are (1,0,0,1), (1,1,0,0), (0,1,1,0), (0,0,1,1). Multiply this matrix by both the original input and the alternating vector.
Change only the requested output to z=(1,0,0,0). Could any input produce it? Every output of this filter has alternating sum zero, but z has alternating sum 1. Thus the request is incompatible. For the original y, in contrast, every vector x+c(1,−1,1,−1) produces the same output. Distinguish “no solution for this request” from “many solutions for an attainable request.”
For a nearby action, delay an impulse at index 0 by one position. It becomes the impulse at index 1. Its transform is (1,−i,−1,i), not (1,i,−1,−i). This quick check is useful whenever a formula for a delay or a circulant eigenvector seems to have an uncertain sign.
Understand
Expand the transform of the convolution:
Y(k)=Σ over j,ℓ of h(ℓ)x(j−ℓ)ω^(jk).
For each fixed ℓ, the substitution a=(j−ℓ) modulo n permutes the residue indices bijectively. Since ωⁿ=1, replacing an index by another representative of the same residue does not change its power. Consequently ω^(jk)=ω^((a+ℓ)k). The finite double sum factors into the product of the sum over ℓ and the sum over a, proving Y(k)=H(k)X(k). There is no extra factor n in this forward-transform convention. The 1/n occurs when transforming back.
The corresponding matrix statement can be checked without memorizing a Fourier matrix orientation. Define v_k(j)=ω^(−jk). Then
(C_h v_k)(j)=Σ over ℓ of h(ℓ)ω^(−(j−ℓ)k)=H(k)v_k(j).
The preceding Fourier orthogonality theorem shows that these n vectors form a basis. Thus C_h is diagonal in that basis, with eigenvalues H(k). It is invertible exactly when all H(k) are nonzero. In that case recover X(k)=Y(k)/H(k) and apply inverse transformation. If H(k)=0, the corresponding eigenvector belongs to the kernel. An output is attainable exactly when Y(k)=0 at every vanished filter mode: necessity follows from the product, while sufficiency follows by dividing the other coordinates and freely choosing the missing ones. This also describes every solution and the entire kernel. At n=1 all statements reduce to ordinary scalar multiplication.
Another useful representation encodes a vector x by the polynomial x(z)=Σ x(j)zʲ. In a product h(z)x(z), the coefficient at a degree congruent to j modulo n contributes to the circular output y(j). Setting zⁿ=1 folds degrees differing by n together. Therefore circular convolution is polynomial multiplication modulo zⁿ−1. This is an equality of residue classes of polynomials, not an assertion that higher coefficients disappeared before the product was formed.
For ordinary linear convolution, suppose the two inputs have lengths m and ℓ and are zero outside indices 0 through m−1 and 0 through ℓ−1. Their product degree is at most m+ℓ−2. Padding each with zeros to a common length n≥m+ℓ−1 leaves every product coefficient below n, so reduction modulo zⁿ−1 changes nothing. Smaller lengths can fold distinct output coefficients together. Special cancellations may allow a shorter length for particular inputs, but they do not supply a guarantee for every pair of the declared lengths.
Finally define a cyclic delay D_r x by (D_r x)(j)=x(j−r). The same residue substitution gives its transform ω^(rk)X(k). A delay changes mode phases, not magnitudes, because each phase factor has modulus 1. Reversing the convolution index to x(j+ℓ) instead changes the multiplier to H(−k modulo n). For real h this equals the complex conjugate of H(k), but for arbitrary complex h it need not. An operation that additionally conjugates the filter requires its own definition; do not infer it from a name such as correlation.
Apply
Multiply a(z)=1+2z and b(z)=1−z+z². The ordinary product is 1+z−z²+2z³, so linear convolution gives (1,1,−1,2). With circular length 3, the last coefficient wraps into index 0, giving (3,1,−1). Padding both inputs to length 4 preserves all four coefficients. Explain which original term was added to the first entry and why a zero-padded input can still produce a nonzero last output.
For an inverse-filter repair, replace the worked filter by h=(2,1,0,0). The polynomial (2+z)(8−4z+2z²−z³) equals 16−z⁴, hence is 15 modulo z⁴−1. Therefore g=(8,−4,2,−1)/15 is its circular inverse: h∗g is the impulse at zero. Check the four entries using 2g(j)+g(j−1). Some filter entries are zero, but no frequency multiplier is zero. Nonzero coefficients and invertible filtering are different properties.
Continue
Record the transform sign, inverse normalization, cyclic index orientation and sampling length before using a convolution formula. A circulant diagonalization identifies which requests are attainable and which modes are lost. Zero padding can convert an ordinary finite convolution into a circular computation only when the output has enough room. Even with no exact zero modes, division by very small H(k) can amplify errors; exact invertibility alone is not a numerical accuracy certificate.
