On Aug 7, 8:21 am, robert bristow-johnson <r...@audioimagination.com> wrote:> ... > remember: periodic in one domain implies discrete in the reciprocal > domain. and vise versa. no matter how you look at it, this is always > true. > > r b-jThat is not true. Periodic data in the continuous-infinite domain implies discrete in the reciprocal continuous-infinite domain. The DFT operates between finite-discrete domains. "Periodicity" is not a characteristic of the sample data in the finite-discrete domain but may be a characteristic, in the continuous-infinite domain, of the signal sampled. You can use this outside information to interpret the output of the DFT, but such interpretation comes from the outside information, not the samples given to the DFT or the DFT itself. It seems to be a curious intellectual conceit of some people who choose to apply the DFT to samples of periodic signals that others should not be allowed to use the DFT for applications where such outside knowledge is inappropriate and incorrect. Dale B. Dalrymple
DFT or DFS: Are they the same thing?
Started by ●August 7, 2009
Reply by ●August 7, 20092009-08-07
Reply by ●August 7, 20092009-08-07
On Aug 7, 2:34 pm, dbd <d...@ieee.org> wrote:> On Aug 7, 8:21 am, robert bristow-johnson <r...@audioimagination.com> > wrote: > > > ... > > remember: periodic in one domain implies discrete in the reciprocal > > domain. and vise versa. no matter how you look at it, this is always > > true. > > > r b-j > > That is not true. > > Periodic data in the continuous-infinite domain implies discrete in > the reciprocal continuous-infinite domain. > > The DFT operates between finite-discrete domains. "Periodicity" is not > a characteristic of the sample data in the finite-discrete domain but > may be a characteristic, in the continuous-infinite domain, of the > signal sampled. You can use this outside information to interpret the > output of the DFT, but such interpretation comes from the outside > information, not the samples given to the DFT or the DFT itself. > > It seems to be a curious intellectual conceit of some people who > choose to apply the DFT to samples of periodic signals that others > should not be allowed to use the DFT for applications where such > outside knowledge is inappropriate and incorrect.Dale, you can apply the DFT or iDFT to whatever N samples of data you want. the data you send to it is exactly the same as the date that the OP, commengr, sends to his DFS or iDFS. funny thing is, except for the scaling coefficient in the front (1 or sqrt(1/N) or 1/N), what the two of you are doing is exactly the same. the thing that you two are doing that is exactly the same doesn't have information that your N samples were yanked outa some aperiodic infinite sequence and that commengr's N samples are the representative set fully describing his infinite periodic sequence. but in either case, any operation that you do that has the effect of shifting or convolving your data, the identical thing that you two are doing will shift or convolve the data as if it were periodic with period N. if you do not define your set of N samples, x[n], beyond the indices of 0 and N-1, the shift or convolution operation will use x[n_mod_N]. for commengr that modulo operation is unnecessary because for him/her, x[n+N]=x[n] for all n. the n mod N operation explicitly periodically extends your data. commengr saying that x[n+N]=x[n] merely accepts the fact implicitly from the common definition of the DFT and DFS (and inverses): N-1 x[n] = (1/N) SUM{ X[k] e^(+j*2*pi*n*k/N) } k=0 N-1 X[k] = SUM{ x[n] e^(-j*2*pi*n*k/N) } n=0 r b-j
Reply by ●August 7, 20092009-08-07
On Aug 7, 2:56�am, Rune Allnor <all...@tele.ntnu.no> wrote:> > Most newbies don't understand that there are several variants > of the Fourier transform around.or are these several variants of the Fourier Transform merely degenerate or special cases of one unified Fourier Transform definition. we can have different scaling conventions (or +j vs. -j), but setting those aside, the DFS or DFT or DTFT can all be derived from the same continuous-time Fourier transform. my favorite convention is: x(t) = integral{ X(f) e^(+j*2*pi*f*t) df} X(f) = integral{ x(t) e^(-j*2*pi*f*t) dt} but you might be attaching your discrete data to dirac impulses to make the connection.> The different variants take > either discrete or continuous data as input, and the data are > of either finite or infinite extent.the simple rule to remember: discrete time means periodic in frequency. and vise versa (because of duality in the FT). DFT (or DFS): discrete periodic t; discrete periodic f DTFT: discrete aperiodic t; continuous periodic f Fourier series: continuous periodic t; discrete aperiodic f continuous FT: continuous aperiodic t; continuous aperiodic f did i miss a combination? it all comes under the continuous FT if you make use of dirac impulses. r b-j
Reply by ●August 7, 20092009-08-07
On Aug 7, 1:35 pm, robert bristow-johnson <r...@audioimagination.com> wrote: ...> > Dale, you can apply the DFT or iDFT to whatever N samples of data you > want. > ... > if you do not define your set > of N samples, x[n], beyond the indices of 0 and N-1, the shift or > convolution operation will use x[n_mod_N].When I use a DFT to implement a filter bank on a long (>>N)) array of sampled data, I calculate with the same complex exponential for each filter each time I calculate the filter bank outputs. There is no modulo addressing of the coefficients, they are indexed 0 to N-1 in each filter each time I implement the filter bank. My data -is- indexed larger than N. When I want the filterbank output at time M, I use input data indexes M to M+N-1 without modulo addressing. There is no periodic extension, but this is still the DFT algorithm.> ... from the common definition of the DFT and DFS (and > inverses): > > N-1 > x[n] = (1/N) SUM{ X[k] e^(+j*2*pi*n*k/N) } > k=0 > > N-1 > X[k] = SUM{ x[n] e^(-j*2*pi*n*k/N) } > n=0 > > r b-jThere is no modulo addressing in these definitions. There are applications where outside knowledge justifies interpretation of the data or coefficients as modulo indexed. There are also applications where there is no modulo addressed interpretation of the DFT operations. The difference is not in the DFT, but in the application wrapped around the DFT. Hopefully the OP will learn to identify when his applications are one or the other. Dale B. Dalrymple
Reply by ●August 7, 20092009-08-07
robert bristow-johnson <rbj@audioimagination.com> wrote: <> That is not true. <> Periodic data in the continuous-infinite domain implies discrete in <> the reciprocal continuous-infinite domain. Yes, that agrees with what he said. The transform pairs: periodic <--> discrete nonperiodic <--> continuous and the combination periodic discrete <--> periodic discrete (snip) <> It seems to be a curious intellectual conceit of some people who <> choose to apply the DFT to samples of periodic signals that others <> should not be allowed to use the DFT for applications where such <> outside knowledge is inappropriate and incorrect. You can use it that way, but should realize that the periodicity might affect the results. < Dale, you can apply the DFT or iDFT to whatever N samples of data you < want. the data you send to it is exactly the same as the date that < the OP, commengr, sends to his DFS or iDFS. funny thing is, except < for the scaling coefficient in the front (1 or sqrt(1/N) or 1/N), what < the two of you are doing is exactly the same. the thing that you two < are doing that is exactly the same doesn't have information that your < N samples were yanked outa some aperiodic infinite sequence and that < commengr's N samples are the representative set fully describing his < infinite periodic sequence. but in either case, any operation that < you do that has the effect of shifting or convolving your data, the < identical thing that you two are doing will shift or convolve the data < as if it were periodic with period N. if you do not define your set < of N samples, x[n], beyond the indices of 0 and N-1, the shift or < convolution operation will use x[n_mod_N]. If you do define them differently, but don't include them in the transform, you will also get that result. Since it hasn't been mentioned yet, I will add that DCT and DST have different boundary conditions. DST has zeros at the boundary (not necessarily at a sample point), and DCT the derivative is zero at the boundary (again, not necessarily at a sample point). The resulting functions necessarily have a 2N period, but not for quite the same reason as the DFT. -- glen
Reply by ●August 7, 20092009-08-07
On Aug 7, 5:51�pm, dbd <d...@ieee.org> wrote:> On Aug 7, 1:35 pm, robert bristow-johnson <r...@audioimagination.com> > wrote: > ... > > > > > Dale, you can apply the DFT or iDFT to whatever N samples of data you > > want. > > ... > > �if you do not define your set > > of N samples, x[n], beyond the indices of 0 and N-1, the shift or > > convolution operation will use x[n_mod_N]. > > When I use a DFT to implement a filter bank on a long (>>N)) array of > sampled data, I calculate with the same complex exponential for each > filter each time I calculate the filter bank outputs. There is no > modulo addressing of the coefficients, they are indexed 0 to N-1 in > each filter each time I implement the filter bank. My data -is- > indexed larger than N. When I want the filterbank output at time M, I > use input data indexes M to M+N-1 without modulo addressing. There is > no periodic extension, but this is still the DFT algorithm. >what, exactly, is the shift or convolution operation (or their multiplicative counterparts in the frequency domain) are you doing? so far what you said you were doing didn't explicitly have shifting or convolving in it. now, if you're doing "perfect reconstruction" with your filter bank, and you have these complementary window functions that you multiply your frequency-domain data with, in that multiplication you *are* working with periodically extended (or modulo indexed) data (it is *not* zero extended), but in perfect reconstruction the periodically extended terms (in the iDFT of the separated banks) get opposite signs and kill each other off.> > ... from the common definition of the DFT and DFS (and > > inverses): > > > � � � � � � � � �N-1 > > � � x[n] = (1/N) SUM{ X[k] e^(+j*2*pi*n*k/N) } > > � � � � � � � � �k=0 > > > � � � � � � � � �N-1 > > � � X[k] = � � � SUM{ x[n] e^(-j*2*pi*n*k/N) } > > � � � � � � � � �n=0 > > > r b-j > > There is no modulo addressing in these definitions.i guess not, but x[n] and X[k] on the left side are explicitly periodic with period N.> There are > applications where outside knowledge justifies interpretation of the > data or coefficients as modulo indexed.this outside knowledge does not get into the equations above. when you multiply X[k] times H[k] (that have iDFTs of x[n] and h[n]) to get Y[k], the result is N-1 y[n] = SUM{ h[i] x[n-i] } i=0 or N-1 y[n] = SUM{ x[i] h[n-i] } i=0 where Y[k] = iDFT{y[n]} the above only works if x[n+N]=x[n] or h[n+N]=h[n] or you must explicitly say N-1 y[n] = SUM{ h[i] x[(n-i)mod_N] } i=0 or N-1 y[n] = SUM{ x[i] h[(n-i)mod_N] } i=0> There are also applications > where there is no modulo addressed interpretation of the DFT > operations.the mathematics doesn't give a rat's ass about our interpretations. if you multiply in one domain, periodic extension in the other domain is necessary. whether you do it with modulo operations or not. whether these time-aliased terms are cancelled in your perfect- reconstruction filter bank or not.> The difference is not in the DFT, but in the application > wrapped around the DFT.*any* application has the *potential* of periodic extension. it happens, whether you interpret it so or not, when there is multiplication by some function in the other domain. there may be applications where the time-aliased terms kill each other off, but that doesn't mean that this periodic extension is not inherent to the transformation.> Hopefully the OP will learn to identify when > his applications are one or the other.but how do you do that when the math for either DFT or DFS is the same and the latter explicitly refers to the periodic extension? what the OP (and all of us) need to do is identify when the periodic extension, that always occurs, makes a difference in the end result or not. r b-j
Reply by ●August 7, 20092009-08-07
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. -- glen
Reply by ●August 7, 20092009-08-07
dbd <dbd@ieee.org> wrote: < On Aug 7, 1:35 pm, robert bristow-johnson wrote: <> Dale, you can apply the DFT or iDFT to whatever N samples of data you <> want. (snip) < When I use a DFT to implement a filter bank on a long (>>N)) array of < sampled data, I calculate with the same complex exponential for each < filter each time I calculate the filter bank outputs. There is no < modulo addressing of the coefficients, they are indexed 0 to N-1 in < each filter each time I implement the filter bank. My data -is- < indexed larger than N. When I want the filterbank output at time M, I < use input data indexes M to M+N-1 without modulo addressing. There is < no periodic extension, but this is still the DFT algorithm. For M sufficiently large, yes, you can ignore the periodicity. (Especially for signals with noise.) In each case, you have to decide what is 'large enough.' -- glen
Reply by ●August 7, 20092009-08-07
On 8/7/2009 3:27 PM, glen herrmannsfeldt 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. > > -- glenWhy does this all sound vaguely familiar? ;) -- Eric Jacobsen Minister of Algorithms Abineau Communications http://www.abineau.com
Reply by ●August 7, 20092009-08-07
On Aug 7, 6:38�pm, Eric Jacobsen <eric.jacob...@ieee.org> wrote:> On 8/7/2009 3:27 PM, glen herrmannsfeldt 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.i agree with this judgment. i have the same. but i don't think it means that they are different species of animal (like the Hilbert Transform is different than the Fourier Transform). the DFT, DTFT, or FS are all degenerate cases of the good ol' continuous Fourier Transform. but to connect them, you might need to make use of dirac impulses.> > Also, some people don't like delta functions.well, then, f^ck 'em. if they don't worry about the delta functions, the delta functions will come and kill them in their sleep.> > Why does this all sound vaguely familiar? � ;) >i have no idea. (-:
