On Aug 8, 9:45 pm, robert bristow-johnson <r...@audioimagination.com> wrote: .> ... .> other interpretations are fine as long as they are mathematically .> valid. is there a single, mathematically valid interpretation of the .> DFT that shows that when the samples are shifted, either to the left .> or to the right, that the samples that are shifted in from the right .> or from the left are zero? or undefined? or *anything* other than .> the samples you would get from being periodically extended? What a silly irrelevant strawman. From what application do you get a requirement for shift in and shift out concepts? I gave the application of the DFT to compute a filter bank. N filters are calculated on the N samples and the results are demodulated to DC by the DFT. There are no extended samples. There is no shift in or shift out. The process operates on N samples as defined by the DFT. Any time the operation is performed the samples are independently selected and weighted. There is no periodic extension. Any new samples in the next call to the process are new samples from an approximately band-limited real-world process, not periodic extensions. There is no periodic extension in the DFT formula, just a set of convolutions with finite sets of constants, and there is no periodic extension in the application data organization. .> ... .> please provide an example, then my claim is disproven (falsified). .> .> r b-j This is a long established example of the use of the DFT formula without recourse to any interpretation involving periodic extension. This simply isn't an attempt to look like, feel like, be derived from or approximate a continuous-infinite transform. It is a set of FIR filters. Dale B. Dalrymple
DFT or DFS: Are they the same thing?
Started by ●August 7, 2009
Reply by ●August 9, 20092009-08-09
Reply by ●August 9, 20092009-08-09
dbd <dbd@ieee.org> wrote: (snip) < What a silly irrelevant strawman. From what application do you get a < requirement for shift in and shift out concepts? I gave the < application of the DFT to compute a filter bank. N filters are < calculated on the N samples and the results are demodulated to DC by < the DFT. There are no extended samples. There is no shift in or shift < out. The process operates on N samples as defined by the DFT. Any time < the operation is performed the samples are independently selected and < weighted. There is no periodic extension. I agree that there is not periodic extension, but that is independent of periodic boundary conditions. If, for example, you low pass filter in the frequency domain, sample values will tend to get closer together. It takes high frequency components to create sharp changes. Because of the periodic boundary conditions, the last sample is as far from the first as any neighboring pair. If you consider points on a circle instead of points on a line segment maybe that is more obvious. Otherwise, without claiming periodic extension, if you have a finite set of uniform spaced points, and make all other points "don't care" in the logic minimization sense then the simplest result is that of periodic extension. That doesn't mean that there actually is any periodic extension, only that it is a convenient way to map a circle onto an infinite line. In logic minimization you give the "don't care" states the value that results in the simplest logic. That doesn't change the properties of those states. < Any new samples in the next < call to the process are new samples from an approximately band-limited < real-world process, not periodic extensions. There is no periodic < extension in the DFT formula, just a set of convolutions with finite < sets of constants, and there is no periodic extension in the < application data organization. When my son was about four, he figured that he wanted his bedtime to be 9:61. We figured out that there was no such time, and that he wouldn't have to go to bed. That is periodic extension in the time domain. -- glen
Reply by ●August 9, 20092009-08-09
On 9 Aug, 11:02, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:> < and there is no periodic extension in the > < application data organization. > > When my son was about four, he figured that he wanted his > bedtime to be 9:61. �We figured out that there was no such time, > and that he wouldn't have to go to bed. �That is periodic extension > in the time domain.Smart kid, for sure. Maybe too smart for his own good. Did it work? Did he stay up till he fell over in his tracks, or did somebody explain his logical flaw for him? Unless he understands exactly where he went wrong, his self-confidence might have got a serious kick. Similar lines of arguments might cause similarly smart people to reach the inevitable conclusion: "If the DFT is based on the assumption that the input sequence is exactly one period of an infinitely long, periodic sequence, the DFT has no practical purpose since the stated scenario occurs with probability ~0." And all of a sudden poor teaching has claimed yet another victim. With a bit of luck, the student does as Jerry's friend, who did not understand why the rules of sign changes under multiplication are as they are, and leave the subject alltogether. The worst case scenario is that the student stays, but with a deep mistrust of all he hears and everybody he meets, and we have another Mr Bean on our hands. I remember my first class on DSP. The teacher was too wise to pretend that DSP was a self-contained, easily understood subject. Whenever necessary, instead of attempting an ad-hoc explanation based on the subjects we already knew, he often said that "mathemathical results you have'nt been taught yet (and will not be, for some years to come), show that..." That way he kept us aware of the fact that we had a lot to learn, at the same time he instilled the attitude at least in me that I tried to retrofit new maths into the concept of DSP as I kept learning new stuff. Rune
Reply by ●August 9, 20092009-08-09
On Aug 7, 2:56�am, Rune Allnor <all...@tele.ntnu.no> wrote:> On 7 Aug, 06:06, "commengr" <communications_engin...@yahoo.com> wrote: > > > Hello, > > > I have a question, it may be simple but its bugging me, so I need your > > help. What is the difference between Discrete Fourier Series (DFS) and the > > Discrete Fourier Transform (DFT) both theoretically and practically > > > Now, I know that we use DFS for the spectral analysis of Periodic > > sequences and DFT for Aperiodic. > > You haven't defined the terms very detailed, but the DFS, as I > understadn the term, is the trannsform of an infinitely long but > periodic sequence. The DFT is a special case of the Discrete-Time > Fourier Transform, which handles infinitely long sequences > arbitrary sequences. > > > (My concept is that in DFT, we have an > > aperiodic sequence so we decide on the length of the sequence N to use for > > spectral analysis, since we don't have a 'period', we repeat the sequence > > as after those N samples, so its like an artificial periodic sequence) > > Wrong. The DFT is the transform of a sequence with a finite > number of elements. > > > However, if I give the same sequence of length N to a DFS algorithm, would > > I not get the same results? The algorithm assumes, if I'm not mistaken, > > that the sequence will be periodic. > > Most newbies don't understand that there are several variants > of the Fourier transform around. The different variants take > either discrete or continuous data as input, and the data are > of either finite or infinite extent. > > The DFT takes a finite siquence of discrete data as input, > and thus happens to be the variant that can be computed with > what we understand as a 'computer' (there used to be analog > computers in the past). There are no assumptions or > constraints whatsoever imposed by the DFT on anything. > > The DFS is an ad hoc attempt for people to conceptually link > the results of computations on finite discrete sequences > to the desired results, that are computations on infinite > length discrete sequences.http://12000.org/my_notes/transforms/transforms.png hope this helps. Greg
Reply by ●August 9, 20092009-08-09
On Aug 9, 2:02 am, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:> ... > I agree that there is not periodic extension, but that is > independent of periodic boundary conditions. If, for example, > you low pass filter in the frequency domain, sample values will > tend to get closer together. It takes high frequency components > to create sharp changes. Because of the periodic boundary conditions, > the last sample is as far from the first as any neighboring pair. > If you consider points on a circle instead of points on a line > segment maybe that is more obvious. >.> Otherwise, without claiming periodic extension, if you have a finite .> set of uniform spaced points, and make all other points "don't care" .> in the logic minimization sense then the simplest result is that of .> periodic extension. That doesn't mean that there actually is any> periodic extension, only that it is a convenient way to map > a circle onto an infinite line. In logic minimization you give the > "don't care" states the value that results in the simplest logic. > That doesn't change the properties of those states. > > ... > -- glenThe FIR filter application of the DFT formula has no "don't care" points. All points outside the FIR are weighted by zero on purpose. There is no periodic extension and no infinite line. The application is a finite set of real-world samples that I wish to calculate the local characteristics of even smaller sections of. There are no "don't cares", there is only a set of finite impulse responses and everything outside each finite impulse response is required to be weighted zero. Dale B. Dalrymple
Reply by ●August 9, 20092009-08-09
On Aug 9, 4:05�am, dbd <d...@ieee.org> wrote:> On Aug 8, 9:45 pm, robert bristow-johnson <r...@audioimagination.com> > wrote: > > .> ... > .> other interpretations are fine as long as they are mathematically > .> valid. �is there a single, mathematically valid interpretation of > the > .> DFT that shows that when the samples are shifted, either to the > left > .> or to the right, that the samples that are shifted in from the > right > .> or from the left are zero? �or undefined? �or *anything* other than > .> the samples you would get from being periodically extended? > > What a silly irrelevant strawman. From what application do you get a > requirement for shift in and shift out concepts?convolution.> I gave the > application of the DFT to compute a filter bank. N filters are > calculated on the N samples and the results are demodulated to DC by > the DFT.for each filter bank, are you multiplying the spectra (output of the DFT) by some transfer function? if you are doing that, you are convolving in the time domain, no? is that convolution linear or circular?> There are no extended samples. There is no shift in or shift > out.no shifting involved in convolution? what's happening in the second factor of each term: N-1 y[n] = SUM{ x[i] h[n-i] } i=0 what's happening when n=2 and i=4? what value is used for h[2-4]?> The process operates on N samples as defined by the DFT. Any time > the operation is performed the samples are independently selected and > weighted. There is no periodic extension.are you sure? or are you ignoring the effects periodic extension because you can (perhaps by the use of some zero-padding)?> Any new samples in the next > call to the process are new samples from an approximately band-limited > real-world process, not periodic extensions. There is no periodic > extension in the DFT formula,name that formula (not the definition of the DFT, but the what you are doing with your filtering). if you are multiplying in the frequency domain, you are convolving in the time domain, and when you convolve using the the DFT, you are circularly convolving. there is no escape from that (but there are things we can do about it).> just a set of convolutions with finite > sets of constants, and there is no periodic extension in the > application data organization.that is mathematically mistaken. there is no linear convolution using the DFT. only circular convolution. perhaps the periodic extension is mitigated. my silly strawman seems to be a little tougher than you estimate. let's get into the math, Dale. you have to spell out exactly what you're doing and i'll show you where the periodic extension is.> .> ... > .> please provide an example, then my claim is disproven (falsified). > .> > .> r b-j > > This is a long established example of the use of the DFT formula > without recourse to any interpretation involving periodic extension. > This simply isn't an attempt to look like, feel like, be derived from > or approximate a continuous-infinite transform. It is a set of FIR > filters.but, just like in fast-convolution (which is what you do with an FFT), the FIRs done with the DFT are accomplished by the use of circular convolution. if you zero-pad sufficiently, and line your ducks up correctly, you can arrange it so that there are a sufficient number of output samples that are computed with no non-zero samples straddling the discontinuity between N-1 and 0. you can accomplish linear convolution by use of a circular convolver. but it's still doing circular convolution fundamentally. Dale, as we drill into this, and get specific with the math, you will lose the argument. it's inescapable. and it has nothing to do with me. the maths are not on your side. r b-j
Reply by ●August 9, 20092009-08-09
Rune Allnor wrote:> On 9 Aug, 11:02, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote: > >> < and there is no periodic extension in the >> < application data organization. >> >> When my son was about four, he figured that he wanted his >> bedtime to be 9:61. We figured out that there was no such time, >> and that he wouldn't have to go to bed. That is periodic extension >> in the time domain. > > Smart kid, for sure. Maybe too smart for his own good. > > Did it work? Did he stay up till he fell over in his > tracks, or did somebody explain his logical flaw for him? > Unless he understands exactly where he went wrong, his > self-confidence might have got a serious kick.I would simply have put him to bed at 10:01, assuming that time to be acceptable. After all, that's 61 minutes after 9:00. Periodic extension holds. (The age of majority used to be eleventeen.) My wife's boss once insisted that she date a report Sept.31 despite her reminding him that September has only 30 days. He was the boss; he won. (You never can tell with psychiatrists.)> Similar lines of arguments might cause similarly smart > people to reach the inevitable conclusion: "If the DFT > is based on the assumption that the input sequence is > exactly one period of an infinitely long, periodic > sequence, the DFT has no practical purpose since the > stated scenario occurs with probability ~0." > > And all of a sudden poor teaching has claimed yet another > victim. With a bit of luck, the student does as Jerry's > friend, who did not understand why the rules of sign > changes under multiplication are as they are, and leave > the subject altogether. The worst case scenario is that > the student stays, but with a deep mistrust of all he > hears and everybody he meets, and we have another Mr Bean > on our hands.My friend, and later my wife. I was attracted to her because she was the only person I knew who was clearly smarter than I. She was attracted to me in part because I liked that.> I remember my first class on DSP. The teacher was too > wise to pretend that DSP was a self-contained, easily > understood subject. Whenever necessary, instead of > attempting an ad-hoc explanation based on the subjects > we already knew, he often said that "mathemathical results > you have'nt been taught yet (and will not be, for some > years to come), show that..."Refreshing!> That way he kept us aware of the fact that we had a > lot to learn, at the same time he instilled the attitude > at least in me that I tried to retrofit new maths > into the concept of DSP as I kept learning new stuff.Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●August 9, 20092009-08-09
On Aug 9, 9:54�am, Greg <he...@alumni.brown.edu> wrote:> > http://12000.org/my_notes/transforms/transforms.png > > hope this helps.it actually does, Greg. and in ways the author of the diagram might not have intended. what is called "DTFS" in the diagram is what we have been simply calling the DFS here, the Discrete Fourier Series. now, compare the DTFS box with the DFT box. except for different symbols in one place ("c[k]" vs. "X[k]") and where they decided to put the 1/N factor (a matter of mere convention, they could have put sqrt (1/N) in front of both summations), is there any mathematical difference between the DTFS and the DFT? the answer is yes, but the difference is only contrived. in the DFT box you will see "k = 0,1,...,N-1" and similarly for "n = 0,1,...,N-1", implying that there is no X[k] or x[n] outside of those domains of k and n. you will also see a qualification for x[n] going into the box that says "Finite x[n] length N, zero elsewhere" which seems to contradict that x[n] has no definition outside of (0..N-1). all of that has no use and essentially has no meaning, and you have to undo it (by use of the modulo_N operator on indices) when you shift or convolve. those extra restrictions on n and k in the DFT box serve no useful purpose. you may as well just call it a DFS. i think this is what the OP, commengr, was noticing when he/she started this thread. r b-j
Reply by ●August 9, 20092009-08-09
On 9 Aug, 17:18, Jerry Avins <j...@ieee.org> wrote:> Rune Allnor wrote: > > On 9 Aug, 11:02, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote: > > >> < and there is no periodic extension in the > >> < application data organization. > > >> When my son was about four, he figured that he wanted his > >> bedtime to be 9:61. �We figured out that there was no such time, > >> and that he wouldn't have to go to bed. �That is periodic extension > >> in the time domain. > > > Smart kid, for sure. Maybe too smart for his own good. > > > Did it work? Did he stay up till he fell over in his > > tracks, or did somebody explain his logical flaw for him? > > Unless he understands exactly where he went wrong, his > > self-confidence might have got a serious kick. > > I would simply have put him to bed at 10:01, assuming that time to be > acceptable. After all, that's 61 minutes after 9:00. Periodic extension > holds. (The age of majority used to be eleventeen.)My point was the the kid confused a conveinient but ad hoc reference system with physical reality. And don't underestimate the psychological impact of these sorts of episodes. Sure, one would not do too much damage, but if there are many of them, the child might experience a pattern of episodes where stuff that is obvious and logical to him, backfires. No good will come out of that.> My wife's boss once insisted that she date a report Sept.31 despite her > reminding him that September has only 30 days. He was the boss; he won. > (You never can tell with psychiatrists.)I have seen the same argument every now and then used for May 1st. Not everybody are equally all that with the political symbolism of that date, so some use April 31st instead. Rune
Reply by ●August 9, 20092009-08-09
On Aug 9, 10:52�am, dbd <d...@ieee.org> wrote:> On Aug 9, 2:02 am, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:> ... > > I agree that there is not periodic extension, but that is > > independent of periodic boundary conditions. �If, for example, > > you low pass filter in the frequency domain, sample values will > > tend to get closer together. �It takes high frequency components > > to create sharp changes. �Because of the periodic boundary conditions, > > the last sample is as far from the first as any neighboring pair. > > If you consider points on a circle instead of points on a line > > segment maybe that is more obvious. > > > Otherwise, without claiming periodic extension, if you have a finite > > set of uniform spaced points, and make all other points "don't care" > > in the logic minimization sense then the simplest result is that of > > periodic extension. �That doesn't mean that there actually is any > > periodic extension, only that it is a convenient way to map > > a circle onto an infinite line. �In logic minimization you give the > > "don't care" states the value that results in the simplest logic. > > That doesn't change the properties of those states. > > > The FIR filter application of the DFT formula has no "don't care" > points. All points outside the FIR are weighted by zero on purpose. > There is no periodic extension and no infinite line. The application > is a finite set of real-world samples that I wish to calculate the > local characteristics of even smaller sections of. There are no "don't > cares", there is only a set of finite impulse responses and everything > outside each finite impulse response is required to be weighted zero.what is the non-zero length of your FIR and what is N, the DFT size? and how many uncorrupted output samples do you expect to get for each frame? r b-j
