On Friday, August 2, 2013 7:11:15 AM UTC-5, Rick Lyons wrote:> > Notice their initial words: "Although several points of > > view can be taken ..." >Rick: You sure believe in throwing fuel on the fire, don't you? :-) :-) Let us brace ourselves for the usual impassioned rebuttal from rb-j that only one point of view can be taken and thou shalt have no other gods before me. :-) Dilip Sarwate
discrete fourier series and transform
Started by ●July 29, 2013
Reply by ●August 2, 20132013-08-02
Reply by ●August 2, 20132013-08-02
On Fri, 02 Aug 2013 05:11:15 -0700, Rick Lyons <R.Lyons@_BOGUS_ieee.org> wrote:>On Mon, 29 Jul 2013 14:54:08 -0700 (PDT), dvsarwate ><dvsarwate@yahoo.com> wrote: > >>On Monday, July 29, 2013 12:10:52 PM UTC-5, robert bristow-johnson wrote: >> >>> but Dilip, i think the term we have for that is simply "Fourier series" >>> >>> or, in the case of c_n * e^(j*2*pi*n*t/T), we might call it the >>> >>> "complex Fourier series". at least in my copy of O&S, the term >>> >>> "Discrete Fourier Series" is about "a sequence ~x[n] that is periodic >>> >>> with period N so that ~x[n] = ~x[n+rN] for any integer value of r." (the >>> >>> tilde ~ is meant to be above the "x".) that's what O&S call the >>> >>> "Discrete Fourier Series". it's explicitly a mapping of one discrete >>> >>> and periodic sequence with period N to another discrete and periodic >>> >>> sequence of period N. >> >> >>Robert: >> >>With genuflections and obeisances in the general >>direction of O&S which tome I do not have on my >>bookshelf, I suggest that you are misinterpreting >>what O&S are saying, and if not, I am willing to >>entertain the possibility that what O&S are saying >>is flat out wrong. >> >>The discrete Fourier transform maps a vector x of >>N complex-valued numbers to another vector X of >>length N of complex-valued numbers. If we extend >>x periodically to construct a complex-valued >>sequence of period N, then the discrete Fourier >>transform of the sequence can be defined as the >>the corresponding periodic extension of X. >> >>On the other hand, a discrete Fourier series >>(manishp's choice, not the one I would have >>chosen) represents a periodic continuous-time >>signal x(t) as the sum of complex exponentials >>exp(j 2pi nt/T) weighted by complex numbers >>c_n. There is _nothing_ that is periodic about >>the sequence {c_n}: indeed, if the sequence of >>c_n's were repeating periodically, the >>continuous-time signal x(t) would deliver infinite >>energy in each period, and we could all retire >>since the energy crisis will have been solved! >> >>So, I disagree with you, and possibly O&S, if you >>are asserting that there is no difference except >>for the typographical notation ~ between these >>two notions: the representation of a periodic >>sequence of complex numbers in terms of another >>periodic sequence of complex numbers, and the >>representation of a continuous-time periodic >>signal by an aperiodic sequence of complex >>numbers. There is considerable family resemblance: >>they are kissing cousins, maybe even first cousins >>or siblings, but identical twins, No. > >Hi Dilip, > for what it's worth, at the beginning of their chapter >titled: "The Discrete Fourier Transform", on page 541 of >their 2nd Edition, Oppenheim & Schafer state: > > "Although several points of view can be taken toward the > derivation and interpretation of the DFT representation > of a finite-duration sequence, we have chosen to base > our presentation on the relationship between periodic > sequences and finite-length sequences. We will begin by > considering the Fourier series representation of > periodic sequences. While this representation is > important in its own right, we are most often interested > in the application of Fourier series results to the > representation of finite-length sequences. We accomplish > this by constructing a periodic sequence for which each > period is identical to the finite-length sequence. As we > will see. the Fourier series representation of the > periodic sequence corresponds to the DFT of the > finite-length sequence. Thus, our approach is to define > the Fourier series representation for periodic sequences > and to study the properties of such representations. > Then we repeat essentially the same derivations, assuming > that the sequence to be represented is a > finite-length sequence." > > >Notice their initial words: "Although several points of >view can be taken ..." > >Dilip, as far as I can tell, I conform to your viewpoint >concerning this topic. > >[-Rick-]That's the text I was alluding to elsewhere. Similar text appears in both O&S "Digital Signal Processing" and "Discrete-Time Signal Processing". Eric Jacobsen Anchor Hill Communications http://www.anchorhill.com
Reply by ●August 2, 20132013-08-02
On 8/2/13 5:11 AM, Rick Lyons wrote:> On Mon, 29 Jul 2013 14:54:08 -0700 (PDT), dvsarwate > <dvsarwate@yahoo.com> wrote:...>> >> With genuflections and obeisances in the general >> direction of O&S which tome I do not have on my >> bookshelf, I suggest that you are misinterpreting >> what O&S are saying, and if not, I am willing to >> entertain the possibility that what O&S are saying >> is flat out wrong. >>...>> >> So, I disagree with you, and possibly O&S, if you >> are asserting that there is no difference except >> for the typographical notation ~ between these >> two notions: the representation of a periodic >> sequence of complex numbers in terms of another >> periodic sequence of complex numbers, and the >> representation of a continuous-time periodic >> signal by an aperiodic sequence of complex >> numbers. There is considerable family resemblance: >> they are kissing cousins, maybe even first cousins >> or siblings, but identical twins, No. > > Hi Dilip, > for what it's worth, at the beginning of their chapter > titled: "The Discrete Fourier Transform", on page 541 of > their 2nd Edition, Oppenheim& Schafer state: > > "Although several points of view can be taken toward the > derivation and interpretation of the DFT representation > of a finite-duration sequence, we have chosen to base > our presentation on the relationship between periodic > sequences and finite-length sequences. We will begin by > considering the Fourier series representation of > periodic sequences. While this representation is > important in its own right, we are most often interested > in the application of Fourier series results to the > representation of finite-length sequences. We accomplish > this by constructing a periodic sequence for which each > period is identical to the finite-length sequence. As we > will see. the Fourier series representation of the > periodic sequence corresponds to the DFT of the > finite-length sequence. Thus, our approach is to define > the Fourier series representation for periodic sequences > and to study the properties of such representations. > Then we repeat essentially the same derivations, assuming > that the sequence to be represented is a > finite-length sequence." > > > Notice their initial words: "Although several points of > view can be taken ..."On 8/2/13 8:04 AM, dvsarwate wrote:> > Rick: > > You sure believe in throwing fuel on the fire, > don't you? :-) :-) Let us brace ourselves for > the usual impassioned rebuttal from rb-j that > only one point of view can be taken and thou > shalt have no other gods before me. :-)so how is this (additional) fuel on the fire that i had been burning? the last time (as i recall) that we had this fracas in detail was in January/February 2011 (like the MATLAB indexing thing, i usually do not waste opportunities to reignite some fuel when someone leaves some laying around, and this is only the latest instance of that). here is what *I* said O&S said back then: https://groups.google.com/forum/message/raw?msg=comp.dsp/MWKlDCulP7E/Ifl1ISPUt1cJ note i quoted the very same thing. but Rick left out another observation (section 8.6, p 532 in my book, i have the first quote at 514 rather than 541) that O&S make immediately after they state, for the first time, the DFT and iDFT equations that look surprizingly similar to the DFS equations that they had earlier. i quoted it then (along with what Rick does above) and i'll restate it here (just because O&S say it better than me): "In recasting Eqs. (8.11) and (8.12) in the form of Eqs. (8.61) and (8.62) for the finite-duration sequences, we have not eliminated the inherent periodicity. As with the DFS, the DFT X[k] is equal to samples of the periodic Fourier transform X(e^jw), and if Eq. (8.62) is evaluated for values of n outside the interval 0 <= n <= N-1, the result will not be zero but rather a periodic extension of x[n]. 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." besides the admonition (ignoring it invites trouble), it's O&S saying "inherent periodicity", "periodic extension", "inherent periodicity always present". i didn't just make it up. Rick, O&S are recognizing that there are other viewpoints (and i quoted that in 2011 and the earlier times we argued about it here), but they are hardly neutral on the issue. just more diplomatic about it than i am. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●August 2, 20132013-08-02
and, Rick, you left out the concluding statement in the paragraph you quoted (i just noticed that now). i'll finish the quote below:> On 8/2/13 5:11 AM, Rick Lyons wrote: >> >> for what it's worth, at the beginning of their chapter >> titled: "The Discrete Fourier Transform", on page 541 of >> their 2nd Edition, Oppenheim & Schafer state: >> >> "Although several points of view can be taken toward the >> derivation and interpretation of the DFT representation >> of a finite-duration sequence, we have chosen to base >> our presentation on the relationship between periodic >> sequences and finite-length sequences. We will begin by >> considering the Fourier series representation of >> periodic sequences. While this representation is >> important in its own right, we are most often interested >> in the application of Fourier series results to the >> representation of finite-length sequences. We accomplish >> this by constructing a periodic sequence for which each >> period is identical to the finite-length sequence. As we >> will see. the Fourier series representation of the >> periodic sequence corresponds to the DFT of the >> finite-length sequence. Thus, our approach is to define >> the Fourier series representation for periodic sequences >> and to study the properties of such representations. >> Then we repeat essentially the same derivations, assuming >> that the sequence to be represented is a finite-length >> sequence. ...... This approach to the DFT emphasizes the fundamental inherent periodicity of the DFT representation and ensures that this periodicity is not overlooked in applications of the DFT.">> >> >> Notice their initial words: "Although several points of >> view can be taken ..."the concluding words, IMO, speak more loudly. especially when they say this a few pages later:> "In recasting Eqs. (8.11) and (8.12) in the form of Eqs. (8.61) and > (8.62) for the finite-duration sequences, we have not eliminated the > inherent periodicity. As with the DFS, the DFT X[k] is equal to > samples of the periodic Fourier transform X(e^jw), and if Eq. (8.62) > is evaluated for values of n outside the interval 0 <= n <= N-1, the > result will not be zero but rather a periodic extension of x[n]. 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."Dilip, you *are* disagreeing with O&S besides me. and also with that Kabal reference that Dale brought to our attention. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●August 2, 20132013-08-02
On Monday, July 29, 2013 3:28:55 AM UTC-5, manishp wrote:> Sirs, While reading on frequency representation, I am a little confused with discrete fourier series (as opposed to discrete fourier transform) and its application. Can I get some inputs please. Thanks, manish _____________________________ Posted through www.DSPRelated.comThe simplest way to see it is as a discretized version of the continuous Fourier transform -- particularly keeping explicit and intact the actual scalings and measures used (something DSP references almost never do). For the forward transform, you end up going from (f(t_k): k in N) -> (f'(nu_n): n in N) where I'm using the convention of identifying the integer N as the set { 0, 1, ..., N - 1 }. The discretized spacings are delta_t for t_k and delta_nu for nu_n and the requirement is that they satisfy the "quantization" condition that their product be 1/N. So, the density of the transform in the (t, nu) "time-frequency" plane is 1/N. The actual points would then have the form t_k = t* + (k + 1/2) delta_t nu_n = nu* + (nu + 1/2) delta_nu where t* and nu* can be arbitrarily chosen (something most DSP references fail to note!) The transform inteverals associated with the center points are then +/- 1/2 delta_t and +/- delta_nu respectively. Then the sum mimicks the integral form almost exactly: f'(nu_n) = sum_{k in N} f(t_k) exp(-2 pi i t_k nu_n) delta_t and the inverse f(t_k) = sum_{n in N} f(nu_n) exp(2 pi i nu_n t_k) delta_nu The usual conditions are to take delta_t = delta_nu or to take one of them to be 1. The interval transformed (i.e. the bandwidths) are over the time frequency rectangle: [t*, t* + 1/delta_nu] x [nu*, nu* + 1/delta_t] and it's common to take the frequency part of this as being centered on 0 or as starting at 0. More correctly, it should be centered on 0 (so nu* = -1/(2 delta_t), but DSP references generally start it at 0. t* can start anywhere. The uses for the transform as are a workhorse "nuts and bolts" level tool for carrying out a lot of other transforms. Time permitting, I'll add more on this with respect to two applications: (1) the windowed Fourier transform and (2) a discretized form of the same suitable for octave scaling. Item (2) is a discretized form of the S-transform (and in effect, also of the Morlet wavelet transform) and can be generalized and merged with a general filterbank construction that also allows matching against templates other than single-frequency tones.
Reply by ●August 3, 20132013-08-03
Ah, Robert, Robert, to be so young and yet so ossified (or did I mean to say O&Ssified?)in your thinking..... As Rick Lyons pointed out to you, O&S said "Although several points of view can be taken toward the derivation and interpretation of the DFT representation of a finite-duration sequence, we have CHOSEN (emphasis added) .... and so it is not O&S who are denying the validity of other points of view; in fact they are admitting upfront that other viewpoints are possible. It is natural for them to prefer their own chosen viewpoint over others, but why shouldn't they? After all, they have put in considerable effort in writing a textbook from that viewpoint, and there is no reason to expect them to be neutral in this matter! But, as even you admit "Rick, O&S are recognizing that there are other viewpoints (and i quoted that in 2011..." I don't see where O&S are DENYING the validity of other viewpoints whether in diplomatically acceptable terms or not; it is YOU who are continually insisting that the O&S viewpoint is the _only_ correct one and that all who use other viewpoints are in a state of mortal sin. You are insisting that "Thou shalt have no other gods before O&S" is a commandment that must be accepted by all even though all the evidence indicates that this commandment does not issue from O&S themselves. So, I will disregard your annotations and additions to the received wisdom from O&S and interpret their sayings according to what **I** read in their text, and what you say they do. Dilip Sarwate P.S. Since this post has gotten various non-dsp overtones, let me, as a determined polytheist, remind you that atheists differ from monotheists such as yourself by only one in the number of gods whose existence they deny.
Reply by ●August 4, 20132013-08-04
On 8/3/13 7:48 PM, dvsarwate wrote:> Ah, Robert, Robert, to be so young> and yet so > ossified (or did I mean to say O&Ssified?)in > your thinking..... > > As Rick Lyons pointed out to you, O&S said > > "Although several points of view can be taken toward the > derivation and interpretation of the DFT representation > of a finite-duration sequence, we have CHOSEN (emphasis > added) .... > > and so it is not O&S who are denying the > validity of other points of view; in fact > they are admitting upfront that other > viewpoints are possible.they are conceding that other viewpoints exist. not that they are correct. but i am not depending on O&S. they just agree with me about the math. explicitly. i just find it astonishing when people deny that O&S say that the periodicity is always there, and that to ignore that fact can lead to trouble. they're clear about that. alls i am saying is, whether you explicitly periodically extend the N samples passed to the DFT (which is saying x[n+N] = x[n] for all n) or not, the value that comes after x[N-1] is the value of x[0]. the input to the DFT: {x[0], x[1], x[2] ... x[N-1]} is not just an unordered collection of values. i.e. suppose N = 8 and the input {x[0], x[1], x[2] ... x[7]} is {4, 2, -1, -2, 0, 3, 6, 5}. now the order in that is important. the DFT is going to treat that input sequence differently than it will {0, 6, 4, -2, 5, -1, 3, 2}, even though they are the same values, just in a different order. so in the original input, it *matters* that x[1]=2 comes right after x[0]=4, and that x[6]=6 comes right after x[5]=3. so this is what i am saying, what O&S is saying, and what the math is saying in the context of the DFT: in every manner that it is true that x[6]=6 comes right after x[5]=3, so also does x[0]=4 comes right after x[7]=5. in the same way that 6 comes after 3, so also does 4 have the very same relationship with the 5 sitting next to it. to deny that is to deny the math of the DFT. you wouldn't be denying what the DFT linearity property says, but you *are* denying the shifting and convolution theorems and that is not a matter of interpretation. you cannot simply interpret that away because the math doesn't let you. SO... i think (this is preference, not a theorem or a fact claim) the simplest and most compact way to state this is that "x[N] = x[0]" and, in general "x[n+N] = x[n]". but you can also say that there *is* no x[N] or any other sample with index above N-1 or with index below 0. but if you do that, you must replace x[n] in general with x[n mod_N]. i do not know of another notational convention to express that. now lacking a third notational convention, then, if you're talking about the DFT of length N, you *must* choose one of those two. and both are periodic extensions. the "x[n+N] = x[n]" is explicit about the periodic extension and the "x[n mod_N]" is implicit, but they say the same thing. if you deny that you need one or the other, then you're mathematically incorrect unless the only property of the DFT you care about is linearity. if you are using the DFT and any other theorem regarding the DFT, then you *must* say either that "x[n+N] = x[n]" or use "x[n mod_N]" or your math will be wrong. i (and O&S) say that this is "periodic extension". you can call it a radish or something else, but it doesn't change the mathematical fact.> It is natural > for them to prefer their own chosen viewpoint > over others, but why shouldn't they? After > all, they have put in considerable effort in > writing a textbook from that viewpoint, and > there is no reason to expect them to be > neutral in this matter! But, as even you admit > > "Rick, O&S are recognizing that there are > other viewpoints (and i quoted that in 2011..." > > I don't see where O&S are DENYING the validity > of other viewpoints whether in diplomatically > acceptable terms or not; it is YOU who are > continually insisting that the O&S viewpoint > is the _only_ correct one and that all who > use other viewpoints are in a state of mortal > sin. You are insisting that > > "Thou shalt have no other gods before O&S"no, i am insisting that O&S say that the input to the DFT is periodically extended. and Dale (and perhaps Eric and Rick, i dunno) say that O&S do not say that. that's astonishing, because O&S are explicit about it. with words like "the inherent periodicity is always present". they're not saying that the inherent periodicity is present only for those who recognize the inherent periodicity. and neither do i say that. but i think that some others on this forum (perhaps you) *do* say that taking another point of view allows one to avoid this inherent periodicity and i am saying that taking such a position is simply mathematically incorrect. and that the math is clear.> is a commandment that must be accepted by > all even though all the evidence indicates > that this commandment does not issue from > O&S themselves. So, I will disregard your > annotations and additions to the received > wisdom from O&S and interpret their sayings > according to what **I** read in their text, > and what you say they do. > > Dilip Sarwate > > P.S. Since this post has gotten various > non-dsp overtones, let me, as a determined > polytheist, remind you that atheists differ > from monotheists such as yourself by only > one in the number of gods whose existence > they deny.i hadn't at all brought issues of faith into this, either directly or metaphorically. early on (back in the 90s), i think it was Eric that first referred to *my* citing of O&S as "quoting O&S scripture" and i thought that was kinda cute so i sorta ran with it. but only metaphorically and only tongue-in-cheek. the only god in this is Mathematics. and, in this metaphor, the Word of God are mathematical theorems. and it is a mathematical fact that x[0] comes after x[N-1] in the DFT in the same way that x[5] comes after x[4]. that's a fact claim, and if you deny it or even say that it's only an interpretation or a viewpoint; something less than a mathematical fact, i say you're wrong. and that the mathematics say you're wrong. and that O&S agree (but what do they know?). -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
