# Chirp Transform and Convolution

I was reading about the discrete fourier transform from the CLR algorithms book and I came upon an exercise whose hint confuses me. The exercise reads as follows:

The chirp transform of a vector $a=(a_0,a_1,\ldots,a_n)$ is a vector $y=(y_0,y_1,\ldots,y_n)$, where $y_k=\sum_{j=0}^{n-1}a_j (z^{k})^j$ and $z$ is any complex number. The DFT is therefore a special case of the chirp transform, obtained by taking $z=\omega_n$. Prove that the chirp transform can be evaluated in time $O(n\lg n)$ for any complex number $z$. (Hint: use the equation $$y_k = z^{k^2/2}\sum_{j=0}^{n-1}(a_j z^{j^2/2})(z^{-(k-j)^2/2})$$ to view the chirp transform as a convolution.

My question is about what is a convolution. I am familiar with taking two vectors $a=(a_0,a_1,\ldots,a_n)$ and $b=(b_0,b_1,\ldots,b_n)$ and forming the convolution $c=(c_0,c_1,\ldots,c_n)$ where $c_k = \sum_{j=0}^k a_j b_{k-j}$. Here the index of $j$ runs from $0$ to $k$ unlike in the hint given above where the index runs from $0$ to $n-1$. In what sense is the hint above a convolution?

-
I presume you haven't seen Bluestein's trick, then? –  Ｊ. Ｍ. Jan 31 '12 at 4:14
My question isn't about why Bluestein's trick is true. It's about why can the DFT be used to compute the "convolution" in Bluestein's trick –  user782220 Jan 31 '12 at 5:45
Well, one could adapt the reasoning here to the discrete Fourier transform... –  Ｊ. Ｍ. Jan 31 '12 at 5:59
Your statement about the convolution theorem is correct (though unduly restrictive in that it is not necessary for $n$ to be a power of $2$; $n$ can be any positive integer), but the point you are missing is that the result $a\otimes b$ is a vector of length $2n$ of which as many as $2n-1$ components can be nonzero. In other words, $a\otimes b$ is not a vector of length $n$ padded with $0$s to length $2n$, it is a vector of length $2n-1$ padded with one $0$. The convolution supported by the DFT is circular convolution, not linear convolution, and that is .... –  Dilip Sarwate Jan 31 '12 at 23:46
...and that is why you have to use a DFT twice as long as the vectors, and zero-pad the vectors, so as to use the convolution theorem to get the result of a linear convolution. –  Dilip Sarwate Jan 31 '12 at 23:48

Convolution and the Discrete Fourier Transform:

Suppose $(a_0, a_1, \ldots, a_{n-1})$ and $(b_0, b_1, \ldots, b_{n-1})$ denote two complex-valued sequences of length $n$, and let $a(z)=\sum_k a_kz^k$ and $b(z)=\sum_k b_kz^k$ denote the corresponding polynomials of degree $< n$.

• The linear or aperiodic convolution of the two sequences is defined as the sequence $(c_0, c_1, \ldots, c_{2n-2})$ of length $2n-1$ where $$c_k = \begin{cases}\sum_{j=0}^k a_jb_{k-j}, &0 \leq k \leq n-1\\ \sum_{j=k-(n-1)}^{n-1} a_jb_{k-j}, &n \leq k \leq 2n-2. \end{cases}$$ and the corresponding polynomial $c(z) = \sum_k c_kz^k$ of degree $< 2n-1$ equals $a(z)b(z)$.

• The circular or cyclic or periodic convolution of the two sequences is defined as the sequence $(d_0, d_1, \ldots, d_{n-1})$ of length $n$ where $$d_k = \sum_{j=0}^{n-1}a_jb_{(k-j) \bmod ~n}, ~0 \leq k \leq n-1.$$ Note that $$d_k = \begin{cases}c_k + c_{k+n}, &0 \leq k \leq n-2,\\ c_{n-1}, & k = n-1, \end{cases}$$ and the corresponding polynomial $d(z) = \sum_k d_k z^k$ of degree $< n$ equals $a(z)b(z) \bmod (z^n - 1)$ where for future reference we write this as $a(z)b(z) = q(z)(z^n-1) + d(z)$.

• Let $\omega = \exp(i2\pi/n)$ denote a complex $n$-th root of unity. The Discrete Fourier Transform (DFT) of $(a_0, a_1, \ldots, a_{n-1})$ is $(A_0, A_1, \ldots, A_{n-1})$ where $$A_k = \sum_{j=0}^{n-1} a_j \omega^{-jk} = a(\omega^{-k}), ~ 0 \leq k \leq n-1.$$ The inverse DFT of $(A_0, A_1, \ldots, A_{n-1})$ is $$a_k = \frac{1}{n}\sum_{j=0}^{n-1} A_j \omega^{jk} = \frac{1}{n}A(\omega^{k}), ~ 0 \leq k \leq n-1.$$ The inverse DFT of $(A_0B_0, A_1B_1, \ldots, A_{n-1}B_{n-1})$, the term-by-term product of the DFTs of $(a_0, a_1, \ldots, a_{n-1})$ and $(b_0, b_1, \ldots, b_{n-1})$, is $(d_0, d_1, \ldots, d_{n-1})$, the periodic convolution of the two sequences, not the aperiodic convolution. An informal proof of this is that $A_kB_k = a(\omega^{-k})b(\omega^{-k})$ are the values of $a(z)b(z)$ at the $n$-th roots of unity. Since $a(z)b(z) = q(z)(z^n-1) + d(z)$, we know the values of $d(z)$ at the $n$ $n$-th roots of unity, and thus $d(z)$ of degree $< n$ must be the unique polynomial of degree $< n$ that interpolates through these $n$ points.

Chirp signals: The OP asks in what sense $$\sum_{j=0}^{n-1}(a_j z^{j^2/2})(z^{-(k-j)^2/2})$$ can be considered a convolution? With $\hat{a}_j = a_jz^{j^2/2}$ and $b_j = z^{-j^2/2}$, this is very much like a cyclic convolution $$d_k = \sum_{j=0}^{n-1}\hat{a_j}b_{(k-j) \bmod ~n}, ~0 \leq k \leq n-1$$ and is a cyclic convolution if $z^{n^2/2} = 1$.

-