Prove finite transform identities, diagonalize circular filters and derive a bounded radix-two implementation with explicit normalization and arithmetic costs.
Open any lesson. Completion records participation; automatic practice checks and human judgment of written arguments are separate. This unit retains its own versioned requirements.
Readiness and preparation
Check your starting point
Try these short questions on paper, then compare your reasoning. They are optional self-checks, not a placement score or a navigation requirement. Use a targeted review when useful and return with your browser’s Back control.
What does multiplication by exp(iθ) do to a complex number?
Fourier coefficients combine rotations and magnitudes; the sign of the angle determines the convention.
Compare reasoning and find a refresher
It rotates by θ without changing magnitude. Conjugation reverses the angle; at θ=−π/2 the multiplier is −i.
Why does an orthogonal basis allow coefficients to be recovered by inner products?
Fourier inversion depends on orthogonality and the norm of each basis vector, not merely on having distinct vectors.
Compare reasoning and find a refresher
Taking the inner product with one basis vector kills the other terms. Divide by its squared norm to recover that coefficient; normalized vectors have squared norm one.
Track cyclic indices through the Fourier transform, identify circulant eigenmodes and determine when padding turns a circular computation into an ordinary convolution.
Prove the circular convolution theorem and circulant diagonalization with the specified Fourier signs and normalization.
Classify invertibility, attainable outputs and kernel modes by transformed filter values.
Derive delay phases and polynomial wraparound, then justify a sufficient zero-padding length for linear convolution.
Split a negative-exponent Fourier transform into even and odd subsequences, prove the recursive index contract, and audit exact work and numerical checks.
Prove the even/odd butterfly identities and the recursive natural-order output contract for powers of two.
Derive exact complex-arithmetic operation counts under a stated treatment of trivial twiddles.
Construct the inverse through conjugation and distinguish exact identities from floating-point comparison evidence.