# Frequency estimation of circularly shifted single tone signal

I have a discrete signal $$y[n] = _J + ~w[n]$$ with $$n \in [0, N[$$ and $$w[n]$$ AWGN, $$_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):

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.

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

• Have you come across this blog? – 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.

• Indeed, thanks for the explanation. This makes more sense than what I originally had in mind. – Zashas Sep 5 '19 at 13:55