3
$\begingroup$

I am currently trying to understand the Chirp Z Transform, and compute an FFT for a vector that has size which is not necessarily a power of 2. The key step in the Chirp Z transform to recognize that the boils down to computing a circular convolution of two vectors of length $n$.

My question is: How does one compute the circular convolution of two vectors say ($x[1],x[2],...,x[n]$) and ($y[1],y[2],...,y[n]$) using DFTs only sizes that are a power of 2? I know that by the convolution theorem, I can find the circular convolutions of two vectors applying the DFT (and it's inverse) a few times, but I only have power of 2 sized DFTs at my disposal to compute this for arbitrary $n$. I considered padding the vectors to increase their size to the nearest power of 2, but it seems as if one must carefully construct such a padding to get the right result (since we need to compute modulo $n$ and not $2^k$).

For more context: I was going through Dilip Sarwate's answer on this topic at this link: https://math.stackexchange.com/questions/104148/chirp-transform-and-convolution[on math stackexchange]1 and was unable to figure out how one can compute a circular convolution efficiently.

$\endgroup$
4
$\begingroup$

Circular convolution is just linear convolution aliased by DFT length $n$. The length of linear convolution of $a$ and $b$ will be $2n-1$. So take $FFTs$ of $a$ and $b$ , padding each of them to length nearest power of 2 more than or equal to $2n-1$. Multiply the corresponding $FFTs$ point by point to get a power of 2 length sequence and take $IFFT$ of it. This sequence is actually the linear convolution of $a$ and $b$ since we had done enough padding before taking their individual $FFT$. Let this sequence be named $c$. Now, alias in time domain by shifting copies of $c$ by $n$ and adding them on top of each other. $$ d[m] = \sum_{k=-\infty}^{k=+\infty} c[m - nk] $$ The final output you want is $d[m]\,\text{for}\, 0\le m \le n-1$

$\endgroup$
1
  • $\begingroup$ Thanks! This makes sense now. $\endgroup$
    – darthsid
    Dec 20 '20 at 18:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.