Fractional Frequency Shifting a Discrete Signal in the Frequency Domain

Question

In our current hardware-based signal processing pipeline, we have a time-domain signal $x[n]$ that we want to frequency shift by $f_0$. To do this, we multiply the signal by a complex exponential in the time-domain. Afterwards, as part of our processing, we feed it into an FFT to get $X[k+f_0]$.

Given that we are converting to the frequency-domain, a consideration is to change our signal processing chain and instead frequency shift after the FFT, in the frequency-domain instead. If this could be done with relatively fewer hardware resources, we would be able to store $X[k]$ and perform a frequency shift on the frequency-domain samples of $X[k]$ later, eliminating an FFT that is part of our processing pipeline. The reality of doing this in hardware is yet to be determined, but I am simply surveying this in MATLAB and the three methods for frequency shifting that I am comparing are:

• Multiplying $x[n]$ by a complex exponential (time-domain)
• Linear interpolation on $X[k]$ (frequency-domain)
• Sinc interpolation on $X[k]$ (frequency-domain)

It is clear that for frequency shifts that are a multiple of the FFT bin spacing, a simple rotation from $X[k]$ to $X[k+l]$ where $l$ is an integer gives us accurate shifts. However, for frequency shifts that are between the frequency bins, we find that we require fractional shifts and need to interpolate between values of $X[k]$. Reading about this (and getting refreshers on signal theory that I probably should not have forgotten), the Nyquist-Shannon Sampling Theorem says we can use sinc interpolation to reconstruct a signal from its discrete samples provided it satisfies Nyquist sampling criteria.

As a demonstration to show each method of frequency shifting, I am plotting the value of a single sample from the FFT of a randomly generated complex signal as it is frequency-shifted, using each method. Each asterisk marks the discrete FFT values of $X[k]$. The blue curve on the first three graphs is either the true or reconstructed $X[k+f_0]$, depending on which method is used. The last graph is then same test but with different samples, and with each result overlaid. We see that the monitored FFT point passes through each discrete value, but the linear and sinc interpolation plots differ from the exponential-shifted result. This makes sense for linear, however I would expect sinc interpolation to match.

The sinc interpolation code that I am using is based on MATLAB's interpolation code found on the sinc function page. I have also tried various time-domain inputs ranging from random complex data, step, delta, ramp, and tone. Additionally, I have performed the same test when applying low-pass filtering to the input. In each of these cases, both my sinc interpolation and MATLAB's example code match, but fails to match the complex exponential frequency shift. The code that I'm using for the sinc interpolation (since it may be beneficial) is:

function Y = sinc_interpolation(X,shift)   
    n = (0:length(X)-1)+shift;
    Y = zeros(1,length(X));
    for i = 0:length(X)-1
        s = sinc(n-i);
        Y(i+1) = s * X';
    end
    Y = conj(Y);
end

With the gist of my code being:

% Parameters
N = 64;          % Data Length
BIN_WIDTH = 32;  % Number of frequency steps between bins
F0 = 32;          % Freqeuency shift

% Determine fractional shift
FRAC_SHIFT = F0 / BIN_WIDTH;

% Generate Random signal 
x = (-1 + 2 * rand(1,N)) + 1i * (-1 + 2 * rand(1,N));
X = fft(x);

% Complex exponential (time domain, reference)
x_shift = x .* exp(FRAC_SHIFT*2*pi*-1i*(0:N-1)/N);
X_COMPLEX_EXPONENTIAL = fft(x_shift);

% Linear interpolation (freq domain)
X_LINEAR_INTERPOLATION = fraccircshift(X,FRAC_SHIFT);

% Sinc interpolation (freq domain)
X_SINC_INTERPOLATION   = sinc_interpolation(X,FRAC_SHIFT);

...
% This is then extended to repeat these functions
% for varying frequency shifts, to grab one sample
% from the interpolated FFT results, and to plot them.
...

Are there critical steps pertaining to sinc interpolation that I may be missing? Would sinc interpolation be failing to match the time-domain frequency shifting because this data (despite attempting to band-limited in the time-domain) is not band limited when treated as an arbitrary sequence of numbers for sinc interpolation?

Lastly, is this a practical approach or does general wisdom from a signal processing engineer say to stick to the time-domain?

Answer 1

The frequency domain equivalent of frequency shifting is NOT sinc interpolation but circular convolution with a spectrum of $x[n] = e^{j2\pi\frac{n+\delta}{N}}$, where $\delta$ is your fractional shift value.

The magnitude of this is similar to a circular (not linear) sinc, but it is complex, so there is also phase component to it.

If this could be done with relatively fewer hardware resources,

Unless your FFT size is very small (64 or less) that outcome is very unlikely. Direct circular convolution in the frequency domain is expensive and hence the standard implementation is done in the time domain using FFTs.