# Bluestein's algorithm to evaluate the DFT from $f_o$ to $f_o + k\Delta_F$

Briefly, the convolution between $$x(nT) e^{-j2\pi f_o nT} e^{-j \pi \Delta_F Tn^2}$$ and $$c(nT) = e^{j \pi \Delta_F T n^2}$$ multiplied $$e^{j \pi \Delta_F T k^2}$$ allows me to find the DFT $$X(f_k = f_o + k\Delta_F)$$. Let $$N_x$$ be the number of samples of $$x(nT)$$, I found that $$c(nT)$$ must be at least of length $$2N_x$$ but I don't know why. Can someone tell me how do I choose the number of samples of $$c(nT)$$?

• Your question is hard to read. It would help if you write this a complete equation showing all operations and properly defining all your symbols. Sep 18 '20 at 11:51
• We need to find the first k-th element of the Fourier transform of $x(nT)$ starting from $f_o$ and going up with steps of amplitude $\Delta_F$. The way to do that is using the following relation $X(f_k = f_o + k\Delta_F) = T \sum_{n=0}^{N_x-1} x(nT) e^{-j2\pi (f_o + k\Delta_F) nT}$ $X(f_k) = T \, e^{-j\pi\Delta_F T k^2} \sum_{n=0}^{N_x-1} x(nT) e^{-j2\pi f_o nT} e^{-j\pi\Delta_F Tn^2} e^{j\pi\Delta_F T (k-n)^2}$ Which can be seen as the convolution of two signals $X(f_k) = e^{-j\pi\Delta_F T k^2} \, T \sum_{n=0}^{N_x-1} z(nT) c(kT-nT)$ The question is Sep 18 '20 at 14:35
• How do I properly choose the length of $c(nT)$ ? Sep 18 '20 at 14:47
• $T$ is the sampling period Sep 18 '20 at 14:57

The convolution in Bluestein's algorithm is a linear convolution, not circular. Since the approach is to use standard FFT's for the convolution operation, the underlying waveforms being convolved must be zero padded out to $$M \ge 2N-1$$ to compute the linear convolution accurately.
• Yes, $z(nT)$ must be zero padded to perform the convolution but I can also perform the circular convolution without padding $c(nT)$ because $X(f_k)$ can be suppose periodic. For example I can choose $c(nT)$ with $2N_x$ samples pad with $N_x$ the signal $z(nT)$ perform the convolution and discard the first $N_x$ samples. The question is not how to perform the convolution but why do I build the signal $c(nT)$ with $2N_x$ samples and $n$ that goes from $-N_x$ to $N_x-1$ ? Can you explain what "zero padded out" means? Unfortunately I'm not English Sep 18 '20 at 23:46
• I know what zero padding means but you said "zero padded out", my question was "out" where? At the end of $c(nT)$? Anyway, you can pad $z(nT)$ with $N_x$ values and perform the convolution via dft (circular convolution) and discard the transient (the first $N_x$ samples) the results is right without adding zeros to $c(nT)$, I think this is due to the periodicity of $X(f_k)$. Can you also explain me why do I choose $c(nT)$ with $2N_x$ samples? Sep 19 '20 at 9:06