Prev: decimation in time - butterfly
Next: Equalization without a training sequence
From: dbd on 16 May 2010 01:35
On May 15, 8:13 pm, Jerry Avins <j...(a)ieee.org> wrote:
> On 5/15/2010 10:02 PM, Greg Heath wrote:
>> ...
>
> > I assumed that comp.dsp is read by users of
> > MATLAB that could use the info.
>
> > You haven't convinced me otherwise.
>
> Thanks for the post. It's on topic if Matlab is.
>
> Jerry

Actually Jerry, Matlab syntax is not on topic here. There have, of
course, always been many posts that some have welcomed here that have
been off topic. That's how comp.dsp is.

Greg chose the title:
"Filtering with MATLAB's ifftshift"
If he had chosen to address that, I would have considered the post on
topic. He left out the filtering part. If he had claimed that the use
of a Matlab "shift" syntax was necessary to the performance of fft-
filter-ifft operations in Matlab, it might have been on topic but it
isn't and he didn't.

I have responded to the thread in comp.soft-sys.matlab that Greg
claims motivation from. The title of that thread is "FFT-filter-IFFT
problem" Since my response was in the form of Matlab code (and the
question was asked there), I decided that comp.soft-sys.matlab was the
proper place to respond. If you are interested see:
http://groups.google.com/group/comp.soft-sys.matlab/browse_thread/thread/3c6e6fdc248a4163/41d54ba6e5a8b24a?hl=en#41d54ba6e5a8b24a
You will need Matlab or Octave to run the script. (I have not tested
it with Octave).

Dale B. Dalrymple
From: Greg Heath on 17 May 2010 11:19
On May 16, 1:35 am, dbd <d...(a)ieee.org> wrote:
> On May 15, 8:13 pm, Jerry Avins <j...(a)ieee.org> wrote:
> > On 5/15/2010 10:02 PM, Greg Heath wrote:
> >> ...
> > > I assumed that comp.dsp is read by users of
> > > MATLAB that could use the info.
>
> > > You haven't convinced me otherwise.
>
> > Thanks for the post. It's on topic if Matlab is.
>
> > Jerry
>
> Actually Jerry, Matlab syntax is not on topic here. There have, of
> course, always been many posts that some have welcomed here that have
> been off topic. That's how comp.dsp is.
>
> Greg chose the title:
> "Filtering with MATLAB's ifftshift"
> If he had chosen to address that, I would have considered the post on
> topic. He left out the filtering part. If he had claimed that the use
> of a Matlab "shift" syntax was necessary to the performance of fft-
> filter-ifft operations in Matlab, it might have been on topic but it
> isn't and he didn't.

Dale is right and Dale is wrong :

1. Dale is right

I left out explaining what to do if the signal and
filter are different lengths.

Assume the original scenario where xb and Hb are
specified on symmetric bipolar time and frequency
intervals.

If length(xb) = N ~= length(Hb) = M

then Xb.*Hb is not defined. However

length(conv(x,h)) = M+N-1

where

h = ifft(fftshift(Hb));

Therefore, both x and h have to be zero padded
to a common length of at least M+N-1 in order
to obtain compatible spectral representations.

2. Dale is wrong

Given the assumption that both xb and Hb are
specified on symmetric bipolar time and frequency
intervals, one or more applications of the shift
functions appears to be necessary to achieve the
above mentioned compatibility.

> I have responded to the thread in comp.soft-sys.matlab that Greg
> claims motivation from. The title of that thread is "FFT-filter-IFFT
> problem" Since my response was in the form of Matlab code (and the
> question was asked there), I decided that comp.soft-sys.matlab was the
> proper place to respond. If you are interested see:http://groups.google.com/group/comp.soft-sys.matlab/browse_thread/thr...
> You will need Matlab or Octave to run the script. (I have not tested
> it with Octave).

That reply is not directly applicable to the
OP's scenario where both xb and Hb are
specified on symmetric bipolar time(sec) and
frequency(Hz) intervals. In fact, starting time
and sampling rate were unspecified in Dale's
example so time and frequency intervals cannot
even be calculated.

To begin with, the filter is specified by discrete
unipolar time h(n), not bipolar freqency domain
Hb(f). Next, the signal is specified by unipolar
discrete time x(n), not bipolar time domain xb(t).
Therefore, in this example, no shifts are necessary.

The most important part of the reply was that
the lengths of h and x were different so that
both had to be zero-padded.

Bottom line:

1. I was concerned with the OP's confusion in a
filter application over how to deal with MATLAB's
fft/ifft when confronted with symmetric bipolar time
and frequency intervals. I overlooked the important
filter-specific step of zero padding to obtain spectral
representations that had the same length of the
time-domain convolution.

2. Dale was concerned about the emphasis on the
need for shifting in a thread that he thought was going
to emphasize more important considerations in the
application of filters. He then gave an example without
shifting that was not directly applicable to the
original scenario but did reveal the need for
the essential step of zero-padding for frequency
domain filtering.

So, betwixt the two ...

Hope this helps.

Greg

From: dbd on 17 May 2010 15:07
On May 17, 8:19 am, Greg Heath <he...(a)alumni.brown.edu> wrote:
....
>
> Dale is right and Dale is wrong :
>
> 1. Dale is right
>
> I left out explaining what to do if the signal and
> filter are different lengths.
> ...
>...
>
> 2. Dale is wrong
>
> Given the assumption that both xb and Hb are
> specified on symmetric bipolar time and frequency
> intervals, one or more applications of the shift
> functions appears to be necessary to achieve the
> above mentioned compatibility.

The assumptions about xb or Hb generation are not a part of how the
fft-filter-ifft process works. Focusing on them is misleading and
harmful.
>
> > I have responded to the thread in comp.soft-sys.matlab ...
>
> That reply is not directly applicable to the
> OP's scenario where both xb and Hb are
> specified on symmetric bipolar time(sec) and
> frequency(Hz) intervals. In fact, starting time
> and sampling rate were unspecified in Dale's
> example so time and frequency intervals cannot
> even be calculated.

In the first response to the c.ss.m posting, I referenced the
description of fft convolution in Stephen Smith's book. It does not
use "bipolar time" labels.
In fact, the fft and filter operations are not functions dependent on
the frequency and time intervals. Representing the fft-filter-ifft
process as dependent in those intervals or their offsets is incorrect
and harmful to understanding. The fft-filter-ifft process does not
alter those intervals, so what ever they were is what they stay.
>
> To begin with, the filter is specified by discrete
> unipolar time h(n), not bipolar freqency domain
> Hb(f).

Actually, my filter was a truncated sinc, calculated over both
negative and positive indices but over a fft-even interval. The OP's
use of a frequency domain Hb(f) that did not represent the
appropriately sized fft of an M point sequence was an error that
needed to be corrected in the use of the fft-filter-ifft process.

> Next, the signal is specified by unipolar
> discrete time x(n), not bipolar time domain xb(t).
> Therefore, in this example, no shifts are necessary.

The process is transparent to offsets in time labeling. The process is
often taught and then extended to the filtering of very long data
sequences via such techniques as overlap-add where the time domain
indices are constantly changing. This is indeed the approach
illustrated by the chapter of Stephen Smith's book that I referenced.
>
> The most important part of the reply was that
> the lengths of h and x were different so that
> both had to be zero-padded.

If Greg thinks that the zero extension was required only because
lengths of h and x are different, I will have to admit that the
failure to address the c.s-s.m OP's filtering issues was the one
helpful thing Greg did here.

>
> Bottom line:
>
> 1. I was concerned with the OP's confusion in a
> filter application over how to deal with MATLAB's
> fft/ifft when confronted with symmetric bipolar time
> and frequency intervals. I overlooked the important
> filter-specific step of zero padding to obtain spectral
> representations that had the same length of the
> time-domain convolution.

I think the OP's confusion came from trying to understand the fft-
filter-iff process by concentrating on the Matlab syntax. That is not
where the problem lay. The OP couldn't see the forest for the trees.
Greg is a tree expert and jumped in with more tree information because
he doesn't recognize or understand the signal processing issues. In
other words, I think Greg has played Paul Revere when there are no
British coming.
>
> 2. Dale was concerned about the emphasis on the
> need for shifting in a thread that he thought was going
> to emphasize more important considerations in the
> application of filters. He then gave an example without
> shifting that was not directly applicable to the
> original scenario but did reveal the need for
> the essential step of zero-padding for frequency
> domain filtering.
>
> So, betwixt the two ...
>
> Hope this helps.
>
> Greg

In situations like this, we seldom determine whether the c.s-s.m OP
was using signal processing in a Matlab class or using Matlab in a
signal processing class or something else entirely. I tried to point
the OP toward a source of understanding of how the fft-filter-ifft
process works. That might not be what the OP thinks the OP wants.

I think a nice alternate title for this response would be "Shift
Statements Considered Harmful". My apologies to Edsger Dijkstra [1].

Dale B. Dalrymple

[1]
Go To Statement Considered Harmful
Commmunications of the ACM VoL11 (2), 1968 pp. 147-148
Edsger W. Dijkstra

From: Greg Heath on 20 May 2010 05:51
On May 17, 3:07 pm, dbd <d...(a)ieee.org> wrote:
> On May 17, 8:19 am, Greg Heath <he...(a)alumni.brown.edu> wrote:
> ...
> > Dale is right and Dale is wrong :
>
> > 1. Dale is right
>
> > I left out explaining what to do if the signal and
> > filter are different lengths.

CORRECTION: I left out explaining the necessity of
zero-padding to obtain tranforms that have the same
length as the convolution of signal and filter.

> > 2. Dale is wrong
>
> > Given the assumption that both xb and Hb are
> > specified on symmetric bipolar time and frequency
> > intervals, one or more applications of the shift
> > functions appears to be necessary to achieve the
> > above mentioned compatibility.
>
> The assumptions about xb or Hb generation are not a part of how the
> fft-filter-ifft process works. Focusing on them is misleading and
> harmful.

The assumptions about xb and Hb generation were specified
by the OP of the fft-filter-ifft thread. Given those, I
addressed how to proceed. Granted, I flubbed on the
zero-padding necessary for obtaining a length suitable for
representing the fft of the convolution of signal and
filter.

Focussing on how to deal with the specified bipolar time
and frequency intervals was essential for helping the
OP and many other inexperienced MATLAB fft/ifft users
get anywhere near the solution to the specified problem.

> > > I have responded to the thread in comp.soft-sys.matlab ...
>
> > That reply is not directly applicable to the
> > OP's scenario where both xb and Hb are
> > specified on symmetric bipolar time(sec) and
> > frequency(Hz) intervals. In fact, starting time
> > and sampling rate were unspecified in Dale's
> > example so time and frequency intervals cannot
> > even be calculated.
>
> In the first response to the c.ss.m posting, I referenced the
> description of fft convolution in Stephen Smith's book. It does not
> use "bipolar time" labels.

Irrelevant to the OP's problem.

> In fact, the fft and filter operations are not functions dependent on
> the frequency and time intervals. Representing the fft-filter-ifft
> process as dependent in those intervals or their offsets is incorrect
> and harmful to understanding. The fft-filter-ifft process does not
> alter those intervals, so what ever they were is what they stay.

Somehow you have inferred a multitude of concepts
that were never inferred.

> > To begin with, the filter is specified by discrete
> > unipolar time h(n), not bipolar freqency domain
> > Hb(f).
>
> Actually, my filter was a truncated sinc, calculated over both
> negative and positive indices but over a fft-even interval.

Your filter is specified by sinc(0.2*(-M/2:-1+M/2))without
explicit reference to time or frequency.

You and I know that it is equivalent to the time function

sin(2*pi*f0*(t-t0))/(2*pi*(t-t0))

with

t = t0 + (-M/2:-1+M/2)/Fs

with f0/Fs fixed but t0, f0 and Fs unspecified.

Hardly enlightening to an inexperienced user of
MATLAb's fft/ifft who is wrestling with a filter
that is defined on a bipolar frequency interval.

> The OP's
> use of a frequency domain Hb(f) that did not represent the
> appropriately sized fft of an M point sequence was an error that
> needed to be corrected in the use of the fft-filter-ifft process.

Agree.

> > Next, the signal is specified by unipolar
> > discrete time x(n), not bipolar time domain xb(t).
> > Therefore, in this example, no shifts are necessary.
>
> The process is transparent to offsets in time labeling. The process is
> often taught and then extended to the filtering of very long data
> sequences via such techniques as overlap-add where the time domain
> indices are constantly changing. This is indeed the approach
> illustrated by the chapter of Stephen Smith's book that I referenced.

Beyond the scope of the OP's problem of a specified
deterministic, nonstationary, signal.

> > The most important part of the reply was that
> > the lengths of h and x were different so that
> > both had to be zero-padded.
>
> If Greg thinks that the zero extension was required only because
> lengths of h and x are different,

No he doesn't. See above.

> I will have to admit that the
> failure to address the c.s-s.m OP's filtering issues was the one
> helpful thing Greg did here.

As Michael Jackson used to say: Tee Hee.

> > Bottom line:
>
> > 1. I was concerned with the OP's confusion in a
> > filter application over how to deal with MATLAB's
> > fft/ifft when confronted with symmetric bipolar time
> > and frequency intervals. I overlooked the important
> > filter-specific step of zero padding to obtain spectral
> > representations that had the same length of the
> > time-domain convolution.
>
> I think the OP's confusion came from trying to understand the fft-
> filter-iff process by concentrating on the Matlab syntax.

Some of the OP's problem appeared to be language independent.
Whether the problem was exascerbated by using MATLAB
instead of another language is not clear.

I believe that most inexperienced users of fft/ifft
would not be able to produce the correct time labelled
output for this type of problem (i.e., double bipolar
specifications) regardless of the programming language
used.

> That is not
> where the problem lay. The OP couldn't see the forest for the trees.
> Greg is a tree expert and jumped in with more tree information because
> he doesn't recognize or understand the signal processing issues. In
> other words, I think Greg has played Paul Revere when there are no
> British coming.

I think Dale doesn't realize that the British have come and gone.

> > 2. Dale was concerned about the emphasis on the
> > need for shifting in a thread that he thought was going
> > to emphasize more important considerations in the
> > application of filters. He then gave an example without
> > shifting that was not directly applicable to the
> > original scenario but did reveal the need for
> > the essential step of zero-padding for frequency
> > domain filtering.
>
> > So, betwixt the two ...
>
> > Hope this helps.
>
> > Greg
>
> In situations like this, we seldom determine whether the c.s-s.m OP
> was using signal processing in a Matlab class or using Matlab in a
> signal processing class or something else entirely. I tried to point
> the OP toward a source of understanding of how the fft-filter-ifft
> process works. That might not be what the OP thinks the OP wants.
>
> I think a nice alternate title for this response would be "Shift
> Statements Considered Harmful".

Shifts would be very helpful if MATLAB had better
documentation on the fft and ifft functions as
well as the shifts. Given the years of difficulty
by inexperienced users (as witnessed by the volumes
of newsgroup threads), it is puzzling why the
fft/ifft documentation hasn't been rewritten.

Hope this helps.

Greg
From: dbd on 20 May 2010 13:47
On May 20, 2:51 am, Greg Heath <he...(a)alumni.brown.edu> wrote:
> On May 17, 3:07 pm, dbd <d...(a)ieee.org> wrote:
> ...
>
> > The assumptions about xb or Hb generation are not a part of how the
> > fft-filter-ifft process works. Focusing on them is misleading and
> > harmful.
>
> The assumptions about xb and Hb generation were specified
> by the OP of the fft-filter-ifft thread. Given those, I
> addressed how to proceed. Granted, I flubbed on the
> zero-padding necessary for obtaining a length suitable for
> representing the fft of the convolution of signal and
> filter.

The assumptions made by the OP were incorrect and needed to be
replaced, not parroted.
>
> Focussing on how to deal with the specified bipolar time
> and frequency intervals was essential for helping the
> OP and many other inexperienced MATLAB fft/ifft users
> get anywhere near the solution to the specified problem.
>
Getting the OP to find a valid replacement for the specified values
was essential to helping the OP and many inexperienced MATLAB fft/ifft
users get anywhere near a correct solution to the specified problem.
Greg insists on the use of fftshift/ifftshift to reinforce the errors
of the OP.
> ...

>
> > The process is transparent to offsets in time labeling. The process is
> > often taught and then extended to the filtering of very long data
> > sequences via such techniques as overlap-add where the time domain
> > indices are constantly changing. This is indeed the approach
> > illustrated by the chapter of Stephen Smith's book that I referenced.
>
> Beyond the scope of the OP's problem of a specified
> deterministic, nonstationary, signal.

The OP's problem statement was broken, a common occurrence. It was
necessary to get the OP to understand why and consider a correct
alternative. Re-enforcing errors with "shift" babble is harmful to a
correct(ing) response to the OP's question.
> ...

>
> I believe that most inexperienced users of fft/ifft
> would not be able to produce the correct time labelled
> output for this type of problem (i.e., double bipolar
> specifications) regardless of the programming language
> used.
>
I believe that most inexperienced users of fft/ifft
should not be forced to produce the time labeled
output for this type of problem in Greg's
knee-jerk form (i.e., double bipolar
specifications) regardless of the programming language
used.

> > That is not
> > where the problem lay. The OP couldn't see the forest for the trees.
> > Greg is a tree expert and jumped in with more tree information because
> > he doesn't recognize or understand the signal processing issues. In
> > other words, I think Greg has played Paul Revere when there are no
> > British coming.
>
> I think Dale doesn't realize that the British have come and gone.
>
That the British have come and gone is my point, why would it be
helpful for someone to insist on playing Paul Revere now? (I realize
that many readers won't find this explanation necessary, but Greg may
read this and get a better understanding of my figure of speech.)
>
> ...
>
> Shifts would be very helpful if MATLAB had better
> documentation on the fft and ifft functions as
> well as the shifts. ...
>
Documentation can almost always be improved. Shifts, if and when
needed, would be more helpfully presented by someone who understood
the subject matter of the question well enough to determine which of
the OP's codes should be removed and which improved.
> ...

I will admit that I have used fftshift/ifftshift. It's kind of like
picking your nose: Sometimes it is necessary and appropriate to clear
the airway, but it is not necessary or helpful to keep posting it up
afterward to show everyone.

Dale B. Dalrymple

First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: decimation in time - butterfly
Next: Equalization without a training sequence