Time shift and FFT
Frank
I created 2 signals, one sinusoid and its shifted version. I performed FFT on both and tried to multiply the FFT of the original signal elementwise by a vector which contains the phase shift. However, I found that it is not equal to the FFT of the shifted version. Can anyone help?
Attached please find my code:
clear all;
%sample frequency = 1
w = 2*pi*0.17;%angular frequency
N = 256;%No. of data
n = 0:N-1;%time index
phi = 1;%phase
t = 0.1;%delay
s = cos(w*n+phi);%orignal time domain signal
s1 = cos(w*(n-t)+phi);%shifted version of the sinusoid
S = fft(s);%FFT of the sinusoid
S1 = fft(s1);%FFT of the shifted sinusoid
e = exp(-1i*2*pi/N*n*t);% vector contains phase shift
norm(S.*e-S1)%should be zero
Thanks.
Wayne King
Hi Frank, I'm not sure why you're comparing norm(S.*e-S1).
n=0:95;
x = cos(pi/4*n);
delay=2;
y = cos(pi/4*(n-delay));
k=0:95;
% the DFT of y is exp(-1j*2*pi*k*delay/96)
phaseshift = exp(1j*2*pi*k*delay/96);
ydft = fft(y);
xdft = fft(x);
ydft=ydft.*phaseshift;
norm(xdft-ydft)
% 3.0397e-014
max( max(real(xdft)-real(ydft)), max(imag(xdft)-imag(ydft)))
% also on the order of 10^(-14)
y1 = ifft(ydft,'symmetric');
subplot(211);
plot(x);
subplot(212);
plot(y1);
Wayne
Frank
However, if I try to set the delay to 0.12 instead of 2, norm(xdft-ydft) = 35.34, which is greater than zero by a lot. What can we do in this case?
Frank
"Wayne King" <wmki...@gmail.com> wrote in message <hpkqq5$q1t$1...@fred.mathworks.com>...
Wayne King
Hi Frank, that's because you are attempting to deal with fractional delays. If your sampling rate is 1 and you try to delay a signal by 0.2, you have a fractional delay, a delay that is not an integer number of samples. Read up on fractional delay filters to see the adjustments you have to make in that case.
Wayne
omegayen
As a follow up to the original question let me ask this. The goal here is to confirm that the time shift Fourier transform relationship holds true.
my question is, is does the fourier transform only hold true for real signals and not complex signals... http://en.wikipedia.org/wiki/Fourier_transform
let's say I do the following
n=0:95;
x = cos(pi/4*n)+i*cos(2*pi/4*n);
delay=2;
y = cos(pi/4*(n-delay))+i*cos(2*pi/4*(n-delay));
k=0:95;
% the DFT of y is exp(-1j*2*pi*k*delay/96)
phaseshift = exp(1j*2*pi*k*delay/96);
ydft = fft(y);
xdft = fft(x);
ydft=ydft.*phaseshift;
norm(xdft-ydft)
% 3.0397e-014
max( max(real(xdft)-real(ydft)), max(imag(xdft)-imag(ydft)))
% also on the order of 10^(-14)
y1 = ifft(ydft,'symmetric');
subplot(211);
plot(x);
subplot(212);
plot(y1);
this doesn't work.....
dbd
>
[quoted code removed]
>
> As a follow up to the original question let me ask this. The goal here is to confirm that the time shift Fourier transform relationship holds true.
>
>
> let's say I do the following
>
>
> this doesn't work.....
Which parts do you think don't work? And why?
Try it with 0:94 for n,k.
Why (and when) do you think it is correct to try to represent a
(continuous/infinite)Fourier transform with Matlab's fft() which
performs a discrete Fourier transform?
Dale B. Dalrymple
omegayen
I was just extending the original example.
My new example made the signal in the time domain complex and I was merely trying to prove or disprove to myself that the Fourier Transform is only defined for real signals and not complex signals.
Does this make sense?
Essentially I was asking the question, can you take the Fourier transform of a complex signal which is in the time domain?
dbd
> dbd <d...@ieee.org> wrote in message <f080661f-69fd-447b-9610-681edac15...@q39g2000prh.googlegroups.com>...
> I was just extending the original example.
>
> My new example made the signal in the time domain complex and I was merely trying to prove or disprove to myself that the Fourier Transform is only defined for real signals and not complex signals.
>
> Does this make sense?
>
> Essentially I was asking the question, can you take the Fourier transform of a complex signal which is in the time domain?
So what was your conclusion?
Did you try 0:94 for n and k? What was your conclusion?
Dale B. Dalrymple
omegayen
Yes I tried for 0:94 for n and k, when I made the signal x and y in this case, complex
specifically I ran
n=0:94;
x = cos(pi/4*n)+i*cos(2*pi/4*n);
delay=2;
y = cos(pi/4*(n-delay))+i*cos(2*pi/4*(n-delay));
k=0:94;
% the DFT of y is exp(-1j*2*pi*k*delay/95)
phaseshift = exp(1j*2*pi*k*delay/95);
ydft = fft(y);
xdft = fft(x);
ydft=ydft.*phaseshift;
norm(xdft-ydft)
% 3.0397e-014
max( max(real(xdft)-real(ydft)), max(imag(xdft)-imag(ydft)))
% also on the order of 10^(-14)
y1 = ifft(ydft,'symmetric');
subplot(211);
plot(x);
subplot(212);
plot(y1);
this shows that you can't take the Fourier Transform, do the time shift, and then take the inverse Fourier Transform to get the original signal when the original signal is complex (in the time domain)
Wayne King
Hi, I don't think that's correct. There's nothing about the time-shift property that demands that the data is real-valued. The mistake you're making is in using the 'symmetric' flag in the inverse discrete Fourier transform. You are forcing the signal to be real-valued. You only use that flag when the Fourier transform is conjugate symmetric and you know that you should obtain a real-valued signal in the time domain, but you might get nonzero imaginary parts due to rounding errors.
n = 0:95; k = 0:95; delay =2;
y = cos(pi/4*(n-delay))+i*cos(2*pi/4*(n-delay));
x = cos(pi/4*n)+i*cos(2*pi/4*n);
yDFT = fft(y);
xDFT = fft(x);
phaseshift = exp(1j*2*pi*k*delay/96);
y1 = yDFT.*phaseshift;
y1 = ifft(y1);
subplot(211);
plot(real(y1),'k'); hold on;
plot(real(x),'b');
subplot(212);
plot(imag(y1),'k'); hold on;
plot(imag(x),'b');
Hope that helps,
Wayne
omegayen
yeah I did not think that was a correct statement...
thanks for clarifying the code Wayne
dbd
On Apr 8, 3:42 am, "Frank " <allinone_2...@yahoo.com.hk> wrote:
> Dear all,
>
> I created 2 signals, one sinusoid and its shifted version. I performed FFT on both and tried to multiply the FFT of the original signal elementwise by a vector which contains the phase shift. However, I found that it is not equal to the FFT of the shifted version. Can anyone help?
>
>
> As a follow up to the original question let me ask this. The goal here is to confirm that the time shift Fourier transform relationship holds true.
>
> my question is, is does the fourier transform only hold true for real signals and not complex signals...http://en.wikipedia.org/wiki/Fourier_transform
>
> let's say I do the following
The question seems to be about the time shift property of the
(continuous/infinite)Fourier transform. But Matlab performs the
discrete Fourier transform(DFT) with the fft(). The DFT is a set of
discrete, finite convolutions with periodic basis functions.
Setting up omegayen's code for varying parameters:
---------------------------------------------------------------------------
N = 96;
n=0:(N-1);
x = cos(pi/4*n)+i*cos(2*pi/4*n);
delay=2.0;
y = cos(pi/4*(n-delay))+i*cos(2*pi/4*(n-delay));
k=0:(N-1);
% the DFT of y is exp(-j*2*pi*k*delay/N)
phaseshift = exp(j*2*pi*k*delay/N);
ydft = fft(y);
xdft = fft(x);
ydft=ydft.*phaseshift;
errornorm = norm(xdft-ydft);
% 3.0397e-014
max1 = max( max(real(xdft)-real(ydft)), max(imag(xdft)-imag(ydft)));
% also on the order of 10^(-14)
disp(['N = ' num2str(N) ', delay = ' num2str(delay) ...
', errornorm = ' num2str(errornorm)])
figure
plot(1:N,real(x),'r-',1:N,real(y),'g-',1:N,real(phaseshift),'b-')
-----------------------------------------------------------------------------------
For some examples:
N = 96, delay = 2, errornorm = 4.4142e-014
N = 96, delay = 2.5, errornorm = 135.7645
N = 95, delay = 2, errornorm = 16.8819
In the first case, the error is round-off error. The shift works. Yes
for complex data. The other two cases fail. Why? The N point DFT only
performs the time shift operation on a length N sequence iff the
sequence 'x' and the shift function 'phaseshift' are periodic in N
samples. Otherwise, the DFT size must be chosen larger and end effects
must be considered as is also the case in filtering by DFT convolution
(fft=>filter=>ifft).
Dale B. Dalrymple
omegayen
Thanks for the explanation Dale. Could you possibly take it a bit further and explain how to ensure the sequence x and shift function phaseshift are periodic in N samples. Also how does N relate to the sampling frequency?
dbd
Discrete time signal processing is a large topic area, and only one of
the applications of Matlab's fft().
You should consider a text on the subject to learn the (sometimes
extensive) guidelines. Some of my favorites are:
Alan V. Oppenheim, Ronald W. Schafer, John R. Buck : Discrete-Time
Signal Processing, Prentice Hall, ISBN 0-13-754920-2
Richard G. Lyons: Understanding Digital Signal Processing, Prentice
Hall, ISBN 0-13-108989-7
Steven W. Smith: Digital Signal Processing - A Practical Guide for
Engineers and Scientists, Newnes, ISBN 0-7506-7444-X
The first of these has the greatest depth.
The last of these is available on the web at:
http://www.dspguide.com/pdfbook.htm
And N is the size of the transform, a value independent of the
sampling frequency.
Dale B. Dalrymple