Circular Convolution and FFT of power 2

Question

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.

Answer 1

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$