CAUTION! was "What is the advantage on high-sampling rate ?"

In article BCBDD918.AFE2%rbj@surfglobal.net, robert bristow-johnson at
rbj@surfglobal.net wrote on 05/04/2004 23:34:

> DFT{ exp(j*2*pi*k0*n/N) * x[n]) = X[k-k0]
> 
>                                     N-1
> iDFT{ H[k] * X[k] } =  h(*)x[n]  =  SUM{ h[m]*x[n-m] }
>                                     m=0
> 
> ( " (*) " means "discrete convolution" )

just to dot the i's, i think the latter needs a scaling correction:

                                              N-1
    iDFT{ H[k] * X[k] } =  h(*)x[n]  =  1/N * SUM{ h[m]*x[n-m] }
                                              m=0


it doesn't change the basic point.  i like to pick my own nits before
someone else gets to it.

r b-j

robert bristow-johnson wrote:

> Bob, i finally got around to responding Sunday night.  did you see it?  (it
> shows up on Google groups, so i didn't think it got lost into the USENET bit
> bucket.)

No, it didn't seem to show up on Newsguy.  I've been 
checking in looking for it.

> 
> Stan was responding to Randy's post that was responding to yours, Bob.
>

Ah, one would think I was spoiling for an argument.

> 
> it's necessary if you apply any operation that involves shifting or delaying
> of the data in one domain or the other:
> 
>     DFT{ exp(j*2*pi*k0*n/N) * x[n]) = X[k-k0]
> 
>                                         N-1
>     iDFT{ H[k] * X[k] } =  h(*)x[n]  =  SUM{ h[m]*x[n-m] }
>                                         m=0
> 
>     ( " (*) " means "discrete convolution" )

Yes, I can see that but again, I see it as akin to buffer 
wrap around.  Shifting in this sense is a rotation 
operation.  Extend the data and it remains a shift, the same 
principle as extension for convolution to make the result 
container big enough to contain the result.  If you don't, 
where else will it go but back around into the other end of 
the container.  I know that's not a very scientific 
explanation but it is very intuitive.

> 
> 
> 
>>Of course in certain problem domains it can be a useful extension ...
> 
> 
> it is *useful* in very few problem domains.  the inherent periodicity
> usually gets in the way (as it does in fast convolution) requiring a
> workaround (overlap-add or overlap-save or zero-padding, etc).  

See, I don't think of that as a workaround but as the 
logically correct way to do convolution because otherwise 
the result is too large for the container and wraps around. 
  It's the correct way to do convolution using a DFT for 
pretty obvious reasons.

I liken this to multiplication.  It would just be wrong to 
not provide a double length container for the result for 
much the same reasons.

> the only
> problem domain i can think of where this inherent periodic property *is*
> useful is in dealing with periodic or quasi-periodic functions that have
> exactly an integer N samples per period (or can be resampled to have exactly
> N samples per period).  that's what was done in that Wavetable-101 paper.
> but it's a small problem domain.  (BTW, i like that term "problem domain".
> i'm gonna have to use it in the future.)

Yeah, I like it too.

> 
> 
>>but in mine it is merely cumbersome and belies the reality of my signals.
> 
> 
> are all of your signals periodic?!  i sorta doubt it.  

Maybe we've lost track of the disagreement here, none of 
mine are.

> then, if they ain't
> periodic, you need to worry about the inherent periodic property of the DFT
> so you don't screw things up.

Or just provide enough room to contain the result by 
extending the inputs.  Thinking of it that way, periodicity 
never enters my consciousness at all.  :-)

> 
> 
> these are the only DEFINITIONs (as long as we're capitalizing it) that i am
> working on:
> 
>                                   N-1
>     DFT{ x[n] }  =  X[k]  =       SUM{ x[n] * exp(-j*2*pi*n*k/N) }
>                                   n=0
> 
> 
>                                   N-1
>     iDFT{ x[n] } =  x[n]  = 1/N * SUM{ X[k] * exp(+j*2*pi*n*k/N) }
>                                   k=0
> 
> 
> i must confess, as long as we're talking "definition", that i wish that they
> put the 1/N factor in the DFT and not in the iDFT.  from a conceptual POV,
> that is where it belongs.  

I totally agree.

> 
> which clearly shows that the DFT periodically extends the N samples given to
> it, for better or for worse.

??? Not clear at all.  I see no extension.  The complex 
exponential is only evaluated in the region of the limits. 
The fact that it has an infinite extension outside those 
limits is irrelevant.  A function that was zero, or anything 
else, outside those limits would serve the definition just 
as well.  But why bother when you only care about the value 
of the function within those limits and the complex 
exponential does that just fine.

Your extension derives from other Fourier operators on other 
domains where that extension must exist or the answer is wrong.


Bob
-- 

"Things should be described as simply as possible, but no 
simpler."

                                              A. Einstein

Bob Cain wrote:

> 
> 
> robert bristow-johnson wrote:
> 
   ...

Youze guys is looking at different parts of the same elephant. However
you intuit it is the right way for you. If you got different results,
then the argument would be worth the ink.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Jerry Avins wrote:

> Bob Cain wrote:
> 
>>
>>
>> robert bristow-johnson wrote:
>>
>   ...
> 
> Youze guys is looking at different parts of the same elephant. However
> you intuit it is the right way for you. If you got different results,
> then the argument would be worth the ink.

Sorry, Jerry but I think it a bit deeper than that.  If one 
is working with finite systems and finite impulse responses, 
I believe that appeals to periodicity do no more than cloud 
an issue that is really much simpler than that.  I know that 
I ran in circles around the periodicity issue for a long 
time, not really understanding what was going on, before 
realizing that I could think about it more simply.  This led 
me to framing problems in ways that led to solutions quicker 
and with less head scratching about irellevant notions.

It is just a whole lot more straightforward to keep in mind 
that convolution requires a double length result container 
to deal with finite systems than to try and keep track of 
peridicity considerations.  We all know how to multiply and 
many of us know how to do so incrementally over large 
numbers and moving the considerations involved in that to 
signal processing is not much of a conceptual leap.

OTOH, I do agree that either point of view can be applied 
depending on the domain of application.  However, that 
distinction is rarely, if ever, made in pedagogical material 
and it should be in the clearest of terms.


Bob
-- 

"Things should be described as simply as possible, but no 
simpler."

                                              A. Einstein

On 28 Apr 2004 20:40:39 -0700, danlavry@mindspring.com (dan lavry)
wrote:

  (snipped)
>
>I have no problem talking and listning to technical people. But at
>least one NG I was on is made of at least 50% non tecnical recording
>and mastering people, and so a statment like that CAUTION! causes a
>lot of harm. So of course once it happened I had to spend more time
>and outside of this NG, all without help.
>
>The common ethical way is to let folks know and give them an
>opertunity to answer.
>
>But there was an appology, and I do accept it. 
>
>BR
>Dan Lavry

Hi,
  Again Dan, please accept my apology for 
clumsily causing you heartache.  I sure didn't 
mean to.

Regards,
[-Rick-]


 

In article c7b8rk0k55@enews4.newsguy.com, Bob Cain at
arcane@arcanemethods.com wrote on 05/05/2004 13:39:

> Jerry Avins wrote:
... 
>> Youze guys is looking at different parts of the same elephant. However
>> you intuit it is the right way for you. If you got different results,
>> then the argument would be worth the ink.
> 
> Sorry, Jerry but I think it a bit deeper than that.

this is where we agree.

>  If one 
> is working with finite systems and finite impulse responses,
> I believe that appeals to periodicity do no more than cloud
> an issue that is really much simpler than that.

and this is where we disagree.  i don't *appeal* to periodicity (that
property of the DFT and some of its theorems usually get in the way, rather
than help), but i *recognize* it where it exists.  by recognizing that right
off the bat, one is able to deal with the reality of it from square one.  by
failing to recognize it, one can get into a bit of a pickle in applications
such as linear convolution.  by use of different (and more complicated)
semantics, you *seem* to recognize it, also, because you recognize the need
for "wrap-around".  but why must one worry about wrap-around?  is it not
because the inputs to the DFT and iDFT have been periodically extended?

>  I know that 
> I ran in circles around the periodicity issue for a long
> time, not really understanding what was going on, before
> realizing that I could think about it more simply.

for me, it was the opposite.  by keeping that in mind from the beginning
helped me understand right away why efforts to overlap-add or overlap-save
were necessary for "fast convolution".  we had a tool that performed
circular convolution (with the FFT it performed circular convolution very
quickly) and we had to somehow use that tool to perform linear convolution.
it's also conceptually useful to keep in mind how spectral leakage (or the
equivalent in the time-domain) wraps around from positive frequency to
negative frequency.

>  This led 
> me to framing problems in ways that led to solutions quicker
> and with less head scratching about irellevant notions.
> 
> It is just a whole lot more straightforward to keep in mind
> that convolution requires a double length result container

why double length?  is the set of data necessarily the same length as the
FIR length?
 
> to deal with finite systems than to try and keep track of
> peridicity considerations.

*what* periodicity consideration?

>  We all know how to multiply and
> many of us know how to do so incrementally over large
> numbers and moving the considerations involved in that to
> signal processing is not much of a conceptual leap.

i guess it is for me.  i'm not sure what you're driving at, Bob.

> OTOH, I do agree that either point of view can be applied
> depending on the domain of application.

if something is true, it's true.  no matter what the application.

>  However, that 
> distinction is rarely, if ever, made in pedagogical material
> and it should be in the clearest of terms.

i agree, but still wonder why you dance around (without totally rejecting)
the built-in periodicity of the DFT and iDFT and the theorems associated
with them?  it should be simply clear.

r b-j

arcane@arcanemethods.com wrote on 05/05/2004 13:39:
> 
>  This led 
> me to framing problems in ways that led to solutions quicker
> and with less head scratching about irellevant notions.

If you're sick, it might sometimes be a quicker way to restore your
health by treating your symptoms. However, every symptom has its
cause, and if you don't recognize this you will ultimately fail in
your endeavour to cure the desease.

The DFT is inherently periodic. The complex exponentials have no
localization in the time domain, and a single time domain sample has
no localization in the frequency domain. No localization means that it
is totally irrelevant if you're right here, or one period away - it's
exactly the same world. This is practically the definition of
"periodic".

It's like being inside a sphere - you can increase the size of the
sphere so the surface appears almost flat, but it will not change the
fact that it's still a sphere - if you travel far enough, you'll
always end up at the same spot.

You can ignore that fact in your application if you are careful about
the implementation, but the fact itself does not change. It also does
not make it irrelevant "per se" - even though it might be irrelevant
in your context.

--smb

robert bristow-johnson wrote:

> In article c7b8rk0k55@enews4.newsguy.com, Bob Cain at
> arcane@arcanemethods.com wrote on 05/05/2004 13:39:
> 
> 
>>Jerry Avins wrote:
> 
> ... 
> 
>>>Youze guys is looking at different parts of the same elephant. However
>>>you intuit it is the right way for you. If you got different results,
>>>then the argument would be worth the ink.
>>
>>Sorry, Jerry but I think it a bit deeper than that.
> 
> 
> this is where we agree.
> 
> 
>> If one 
>>is working with finite systems and finite impulse responses,
>>I believe that appeals to periodicity do no more than cloud
>>an issue that is really much simpler than that.
> 
> 
> and this is where we disagree.  i don't *appeal* to periodicity (that
> property of the DFT and some of its theorems usually get in the way, rather
> than help), but i *recognize* it where it exists.  by recognizing that right
> off the bat, one is able to deal with the reality of it from square one.  by
> failing to recognize it, one can get into a bit of a pickle in applications
> such as linear convolution.  by use of different (and more complicated)
> semantics, you *seem* to recognize it, also, because you recognize the need
> for "wrap-around".  but why must one worry about wrap-around?  is it not
> because the inputs to the DFT and iDFT have been periodically extended?
> 
> 
>> I know that 
>>I ran in circles around the periodicity issue for a long
>>time, not really understanding what was going on, before
>>realizing that I could think about it more simply.
> 
> 
> for me, it was the opposite.  by keeping that in mind from the beginning
> helped me understand right away why efforts to overlap-add or overlap-save
> were necessary for "fast convolution".  we had a tool that performed
> circular convolution (with the FFT it performed circular convolution very
> quickly) and we had to somehow use that tool to perform linear convolution.
> it's also conceptually useful to keep in mind how spectral leakage (or the
> equivalent in the time-domain) wraps around from positive frequency to
> negative frequency.
> 
> 
>> This led 
>>me to framing problems in ways that led to solutions quicker
>>and with less head scratching about irellevant notions.
>>
>>It is just a whole lot more straightforward to keep in mind
>>that convolution requires a double length result container
> 
> 
> why double length?  is the set of data necessarily the same length as the
> FIR length?
>  
> 
>>to deal with finite systems than to try and keep track of
>>peridicity considerations.
> 
> 
> *what* periodicity consideration?
> 
> 
>> We all know how to multiply and
>>many of us know how to do so incrementally over large
>>numbers and moving the considerations involved in that to
>>signal processing is not much of a conceptual leap.
> 
> 
> i guess it is for me.  i'm not sure what you're driving at, Bob.
> 
> 
>>OTOH, I do agree that either point of view can be applied
>>depending on the domain of application.
> 
> 
> if something is true, it's true.  no matter what the application.
> 
> 
>> However, that 
>>distinction is rarely, if ever, made in pedagogical material
>>and it should be in the clearest of terms.
> 
> 
> i agree, but still wonder why you dance around (without totally rejecting)
> the built-in periodicity of the DFT and iDFT and the theorems associated
> with them?  it should be simply clear.
> 
> r b-j

Grrr! There can be legitimate disagreement about the better end to eat
an egg from even though that disagreement is a silly cause for war. You
two actually agree about which end; you disagree only about the reason.
Each of you cites the advantage (to himself) of his particular
viewpoint. There may be good reason for conjoined twins to squabble
about which which direction has the nicer scenery, but such a squabble
is not fruitful for people who can independently gaze where they like.

I actually have a viewpoint of my own, but there's no gain from
inflaming this discussion which is, after all, not about facts as such.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Stephan M. Bernsee wrote:

> The DFT is inherently periodic. The complex exponentials have no
> localization in the time domain, and a single time domain sample has
> no localization in the frequency domain. No localization means that it
> is totally irrelevant if you're right here, or one period away - it's
> exactly the same world. This is practically the definition of
> "periodic".
> 

Yes, the basis functions employed are of infinite extent. 
However, they are only evaluated in a finite region of that 
extent within the DFT and as such their value outside that 
region need not be assumed periodic unless the problem 
domain is such that one knows that the region is exactly one 
period of an infinitely repeating sequence.

If that is not the case, no value obtains from extending the 
definition of the basis functions as repeating outside the 
region.  If I define the basis functions to be zero outside 
the region of evaluation in the DFT the result is identical. 
  What isn't is the presumed behavior of the transformed 
function outside the region.  One should presume the 
behavior of the basis outside the region to match the 
problem under attack rather than take a fixed view of it.

In finite systems the presumtion of zero outside the region 
fits the physical reality so that any consideration of 
infinite periodicity are simply wrong and give results that 
don't match the system.

All I am saying is that it is not productive to limit the 
definition of the regions that are not evaluated within the 
DFT to any particular set of values as is done by the people 
why claim that the infinitely repeating basis is the only 
legitimate view.


Bob
-- 

"Things should be described as simply as possible, but no 
simpler."

                                              A. Einstein

Admittedly I'm coming in here late (unfortunately too busy to keep up
with comp.dsp these days), but since this is one of those topics to
which I have in the past enjoyed contributing, I gotta get my dos
centavos in again.

It sounds like many here are in violent agreement on many of the
practicalities of application of the DFT.   I'll add the following in
hopes that it offers some modicum of clarification:

The anthropomorphised DFT has no way of knowing whether the input
sequence that it is processing is periodic, since a window has been
applied (at the least a rectangular window if not some more
sophisticated example).  What happened to the sequence outside of the
window is unknown and inconsequential to the process applied by the
DFT to the input sequence.

However, the output sequence will be the appropriate, valid, and
legitimate sequence assuming that the input sequence was periodic with
period equal to the length of the transform.  Note that the period
assumption is not even to the length of the input window, since
zero-padding could have been applied to shorten the window, the
effective assumed period is the length of the transform.   The
accurate reproduction of the assumed input would be a repeating
sequence of the inverse transform of the output.

As Jerry aptly and correctly (IMHO) pointed out: The DFT is a tool,
but like any tool in order to be applied most effectively one needs to
be aware of its quirks, limitations, and assumptions.   When
interpreting the output of a DFT, one may do well to keep in mind that
the signal has been processed as though it were periodic.  I don't
think there's disagreement here on that, and the distinction is
actually fairly subtle in my opinion.

Hope that helps a bit or so.

Cheers,

Eric


On Thu, 06 May 2004 09:27:15 -0700, Bob Cain
<arcane@arcanemethods.com> wrote:

>
>
>Stephan M. Bernsee wrote:
>
>> The DFT is inherently periodic. The complex exponentials have no
>> localization in the time domain, and a single time domain sample has
>> no localization in the frequency domain. No localization means that it
>> is totally irrelevant if you're right here, or one period away - it's
>> exactly the same world. This is practically the definition of
>> "periodic".
>> 
>
>Yes, the basis functions employed are of infinite extent. 
>However, they are only evaluated in a finite region of that 
>extent within the DFT and as such their value outside that 
>region need not be assumed periodic unless the problem 
>domain is such that one knows that the region is exactly one 
>period of an infinitely repeating sequence.
>
>If that is not the case, no value obtains from extending the 
>definition of the basis functions as repeating outside the 
>region.  If I define the basis functions to be zero outside 
>the region of evaluation in the DFT the result is identical. 
>  What isn't is the presumed behavior of the transformed 
>function outside the region.  One should presume the 
>behavior of the basis outside the region to match the 
>problem under attack rather than take a fixed view of it.
>
>In finite systems the presumtion of zero outside the region 
>fits the physical reality so that any consideration of 
>infinite periodicity are simply wrong and give results that 
>don't match the system.
>
>All I am saying is that it is not productive to limit the 
>definition of the regions that are not evaluated within the 
>DFT to any particular set of values as is done by the people 
>why claim that the infinitely repeating basis is the only 
>legitimate view.
>
>
>Bob
>-- 
>
>"Things should be described as simply as possible, but no 
>simpler."
>
>                                              A. Einstein

Eric Jacobsen
Minister of Algorithms, Intel Corp.
My opinions may not be Intel's opinions.
http://www.ericjacobsen.org