2
$\begingroup$

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); stem(abs(Z2)); hold on; stem(abs(Y2)); 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)

$\endgroup$
1
  • 3
    $\begingroup$ Have you come across this blog? $\endgroup$ Commented Sep 4, 2019 at 18:19

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Indeed, thanks for the explanation. This makes more sense than what I originally had in mind. $\endgroup$ Commented Sep 5, 2019 at 13:55

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.