I have a discrete signal $y[n] = <e^{j ~ 2 \pi f ~ n}>_J + ~w[n]$ with $n \in [0, N[$ and $w[n]$ AWGN, $<x[n]>_K$ denotes the signal $x[n]$ circularly shifted by $K$ samples. Let's define $Y_k = \mathrm{DFT}(y[n])$ the output of the $N$-point DFT of $y[n]$. By ignoring the AWGN and using well-known Fourier properties, we can deduce that $Y_k$ is a sinc function centered around $f$, multiplied by $e^{\tfrac{k J}{N} }$ due to the circular shift.

In my application, $J$ is unknown to me but I am interested in obtaining an estimation of $f$ (which is real-valued in $[0, N[$). Over the years, many estimators $\hat{f}$ for single tone signals $z[n] = e^{j ~ 2 \pi f ~ n} + ~w[n]$ have been designed, and they work fairly well. These estimators rely either on the complex values $Z_k$ (i.e. the DFT of $z[n]$, see e.g. [R1], which I can't use because I don't know $J$), or use the amplitudes of interpolated DFT bins, e.g. $\hat{f}_{res}$ which computes the residual frequency offset inside two DFT bins from [R2]:

$$ \hat{f}_{res} = \frac{|\bar{Z_1}|^2 - |\bar{Z}_{-1}|^2}{u(|\bar{Z_1}|^2 + |\bar{Z}_{-1}|^2) + v|\bar{Z_0}|^2} $$

where $\bar{Z}_k$ is the zero-padded $2N$-point DFT ($N$ points are from $z[n]$, the following $N$ points are $0$). $\bar{Z}_0$ is the bin with greatest amplitude and $\bar{Z}_1$/$\bar{Z}_{-1}$ are its neighbors. It is interesting to note that in the case of a $N$-point DFT, $|Y_k| = |Z_k|$. However this property does not hold anymore for the interpolated bins in $\bar{Y}_k$ obtained through the zero-padding, and I am unable to figure why analytically.

Here's an illustration of the difference of amplitudes between $\bar{Z}_k$ (zero-padded DFT of true single tone signal) and $\bar{Y}_k$ (zero-padded DFT of the circularly shifted signal): enter image description here

and the MATLAB code used to generate the figure:

N = 256;
f = 100.4/N;
J = 125;

% Compute z[n]
n = 0:(N-1);
z = exp(2*pi*1j*f*n);

% Compute zero-padded DFT Z[k]
z2 = zeros(1, N*2);
z2(1:N) = z;
Z2 = fft(z2);

% Compute zero-padded DFT Y[k]
y2 = zeros(1, N*2);
y2(1:N) = circshift(z, J);
Y2 = fft(y2);

subplot(2, 1, 1);
hold on;
xlim([1 2*N])
legend('|Z(k)|', '|Y(k)|', 'Location','northwest')

subplot(2, 1, 2);
stem(abs(Z2) - abs(Y2))
xlim([1 2*N])
legend('|Z(k)| - |Y(k)|', 'Location','northwest')

Does someone have any clue on how to model analytically the interpolated DFT bins in $\bar{Y}_k$, or the DTFT of $y[n]$ ? Thanks.

[R1] https://www.researchgate.net/publication/3321864_Fast_Accurate_Frequency_Estimators_DSP_Tips_Tricks

[R2] https://ieeexplore.ieee.org/document/5910415 (unfortunately behind a paywall)

  • 3
    $\begingroup$ Have you come across this blog? $\endgroup$ – Irreducible Sep 4 '19 at 18:19

The clue is that without zero-padding, the circulary shifted sequence is just a shifted version of the periodic continuation of the original sequence. That's why without zero-padding the magnitudes of the DFTs of both sequences are identical.

When you use zero-padding, the two sequences cannot be obtained from each other by pure shifting. So the DFTs must be different.

You can avoid the problem by zero-padding the circularly shifted sequence between the last and the first element of the original sequence:

% this assumes that J is in [0,N]
y2 = [z(N-J+1:N),zeros(1,N),z(1:N-J)];
Y2 = fft(y2);

This will guarantee that the magnitudes of the DFTs of the two sequences are the same, even after zero-padding.

| improve this answer | |
  • $\begingroup$ Indeed, thanks for the explanation. This makes more sense than what I originally had in mind. $\endgroup$ – Zashas Sep 5 '19 at 13:55

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.