# Circular Convolution and FFT of power 2

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.

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$$