Re: The inherent periodicity of the Discrete Fourier Transform

robert bristow-johnson <rbj@audioimagination.com> wrote:
(snip)

> i am still curious to how you're not able to see it, especially after
> looking at the pdf file i sent without use of "ASCII math".  you don't
> have ASCII math to kick around anymore, Eric.  substitute "n-m" into
> the argument of x[.] as shown in (A), (B), and (C).  set m to 1 and
> formally evaluate what y[0] is in all three cases.  i can't make it
> any more clear.

I see no-one followed up on my attempt to get away from the DFT, and
toward sampling theory.  The same math that covers the periodicity
of the DFT also comes out in sampling with a finite number of
samples.

It is often noted how, with Nyquist sampling of an appropriately
band-limited signal, one can exactly recreate that signal from
the samples.  (In theory, and assuming no quantization.)  That is,
however, only true for an infinite number of samples.

It isn't hard to see that the reconstruction can vary.  Consider
the two cases of padding a finite set if samples with zeros,
or with a periodic extension.  For those two cases, one can show
the exact reconstruction, and show that they are different.
Not so different away from the ends, but different.

Now, in digital logic minimization there are commonly "don't care"
states, where one chooses the minimal logic generating the
desired outputs, over the set of possible different values for
the unimportant "don't cares."  In the case of finite interval
sampling, the sample points outside the interval are "don't care"
values, and, it isn't hard to see, that a periodic signal with
period equal to the interval is optimal.  That which some are
calling "periodic extension."  

-- glen

On Feb 7, 4:31&#4294967295;pm, dbd <d...@ieee.org> wrote:
> On Feb 6, 2:55 pm, robert bristow-johnson <r...@audioimagination.com>
> wrote:
>
> > On Feb 6, 2:33 pm, dbd <d...@ieee.org> wrote:
>
> [ Four paragraphs complaining about O&S notational choices deleted.]
>

what i'm complaining about in O&S is what they do starting with Eq.
(8.55).  it's no derivation, they just define the DFT X[k] to be a
windowed copy of the DFS ~X[k].  but there is no reason to bother
doing that, except to provide the likes of you a windowed definition
of the DFT which has NO MEANING that exists outside the DFS.  as i've
pointed out in the earlier post today, those zeros (for indices
outside of 0 <= n,k < N) could just as well have values equal to my
ass, because those numbers will never get into any calculation
regarding any theorem or use of the DFT at all.  they serve no
mathematical purpose.

> > > The coefficients of the DFT do not correspond to values of the DFS.
>
> > wrongo, Dale. &#4294967295;epic fail.
>
> The definition of the DFT is that if you give it N samples from a
> sequence periodically extended from the N samples it will return N
> samples from one period of the DFS of the periodically extended
> sequence.

and the X[k] for the DFS are exactly the same as the X[k] for the DFT
(for 0 <= k < N) given the same x[n].  same for the iDFT.  we'll get
back to this.

> If the N samples input to the DFT do not come from a sequence
> periodically extended from the N samples,

the DFT has no way of know whether or not the N samples "come from a
sequence periodically extended from the N samples".  it doesn't know
and it doesn't care and merrily crunches the numbers the same anyway.
we'll get back to this.


> the DFT does not calculate
> the DFS of the sequence the inputs were taken from.

yes it does.  explicitly.  this is explicitly what O&S do in section
8.6 (pp. 530-532).

> (It still
> calculates the one period of the DFS of the periodically extended
> sequence instead, but that's not the sequence being processed.)

yes it is.  explicitly.  as long as the DFT X[k] is the same as the
DFS ~X[k] (and same for x[n] and ~x[n]) for 0 <= n < N, (which they
are), there is no difference in anything that the DFT does and what
the DFS does regarding the corresponding theorems.  they crunch
exactly the same numbers.  it's just that the DFS theorem will call it
"x[n]" or "X[k]" (if i remove the squiggles) and the DFT theorem will
call it x[(n)mod_N] and X[(k)mod_N].  they're precisely the same
thing, but the modulo notation might be a little klunky to do
additional math with.

> If the
> analyst wants to validate the interpretation of the DFT coefficients
> as the DFS of the sequence under analysis, the analyst must
> demonstrate that the sequence under analysis is equal to the sequence
> periodically extended from the N samples. The DFT has nothing the do
> with this. It requires analysis of additional samples from the
> sequence being processed. But you say you have looked at this before:
>
>
> > this was the illustration Eric made 16 years ago right here. &#4294967295;so you
> > got this sinusoid that makes exactly 10.5 cycles in the time it takes
> > for the N samples going to the DFT. &#4294967295;so you say: "oooh, oooh! look at
> > my spectrum analyzer! that spectrum displayed is the spectrum of a
> > simple sine wave with lots of windowing effects. &#4294967295;therefore the DFT
> > did this windowing and the DFT output, with all them non-zero values
> > of X[k], is different than the simple coefficients for the single
> > sinusoid (where you might expect that just two coefficients are non-
> > zero).
>
> > but what is displayed there is undifferentiable from if you had a
> > periodic function with period N, and this periodic function does 10
> > sinusoidal cycles and one more half cycle, then does a polarity
> > reversal and does is all again for the next period. &#4294967295;given the display
> > of this spectrum analyzer, you don't know the difference, even if due
> > to our experience, we *guess* that the original stream of data is a
> > single sinusoid that got hacked at 10.5 cycles.
>
> > but strictly speaking, we really don't know the difference between the
> > two possibilities and neither does the DFT. &#4294967295;it just keeps
> > periodically extending the data passed to it anyway. &#4294967295;you can't turn
> > that off, just because your data is N samples yanked from a longer
> > stream and it was a single sinusoid before you windowed off all but N
> > samples.
>
> If you really did sell this argument to Eric years ago, he was far too
> kind to you.

well, i've been too kind too you, Dale.

first of all, it was Eric who brought up the illustration of the 10.5
cycle segment of signal that was an example that somehow
differentiated the DFT from the DFS, that this was proof that the DFT
itself was doing the windowing because the spectrum would looks so
radically different if it was exactly 10 cycles (then only X[10] and
X[N-10] would be nonzero) and when the frequency changed to 10.5
cycles (per N samples), then all of this effect of windowing would be
evident (all sorts of DFT bins would be nonzero), which he put forth
as proof that the DFT does the windowing.

then i brought up the case that the original signal *could* have been
that N-periodic signal with 10.5 cycles of sine wave, a polarity
reversal and repeating another 10.5 cycles of sine wave, etc.  when
pressed, he finally conceded that point.  looking at the *same*
output, where did the "effect of windowing" go?  is it there or isn't
it there?  Eric conceded the point.

there is no way for the DFT to know which of the two cases it might
be.  the only place where you can make that judgment (that these
spurious non-zero bins are from windowing) is at the point in the
signal chain where the windowing operation is done.  which is long
before (at least micro-seconds before) the DFT ever sees the data.

> The DFT calculates complex ooefficients. To compare the
> two sets of DFT coefficients, you must compare both magnitude and
> phase.

nothing you're saying here is of any consequence.  it's like a
tautology.  nothing of controversy and nothing of substance.  you make
take pride in that it's true, but it says nothing to the issue of
debate.

> The phase plots will be complementary instead of equal which
> invalidates of the interpretation of the DFT coefficients as N samples
> of the period of a DFS periodic in N. It shows that the sequence under
> analysis does not have a DFS periodic in N samples so that the DFT
> coefficients cannot be N samples of a period of the DFS of the signal
> under analysis. (The DFT coefficients are still samples of a period of
> a periodic DFS of a sequence periodic in N samples, we've just shown
> that this sequence used by O&S in the derivation of the DFT is not the
> sequence the analyst is processing.) And that's OK. The DFT
> coefficeints are still useful whether robert is interested or not.

there is nothing of substance here.  just vapid.

now, second of all, this time around, i wasn't bringing up O&S. the
facts and argument stand on their own ground and i don't need O&S, but
it's nice that they agree with me.  it was you who brought it up
saying

On Feb 1, 11:58 pm, dbd <d...@ieee.org> wrote:
> ...
> One of the improvements in this year's go-round on this topic from the
> August 2009 version is that robert no longer misrepresents the text
> books as agreeing with his interpretation of the DFT. Texts such as
> Digital Signal Processing-Oppenheim&Schafer1975, Discrete-Time Signal
> Processing-Oppenheim&Schafer1989 ...

so i requote O&S in their DFT chapter, first in the Introduction:

"We accomplish this by constructing a periodic sequence for which each
period is identical to the finite-length sequence.  As we sill 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."

And later, in section 8.6 immediately after after they *present* (it's
not derived) the form of the DFT you seem to prefer:

"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."

then you, Dale, responded with blabber.  you accuse me of "handwaving"
when i've been only doing math.  but it's you're dismissing of the
simple and plain reading of what O&S say here, both in the Intro:

"the Fourier series representation of the periodic sequence
corresponds to the DFT of the finite-length sequence. Then we repeat
essentially the same derivations [to those of the DFS] **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."

and just after they present the DFT form that you hold up (Sec 8.6):

"In recasting ... for the finite-duration sequences, we have not
eliminated the inherent periodicity ...The inherent periodicity is
always present."

yet you deny that O&S are saying what they plainly say: The DFT is
inherently periodic.  you claim you understand and interpreted what
O&S just said, yet you "den[y] that periodic extension is a property
of the DFT."  they say it's inherent, you say it's not a property.
*you* were the person to bring up O&S, not me (this year).  *you* deny
explicitly what they affirm explicitly and somehow you're saying O&S
take your position.  it's ludicrous.  it's like climate change deniers
or evolution deniers saying that the scientific community supports
their belief when it is clear with any plain-reading of what
scientists are saying is exactly the opposite.

that's why i think you're a Bushie-Rovie-Glenn_Beck Republican.  they
have the chutzpah to take damning evidence and analysis and claim it
supports them as if no one can read the reports themselves.

you're not fooling anyone, Dale.  except maybe yourself.

you're the handwaver, Dale.  i do mathematics.

But when you said that the DFS comes up with different coefficients
than the DFT (presuming the same input, x[n]), that's when you
*really* made a fool of yourself.

Neither you, nor Eric, nor anyone else, have shown how this definition
you like (which are Eqs. (8.59) and (8.60) in O&S):

          {    N-1
          {    SUM x[n] e^(-j*2*pi*n*k/N)    for  0 <= k < N
 X[k] =   {    n=0
          {
          {    0                             otherwise

and
          {     N-1
          { 1/N SUM X[k] e^(+j*2*pi*n*k/N)   for  0 <= n < N
 x[n] =   {     k=0
          {
          {    0                             otherwise


...how the "0" values (for "otherwise") for x[n] or X[k] enter into
any mathematics of any theorem regarding the DFT, much less have shown
how those zeros make any calculation more correct or more simple (or
elegant) in any mathematics of manipulating the DFT input or output
data.  Those zeros never go into any calculation at all (because in
the DFT theorems, there are always the modulo_N operators, even
implicitly for the trivial theorems that don't need the modulo_N
operators like superposition and scaling).  This expression cannot
make the calculations more correct because the zeros never enter into
anything regarding the DFT and the associated theorems.  That's why
they have no utility and the DFT definition you're so enamored of has
no utility over that of the simplified definition, Eqs. (8.61) and
(8.62) (which are identical to the DFS definition without the
squiggles).

Eric even tried to claim that the definition of x[n] with the windowed
basis didn't change something (to the detriment) in Answer (B) or
that, if it did, I wasn't "compliant to the usual definition of a
DFT":

On Feb 7, 5:48 pm, eric.jacobsen@ieee.org (Eric Jacobsen) wrote:
>
> I thought I understood what you meant with the ABC thing, then I
> didn't then I did and now I don't.
>
> In B the window either just puts a formal window around the basis
> functions, which doesn't change anything, and won't change the basis
> functions, and therefore won't change the result, OR it changes the
> basis functions and slides them with the data, which means it's no
> longer compliant to the usual definition of a DFT and therefore not a
> DFT by the usual definition...

Here is what I said for Answers (B) and (C):

             N-1
 X[k] =      SUM x[n]*e^(-j*2*pi*n*k/N) * (u[k]-u[k-N])
             n=0

             N-1
 x[n] =  1/N SUM X[k]*e^(+j*2*pi*n*k/N) * (u[n]-u[n-N])
             k=0

where u[n] is the discrete-time unit step function

        { 1    n >= 0
 u[n] = {
        { 0    n < 0

I'd still like to see Eric or you show that the basis function
definitions I had for Answers (B) and (C) are any different than "the
usual definition of a DFT" as you guys are defining the "usual
definition".  *You* say the usual definition is O&S Eqs. (8.59) and
(8.60) which I have restated above.  How are they different than the
basis function definition with rectangular windows (u[k]-u[k-N]) or
(u[n]-u[n-N])?

They are precisely your "usual definitions of the DFT", and I have
shown (quite trivially) that in (B) you get an error if you say simply
that

   y[n] = x[n-m]

and that in (C) you get it right but you must use the modulo_N
operator and say that

   y[n] = x[(n-m)mod_N] .


But Answer (A) both allows the simple expression y[n]=x[n-m] *and*
it's correct.

Neither of you (nor anyone else) have shown any utility there is in
having your zero-extended sequences for x[n] and X[k] (the zeros don't
legitimately go into any mathematics), nor any utility in being forced
to use modulo_N arithmetic in the indices for the useful theorems
associated with the DFT.

r b-j

On Tue, 8 Feb 2011 22:18:58 -0800 (PST), robert bristow-johnson
<rbj@audioimagination.com> wrote:

>On Feb 7, 4:31=A0pm, dbd <d...@ieee.org> wrote:
>> On Feb 6, 2:55 pm, robert bristow-johnson <r...@audioimagination.com>
>> wrote:
>>
>> > On Feb 6, 2:33 pm, dbd <d...@ieee.org> wrote:
>>
>> [ Four paragraphs complaining about O&S notational choices deleted.]
>>

>>
>> > but strictly speaking, we really don't know the difference between the
>> > two possibilities and neither does the DFT. =A0it just keeps
>> > periodically extending the data passed to it anyway. =A0you can't turn
>> > that off, just because your data is N samples yanked from a longer
>> > stream and it was a single sinusoid before you windowed off all but N
>> > samples.
>>
>> If you really did sell this argument to Eric years ago, he was far too
>> kind to you.
>
>well, i've been too kind too you, Dale.
>
>first of all, it was Eric who brought up the illustration of the 10.5
>cycle segment of signal that was an example that somehow
>differentiated the DFT from the DFS, that this was proof that the DFT
>itself was doing the windowing because the spectrum would looks so
>radically different if it was exactly 10 cycles (then only X[10] and
>X[N-10] would be nonzero) and when the frequency changed to 10.5
>cycles (per N samples), then all of this effect of windowing would be
>evident (all sorts of DFT bins would be nonzero), which he put forth
>as proof that the DFT does the windowing.
>
>then i brought up the case that the original signal *could* have been
>that N-periodic signal with 10.5 cycles of sine wave, a polarity
>reversal and repeating another 10.5 cycles of sine wave, etc.  when
>pressed, he finally conceded that point.  looking at the *same*
>output, where did the "effect of windowing" go?  is it there or isn't
>it there?  Eric conceded the point.
>
>there is no way for the DFT to know which of the two cases it might
>be.  the only place where you can make that judgment (that these
>spurious non-zero bins are from windowing) is at the point in the
>signal chain where the windowing operation is done.  which is long
>before (at least micro-seconds before) the DFT ever sees the data.

I think you misrepresent my position, and now it seems like you're
conceding that there is not a large distinction between the periodic
extension point of view and the windowed point of view.   Perhaps
you're coming around to the idea that the periodic point of view isn't
the only one that works?


Eric Jacobsen
http://www.ericjacobsen.org
http://www.dsprelated.com/blogs-1//Eric_Jacobsen.php

On Mon, 07 Feb 2011 21:20:50 -0600, jim <"sjedgingN0Sp"@m@mwt.net>
wrote:

>Eric Jacobsen wrote:
>> 
>> On Mon, 07 Feb 2011 13:03:25 -0600, jim <"sjedgingN0Sp"@m@mwt,net>
>> wrote:
>> 
>> >
>> >
>> >Eric Jacobsen wrote:
>> >
>> >
>> >>
>> >> Perhaps I'll stir the pot and say that, again, just looking at the
>> >> definition and operation of the DFT, as a linear algebra expression, I
>> >> think it's hard to justify an absolute position that periodic
>> >> extension is inherent.
>> >
>> >
>> >All you have to do is replace Pi with any integer
>> >to change the DFT to be aperiodic.
>> >If you don't use that number Pi it won't be periodic.
>> >Why do you use that particular number if you don't care
>> >if the DFT is not periodic?
>> 
>> I care that the DFT does the analysis I expect it to do, and that the
>> output has certain properties, like the bins are orthogonal, and
>> represent what I expect them to represent about the signal.   There
>> are a lot of other things that can be said about that, but if one
>> substitutes something else for the basis functions other than what's
>> in the usual DFT definition, IMHO it ceases to be a DFT and is
>> something else entirely.
>
>Except that it is not "something else entirely".
> It is the exact same thing except that the bins in the frequency domain
>are now spaced differently. 

Which is clearly different, no?   The results obtained from sliding
the basis functions will not be the same as those obtained from using
the usual definition of a DFT.

>You claim you want it to be not periodic 
>That's a way to make the DFT  not periodic.
>
>-jim 

I do not claim that I want the DFT to be not periodic, and have not
done so.  I claim only that it is not necessary to look at it that way
to have a broad understanding of what the DFT does and how it works.


Eric Jacobsen
http://www.ericjacobsen.org
http://www.dsprelated.com/blogs-1//Eric_Jacobsen.php

On Tue, 8 Feb 2011 22:52:36 +0000 (UTC), glen herrmannsfeldt
<gah@ugcs.caltech.edu> wrote:

>robert bristow-johnson <rbj@audioimagination.com> wrote:
>(snip)
>
>> i am still curious to how you're not able to see it, especially after
>> looking at the pdf file i sent without use of "ASCII math".  you don't
>> have ASCII math to kick around anymore, Eric.  substitute "n-m" into
>> the argument of x[.] as shown in (A), (B), and (C).  set m to 1 and
>> formally evaluate what y[0] is in all three cases.  i can't make it
>> any more clear.
>
>I see no-one followed up on my attempt to get away from the DFT, and
>toward sampling theory.  The same math that covers the periodicity
>of the DFT also comes out in sampling with a finite number of
>samples.

>It is often noted how, with Nyquist sampling of an appropriately
>band-limited signal, one can exactly recreate that signal from
>the samples.  (In theory, and assuming no quantization.)  That is,
>however, only true for an infinite number of samples.
>
>It isn't hard to see that the reconstruction can vary.  Consider
>the two cases of padding a finite set if samples with zeros,
>or with a periodic extension.  For those two cases, one can show
>the exact reconstruction, and show that they are different.
>Not so different away from the ends, but different.

>Now, in digital logic minimization there are commonly "don't care"
>states, where one chooses the minimal logic generating the
>desired outputs, over the set of possible different values for
>the unimportant "don't cares."  In the case of finite interval
>sampling, the sample points outside the interval are "don't care"
>values, and, it isn't hard to see, that a periodic signal with
>period equal to the interval is optimal.  That which some are
>calling "periodic extension."  
>
>-- glen

I'm actually a little surprised that more people haven't pointed this
out.  It's not really a DFT thing (which I've also been trying to
point out), I think it's more a general theory thing.   The periodic
extension point of view is very handy for both sampling theory and the
DFT (and even straightforward convolution and correlation), and ties
in nicely to the relevant theories in continuous time.  

It is, however, in my point of view, still just one tool in the
toolbox.   It is a very useful tool, but it's not the only one.


Eric Jacobsen
http://www.ericjacobsen.org
http://www.dsprelated.com/blogs-1//Eric_Jacobsen.php

On Mon, 7 Feb 2011 22:10:00 -0800 (PST), robert bristow-johnson
<rbj@audioimagination.com> wrote:

>
>much to comment on.  too much.  so i will select.
>
>On Feb 7, 5:48=A0pm, eric.jacob...@ieee.org (Eric Jacobsen) wrote:
>> On Mon, 7 Feb 2011 12:15:56 -0800 (PST), robert bristow-johnson
>> <rbj@audioimagination.com> wrote:
>> >On Feb 7, 1:28=3DA0pm, eric.jacobsen@ieee.org (Eric Jacobsen) wrote:
>>
>>
>> I thought I understood what you meant with the ABC thing, then I
>> didn't then I did and now I don't.
>>
>> In B the window either just puts a formal window around the basis
>> functions, which doesn't change anything, and won't change the basis
>> functions, and therefore won't change the result,
>
>the window *shifts* with the basis functions.  this is why, when m=3D1,
>that
>
>   (A)  y[0] =3D x[0-1] =3D x[N-1]
>
>   (B)  y[0] =3D (something)*(u[-1]-u[-1-N]) =3D 0
>
>   (C)  y[0] =3D x[(0-1)mod_N] =3D x[N-1]
>
>i am still curious to how you're not able to see it, especially after
>looking at the pdf file i sent without use of "ASCII math".  you don't
>have ASCII math to kick around anymore, Eric.  substitute "n-m" into
>the argument of x[.] as shown in (A), (B), and (C).  set m to 1 and
>formally evaluate what y[0] is in all three cases.  i can't make it
>any more clear.

And you just keep typing the same thing over and over again without
addressing questions I ask or points I make trying to clarify the
issue.   I don't think that is an effective process.

>> OR it changes the
>> basis functions and slides them with the data, which means it's no
>> longer compliant to the usual definition of a DFT and therefore not a
>> DFT by the usual definition and therefore, IMHO, out of the scope of
>> the discussion.

>
>tell me what is the difference between the two, then put the (u[n]-u[n-
>N]) inside the summation to multiply the (1/N)e^(+j*2*pi*n*k/N) and
>you have precisely the basis functions i put in the problem.  nothing
>fancy nor obscure nor obfuscated.  *very* straightforward and simple
>for a DSPer as good as you.

If you substitute n-m for n in the exponential it changes the basis
functions.  This is no longer a DFT, at least not as per the usual
definition, and will be expected to produce a different output than if
the usual definition were used.   I don't think discussing that case
is relevant.  

If you leave the basis functions alone and just put a formal window
around them, you haven't changed the DFT and will get the same result
one always gets.  

>well, the math doesn't care.  i'm commenting about a mindless
>mathematical operation that doesn't care how effectively i deal with
>people who do or do not share my POV.  the math just does what it does
>anyway.
>
>r b-j

Exactly.


Eric Jacobsen
http://www.ericjacobsen.org
http://www.dsprelated.com/blogs-1//Eric_Jacobsen.php

Eric Jacobsen wrote:
> 
> On Mon, 07 Feb 2011 21:20:50 -0600, jim <"sjedgingN0Sp"@m@mwt.net>
> wrote:
> 
> >Eric Jacobsen wrote:
> >>
> >> On Mon, 07 Feb 2011 13:03:25 -0600, jim <"sjedgingN0Sp"@m@mwt,net>
> >> wrote:
> >>
> >> >
> >> >
> >> >Eric Jacobsen wrote:
> >> >
> >> >
> >> >>
> >> >> Perhaps I'll stir the pot and say that, again, just looking at the
> >> >> definition and operation of the DFT, as a linear algebra expression, I
> >> >> think it's hard to justify an absolute position that periodic
> >> >> extension is inherent.
> >> >
> >> >
> >> >All you have to do is replace Pi with any integer
> >> >to change the DFT to be aperiodic.
> >> >If you don't use that number Pi it won't be periodic.
> >> >Why do you use that particular number if you don't care
> >> >if the DFT is not periodic?
> >>
> >> I care that the DFT does the analysis I expect it to do, and that the
> >> output has certain properties, like the bins are orthogonal, and
> >> represent what I expect them to represent about the signal.   There
> >> are a lot of other things that can be said about that, but if one
> >> substitutes something else for the basis functions other than what's
> >> in the usual DFT definition, IMHO it ceases to be a DFT and is
> >> something else entirely.
> >
> >Except that it is not "something else entirely".
> > It is the exact same thing except that the bins in the frequency domain
> >are now spaced differently.
> 
> Which is clearly different, no?   The results obtained from sliding
> the basis functions will not be the same as those obtained from using
> the usual definition of a DFT.

In what way is it different? When you substitute another number for Pi
you are still dealing with a harmonically related series of complex
exponentials.  The difference is the result will no longer be periodic
in N. 



> 
> >You claim you want it to be not periodic
> >That's a way to make the DFT  not periodic.
> >
> >-jim
> 
> I do not claim that I want the DFT to be not periodic, and have not
> done so.  I claim only that it is not necessary to look at it that way
> to have a broad understanding of what the DFT does and how it works.


What is clear is you refuse to accept it unless it be periodic in N. 

-jim


> 
> Eric Jacobsen
> http://www.ericjacobsen.org
> http://www.dsprelated.com/blogs-1//Eric_Jacobsen.php

okay, just for reference:

____________________________________________________________________

Let the DFT of x[n] be defined as:

             N-1
     X[k] =  SUM{ x[n] * e^(-j*2*pi*n*k/N) }
             n=0


Given x[n], with its DFT X[k], what is y[n], the inverse DFT of

     Y[k]  =  X[k] * e^(-j*2*pi*k*m/N)

where m is an integer?

Is it

(A)  y[n]  =  x[n-m]

where

            N-1
   x[n]  =  SUM{ X[k] * b_k[n] }
            k=0

and  b_k[n]  =  (1/N) * e^(j*2*pi*k*n/N)  ?

Or is it

(B)  y[n]  =  x[n-m]

where

            N-1
   x[n]  =  SUM{ X[k] * b_k[n] }
            k=0

and  b_k[n]  =  (1/N) * e^(j*2*pi*k*n/N) * (u[n]-u[n-N])

and where u[n]-u[n-N] is a rectangular window defined by the
unit step u[n] = 1 for n >= 0  and  0 otherwise ?

Or is it

(C)  y[n]  =  x[ (n-m)mod_N ]

where

            N-1
   x[n]  =  SUM{ X[k] * b_k[n] }
            k=0

and  b_k[n]  =  (1/N) * e^(j*2*pi*k*n/N) * (u[n]-u[n-N])

and where  (n)mod_N = n - N*floor(n/N)

and floor(v) is the largest integer not exceeding the real number v ?

Or is it

(D)  none of the above ?

____________________________________________________________________


On Feb 9, 12:10�pm, eric.jacob...@ieee.org (Eric Jacobsen) wrote:
> On Mon, 7 Feb 2011 22:10:00 -0800 (PST), robert bristow-johnson
>
>
>
> <r...@audioimagination.com> wrote:
>
> >much to comment on. &#4294967295;too much. &#4294967295;so i will select.
>
> >On Feb 7, 5:48=A0pm, eric.jacob...@ieee.org (Eric Jacobsen) wrote:
> >> On Mon, 7 Feb 2011 12:15:56 -0800 (PST), robert bristow-johnson
> >> <r...@audioimagination.com> wrote:
> >> >On Feb 7, 1:28=3DA0pm, eric.jacob...@ieee.org (Eric Jacobsen) wrote:
>
> >> I thought I understood what you meant with the ABC thing, then I
> >> didn't then I did and now I don't.
>
> >> In B the window either just puts a formal window around the basis
> >> functions, which doesn't change anything, and won't change the basis
> >> functions, and therefore won't change the result,
>
> >the window *shifts* with the basis functions. &#4294967295;this is why, when m=3D1,
> >that
>
> > &#4294967295; (A) &#4294967295;y[0] = x[0-1] = x[N-1]
>
> > &#4294967295; (B) &#4294967295;y[0] = (something)*(u[-1]-u[-1-N]) = 0
>
> > &#4294967295; (C) &#4294967295;y[0] = x[(0-1)mod_N] = x[N-1]
>
> >i am still curious to how you're not able to see it, especially after
> >looking at the pdf file i sent without use of "ASCII math". &#4294967295;you don't
> >have ASCII math to kick around anymore, Eric. &#4294967295;substitute "n-m" into
> >the argument of x[.] as shown in (A), (B), and (C). &#4294967295;set m to 1 and
> >formally evaluate what y[0] is in all three cases. &#4294967295;i can't make it
> >any more clear.
>
> And you just keep typing the same thing over and over again without
> addressing questions I ask or points I make trying to clarify the
> issue. &#4294967295; I don't think that is an effective process.
>
> >> OR it changes the
> >> basis functions and slides them with the data, which means it's no
> >> longer compliant to the usual definition of a DFT and therefore not a
> >> DFT by the usual definition and therefore, IMHO, out of the scope of
> >> the discussion.
>
> >tell me what is the difference between the two, then put the
> >(u[n]-u[n-N]) inside the summation to multiply the (1/N)e^(+j*2*pi*n*k/N)
> >and you have precisely the basis functions i put in the problem. &#4294967295;nothing
> >fancy nor obscure nor obfuscated. &#4294967295;*very* straightforward and simple
> >for a DSPer as good as you.
>
> If you substitute n-m for n in the exponential it changes the basis
> functions.

no, it doesn't.  it does not change the basis function.  the basis
function defined in terms of its argument (the dummy variable "n")
remains the same.  it evaluates it (the *whole* basis function,
exponential and window) for the argument "n-m".  what about answer
(A), we just substitute "n-m" in for "n" in the basis function there?
and, unlike (B), it works.  it's the same basis function (for answer
(A), which is not the same basis function for (B) and (C)), just
evaluated for the argument "n-m".

likewise, for answer (C), the basis function is precisely the same as
the basis function is for (B) (but different from from the clean and
mean (A)).  but now we're substituting "(n-m)mod_N" for the argument
of the basis function.  so this works, with the same crappy basis
function you have in (B), but requires a workaround to accommodate the
shortcomings (the window that really shouldn't be there) of the basis
definition.

> &#4294967295;This is no longer a DFT, at least not as per the usual definition,

bullshit, Eric!  c'mon!  you (and Dale and Eqs. (8.59) and (8.60) of
the 1989 O&S) say that the "usual definition" of the DFT is:

          {    N-1
          {    SUM x[n] e^(-j*2*pi*n*k/N)    for  0 <= k < N
 X[k] =   {    n=0
          {
          {    0                             otherwise

and
          {     N-1
          { 1/N SUM X[k] e^(+j*2*pi*n*k/N)   for  0 <= n < N
 x[n] =   {     k=0
          {
          {    0                             otherwise

(look this up in GG, and set it to "Fixed text". i ain't redoing this
onto a pdf.)

i'm saying that the above "usual definition" is mathematically
precisely equivalent to

             N-1
 X[k] =      SUM x[n] e^(-j*2*pi*n*k/N) (u[k] - u[k-N])
             n=0
and

             N-1
 x[n] =  1/N SUM X[k] e^(+j*2*pi*n*k/N) (u[n] - u[n-N])
             k=0

                { 1       for n >= 0
where   u[n] =  {
                { 0       otherwise


the two expressions are mathematically precisely the same.

> and will be expected to produce a different output than if
> the usual definition were used.

the use of the windowed definition using "(u[n] - u[n-N])" cannot
produce a different result from the "usual definition" (with the case
statement and is likewise windowed) because they are precisely the
same.  they are mathematically equivalent and it's trivial to show
that.

> I don't think discussing that case is relevant. &#4294967295;

the relevance i keep asking is simply "why".  what utility is there in
this definition when it either screws you up (gets the wrong answer,
as in (B)) or requires you to use this klunky modulo_N arithmetic on
the indices just so that you can get the right answer (as in (C))?  in
Answer (A), it's the same simple expression as in (B) (but more
correct than (B)) and it's just as correct as (C), but simpler
expression than (C).  what utility do you draw from the windowed DFT
definition?

> If you leave the basis functions alone and just put a formal window
> around them,

i guess i better ask you what you mean by that. what *are* the basis
functions?

the "formal window" *is* part of the basis function, given your
"usual" definition.

> you haven't changed the DFT and will get the same result
> one always gets. &#4294967295;

sounds like to me, if i am inferring your intent correctly, that
you're defining the "basis functions" as only the exponentials (i
would call them "sinusoids" because the exponent is imaginary).  then
you're saying the basis functions are precisely the same was what i am
saying; periodic for all n (or k) out to forever.

that's the basis function and the window is not part of it.  if that's
the case, my question is even more pointed: "What's the friggin'
point?"  So you slap on this window around your periodic basis
functions.  For what purpose?

So you slap this rectangular window on, so that when you need to do
any non-trivial operation in the frequency domain, you have to undo
the window (which makes the data periodic again because the basis
functions are), shift the periodic time-domain data around (as a
consequence of the non-trivial operation in the frequency domain),
then re-apply the window when you're done?

What utility is that?  Again, those zeros in the windowed data that
you have either before or after this operation do not enter into any
mathematical calculation. They have no effect on anything. What good
are they?

Eric, there is no sense in that.

r b-j

On Wed, 09 Feb 2011 11:15:53 -0600, jim <"sjedgingN0Sp"@m@mwt,net>
wrote:

>
>
>Eric Jacobsen wrote:
>> 
>> On Mon, 07 Feb 2011 21:20:50 -0600, jim <"sjedgingN0Sp"@m@mwt.net>
>> wrote:
>> 
>> >Eric Jacobsen wrote:
>> >>
>> >> On Mon, 07 Feb 2011 13:03:25 -0600, jim <"sjedgingN0Sp"@m@mwt,net>
>> >> wrote:
>> >>
>> >> >
>> >> >
>> >> >Eric Jacobsen wrote:
>> >> >
>> >> >
>> >> >>
>> >> >> Perhaps I'll stir the pot and say that, again, just looking at the
>> >> >> definition and operation of the DFT, as a linear algebra expression, I
>> >> >> think it's hard to justify an absolute position that periodic
>> >> >> extension is inherent.
>> >> >
>> >> >
>> >> >All you have to do is replace Pi with any integer
>> >> >to change the DFT to be aperiodic.
>> >> >If you don't use that number Pi it won't be periodic.
>> >> >Why do you use that particular number if you don't care
>> >> >if the DFT is not periodic?
>> >>
>> >> I care that the DFT does the analysis I expect it to do, and that the
>> >> output has certain properties, like the bins are orthogonal, and
>> >> represent what I expect them to represent about the signal.   There
>> >> are a lot of other things that can be said about that, but if one
>> >> substitutes something else for the basis functions other than what's
>> >> in the usual DFT definition, IMHO it ceases to be a DFT and is
>> >> something else entirely.
>> >
>> >Except that it is not "something else entirely".
>> > It is the exact same thing except that the bins in the frequency domain
>> >are now spaced differently.
>> 
>> Which is clearly different, no?   The results obtained from sliding
>> the basis functions will not be the same as those obtained from using
>> the usual definition of a DFT.
>
>In what way is it different? When you substitute another number for Pi
>you are still dealing with a harmonically related series of complex
>exponentials.  The difference is the result will no longer be periodic
>in N. 

If you transform a given vector with two transforms, one with the
usual basis functions and one with the basis functions changed, even
subtly, to something else, the results will be different.

Something like a scale factor may not be consequential, but changing
the phase, shape, or period of the basis functions means that how the
output is interpreted has to change as well.

>> >You claim you want it to be not periodic
>> >That's a way to make the DFT  not periodic.
>> >
>> >-jim
>> 
>> I do not claim that I want the DFT to be not periodic, and have not
>> done so.  I claim only that it is not necessary to look at it that way
>> to have a broad understanding of what the DFT does and how it works.
>
>
>What is clear is you refuse to accept it unless it be periodic in N. 

On the contrary.  I think you've not read or understood what I've been
writing.


Eric Jacobsen
http://www.ericjacobsen.org
http://www.dsprelated.com/blogs-1//Eric_Jacobsen.php

Eric Jacobsen wrote:

> 
> Something like a scale factor may not be consequential, but changing
> the phase, shape, or period of the basis functions means that how the
> output is interpreted has to change as well.

Yes we are talking about changing the period from N to something else. 


> >
> >What is clear is you refuse to accept it unless it be periodic in N.
> 
> On the contrary.  I think you've not read or understood what I've been
> writing.

Don't have read or understand anything you wrote. I suggest a change
that makes it not periodic and your reaction says it all. It is pretty
clear to me you need it to be periodic regardless of what you say. 

-jim