Forums

Relationship between z and Fourier transforms

Started by commsignal July 30, 2013
On Fri, 02 Aug 2013 18:39:50 -0700, robert bristow-johnson
<rbj@audioimagination.com> wrote:

>On 8/2/13 8:50 AM, Eric Jacobsen wrote: >> On Thu, 01 Aug 2013 17:05:11 -0700, robert bristow-johnson >> <rbj@audioimagination.com> wrote: >> >>> On 8/1/13 3:57 PM, Eric Jacobsen wrote: >>>> On Thu, 01 Aug 2013 14:43:37 -0700, robert bristow-johnson >>>> <rbj@audioimagination.com> wrote: >>>> >>>>> On 8/1/13 2:06 PM, Eric Jacobsen wrote: >>>>>> On Thu, 01 Aug 2013 13:42:19 -0700, robert bristow-johnson >>>>>> <rbj@audioimagination.com> wrote: >>>>>> >>>>>>> On 8/1/13 1:25 PM, Tim Wescott wrote: >>>>> ... >>>>>>>> The math just is, and if you're getting the right >>>>>>>> results you are, ipso facto, using it correctly. >>>>>>> >>>>>>> fully agree with that. and, unless there is no shifting nor convolution >>>>>>> (in time or frequency) going on (which means the only property or >>>>>>> theorem of the DFT one can make use of is Linearity) then the *only* >>>>>>> (and this "only" is me being inflexible) correct mathematics is to >>>>>>> either explicitly periodically extend the data: >>>>>>> >>>>>>> x[n+N] = x[n] or X[k+N] = X[k] >>>>>>> >>>>>>> or to implicitly periodically extend the data: >>>>>>> >>>>>>> x[n mod N] or X[k mod N] >>>>>>> >>>>>>> >>>>>>> either way you're periodically extending the data, the math says so, and >>>>>>> it seems to me silly to deny it. there is no way to get away from it. >>>>>>> "resistance is futile." >>>>>> >>>>>> Except for the numerous counter-examples that have been pointed out to >>>>>> you over the decades. >>>>> >>>>> you have numerous counter-examples which involve shifting the data or >>>>> convolving the data (or their counterparts in the other domain which >>>>> means multiplying by something that is not constant) where you can >>>>> ignore both >>>>> >>>>> x[n+N] = x[n] >>>>> >>>>> or >>>>> >>>>> x[n mod N] >>>>> >>>>> and the X[k] counterparts? >>>>> >>>>> would you mind repeating just one of those counter examples? and in >>>>> these numerous counter examples you are able to show mathematical >>>>> correctness while ignoring x[n+N] = x[n] and x[n mod N] (or the same >>>>> thing in X[k])? >>>> >>>> It's been said many times already. I've long grown tired of >>>> repeating them over again to you. >>> >>> many words were said. and the mathematical case was never made by you >>> (nor Dale nor anyone else). not even with that .pdf you sent (after my >>> .pdf because you didn't like ASCII math on USENET). i've grown tired of >>> the whole thing too, but the math doesn't care. >> >>> and it was about the same question. i would like to see *any* shift >>> operation done in the context of the DFT that isn't circular. and you >>> cannot provide such an example because the math won't let you. >> >> You just cannot recognize that this has all been done before by so >> many other people. I cannot help that you continually, over decades, >> refuse to see arguments other than your own. > >not seeing an argument isn't the same as rejecting it. and presenting >an argument is not the same as defending it. > >> It does no harm to >> anyone else that you do this other than the periodic pest you make of >> yourself over it, so its no big deal. >> >>>>> zero-padding is a questionable counter-example because if you claim that >>>>> the zero shifted in isn't the same zero that was shifted out the other >>>>> end, then i would dispute that. >>>> >>>> You dispute a lot of things. >>> >>> perhaps, but about the topic at hand, i only dispute only one thing. >>> well, maybe two. i dispute: >>> >>> 1. that, regarding the DFT mapping, when any operation is done in one >>> domain that causes shifting in the other domain, that this shifting is >>> anything other than circular. > >so are you stipulating to number 1? (evidently not to number 2.) > >>> >>> 2. that the DFT, itself, is responsible (inherently or in any other >>> manner) for the effects of windowing. even rectangular windowing. >> >> The DFT has no responsibilities. It is not an entity. > >you sure about that? the DFT is a "thing" and at least when i look up >"entity", it pretty much means "thing" and the thing need not be >conscious nor sentient nor animate. every online source (which was only >Wikipedia and google) i looked at seems to agree. > >the DFT is an algorithm, right? can we agree that algorithms perform >"tasks", Eric? can we agree that these tasks have specifications? then >if we agree on those 3 stipulations, do you say that the word >"responsibility" cannot be applied to a "thing" (whether you count it as >an "entity" or not) that performs some task to some set of specifications? > >i mean, what is the meaning of something like an API or even simply a >"plan" (involving multiple "entities") without a concept of spec'ing out >"responsibility". different tasks and algs do different things and >expect (there i go anthropomorphizing them algs again) other things >(like their input) to be a certain way in order to work. > >and another sense of "responsibility" vis-a-vis inanimate things is that >of *cause* (the first half of "cause and effect"). > >*something* is causing that scalloping in the spectrum and that >something is windowing. and that windowing happens to the data before >the data goes to the DFT. the DFT just tells you what you got in the >discrete-frequency domain. (and that's doing pretty good for a non-entity.) > >>> the >>> effects of windowing happens when you actually window the data. in the >>> simple case of rectangular windowing, it is when you yank N samples out >>> if a stream or a longer sequence of samples. the windowing happens >>> before the DFT ever sees the data. >> >> The DFT cannot "see" anything. > >well, for that matter than neither do we. we're just biochemical >mechanisms that just react (oh, that's too anthropomorphic) errr, >respond to stimulus. > >the DFT sees its input. the DFT sees x[0], x[1], x[2] ... x[N-1] which >came from samples x[m+0], x[m+1], x[m+2] ... x[m+N-1] from some stream >or longer sequence of data. the DFT does *not* see x[m-1] nor x[m-2] >nor x[m+N] nor x[m+N+1]. > > >> Such anthropomorphisms come from one's own interpretation and >> assignment and not from any actual properties of the transform. > >they're just words. they're words that start with one meaning, and from >usage get applied metaphorically to similar situations involving objects >of a different group than in the original use. > >are you saying that C++ (or pick your OOP) classes don't inherit because >they are not living things? don't have DNA? > >> Other people have equally valid interpretations other than your own. >> I do not know why you think everyone should have to see it only the >> way you do, and that they are wrong if they do not. > >if they (or you) say that, when using the DFT, if they apply an >operation in one domain (e.g. multiply by something non-constant) that >causes shifting in the other domain, and that their interpretation of >the DFT allows them to consider that this shifting is not circular, then >they (or you) are wrong. that's a mathematical fact and is no mere >interpretation. > >to mathematically depict this circular shifting, i have seen *two* >notations and no others (but if you see another, we can talk about it). > >either you must say x[n+N] = x[n] or you must use x[n mod_N] (or the >only property of the DFT that counts is linearity because any other >property depends explicitly on this periodic extension). now the first >means explicitly periodic extension and the latter means the same damn >thing. how can you say that this modulo index addressing is not one and >the same as periodic extension? even if you have another notation for >it, because of mathematical necessity, it must mean the same thing as >one of these two notations. it must also mean periodically extended. > > >Eric, i can try to restate the issues without anthropomorphizing (and, >in my opinion, the language would get more clunky *not* better), but i >really think you're tossing up a strawman to hide behind when you point >to such illustration as defective and then use that to avoid answering >the question that you cannot for substantive reasons.
No, for me the issue is that these arguments have all been made before, many times, and your position hasn't changed, and it's clear that it won't. So to me there is no point in reiterating any of it with you. Many here used to indulge you, and I did as well, until I just got way too tired of finding pretty much nothing behind your arguments when I actually pushed down into them. Total waste of time. Not in.
> >-- > >r b-j rbj@audioimagination.com > >"Imagination is more important than knowledge." > >
Eric Jacobsen Anchor Hill Communications http://www.anchorhill.com
On 8/2/13 8:34 PM, Eric Jacobsen wrote:
> > No, for me the issue is that these arguments have all been made > before, many times, and your position hasn't changed, and it's clear > that it won't.
it's the mathematics that doesn't change position. but that might doin' that silly anthropomorphizing again. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
robert bristow-johnson <rbj@audioimagination.com> writes:

> On 8/2/13 8:34 PM, Eric Jacobsen wrote: >> >> No, for me the issue is that these arguments have all been made >> before, many times, and your position hasn't changed, and it's clear >> that it won't. > > it's the mathematics that doesn't change position. but that might > doin' that silly anthropomorphizing again.
The numbers that result from a DFT are just numbers. That's all the mathematics says about them. It's a linear transformation from C^N to C^N. If you want to place an interpretation onto those numbers, that's your doing, not mathematics'. -- Randy Yates Digital Signal Labs http://www.digitalsignallabs.com
On 8/4/13 3:52 PM, Randy Yates wrote:
> robert bristow-johnson<rbj@audioimagination.com> writes: > >> On 8/2/13 8:34 PM, Eric Jacobsen wrote: >>> >>> No, for me the issue is that these arguments have all been made >>> before, many times, and your position hasn't changed, and it's clear >>> that it won't. >> >> it's the mathematics that doesn't change position. but that might >> doin' that silly anthropomorphizing again. > > The numbers that result from a DFT are just numbers.
they're not *just* numbers. they're numbers with a specific relationship to each other and to the DFT input.
> That's all the mathematics says about them.
the mathematics of the DFT say *more* than that they are "just numbers". the mathematics says something about the relationship that these numbers have with each other and with the input.
> It's a linear transformation from C^N to C^N.
there are *many* linear transformations. the DFT is a *specific* linear transformation that maps a discrete and periodic sequence from one domain to another discrete and periodic sequence of the same period in the reciprocal domain.
> If you want to place an interpretation onto those numbers, that's your > doing, not mathematics'.
appears that people want to blame me for it (i'm just the messenger), but it's the mathematics that imposes the periodicity in the DFT. although some claim to do it, you cannot simply "interpret" away the properties of that particular linear transformation from C^N to C^N that we call the DFT. one of those properties comes right out of the definition of the DFT and iDFT and that property imposes periodicity. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
robert bristow-johnson <rbj@audioimagination.com> wrote:
> On 8/4/13 3:52 PM, Randy Yates wrote: >> robert bristow-johnson<rbj@audioimagination.com> writes:
(snip)
>>> it's the mathematics that doesn't change position. but that might >>> doin' that silly anthropomorphizing again.
>> The numbers that result from a DFT are just numbers.
> they're not *just* numbers. they're numbers with a specific > relationship to each other and to the DFT input.
>> That's all the mathematics says about them.
> the mathematics of the DFT say *more* than that they are > "just numbers".
> the mathematics says something about the relationship that these > numbers have with each other and with the input.
>> It's a linear transformation from C^N to C^N.
> there are *many* linear transformations. the DFT is a *specific* linear > transformation that maps a discrete and periodic sequence from one > domain to another discrete and periodic sequence of the same period in > the reciprocal domain.
Also, there are many fine transformations that don't have periodic boundary conditions, such as the DCT. Often it seems to be used where people know that is needed, but if people specifically don't want periodic boundary conditions, instead of arguing that the DFT doesn't have them, use one that doesn't. Also, if I haven't mentioned it too many times already, there is the ICT which shows how far you can get away from the ideal and still be a reasonable transform.
>> If you want to place an interpretation onto those numbers, >> that's your doing, not mathematics'.
> appears that people want to blame me for it (i'm just the messenger), > but it's the mathematics that imposes the periodicity in the DFT. > although some claim to do it, you cannot simply "interpret" away the > properties of that particular linear transformation from C^N to C^N that > we call the DFT. one of those properties comes right out of the > definition of the DFT and iDFT and that property imposes periodicity.
I don't have anything against those that use the DFT for non-periodic signals. It can be done. But don't deny that the transform does have those bounary conditions. -- glen
On Monday, August 5, 2013 1:31:01 PM UTC-4, glen herrmannsfeldt wrote:
> robert bristow-johnson <> wrote: > > > On 8/4/13 3:52 PM, Randy Yates wrote: > > >> robert bristow-johnson<> writes: > > > > (snip) > > >>> it's the mathematics that doesn't change position. but that might > > >>> doin' that silly anthropomorphizing again. > > > > >> The numbers that result from a DFT are just numbers. > > > > > they're not *just* numbers. they're numbers with a specific > > > relationship to each other and to the DFT input. > > > > >> That's all the mathematics says about them. > > > > > the mathematics of the DFT say *more* than that they are > > > "just numbers". > > > > > the mathematics says something about the relationship that these > > > numbers have with each other and with the input. > > > > >> It's a linear transformation from C^N to C^N. > > > > > there are *many* linear transformations. the DFT is a *specific* linear > > > transformation that maps a discrete and periodic sequence from one > > > domain to another discrete and periodic sequence of the same period in > > > the reciprocal domain. > > > > Also, there are many fine transformations that don't have periodic > > boundary conditions, such as the DCT. Often it seems to be used > > where people know that is needed, but if people specifically don't > > want periodic boundary conditions, instead of arguing that the DFT > > doesn't have them, use one that doesn't. > > > > Also, if I haven't mentioned it too many times already, there > > is the ICT which shows how far you can get away from the ideal > > and still be a reasonable transform. > > > > >> If you want to place an interpretation onto those numbers, > > >> that's your doing, not mathematics'. > > > > > appears that people want to blame me for it (i'm just the messenger), > > > but it's the mathematics that imposes the periodicity in the DFT. > > > although some claim to do it, you cannot simply "interpret" away the > > > properties of that particular linear transformation from C^N to C^N that > > > we call the DFT. one of those properties comes right out of the > > > definition of the DFT and iDFT and that property imposes periodicity. > > > > I don't have anything against those that use the DFT for > > non-periodic signals. It can be done. But don't deny that > > the transform does have those bounary conditions. > > > > -- glen
I look at this in an even simpler way. If you are trying to represent a function that is not oscillatory by a sum of oscillatory functions, then either your fit is not very good or you are going to need a large number of them to force the fit. Either way the suggestion is to use a different basis set since you may be trying to fit round pegs into square holes. Clay
clay@claysturner.com wrote:

(snip, I wrote)

>> I don't have anything against those that use the DFT for >> non-periodic signals. It can be done. But don't deny that >> the transform does have those bounary conditions.
> I look at this in an even simpler way. If you are trying to > represent a function that is not oscillatory by a sum of > oscillatory functions, then either your fit is not very good > or you are going to need a large number of them to force > the fit. Either way the suggestion is to use a different > basis set since you may be trying to fit round pegs > into square holes.
Hmm. In that case, you wouldn't use Tchebychev polynomials to approximate monotonic functions, but they are pretty good at doing that. -- glen
On Monday, August 5, 2013 7:46:32 PM UTC-4, glen herrmannsfeldt wrote:
> clay@claysturner.com wrote: > > > > (snip, I wrote) > > > > >> I don't have anything against those that use the DFT for > > >> non-periodic signals. It can be done. But don't deny that > > >> the transform does have those bounary conditions. > > > > > I look at this in an even simpler way. If you are trying to > > > represent a function that is not oscillatory by a sum of > > > oscillatory functions, then either your fit is not very good > > > or you are going to need a large number of them to force > > > the fit. Either way the suggestion is to use a different > > > basis set since you may be trying to fit round pegs > > > into square holes. > > > > Hmm. In that case, you wouldn't use Tchebychev polynomials > > to approximate monotonic functions, but they are pretty > > good at doing that. > > > > -- glen
Personally I take a very practical approach to how I think of the DFT. I break the possible input sequences into 3 categories; 1) The signal is purely periodic with a period that fits exactly in N samples. When I look at the DFT result, I say to myself "This is the exact spectrum of the infinite-length signal; there are no other frequencies present other than the ones computed by the DFT." End of story. 2) Time-limited non-periodic waveform. If I perform the DFT on this signal, I say "the DFT output represents samples of the true Fourier Transform over all frequencies. I can get more spectral resolution by zero-stuffing the time record and performing a longer DFT, or alternatively doing some interpolation in the frequency domain. 3) Infinite-time non-periodic waveform. If I perform an N-point DFT on this signal, I say "the DFT output represents samples of the Fourier transform of the truncated input sequence, or if I have used a window, it represents samples of the FT of the windowed input sequence. I can get more spectral resolution by increasing N, but the window (whether rectangular or something else) has distorted the true spectrum to some degree. I know this is all very basic, but for me, the interpretation of the DFT depends on which category the input falls into, even though the dft itself is just math done on a sequence of numbers. Bob
On 8/5/13 6:34 PM, radams2000@gmail.com wrote:
> > Personally I take a very practical approach to how I think of the DFT. I break the possible input sequences into 3 categories; > > 1) The signal is purely periodic with a period that fits exactly in N samples. When I look at the DFT result, I say to myself "This is the exact spectrum of the infinite-length signal; there are no other frequencies present other than the ones computed by the DFT." End of story. > > 2) Time-limited non-periodic waveform. If I perform the DFT on this signal, I say "the DFT output represents samples of the true Fourier Transform over all frequencies.
whoa! *all* frequencies?? even the frequencies between bin centers? (all depends on how you consider this time-limited waveform in the context of time in the universe that is less limited.)
> I can get more spectral resolution by zero-stuffing the time record and performing a longer DFT,
if you can do that, then you are considering your time-limited waveform as sitting in a sea of zeros. (otherwise you would have to stuff something else.) nonetheless, for each DFT you do (with more and more zero-stuffing), strictly from the DFT, you don't know what it is between the bins unless you assume some kind of extension to your data (that is fully defined by the N samples going into your original DFT). but (to anthropomorphize, since you didn't change the Subject: header) the DFT doesn't know that. the DFT *still* has periodically extended your data (of whatever length it was passed to the DFT, with or without any padded zeros).
> or alternatively doing some interpolation in the frequency domain.
many ways of doing interpolation. and whatever form of interpolation depends entirely on how you consider your time-limited waveform to be extended. if it's extended by zeros that means sinc(), or more accurately a dirichlet thingie (i still haven't settled in my brain what to do with the dirichlet thingie when N even).
> > 3) Infinite-time non-periodic waveform. If I perform an N-point DFT on this signal, I say "the DFT output represents samples of the Fourier transform of the truncated input sequence, or if I have used a window, it represents samples of the FT of the windowed input sequence. I can get more spectral resolution by increasing N, but the window (whether rectangular or something else) has distorted the true spectrum to some degree.
the spectral leakage of the window will distort it in such a way that the quantity in adjacent/neighboring bins will contribute. but since the circularity of the DFT cannot be avoided there around bin N/2, the negative frequencies have spectral bleeding into the positive frequencies and vise versa. and not just around DC (which the analog spectrum would show) but also around Nyquist. so if you had a significant frequency component at around bin N/2 - 1, that bleeding into any other bin in the neighborhood will also have bleeding from bin N/2 + 1 and the analog spectrum won't have that. and that comes from the periodic nature of the DFT, which doesn't know and doesn't care if its N-sample input came from a non-periodic source or not.
> > I know this is all very basic, but for me, the interpretation of the DFT depends on which category the input falls into, even though the DFT itself is just math done on a sequence of numbers.
remember the DFT and ioDFT are not just the definitions. as with the regular old Fourier Transform, the DFT comes with theorems. so the DFT is something more than just doing math on the input sequence. it has properties that exist whether they are hidden from view or not. (and the only way to hide the periodicity property from view is to make use of no other theorem than linearity. and again, i don't know anyone who will DFT a signal, just to scale the DFT spectrum by a constant, and then iDFT it back. if that's all you do, then the periodicity is hidden from view.) hey Bob, did you get to the Boston AES picnic? -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
On Monday, August 5, 2013 10:20:01 PM UTC-4, robert bristow-johnson wrote:
> On 8/5/13 6:34 PM, radams2000@gmail.com wrote: > > > > > > Personally I take a very practical approach to how I think of the DFT. I break the possible input sequences into 3 categories; > > > > > > 1) The signal is purely periodic with a period that fits exactly in N samples. When I look at the DFT result, I say to myself "This is the exact spectrum of the infinite-length signal; there are no other frequencies present other than the ones computed by the DFT." End of story. > > > > > > 2) Time-limited non-periodic waveform. If I perform the DFT on this signal, I say "the DFT output represents samples of the true Fourier Transform over all frequencies. > >
> > whoa! *all* frequencies?? even the frequencies between bin centers? > > (all depends on how you consider this time-limited waveform in the > > context of time in the universe that is less limited.) > > >
What I meant was, you can arbitrarily approach the full Fourier Transform of a finite-length discrete-time sequence by stuffing zeros and doing a longer and longer DFT; whether of not the "in-between" frequencies are important or necessary is another question.
> > > > I can get more spectral resolution by zero-stuffing the time record and performing a longer DFT, > > > > if you can do that, then you are considering your time-limited waveform > > as sitting in a sea of zeros. (otherwise you would have to stuff > > something else.) > > > > nonetheless, for each DFT you do (with more and more zero-stuffing), > > strictly from the DFT, you don't know what it is between the bins unless > > you assume some kind of extension to your data (that is fully defined by > > the N samples going into your original DFT). but (to anthropomorphize, > > since you didn't change the Subject: header) the DFT doesn't know that. > > the DFT *still* has periodically extended your data (of whatever > > length it was passed to the DFT, with or without any padded zeros). > > > > > or alternatively doing some interpolation in the frequency domain. > > > > many ways of doing interpolation. and whatever form of interpolation > > depends entirely on how you consider your time-limited waveform to be > > extended. if it's extended by zeros that means sinc(), or more > > accurately a dirichlet thingie (i still haven't settled in my brain what > > to do with the dirichlet thingie when N even). > > > > > > > > 3) Infinite-time non-periodic waveform. If I perform an N-point DFT on this signal, I say "the DFT output represents samples of the Fourier transform of the truncated input sequence, or if I have used a window, it represents samples of the FT of the windowed input sequence. I can get more spectral resolution by increasing N, but the window (whether rectangular or something else) has distorted the true spectrum to some degree. > > > > the spectral leakage of the window will distort it in such a way that > > the quantity in adjacent/neighboring bins will contribute. but since > > the circularity of the DFT cannot be avoided there around bin N/2, the > > negative frequencies have spectral bleeding into the positive > > frequencies and vise versa. and not just around DC (which the analog > > spectrum would show) but also around Nyquist. so if you had a > > significant frequency component at around bin N/2 - 1, that bleeding > > into any other bin in the neighborhood will also have bleeding from bin > > N/2 + 1 and the analog spectrum won't have that. and that comes from > > the periodic nature of the DFT, which doesn't know and doesn't care if > > its N-sample input came from a non-periodic source or not. > >
Does that come from the DFT or from the sampling theorem?
> > > > > > I know this is all very basic, but for me, the interpretation of the DFT depends on which category the input falls into, even though the DFT itself is just math done on a sequence of numbers. > > > > remember the DFT and ioDFT are not just the definitions. as with the > > regular old Fourier Transform, the DFT comes with theorems. so the DFT > > is something more than just doing math on the input sequence. it has > > properties that exist whether they are hidden from view or not. (and > > the only way to hide the periodicity property from view is to make use > > of no other theorem than linearity. and again, i don't know anyone who > > will DFT a signal, just to scale the DFT spectrum by a constant, and > > then iDFT it back. if that's all you do, then the periodicity is hidden > > from view.)
In my brain, you could take the full FT of a sampled signal (in Dirac form) and it will have the same circular form, but that is due to the sampling operation. You could then just pick off the specific frequencies at 2PI/N and have the same result as the DFT.
> > > > hey Bob, did you get to the Boston AES picnic?
No, I have been on the road a lot, no time for fun stuff like local AES!
> > > > > > -- > > > > r b-j rbj@audioimagination.com > > > > "Imagination is more important than knowledge."
Robert