On Aug 9, 9:14 am, robert bristow-johnson <r...@audioimagination.com> wrote:> On Aug 9, 10:52 am, dbd <d...@ieee.org> wrote: > ... > > 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-jN is the DFT size. N-1 X[n] = (1/N) SUM{ x[k] e^(-j*2*pi*n*k/N) } k=0 The complex exponentials are the FIR filter coefficients. The DFT formula, for each n, is a linear time domain convolution. I get one sample, X[n], for the n-th filter of the N filters in the filter bank, X, for each time I call the N point DFT. When the complex exponential FIR filter coefficients embedded in the DFT definition are suitable for my FIR applications, I can achieve better computational efficiency by calculating my FIR filter bank by calling the FFT. Fortunately, many applications find the complex exponential FIR coefficients useful enough to benefit from this computational advantage. 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
On Aug 9, 3:00�pm, dbd <d...@ieee.org> wrote:> On Aug 9, 9:14 am, robert bristow-johnson <r...@audioimagination.com> > wrote: > > > On Aug 9, 10:52 am, dbd <d...@ieee.org> wrote: > > ... > > > 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 > > N is the DFT size. > > � � � � � � � � �N-1 > � � X[n] = (1/N) SUM{ x[k] e^(-j*2*pi*n*k/N) } > � � � � � � � � �k=0 >(suggestion: view with a mono-spaced font before posting. i'm not to keen about the use of n and k variables to communicate a process. "n" is the output of the nth filter in the filter bank, but what is the time variable? if it's "k", then what is the dummy index variable used in the convolution summation?)> The complex exponentials are the FIR filter coefficients. The DFT > formula, for each n, is a linear time domain convolution. I get one > sample, X[n], for the n-th filter of the N filters in the filter bank, > X, for each time I call the N point DFT.now, since your language is that of simultaneous FIR filters, let's try to get your mathematics to reflect that language. as best as i can understand from what you are saying, you are simultaneously running N FIR filters all of FIR length L equal to N. for the nth FIR the impulse response is { e^(j*2*pi*n*k/N) for 0 <= k < N h_n[k] = { { 0 otherwise the output of the nth filter bank (advanced by N-1 samples, so this is not causal but i'm not worried about that) is L-1 y_n[k] = SUM{ x[i] h[k-i] } i=0 the FIR length L is the same as the DFT length N, right? then is k incremented by N for each frame? is that what you're doing? if k starts at zero, then k is always an integer multiple of N, right? is this y_n[] the same as your X[n]? i'm trying to keep this in filter bank semantics.> When the complex exponential FIR filter coefficients embedded in the > DFT definition are suitable for my FIR applications, I can achieve > better computational efficiency by calculating my FIR filter bank by > calling the FFT. Fortunately, many applications find the complex > exponential FIR coefficients useful enough to benefit from this > computational advantage.now, are you doing anything with these filter bank outputs? are you modifying them and reconstructing x[k] or something corresponding to x [k]? if you are not going to modify your "X[n]" (what i've been calling y_n[]), you can perfectly reconstruct x[k], but you'll find you'll have issues regarding the periodicity or circularity if you try to modify "X[n]" because that modification of X[n] is essentially multiplication in the frequency domain and that will correspond to circular convolution in the "k" domain. Dale, i'm gonna make you get more specific (and legit) with your math notation. it's the only way to settle this. r b-j
Reply by ●August 9, 20092009-08-09
On Aug 9, 3:46�pm, robert bristow-johnson <r...@audioimagination.com> wrote:> > � � � � � � �L-1 > � � y_n[k] = SUM{ x[i] h[k-i] } > � � � � � � �i=0 >whoops, i forgot to subscript the impulse response. should be: L-1 y_n[k] = SUM{ x[i] h_n[k-i] } i=0 this summation might look a little better if i switch around x[] and h []: L-1 y_n[k] = SUM{ h_n[i] x[k-i] } i=0 r b-j
Reply by ●August 9, 20092009-08-09
On Aug 9, 12:46 pm, robert bristow-johnson <r...@audioimagination.com> wrote:> On Aug 9, 3:00 pm, dbd <d...@ieee.org> wrote: > > > > > On Aug 9, 9:14 am, robert bristow-johnson <r...@audioimagination.com> > > wrote: > > > > On Aug 9, 10:52 am, dbd <d...@ieee.org> wrote: > > > ... > > > > 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 >.> > N is the DFT size. .> .> > N-1 .> > X[n] = (1/N) SUM{ x[k] e^(-j*2*pi*n*k/N) } .> > k=0 X[0:N-1] = DFT{x[0:N-1],N} is the DFT call that performs the FIR filter and demodulate operations. x is the vector of N contiguous time samples. e^(...) are the complex FIR coefficients generated within the DFT routine. X is the vector returned by the DFT. In the FIR application, X is a vector of sample outputs for each filter in the bank. There are N filters in the bank. These are time domain outputs for each filter in the bank at the time corresponding to the input sample set x. Each call to the DFT routine calculates a set of N simultaneous single sample outputs for the N filters in the bank from a set of N contiguous time domain samples from a single channel. I cut and pasted it from one of your posts.> ...As I said: .> .> > The complex exponentials are the FIR filter coefficients. The DFT .> > formula, for each n, is a linear time domain convolution. I get one .> > sample, X[n], for the n-th filter of the N filters in the filter bank, .> > X, for each time I call the N point DFT.> > now, since your language is that of simultaneous FIR filtersThe language is your language for transforms. We are talking about interpreting the DFT call as a set of simultaneous time samples on seperate channels instead of frequency samples from a single time on a single signal channel. There is no reason to change the equations. The calculations haven't changed.> ... > as best as i can understand from what you are saying, you are > simultaneously running N FIR filters all of FIR length L equal to N. > for the nth FIR the impulse response is > > { e^(j*2*pi*n*k/N) for 0 <= k < N > h_n[k] = { > { 0 otherwiseThe DFT call accepts no 'otherwise'. .> .> the output of the nth filter bank (advanced by N-1 samples, so this is .> not causal but i'm not worried about that) is 'advanced by N-1 samples' and 'causal' are irrelevant smokescreens. They have no relation to the equations defining the DFT call operations.> ... > > ... > > now, are you doing anything with these filter bank outputs?Take a look at the: "The DFT as a bank of matched filters" "The DFT as a bank of narrowband filters" and the "The DFT as an I-Q Demodulator" sections of: F. J. Harris, "The discrete fourier transform applied to time domain signal processing," IEEE Communications Magazine, vol. 20, pp. 13 - 22, May 1982. for more examples of applications of the filterbank interpretations of the DFT. Dale B. Dalrymple
Reply by ●August 10, 20092009-08-10
On Aug 9, 9:34�pm, dbd <d...@ieee.org> wrote:> On Aug 9, 12:46 pm, robert bristow-johnson <r...@audioimagination.com> > wrote: > .> > N is the DFT size. > .> > .> > � � � � � � � � �N-1 > .> > � � X[n] = (1/N) SUM{ x[k] e^(-j*2*pi*n*k/N) } > .> > � � � � � � � � �k=0 > > X[0:N-1] = DFT{x[0:N-1],N} is the DFT call that performs the FIR > filter and demodulate operations. > > x is the vector of N contiguous time samples. > > e^(...) are the complex FIR coefficients generated within the DFT > routine. > > X is the vector returned by the DFT. In the FIR application, X is a > vector of �sample outputs for each filter in the bank.at what times? every Nth sample?> There are N filters in the bank.patronizing now (and contradicting below) sheds little light.> These are time domain outputs for each filter in > the bank at the time corresponding to the input sample set x.might we call that input sample set a "frame" for semantic purposes to keep consistent with the literature?> Each call to the DFT routine calculates a set of N simultaneous single > sample outputs for the N filters in the bank from a set of N > contiguous time domain samples from a single channel.then, the expression i have below (with the "otherwise" in it) is *precisely* the correct language. your N filters are all FIR filters and they have finite length and that must be expressed in the definition of the impulse response, h_n[k]. "irrelevant smokescreen"?> > As I said: > .> > .> > The complex exponentials are the FIR filter coefficients. The DFT > .> > formula, for each n, is a linear time domain convolution. I get one > .> > sample, X[n], for the n-th filter of the N filters in the filter bank, > .> > X, for each time I call the N point DFT. > > > > > now, since your language is that of simultaneous FIR filters > > The language is your language for transforms.*you* were putting it into the language of filter banks (as if that somehow negated or changed the facts we know from simple theorems of the DFT). i was trying to run with that, but i had to nail it down a little more formally, otherwize the truth of the matter gets to slip out. if we ditch the language of filter banks, your point is already defeated. any operation that involves point-by-point multiplication in one domain (say the frequency domain) *must* correspond to *circular* convolution in the other domain. even with the filter bank semantic, your point (that there are times that the DFT does not periodically extend the data input to it) is defeated anyway, but to prove that to you, we have to disassemble (or maybe the word is "deconstruct") it a bit. i'm happy to ditch the filter bank language, if you want.> We are talking about > interpreting the DFT call as a set of simultaneous time samples on > seperate channels instead of frequency samples from a single time on a > single signal channel. There is no reason to change the equations. The > calculations haven't changed. > > > ... > > as best as i can understand from what you are saying, you are > > simultaneously running N FIR filters all of FIR length L equal to N. > > for the nth FIR the impulse response is > > > � � � � � � �{ e^(j*2*pi*n*k/N) � � �for � 0 <= k < N > > � � h_n[k] = { > > � � � � � � �{ 0 � � � � � � � � � � otherwise > > The DFT call accepts no 'otherwise'.but, using *your* language of filter banks, i had to formally define what each filter in the filter bank is doing. they are FIR filters, no? the "F" means "finite", no? that's what the "otherwise" is about.> .> > .> the output of the nth filter bank (advanced by N-1 samples, so this > is > .> not causal but i'm not worried about that) is > > 'advanced by N-1 samples' and 'causal' are irrelevant smokescreens.talk about "smokescreens". if you want to put this into the context of filter banks, let's put it into the formal language of filter banks.> They have no relation to the equations defining the DFT call > operations.you are calling the DFT repeatedly with buffers of data that are advanced and "refilled" in time. the language i like the best is one that uses the terms "frame", "framelength", "hop length" (or maybe "hop displacement"). i am not sure, but i suspect that your framelength, hop length, and DFT length are all the same length, N, but it wouldn't have to be. if that is the case, you are advancing your frame by N samples each time, the filters in your filter bank have the finite impulse response as indicated above (with the "otherwise" in it). and the problem with our indexing is that x[0] is really N-1 samples in the past while x[N-1] is the sample most recently input. if we were saying that x[0] is the current sample, then x[N-1] would be N-1 samples into the future. that's where all of this "irrelevant smokescreen" language comes from. but, if we're gonna return to the traditional language of transforms, then you lose the argument right away because we know that the theorems that involve shifting in one domain (and multiplication in the other) in the DFT *always*, without exception, do circular shifting which comes only from the inherent periodic extension that the DFT does. this is why i asked:> > now, are you doing anything with these filter bank outputs? >because if you are representing the output bins of your DFT as filter bank outputs, *if* you multiply those bins by some H[n] (i would prefer to say "H[k]" to be consistent with convention, but i certainly don't want to throw up another irrelevant smokescreen) and if that H [n] is not constant with n, then the h[k] that is the iDFT of that H [n] is not the kronecker delta, but has at least two taps that are non- zero. if H[n] *was* constant, then scaling X[n] by that constant will not introduce any circular shifting in the convolution with h[k] (a discrete kronecker delta function). you can retransform back to x[k] and not worry about the time-aliasing effects of circular convolution that naturally happens with the DFT. i dunno what you're doing with your filter bank, maybe you're just disassembling x[k] into X[n], encoding and transmitting it somewhere, and the reversing the process to get x[k] back again. but if H[n] is *not* constant with n, and you are multiplying your X [n] by H[n] for some reason (or if your X[n] bins get modified in some way that is not equivalent to being scaled by a constant), and you iDFT back to x[k], then, whether you call it a "filter bank" or whatever, you *will* *necessarily* experience effects of the periodic extension that the DFT inherently does. there is no avoiding that.> Take a look at the: > "The DFT as a bank of matched filters" > "The DFT as a bank of narrowband filters" > and the > "The DFT as an I-Q Demodulator" > sections of: > > F. J. Harris, "The discrete fourier transform applied to time domain > signal processing," IEEE Communications Magazine, vol. 20, pp. 13 - > 22, May 1982. > > for more examples of applications of the filterbank interpretations of > the DFT.i don't have that. someone who is IEEE is welcome to email me a pdf of it if they have it. i do have Stang and Nguyen, "Wavelets and Filter Bank" (1996) which i got at a seminar taught by them which i attended along with Randy Yates. if you have that book, i'd be happy to try to find common semantics there so that we can be referring to the same stuff rather than talking past each other. r b-j
Reply by ●August 16, 20092009-08-16
On Fri, 7 Aug 2009 22:27:07 +0000 (UTC), glen herrmannsfeldt <gah@ugcs.caltech.edu> wrote:>robert bristow-johnson <rbj@audioimagination.com> wrote: > >< or are these several variants of the Fourier Transform merely >< degenerate or special cases of one unified Fourier Transform >< definition. > >I think there is some advantage to the discrete transforms >over continuous integrals of delta functions. It is easier >to think about, which is often reason enough. > >Also, some people don't like delta functions. > >-- glenHi glen, I don't like delta functions. They're difficult to think about. If you can show me where in the Bible, or in a Harley Dividson Owner's Manual, that it says I should worry about delta functions then I'll start worryin' about delta functions. See Ya', [-Rick-]
Reply by ●August 17, 20092009-08-17
On Aug 16, 8:27�pm, Rick Lyons <R.Lyons@_BOGUS_ieee.org> wrote:> On Fri, 7 Aug 2009 22:27:07 +0000 (UTC), glen herrmannsfeldt > > <g...@ugcs.caltech.edu> wrote: > >robert bristow-johnson <r...@audioimagination.com> wrote: > > >< or are these several variants of the Fourier Transform merely > >< degenerate or special cases of one unified Fourier Transform > >< definition. � > > >I think there is some advantage to the discrete transforms > >over continuous integrals of delta functions. �It is easier > >to think about, which is often reason enough. > > >Also, some people don't like delta functions. > > >-- glen > > Hi glen, > � �I don't like delta functions. �They're difficult > to think about. �If you can show me where in the > Bible, or in a Harley D[a]vidson Owner's Manual, that > it says I should worry about delta functions then > I'll start worryin' about delta functions.i still think when your in bed, they're gonna come and getcha in your sleep. imps and gnomes and gremlins ain't in the Harley Davidson Owner's Manual either. ya gotta worry about delta functions. otherwise them big nasty pointy things nail our sorry little tushies to the wall. maybe i'm just paranoid. r b-j
Reply by ●August 17, 20092009-08-17
"commengr" <communications_engineer@yahoo.com> writes:> 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. (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) > > 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. > > Further, if I take a periodic sequence, feed it to a DFT algorithm like > FFT, I would get the correct results? > > I can't seem to find a good book to clear this confusion (I have not made > an exhaustive search) but one that comes close is the book on DSP by Li TanOne difference is that the DFT requires a bandlimited signal; the DFS does not. This may not matter much in practice, but analytically it can matter a whole lot. -- Randy Yates % "Rollin' and riding and slippin' and Digital Signal Labs % sliding, it's magic." mailto://yates@ieee.org % http://www.digitalsignallabs.com % 'Living' Thing', *A New World Record*, ELO
Reply by ●August 17, 20092009-08-17
Randy Yates <yates@ieee.org> writes:> [...] > One difference is that the DFT requires a bandlimited signal; the DFS > does not. > > This may not matter much in practice, but analytically it can matter a > whole lot.Wups. Sorry. DFS != Continuous Fourier Series. Mea Culpa. -- Randy Yates % "How's life on earth? Digital Signal Labs % ... What is it worth?" mailto://yates@ieee.org % 'Mission (A World Record)', http://www.digitalsignallabs.com % *A New World Record*, ELO
Reply by ●August 17, 20092009-08-17
"glen herrmannsfeldt" <gah@ugcs.caltech.edu> wrote in message news:h5i9nr$c7r$3@naig.caltech.edu...> robert bristow-johnson <rbj@audioimagination.com> wrote: > < or are these several variants of the Fourier Transform merely > < degenerate or special cases of one unified Fourier Transform > < definition. > I think there is some advantage to the discrete transforms > over continuous integrals of delta functions. It is easier > to think about, which is often reason enough. > Also, some people don't like delta functions.The proto-Bible (or proto-Koran, etc, depending upon into which version of make-believe you were brain-washed when young) of DSP, Oppenheim & Schafer, 1975, discusses sampling and reconstruction without appeal to delta functions, and by initiating discussion in the digital world by use of the very-logical Unit Sample avoids the need to bring them in. Some other texts introduce the sampling process by some or other combining process between delta functions and the input signal, but present it with the condescension of, "Don't worry too much about the mathematics", probably because the author of the text didn't trouble her or himself too muchly either. (Perhaps the same semi-ignorance that refers to, "Twiddle Factors" when evaluating the FFT?). Unfortunately, if someone then comes along who is well-versed in the use of delta functions in the analogue world of Fourier, Laplace, Butterworth, Tchebyshev and Ellipticality, then the trite presentation of delta functions (intended for the mathematically juvenile) causes a great deal of angst because the claims made simply, "Do not compute". The archives of this and other news groups throw up many flame wars on such subjects. It is unfortunate IMHO that a throw-away remark targetted at the mathematically juvenile should have been seized upon and promulgated by later authors when a simpler and more rigorous presentation has been available from the very early days via O&S.
