File Exchange

image thumbnail

fshift

version 1.31.0.0 (1.12 KB) by Francois Bouffard
Shifts the elements of an array by a (possibly non-integer) given number of elements.

5 Downloads

Updated 06 Aug 2015

View License

FSHIFT shifts the elements in a vector by a given number of elements, as CIRCSHIFT does. However, a non-integer shift value can be used, in which case the elements are shifted along the perfect (sinc-based) interpolation of the periodisation of the vector. For integer shift values, FSHIFT is equivalent to CIRCSHIFT to machine precision.
The syntax to FSHIFT is slightly different from CIRCSHIFT (FSHIFT expects only vectors for its first argument and a scalar for its second argument). Also, the second arguments produces a shift in the opposite direction of CIRCSHIFT to be consistent with the usual statement of the shift property of the Fourier transform.
FSHIFT works by introducing a linear phase into the vector's DFT. As such, if there is a discontinuity between the first and last elements of the input vector, the output vector may present significant ringing.

Comments and Ratings (16)

Another comment on Earl's note... It would appear that this is due to the ambiguity of having a signal for which the Nyquist frequency component is nonzero (which is only possible for an even-length sequence). Since multiple Nyquist-frequency sinusoids can pass through these samples (e.g. see https://en.wikipedia.org/wiki/Nyquist%E2%80%93Shannon_sampling_theorem#/media/File:CriticalFrequencyAliasing.svg), reconstructing / interpolating the signal (which is what is done here with fshift) is ambiguous.

Thus for now I don't think I will modify fshift, as it produces results compatible with interpft. However be aware that for even-length sequences with nonzero Nyquist components, both fshift and interpft will alter the magnitude spectrum of the sequence and prevent reversibility of fshift.

Just an update on Earl's remark, which is related to Ahmed's 2015 note. When using an even number of sample, the Nyquist frequency is sampled. fshift works by applying a linear phase envelope on the signal's DFT. This phase envelope has unitary modulus (i.e. samples lie on the unit circle) and a linear phase with a slope dependent upon the shift parameter. There is an ambiguity as to what phase to apply at the Nyquist Frequency.

The behavior of fshift can be changed by deciding what to do with the phase envelope at Nyquist. As it is right now, the phase envelope Nyquist sample is forced to be the average of complex conjugates and is real, but no longer of unitary modulus. This makes fshift's sample fall on the Fourier interpolation of the signal as computed by interpft, but is not revertible as Earl noticed. It is thus likely wrong, but this implies interpft's output is also wrong for even cases...

Changing the phase envelope Nyquist sample to 1 or -1 depending on the shift parameters solves Earl's problem (makes fshift revertible) but produces samples that do not fall on interpft's interpolant. The differences are of the order of 1/N where N is the number of samples, so they are best seen with a small number of samples. For larger vectors, the effect might be negligible. With odd N, fshift produces samples on interpft's interpolant.

I am still investigating the situation. If anyone wants to discuss the matter, please contact me at fbouffard (a) gmail.com.

Earl, you're right... I'm investigating. The error seems to be exactly 1/N where N is the number of samples. Funky things happening in the imaginary and real parts for different positions of the impulse. I don't have a lot of time right now to revisit fshift but if I find something I'll post an update here (and hopefully a fix).

This doesn't appear to be perfectly correct. For example, if you create an even-length file with an impulse near the middle, shift it right twice by a half sample, then shift it back 1 sample using circshift, you don't get the original signal:

x = zeros(1000, 1);
x(501) = 1;
plot(x)
hold on
plot(circshift(fshift(fshift(x, 0.5), 0.5), -1))

If you zoom in to the result, the error is on the order of 10^-3. It passes this test for odd-length signals, but I'm not sure if the results are correct in that case.

david cohen

Ramon Rosa

Irenaius

Muchas gracias. Works perfect.

Ahmed Fasih

Merveilleux!

Thanks to Ahmed Fasih for pointing out the bug below. Version 1.3 fixes the bug as far as I can tell.

Ahmed Fasih

The behavior of this function with even-length complex inputs is incorrect. I don't know how to fix it, but here's how to produce the problem:

```
N = 6;
x = randn(N, 1) + 1j * randn(N, 1);

delayValue = 1/3;

% Obtain the correct result for comparison using interpft. This works because delayValue is a nice rational number.
gold = interpft(x, length(x) / delayValue);
gold = circshift(gold(1/delayValue : 1/delayValue : end), 1);

% fshift does the wrong thing if the complex vector is passed in: the error is ~1
errFshift = norm(fshift(x, delayValue) - gold)

% But it does the right thing when the real and imaginary components of the complex vector are passed in individually and the outputs recombined: this value is ~1e-16
errFshiftReIm = norm([fshift(real(x), delayValue) + 1j * fshift(imag(x), delayValue)] - gold)
```

Advice?

Just fixed a bug submitted by Kamil Wojcicki. Thanks Kamil.

Never mind, now that I have more carefully read your file, I see that covered the 2*pi factor in the frequency digitization and you are not forcing the signal to be real.

Helpful.
Two comments:
(1) Is the frequency domain shift appearing as:

exp(-1i*s*pi*f)';

Suppose to include a factor of 2 to be consistent with Matlab's definition of the fft, so that:

exp(-1i*s*2*pi*f)';

(2) Concatenate the input signal with it's flipped version, to make it even, to avoid forcing it to be real, then extract the latter half of the signal.

Ahmed Fasih

I had to remove the following from the function: "if isreal(x); y = real(y); end;". With this gone, the output of the fft() of a complex exponential is exactly equal to an fshift()ed sinc().

Matlab User

Thanks, this was helpful

Updates

1.31.0.0

Simpler code that accomplishes the same for even-length inputs.

1.3.0.0

Fixed a bug with even-length complex inputs. Thanks to Ahmed Fasih for pointing out the problem.

1.2.0.0

Updated the author information in the file.

1.1.0.0

Bugfix: changed conjugate transpose for simple transpose, which fixes the shift direction reversal (e.g. with respect to Matlab's CIRCSHIFT). Thanks to Kamil Wojcicki for pointing out the problem.

1.0.0.0

Bug fix: results for vectors with an even length were slightly off for non-integer shifts. Sorry for the inaccuracies that this could have caused.

MATLAB Release Compatibility
Created with R13
Compatible with any release
Platform Compatibility
Windows macOS Linux