> Randy Yates <yates@ieee.org> writes:
>
>>[...]
>>The analogy I provided implies there is a useful mapping. Further, the
>>existence of such a mapping does not change the point of my argument.
>
>
> Here's an even simpler one: If I use a screwdriver as a hammer, does
> that make it a hammer?
A. Lincoln to his cabinet: "If You call a tail a leg, how many legs does
a sheep have?"
--
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������
Reply by Randy Yates●April 4, 20062006-04-04
Randy Yates <yates@ieee.org> writes:
> [...]
> The analogy I provided implies there is a useful mapping. Further, the
> existence of such a mapping does not change the point of my argument.
Here's an even simpler one: If I use a screwdriver as a hammer, does
that make it a hammer?
--
% Randy Yates % "Maybe one day I'll feel her cold embrace,
%% Fuquay-Varina, NC % and kiss her interface,
%%% 919-577-9882 % til then, I'll leave her alone."
%%%% <yates@ieee.org> % 'Yours Truly, 2095', *Time*, ELO
http://home.earthlink.net/~yatescr
Reply by Randy Yates●April 4, 20062006-04-04
"Ron N." <rhnlogic@yahoo.com> writes:
> Randy Yates wrote:
>> "Ron N." <rhnlogic@yahoo.com> writes:
>>
>> > Randy Yates wrote:
>> >> Do you agree that the output of the DFT is N discrete points
>> >> in frequency? If so, then there are only two possible conclusions:
>> >>
>> >> 1. The DFT output represents a periodic, continuous-time input
>> >> signal. (Assuming the values outside 0 to N-1 are zero.)
>> >>
>> >> 2. The DFT output represents a periodic, discrete-time input
>> >> signal. (Assuming the values outside 0 to N-1 are periodic.)
>> >>
>> >> In either case, the input is periodic.
>> >
>> > What do you mean by the above? Is the DFT useful in the
>> > signal processing of a set of samples from a signal which
>> > is neither periodic in N nor zero outside a window of 0 to N?
>> > If so, why?
>>
>> Sampled data is useful in the processing of continuous-time signals
>> (e.g., via an A/D converter and a DSP). Does that make sampled data
>> continuous-time?
>> [...]
> Is there a useful mapping between a segment of samples of from a
> finite length non-periodic signal and the DFT of those samples?
> Or does a DFT/FFT result only map to things which do not exist?
The analogy I provided implies there is a useful mapping. Further, the
existence of such a mapping does not change the point of my argument.
I never stated the DFT wasn't *useful* (as Robert pointed out about 3
posts ago.) I am, however, claiming what the DFT input *is* and *is
not* given the nature of the DFT output.
--
% Randy Yates % "Ticket to the moon, flight leaves here today
%% Fuquay-Varina, NC % from Satellite 2"
%%% 919-577-9882 % 'Ticket To The Moon'
%%%% <yates@ieee.org> % *Time*, Electric Light Orchestra
http://home.earthlink.net/~yatescr
Reply by Ron N.●April 3, 20062006-04-03
Randy Yates wrote:
> "Ron N." <rhnlogic@yahoo.com> writes:
>
> > Randy Yates wrote:
> >> Do you agree that the output of the DFT is N discrete points
> >> in frequency? If so, then there are only two possible conclusions:
> >>
> >> 1. The DFT output represents a periodic, continuous-time input
> >> signal. (Assuming the values outside 0 to N-1 are zero.)
> >>
> >> 2. The DFT output represents a periodic, discrete-time input
> >> signal. (Assuming the values outside 0 to N-1 are periodic.)
> >>
> >> In either case, the input is periodic.
> >
> > What do you mean by the above? Is the DFT useful in the
> > signal processing of a set of samples from a signal which
> > is neither periodic in N nor zero outside a window of 0 to N?
> > If so, why?
>
> Sampled data is useful in the processing of continuous-time signals
> (e.g., via an A/D converter and a DSP). Does that make sampled data
> continuous-time?
There are some formulations of quantum mechanics which seem
to say that there are no continuous-time signals in reality.
And if there are, they are certainly not measureable. However,
assuming some sort of physical phenomena of interest which can
best be modeled by a continuous-time signal, samples seem to
me to be most useful when there is a mapping of some sort from
the samples to the signal of interest.
Is there a useful mapping between a segment of samples of from a
finite length non-periodic signal and the DFT of those samples?
Or does a DFT/FFT result only map to things which do not exist?
IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M
Reply by robert bristow-johnson●April 3, 20062006-04-03
i didn't see this one either, Ron. (also missed one of Stan's ca. 3/28
until now.)
Ron N. wrote:
> Randy Yates wrote:
> > Do you agree that the output of the DFT is N discrete points
> > in frequency? If so, then there are only two possible conclusions:
> >
> > 1. The DFT output represents a periodic, continuous-time input
> > signal. (Assuming the values outside 0 to N-1 are zero.)
> >
> > 2. The DFT output represents a periodic, discrete-time input
> > signal. (Assuming the values outside 0 to N-1 are periodic.)
> >
> > In either case, the input is periodic.
>
> I think you are confusing multiple meanings of frequency.
he (Randy) is just saying that you're adding up a bunch or scaled
sinusoidal functions:
1. N-1
x(t) = SUM{ X[k] * exp(j*2*pi*k*t/N) } ("t" continuous)
k=0
2. N-1
x[n] = SUM{ X[k] * exp(j*2*pi*k*n/N) } ("n" discrete)
k=0
they *are* N discrete frequencies and both the continuous-time x(t) and
discrete-time x[n] are periodic with period N. i think Randy's meaning
was obvious.
> The DFT basis set appears to be orthogonal and complete
> without reference to any continuous or infinite extensions
> (although reference does make the math a bit more tractable).
> DFT results are often very close whatever a user might define
> as the frequency content of the signal, making the DFT transform
> a useful operator.
>
> In normal use, the DFT output represents a basis transform
> of a vector, related or not to any continuous-time signal,
> and of unknown behavior outside the DFT window [0..N-1].
there is no DFT window. perhaps there was some windowing applied to
the data before it was passed to the DFT.
perhaps, it was orignally unknown (because when the N samples were
yanked from some longer stream of data, the information of the outside
samples was lost), but the DFT is certainly making some assumption (if
i may anthropomorphize) about the nature of the input data outside of 0
and N-1.
> Any meaning of frequency outside the DFT window appears to
> be unconstrained,
i may be for *you* the user of this tool. but the tool is certainly
making some assumption of the data in both domains outside of the
indices 0 <= n,k < N. and "to totally ignore it is to invite trouble."
> although can optionally be extended for
> certain forms of interpretation.
NOT an option if you do shifting or convolution in either domain (or
their multiplicative counterparts in the reciprocal domain). you guys
seem to object to my exclusivity here, but blame the math (the periodic
nature of exp(j*2*pi*n*k/N)), not me. i'm just being the messenger.
> Even within the window,
> it's ambiguous whether any bin represents a frequency or an
> artifact of a non-bin frequency, as the DFT/FFT basis transform
> reduces visibility of non-bin frequencies in a trade-off with
> making bin frequency content more visible.
this is a consequence of windowing before the DFT ever saw the data.
as far as the DFT is concerned, all N of the frequency components are
dead on, mid-bin, and discrete.
> This ambiguity
> can often be resolved by adding additional windowed basis
> vectors offset in time to the original set, as in phase vocoder
> type analysis.
a twist on increasing window size.
> A window, either on the data or on the basis functions, appears
> to be inherent in any finite DFT operator.
no, that is not the case at all. there is no DFT window. *you* (or i
or Randy or Stan) may very well be applying a window to some long
stream of data by yanking out N samples from it, and that is an
operation applied to the data (that has consequences in the reciprocal
domain) before it is passed to the DFT.
once that windowing is done, you have lost all information about what
was outside those indices in x[n]. but when you pass those N samples
to the DFT, it *thinks* it knows what is outside those N indices of
x[n]. that assumption of the DFT may not be right, but you better
accept it lest you err regarding it.
> Whether the window is on the data or on the basis functions
> appears to be a degree of freedom in any working interpretation.
there is no windowing on the basis functions. the DFT and the
"Discrete Fourier Series" are precisely the same operation (some books
might toss the 1/N to the forward transform instead of the inverse in
the DFS)
> Circularity is a property of the basis functions, there is often
> no need to attribute it to the data (except for certain shift
> optimizations of arbitrary distance).
your original data may or may not have been "circular" (or periodic).
whether or not it was is information lost when N samples were drawn
from it (this is before the DFT sees it). when the DFT gets a hold of
those N samples, it is fitting periodic basis sequences (all with
period N) to it and what it gets as a result is periodic with period N
since the some of periodic sequences of the same period add to a
periodic sequence of that same period.
> Time-frequency reassignment type FFT analysis actually
> seems to consider circularity to be a flaw in the DFT basis
> functions,
yeah, but that's what O&S meant by "Sometimes it causes us difficulty
..." sometimes we need to workaround, interpret, or otherwise deal
with this property or "flaw". that is the lot of one who uses the DFT
lest they "invite trouble".
> In common usage, the input is far from periodic,
before passing it to the DFT, that is likely very true.
> and even if so, unlikely to be related in period exactly
> to the DFT window width.
yup. in the case of wavetable synthesis (or analysis of musical tones
for additive synthesis), there can be a pitch detector (more accurately
a fundamental frequency or period estimator) that can be used with a
resampler to set it up so that the period of the input is exactly N
samples before you pass them to the DFT.
> Mathematical consistancy in the analysis
> of certain operations, which may or may not involve some
> DFT-like computation, on linearly sequential frames may
> require periodicity to be completely optional throughout
> the entire analysis, included in the portion using any DFT's.
again, it's not optional if there is any shifting or convolution of
data in either domain (or the corresponding multiplication in the
reciprocal domain), the periodicity property is present. always.
shifting is always circular (because the DFT assumes you passed it N
samples of a periodic sequence). and the periodicity property of the
DFT is moot if there is no shifting of data. there is no case where
the periodicity property is contra-indicated. (like a shifting
operation where zeros or something like that get shifted in on one side
or the other.)
> And, finally, a DFT is just a bunch of FIR filters which just
> happen to be orthogonal and sufficient for reconstruction.
there's more to it than that they're orthogonal and that together they
can be used to reconstruct the current N samples applied. there are
other filter banks that are orthogonal and sufficient for
reconstruction. the DFT has a specific nature regarding its bunch of
FIR filters.
> Do FIR filters require the input to have some periodicity
> property?
no, but in this special class of FIR filters called the "DFT", consider
the reconstruction.
r b-j
Reply by Randy Yates●April 2, 20062006-04-02
"Ron N." <rhnlogic@yahoo.com> writes:
> Randy Yates wrote:
>> Do you agree that the output of the DFT is N discrete points
>> in frequency? If so, then there are only two possible conclusions:
>>
>> 1. The DFT output represents a periodic, continuous-time input
>> signal. (Assuming the values outside 0 to N-1 are zero.)
>>
>> 2. The DFT output represents a periodic, discrete-time input
>> signal. (Assuming the values outside 0 to N-1 are periodic.)
>>
>> In either case, the input is periodic.
>
> What do you mean by the above? Is the DFT useful in the
> signal processing of a set of samples from a signal which
> is neither periodic in N nor zero outside a window of 0 to N?
> If so, why?
Sampled data is useful in the processing of continuous-time signals
(e.g., via an A/D converter and a DSP). Does that make sampled data
continuous-time?
--
% Randy Yates % "The dreamer, the unwoken fool -
%% Fuquay-Varina, NC % in dreams, no pain will kiss the brow..."
%%% 919-577-9882 %
%%%% <yates@ieee.org> % 'Eldorado Overture', *Eldorado*, ELO
http://home.earthlink.net/~yatescr
Reply by robert bristow-johnson●April 2, 20062006-04-02
i thought this one was pedering out. (no one even touched the Dirichet
thingie subthread. i thought maybe Rick might.)
Ron N. wrote:
> Randy Yates wrote:
> > Do you agree that the output of the DFT is N discrete points
> > in frequency? If so, then there are only two possible conclusions:
> >
> > 1. The DFT output represents a periodic, continuous-time input
> > signal. (Assuming the values outside 0 to N-1 are zero.)
Randy, assuming that X[k] = 0 outside of 0 to N-1?
then, i guess the name for this thing would be a complex Fourier series
since there is no corresponding negative frequency components.
> > 2. The DFT output represents a periodic, discrete-time input
> > signal. (Assuming the values outside 0 to N-1 are periodic.)
when
N-1
X[k] = SUM{ x[n] * exp(-j*2*pi*n*k/N) }
n=0
i don't see why it's an assumption. it's pretty explicit. and if you
define
v[n] = x[n] * exp(j*2*pi*m*n/N) m = integer
the DFT of v[n] is V[k]=X[k-m] and thats correct only for X[k+N] =
X[k] (periodic).
> > In either case, the input is periodic.
>
> What do you mean by the above? Is the DFT useful in the
> signal processing of a set of samples from a signal which
> is neither periodic in N nor zero outside a window of 0 to N?
i didn't read the word "useful" in what Randy said.
> If so, why? If not, then why is it mentioned in almost all
> engineering textbooks?
Ron (or anyone else), what specifically is it that is mentioned in
almost all engineering textbooks? (to not be pedantic, i'll assume you
did not mean civil engineering textbooks on soil mechanics and the
like.)
> > What is so difficult for you to accept about this?
>
> What do you want me to accept? That the DFT is useless
> for engineering and signal processing applications.
can we burn the strawmen? no one is saying (by inference) that the DFT
is useless for application to aperiodic signals. as is well
illustrated by the fast convolution application, the FFT (which is the
DFT, but an efficient manner to compute it) can be coerced to perform
linear convolution, even on an input that is aperiodic and unbounded in
length. but what you're doing with the overlap-add or overlap-save
technique is adapting this circular tool, a tool that directly performs
a circular convolution and does not *directly* computes a linear
convolution, to do a linear convolution task. this is because
(defining L as the FIR length), if you zero-pad with L-1 zeros, the
circular convolution will agree with the linear convolution for N-2L+2
samples and linearity will allow you to fix L-1 samples with
overlap-adding. or if you don't zero-pad at all and draw N adjacent
samples from the input stream, circular convolution agrees with linear
convolution for N-L+1 samples and you just "save" those good output
samples and toss the bad ones.
human beings have been doing that kind of adaptation of tools for a
very long time. a dumb example that occurs to me today while i clean
up my wood stove (i used it for the last time this season about a week
ago) is my use of two concatinated drinking straws to _blow_ with as a
cheap and effective bellows to start up a fire.
the point is not and never has been that the DFT is useless for
processing of aperiodic signals, but that it has consequences, due to
this inherent periodic extension of the N samples passed to it, that
you dare not "totally ignore" lest you "invite trouble."
r b-j
Reply by Ron N.●April 2, 20062006-04-02
Randy Yates wrote:
> Do you agree that the output of the DFT is N discrete points
> in frequency? If so, then there are only two possible conclusions:
>
> 1. The DFT output represents a periodic, continuous-time input
> signal. (Assuming the values outside 0 to N-1 are zero.)
>
> 2. The DFT output represents a periodic, discrete-time input
> signal. (Assuming the values outside 0 to N-1 are periodic.)
>
> In either case, the input is periodic.
What do you mean by the above? Is the DFT useful in the
signal processing of a set of samples from a signal which
is neither periodic in N nor zero outside a window of 0 to N?
If so, why? If not, then why is it mentioned in almost all
engineering textbooks?
> What is so difficult for you to accept about this?
What do you want me to accept? That the DFT is useless
for engineering and signal processing applications.
IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M
Reply by Oli Filth●March 31, 20062006-03-31
Bob Cain said the following on 31/03/2006 10:21:
> Oli Filth wrote:
>> Bob Cain said the following on 30/03/2006 08:39:
>>> It's odd that, as long as the aperture is large enough to enclose the
>>> entire FIR, the "period" of the "periodic" FIR depends on the width of
>>> the aperture. No, it's not odd, it's nonsense.
>> Why is it nonsense?
>
> Why would the period of this presumingly repetitive FIR be determined by
> the choice of aperture? It's a one-off and any idea of repetition is
> silly in this context.
Why is it any sillier than taking the DFT of a discrete-time signal
which is non-zero only inside the "aperture" of the DFT, and saying that
there's implied periodicity there?
>>> Neither the definition
>>> nor the calculation have anything to say at all about what exists
>>> outside of the aperture.
>> Well, that goes with the territory if you window data.
>
> Where, by specifying that the aperture encloses the FIR, have I applied
> any window? None is necessary.
Ah, I now see what you were getting at. Well, taking the view that the
DFT is a uniformly-sampled version of the equivalent DTFT, then by
taking these samples, you're throwing information away. Imagine you had
two functions:
h[n], n = 0 outside 0 <= n < N
g[aN + n] = h[n], for all a
i.e. h[n] is your FIR, and g[n] is a periodic version of it.
Taking the DTFT of these two sequences gives G(w) and H(w), two distinct
functions, which can be processed by the IDTFT to get the original
sequences again.
However, the DFT is effectively sampling the DTFT at intervals of
2*pi*k/N, giving G[k] and H[k]. It is clear that in this case, G[k] =
H[k]. Therefore, it should also be clear that it's impossible to
reconstruct both g[n] and h[n] from G[k] and H[k].
So obviously, we have to adopt some kind of convention as to what the
IDFT of a sequence is (is it g[n], h[n], or something else?). Given:
IDFT{H[k]} = Sum{ H[k] . exp(j*2*pi*k*n/N) }
k
I guess you could define that this is invalid for n not in 0 <= n < N,
which would give IDFT{G[k]} = IDFT{H[k]} = h[n].
However, it's mathematically more satisfying (IMHO) to allow it to hold
for all n, which means that IDFT{G[k]} = IDFT{H[k]} = g[n].
It's also more satisying in that it's intuitive (IMHO) to define:
G(w) = Sum { G[k] . delta(w - 2*pi*k/N) }
k
which gives IDTFT{G(w)} = IDFT{G[k]}.
It's also more satisfying in that it makes the transform pair symmetric,
and allows the duality rules to apply.
So, in summary, I think we have to live with the fact that the IDFT of
the DFT of your non-periodic FIR results in a periodic FIR (which should
now be called an IIR, technically ;) ).
--
Oli
Reply by Bob Cain●March 31, 20062006-03-31
robert bristow-johnson wrote:
> Bob Cain wrote:
>> Back to the DFT for a moment, how does the imposition of periodicity or
>> assumptions as to it being inherent to the calculation apply to the FIR?
>
> when you use the FFT to do "fast convolution" (which is a long FIR
> filter), you have to worry about the periodicity because the
> convolution done by using the FFT/DFT is circular convolution and you
> have to manipulate the results (this is what the "overlap-add" or
> "overlap-save" is all about) to make the damn thing do linear
> convolution.
I liken this to the manipulation one must do to make multiplication
work. The operation produces a result that is the sum of the lengths of
the operands and any other way of doing it is just wrong. This is an
exact analog to convolution. Long integer multiplication is programmed
just like "fast convolution" is. Doing a convolution circularly can only
be justified when dealing, in fact, with periodic or quasi-periodic
signals such as the ODFM that Oli pointed out.
>> It's odd that, as long as the aperture is large enough to enclose the
>> entire FIR, the "period" of the "periodic" FIR depends on the width of
>> the aperture.
>
> the width of the DFT is quite a bit longer (at least twice as long) as
> the FIR, but assuming you're FIR filtering an arbitrarily long stream
> of input, you have to bust that input up into segments and filter each
> segment, and reassemble the results.
No, I'm just DFTing the FIR that describes the system. Oh, I know that
in theory you can't have a compact signal that is also band limited but
that seems to be a subtlety that can be well ignored in practice without
fearing any errors in the result.
>
>> No, it's not odd, it's nonsense. Neither the definition
>> nor the calculation have anything to say at all about what exists
>> outside of the aperture.
>
> the DFT *assumes* that outside the aperture, the input sequence is
> continued in a periodic way because it is fitting periodic basis
> functions to that input sequence.
This is our essential and apparently irreconcilable difference of opinion.
> in addition whenever it does an
> operation (in the "frequency domain") that shifts the input, like:
>
> X[k]*exp(-j*2*pi*m*k/N) <---> x[n-m]
>
> if m = 5, somehow the DFT has to come up with a definition for x[-5],
> x[-4], ... x[-1] and it does! x[-5] = x[N-5] and so on. once the
> windowing is done, the knowledge of whatever values existed outside of
> the window aperture is gone. but sometimes we replace it with
> something. usually for the DTFT, we replace those samples with 0, but
> the DFT periodically extends the retained data into the region outside
> the aperture. we may not like it, but we dare not forget it lest
> mistakes happen.
No! The DFT does no such thing. The shifting calculation does all that.
>> The question was asked a short while back and no one proposed a use for
>> "circular" convolution. It's a bug. Just don't do it.
>
> it's not a bug of the DFT but it is a property of the DFT that we
> sometimes have to put up with. as O&S say: "The inherent periodicity is
> always present. Sometimes it causes us difficulty and sometimes we can
> exploit it, but to totally ignore it is to invite trouble."
It's never caused me any at all.
> it can be useful for doing frequency-domain filtering of periodic or
> quasi-periodic tones (musical tones) as would be done if you were
> emulating Additive Synthesis (restricted to harmonic components) using
> a wavetable synthesizer (TRUE Wavetable Synthesis, [...] then the circular
> convolution is just what the doctor ordered.
Bingo! If you have a periodic or quasi-periodic signal to work with
then your view is useful. In this case the doctor is right.
> not the simple PCM
> sample playback done by these sampling keyboards and the myriad
> "wavetable" chips you find on soundcards).
Right. If it's one-off (instrument) event generation, subsequently
processed by an FIR (and with digital samples even the useful IIRs are
finite in practice), then considerations of periodicity do no more than
confuse the job.
Bob
--
"Things should be described as simply as possible, but no simpler."
A. Einstein