COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### FFT Algorithm and Time

• Email
• Follow

```I am new to DSP and FFT.  I have implememented the FFT in Smith's book.
What I am a little confused about is how do I determine what is the
frequency scale of the X axis?

thanks
Don

```
 0
Reply a8723 (11) 11/11/2006 2:42:14 PM

See related articles to this posting

```"d1camero" <a8723@cameronsoftware.com> writes:

> I am new to DSP and FFT.  I have implememented the FFT in Smith's book.
>  What I am a little confused about is how do I determine what is the
> frequency scale of the X axis?

n*Fs/N, 0 < n < N-1, N being the FFT size and Fs being the sample rate
of the data. When you get to n = N/2 and above, you've covered the positive
frequencies and begin the negative frequencies, i.e., n*Fs/N == (n-N)*Fs/N,
n > N/2.
--
%  Randy Yates                  % "I met someone who looks alot like you,
%% Fuquay-Varina, NC            %             she does the things you do,
%%% 919-577-9882                %                     but she is an IBM."
%%%% <yates@ieee.org>           %        'Yours Truly, 2095', *Time*, ELO
```
 0
Reply yates (3949) 11/11/2006 2:57:11 PM

```> what is the frequency scale of the X axis?

A simple fact to bear in mind is that the number of the bin *is* th
actual frequency. The dimensions for these numbers are not in the familia
Hz (cycles/second) but rather in cycles/frame. To convert this to Hz, jus
multiply by the number of input frames/second, or divide by the duratio
of your input frame (in seconds).

It is interesting to note that the number of the bin in which you get
significant spectral response gives a clue as to how many cycles wa
contained in your input frame (+/- 0.5 cycles). For a 1024 point FFT, say
if you had a significant response in bin 211, then there would be betwee
210.5 and 211.5 cycles of that frequency in your original input frame.

Jeff

```
 0
Reply jeffcaunter (49) 11/12/2006 1:10:44 AM

```Thanks Randy, this worked out quite well.

Don

```
 0
Reply a8723 (11) 11/12/2006 2:16:03 AM

```Randy Yates wrote:
> "d1camero" <a8723@cameronsoftware.com> writes:
>
> > I am new to DSP and FFT.  I have implememented the FFT in Smith's book.
> >  What I am a little confused about is how do I determine what is the
> > frequency scale of the X axis?
>
> n*Fs/N, 0 < n < N-1, N being the FFT size and Fs being the sample rate
> of the data. When you get to n = N/2 and above, you've covered the positive
> frequencies and begin the negative frequencies, i.e., n*Fs/N == (n-N)*Fs/N,
> n > N/2.

unless, of course if you're using MATLAB, then "n" is off by one from
the relationship above for which DSP engineers are thankful to TMW for.

(the other think is that the bin at Nyquist (n=N/2 for the regular
world or n=N/2+1 for MATLAB) that it is just as plausible that it's
negative or positive.  i usually like to say half of the value of the
Nyquist bin is at the positive frequency N/2 * Fs/N = Fs/2 and the
other half of the bin amplitude is at the negative frequency -N/2 *
Fs/N = -Fs/2

r b-j

```
 0
Reply rbj (4087) 11/12/2006 3:00:49 AM

```"robert bristow-johnson" <rbj@audioimagination.com> writes:

> Randy Yates wrote:
>> "d1camero" <a8723@cameronsoftware.com> writes:
>>
>> > I am new to DSP and FFT.  I have implememented the FFT in Smith's book.
>> >  What I am a little confused about is how do I determine what is the
>> > frequency scale of the X axis?
>>
>> n*Fs/N, 0 < n < N-1, N being the FFT size and Fs being the sample rate
>> of the data. When you get to n = N/2 and above, you've covered the positive
>> frequencies and begin the negative frequencies, i.e., n*Fs/N == (n-N)*Fs/N,
>> n > N/2.
>
> unless, of course if you're using MATLAB, then "n" is off by one from
> the relationship above for which DSP engineers are thankful to TMW for.

Robert, I think you may actually have this issue carved on your tombstone:

Here lies a man who knew Matlab indexing was wrong.

> (the other think is that the bin at Nyquist (n=N/2 for the regular
> world or n=N/2+1 for MATLAB) that it is just as plausible that it's
> negative or positive.  i usually like to say half of the value of the
> Nyquist bin is at the positive frequency N/2 * Fs/N = Fs/2 and the
> other half of the bin amplitude is at the negative frequency -N/2 *
> Fs/N = -Fs/2

positive. Could just as well be negative. But I don't like the idea of
splitting it up - perhaps simply duplicating it would be better. Yeah,
I know - the energy wouldn't add up right then - but from a GUI
perspective it would seem better.
--
%  Randy Yates                  % "She has an IQ of 1001, she has a jumpsuit
%% Fuquay-Varina, NC            %            on, and she's also a telephone."
%%% 919-577-9882                %
%%%% <yates@ieee.org>           %        'Yours Truly, 2095', *Time*, ELO
```
 0
Reply yates (3949) 11/12/2006 3:13:45 AM

```Randy Yates wrote:
> "robert bristow-johnson" <rbj@audioimagination.com> writes:
>
> > Randy Yates wrote:
> >> "d1camero" <a8723@cameronsoftware.com> writes:
> >>
> >> > I am new to DSP and FFT.  I have implememented the FFT in Smith's book.
> >> >  What I am a little confused about is how do I determine what is the
> >> > frequency scale of the X axis?
> >>
> >> n*Fs/N, 0 < n < N-1, N being the FFT size and Fs being the sample rate
> >> of the data. When you get to n = N/2 and above, you've covered the positive
> >> frequencies and begin the negative frequencies, i.e., n*Fs/N == (n-N)*Fs/N,
> >> n > N/2.
> >
> > unless, of course if you're using MATLAB, then "n" is off by one from
> > the relationship above for which DSP engineers are thankful to TMW for.
>
> Robert, I think you may actually have this issue carved on your tombstone:
>
>   Here lies a man who knew Matlab indexing was wrong.

yeah, i fought the good fight.  even though i lost.

we could just put a big "L" for "loser" on my tombstone.

r b-j

```
 0
Reply rbj (4087) 11/13/2006 4:00:38 AM

```"robert bristow-johnson" <rbj@audioimagination.com> writes:

> Randy Yates wrote:
>> "robert bristow-johnson" <rbj@audioimagination.com> writes:
>>
>> > Randy Yates wrote:
>> >> "d1camero" <a8723@cameronsoftware.com> writes:
>> >>
>> >> > I am new to DSP and FFT.  I have implememented the FFT in Smith's book.
>> >> >  What I am a little confused about is how do I determine what is the
>> >> > frequency scale of the X axis?
>> >>
>> >> n*Fs/N, 0 < n < N-1, N being the FFT size and Fs being the sample rate
>> >> of the data. When you get to n = N/2 and above, you've covered the positive
>> >> frequencies and begin the negative frequencies, i.e., n*Fs/N == (n-N)*Fs/N,
>> >> n > N/2.
>> >
>> > unless, of course if you're using MATLAB, then "n" is off by one from
>> > the relationship above for which DSP engineers are thankful to TMW for.
>>
>> Robert, I think you may actually have this issue carved on your tombstone:
>>
>>   Here lies a man who knew Matlab indexing was wrong.
>
> yeah, i fought the good fight.  even though i lost.
>
> we could just put a big "L" for "loser" on my tombstone.

We're all losers. Some ya' win, some ya' lose. That's partly what makes
these words from my favorite ELO album so true and poignant:

"...the answer lies within your soul, 'cause no one knows which side
the coin will fall."
--
%% Fuquay-Varina, NC            %       'cause no one knows which side
%%% 919-577-9882                %                   the coin will fall."
%%%% <yates@ieee.org>           %  'Big Wheels', *Out of the Blue*, ELO
```
 0
Reply yates (3949) 11/13/2006 4:42:33 AM

```Randy Yates wrote:
> "robert bristow-johnson" <rbj@audioimagination.com> writes:
> > (the other think is that the bin at Nyquist (n=N/2 for the regular
> > world or n=N/2+1 for MATLAB) that it is just as plausible that it's
> > negative or positive.  i usually like to say half of the value of the
> > Nyquist bin is at the positive frequency N/2 * Fs/N = Fs/2 and the
> > other half of the bin amplitude is at the negative frequency -N/2 *
> > Fs/N = -Fs/2
>
> positive. Could just as well be negative. But I don't like the idea of
> splitting it up - perhaps simply duplicating it would be better. Yeah,
> I know - the energy wouldn't add up right then - but from a GUI
> perspective it would seem better.

>From the perspective of trigonometric interpolation (i.e. taking the
DFT formula and using it to interpolate between the samples), splitting
up the Nyquist amplitude half-and-half between positive and negative
frequencies is in some sense the optimal choice.  It leads to a minimal
rms slope interpolation, and also interpolates real data to real data.

On the other hand, if your Nyquist amplitude is not very small then you
probably have more serious problems with aliasing.  If it is small,
then it doesn't matter much what you do with it.

Steven

```
 0
Reply stevenj (522) 11/13/2006 6:11:59 PM

```stevenj@alum.mit.edu wrote:
>
> From the perspective of trigonometric interpolation (i.e. taking the
> DFT formula and using it to interpolate between the samples), splitting
> up the Nyquist amplitude half-and-half between positive and negative
> frequencies is in some sense the optimal choice.  It leads to a minimal
> rms slope interpolation, and also interpolates real data to real data.

this is what was motivating this question i've been having about
bandlimited interpolation of periodic discrete signals.  letting
x[n]=x[n+N] for all n, when the period N is odd, there is no Nyquist
component and the reconstruction formula is the Dirichlet thingie:

N-1
x(t) = SUM{ x[n] * sin(N*pi*(t-n))/(N*sin(pi*(t-n))) }
n=0

x(t+N) = x(t)

but for the case of N even, there is a (potential) component at
Nyquist, for real x[n] this component has to be real, and if you split
it half and half and reconstruct, you get

N-1
x(t) = SUM{ x[n] * sin(N*pi*(t-n))/(N*tan(pi*(t-n))) }
n=0

x(t+N) = x(t)

it's the same for interpolating spectra coming out of the DFT when N is
odd, but not for N even.

Steven (or anyone else), do you know the reason why this is so?

r b-j

```
 0
Reply rbj (4087) 11/14/2006 5:05:51 PM

```robert bristow-johnson wrote:
> stevenj@alum.mit.edu wrote:
> >
> > From the perspective of trigonometric interpolation (i.e. taking the
> > DFT formula and using it to interpolate between the samples), splitting
> > up the Nyquist amplitude half-and-half between positive and negative
> > frequencies is in some sense the optimal choice.  It leads to a minimal
> > rms slope interpolation, and also interpolates real data to real data.
>
> this is what was motivating this question i've been having about
> bandlimited interpolation of periodic discrete signals.  letting
> x[n]=x[n+N] for all n, when the period N is odd, there is no Nyquist
> component and the reconstruction formula is the Dirichlet thingie:
>
>             N-1
>     x(t) = SUM{ x[n] * sin(N*pi*(t-n))/(N*sin(pi*(t-n))) }
>            n=0
>
>     x(t+N) = x(t)
>
> but for the case of N even, there is a (potential) component at
> Nyquist, for real x[n] this component has to be real, and if you split
> it half and half and reconstruct, you get
>
>
>             N-1
>     x(t) = SUM{ x[n] * sin(N*pi*(t-n))/(N*tan(pi*(t-n))) }
>            n=0
>
>     x(t+N) = x(t)
>
> it's the same for interpolating spectra coming out of the DFT when N is
> odd, but not for N even.

>> On the other hand, if your Nyquist amplitude is not very small then you
>> probably have more serious problems with aliasing.  If it is small,
>> then it doesn't matter much what you do with it.

If the signal is strongly bandlimited, then there is no
content in the N/2 bin.  If the signal is weakly bandlimited,
then N has to approach infinity for the N/2 bin to determine
the content at that frequency.  I'm not sure if there is a
significant difference in the two reconstruction formulas
for N and N+1 as N approaches infinity.  Thoughts?

IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M

```
 0
Reply rhnlogic (1111) 11/14/2006 11:38:49 PM

```Ron N. wrote:

> If the signal is strongly bandlimited, then there is no content in the N/2 bin.

let's say we don't know how strongly bandlimited it was originally,
except there was nothing above Nyquist.  maybe *some* energy at
Nyquist.

>  If the signal is weakly bandlimited, then N has to approach infinity for
> the N/2 bin to determine the content at that frequency.

i don't really get that at all.  N is fixed.  the curiousity i was
bringing up is given a perfectly periodic sequence, x[n] such that

x[n+N] = x[n]      for all n.

so if you know one period, say

x[n]      for   0 <= n < N

then you have a complete definition for x[n] for all n.  correct?

so, if we were to reconstruct out of those real samples a
continuous-time periodic signal, x(t) (let's assume the sampling period
to be 1, with no loss of generality) so that x(t-N) = x(t) for all t,
how is the function defined in terms of the finite set of samples x[0],
x[1], ... x[N-1] that fully define the periodic sequence and, these
discrete sequence should be able to fully define the continuous-time
signal it was sampled from (assuming appropriate bandlimiting, which we
are pushing the envelope a little).  now, usually, we think of the
ideal interpolation formula for x(t)  is:

+inf
x(t) = SUM{ x[n] * sinc(t - n) }
n=-inf

N-1     +inf
= SUM{    SUM{ x[n+m*N] * sinc(t - (n+m*N)) } }
n=0    m=-inf

but since x[n+m*N] = x[n] for any integer m, then

N-1     +inf
x(t) = SUM{    SUM{ x[n] * sinc(t - (n+m*N)) } }
n=0    m=-inf

N-1         +inf
= SUM{ x[n] * SUM{ sinc(t - n - m*N) } }
n=0        m=-inf

N-1
= SUM{ x[n] * h(t-n) }
n=0

now this interpolation function,

+inf
h(t) = SUM{ sinc(t - m*N) } }
m=-inf

is periodic with period N, h(t+N) = h(t) for all t, as we expect.  so
what does that periodic interpolation function look like?  i've
pondered this a while and first posted this to comp.dsp in 2001:

take a look at that.   Adrian Hey got into it enough to see the thing
that was bothering me a little.  anyway, the result i get for a closed
for periodic h(t) is

{ sin(pi*t)/(N*sin(pi*t/N))       N odd
h(t) = {
{ sin(pi*t)/(N*tan(pi*t/N))       N even

from above you get show

+inf
h(t) = SUM{ sin(pi*(t - m*N))/(pi*(t - m*N)) } }
m=-inf

+inf
= sin(pi*t) * SUM{ 1/(pi*(t - m*N)) } }                N even
m=-inf

+inf
= sin(pi*t) * SUM{ ((-1)^m)/(pi*(t - m*N)) } }         N odd
m=-inf

>  I'm not sure if there is a significant difference in the two reconstruction
> formulas for N and N+1 as N approaches infinity.  Thoughts?

i just don't want to make that assumption and equality holds exactly
for the two cases, even and odd.  one case the formula looks just like
the Dirichlet interpolation commonly done for the FFT and the other,
it's slightly different, but it *is* different.  in the even case, the
tails of those sinc() functions have bumps of opposite polarity so they
cancel themselves out more than in the odd case where the tails, though
descreasing in amplitude as 1/x, have their bumps of the same polarity,
so they team up.  so i'm pretty sure the formula is correct (the
1/tan() reduces the amplitude more than the 1/sin() as one approaches
midway between the two main pulses.  it also came up (indirectly) with
tthese two mathematical identities:

+inf
1/tan(t) = SUM{ 1/(t - m*pi) }
m=-inf

+inf
1/sin(t) = SUM{ ((-1)^m)/(t - m*pi) }
m=-inf

which i have not been able to prove directly.

if someone has it, i would like some insight for why the Dirichlet
formula applies exactly only for N odd, not exactly for N even,
although it applies exactly for both N odd or N even in the case of
interpolating DFT output to get the DTFT of the time-limited x[n].

do you guys see what it is that is bothering me?  or proving more
directly the two math identities above would be gratifying.  i have not
been able to do that directly, as of yet.

r b-j

```
 0
Reply rbj (4087) 11/15/2006 2:29:00 AM

```robert bristow-johnson wrote:

> stevenj@alum.mit.edu wrote:
> >
> > From the perspective of trigonometric interpolation (i.e. taking the
> > DFT formula and using it to interpolate between the samples), splitting
> > up the Nyquist amplitude half-and-half between positive and negative
> > frequencies is in some sense the optimal choice.  It leads to a minimal
> > rms slope interpolation, and also interpolates real data to real data.
>
> this is what was motivating this question i've been having about
> bandlimited interpolation of periodic discrete signals.  letting
> x[n]=x[n+N] for all n, when the period N is odd, there is no Nyquist
> component and the reconstruction formula is the Dirichlet thingie:
>
>             N-1
>     x(t) = SUM{ x[n] * sin(N*pi*(t-n))/(N*sin(pi*(t-n))) }
>            n=0
>
>     x(t+N) = x(t)
>
> but for the case of N even, there is a (potential) component at
> Nyquist, for real x[n] this component has to be real, and if you split
> it half and half and reconstruct, you get
>
>
>             N-1
>     x(t) = SUM{ x[n] * sin(N*pi*(t-n))/(N*tan(pi*(t-n))) }
>            n=0
>
>     x(t+N) = x(t)

Robert,

are you claiming that x(n) = x[n]? I tried your formula in a maths
program, and it seems that x(t) is periodic with period 1, and does not
at all interpolate x[n] (at any scale).

The (unique) pi-bandlimited interpolation function f(t) of the
uniformly spaced discrete N-periodic data x[n] is given (for n even) by

f(t) = 1/n ( a_0 + 2 sum_{k=1}^{N/2-1} ( a_k cos(2 pi k / N t) - b_k
sin(2 pi k / N t) ) + a_{N/2} cos(pi t) ),

where a_k = Re[ X[k] ] and b_k = Im[ X[k] ], and X[k] = DFT[ x[n] ].
This results in f(n) = x[n], and f(t + N) = f(t) for all t. For odd N,
you can scratch the Nyquist cosine term and sum to (N-1)/2.

Regards,
Andor

```
 0
Reply andor.bariska (1307) 11/15/2006 9:19:50 AM

```Andor wrote:
>
> are you claiming that x(n) = x[n]?

yes, for n = integer.

> I tried your formula in a maths
> program, and it seems that x(t) is periodic with period 1, and does not
> at all interpolate x[n] (at any scale).

it should be periodic with period N.

> The (unique) pi-bandlimited interpolation function f(t) of the
> uniformly spaced discrete N-periodic data x[n] is given (for n even) by
>
> f(t) = 1/N ( a_0 + 2 sum_{k=1}^{N/2-1} ( a_k cos(2 pi k / N t)
>         - b_k sin(2 pi k / N t) ) + a_{N/2} cos(pi t) ),
>
> where a_k = Re[ X[k] ] and b_k = Im[ X[k] ], and X[k] = DFT[ x[n] ].
> This results in f(n) = x[n], and f(t + N) = f(t) for all t. For odd N,
> you can scratch the Nyquist cosine term and sum to (N-1)/2.

well, if you have an arbitrary set of N values of x[n] for 0 <= n < N
so that
x[n+N] = x[n] for all n, when N is even, there is no guarantee that
there is no energy
in the X[N/2] bin.  what do you do with that component?  i think split
it in half in the
only reasonable thing.

so, you have your a_k and b_k defined in terms of X[k] which are
defined in terms of x[n]. can you come up with an expression for f(t)
in terms of x[n]?  in that reference to 2001, i think i *did*, and the
result was not surprizing for N odd, but a little surprizing for N
even.  i used superposition and defined x[n] to be 1 for n = 0 (or an
integer multiple of N) and zero for all other n.

r b-j

```
 0
Reply rbj (4087) 11/15/2006 4:18:10 PM

```robert bristow-johnson wrote:

> Andor wrote:
> >
> > are you claiming that x(n) = x[n]?
>
> yes, for n = integer.
>
> > I tried your formula in a maths
> > program, and it seems that x(t) is periodic with period 1, and does not
> > at all interpolate x[n] (at any scale).
>
> it should be periodic with period N.

I just saw your mistake. It should be

N-1
x(t) = SUM{ x[n] * sin(pi*(t-n))/(N*tan(pi/N*(t-n))) }
n=0

(notice how the frequency is divided by N as compared to your formula).

>
> > The (unique) pi-bandlimited interpolation function f(t) of the
> > uniformly spaced discrete N-periodic data x[n] is given (for n even) by
> >
> > f(t) = 1/N ( a_0 + 2 sum_{k=1}^{N/2-1} ( a_k cos(2 pi k / N t)
> >         - b_k sin(2 pi k / N t) ) + a_{N/2} cos(pi t) ),
> >
> > where a_k = Re[ X[k] ] and b_k = Im[ X[k] ], and X[k] = DFT[ x[n] ].
> > This results in f(n) = x[n], and f(t + N) = f(t) for all t. For odd N,
> > you can scratch the Nyquist cosine term and sum to (N-1)/2.
>
> well, if you have an arbitrary set of N values of x[n] for 0 <= n < N
> so that
> x[n+N] = x[n] for all n, when N is even, there is no guarantee that
> there is no energy
> in the X[N/2] bin.  what do you do with that component?  i think split
> it in half in the
> only reasonable thing.

Don't know what you mean.

>
> so, you have your a_k and b_k defined in terms of X[k] which are
> defined in terms of x[n]. can you come up with an expression for f(t)
> in terms of x[n]?

That's not too hard. Just insert the DFT definition for X[k], then
factor out the whole kasunkle and you get (for N even)

f(t) = 1/N sum_{n=0}^{N-1} ce_{N,n}(t) x[n],

where  ce_{N,n}(t) is the periodic interpolation kernel for even N,
given by

ce_{N,n}(t)  = 1  - cos(pi n) cos(pi t) + 2 sum_{k=1}^{N/2} cos(2 pi n
k/N) cos(2 pi k / N t) + sin(2 pi n k / N) sin(2 pi k / N t)
= 1  - cos(pi n) cos(pi t) + 2 sum_{k=1}^{N/2} cos(2 pi k/N (n-t))
= D_{N/2}(2 pi (n-t) / N) - cos(pi (n-t),

where D_M(x) is the Dirichlet kernel, ie.

D_M(x) = sin( (M+1/2) x) / sin(x/2).

> in that reference to 2001, i think i *did*, and the
> result was not surprizing for N odd, but a little surprizing for N
> even.  i used superposition and defined x[n] to be 1 for n = 0 (or an
> integer multiple of N) and zero for all other n.

For N odd I get the interpolation kernel

co_{N,n(t) = D_{(N-1)/2}(2 pi (n-t) / N).

This is just a consequence, as you said, of the Nyquist term, which is
added in for the even case. By the way, both kernels, ce and co, result
in a pi-bandlimited, periodic interpolation of the data, if applied
naively (ie. without regard to the parity of N). Do you spot the
difference of the two interpolation functions (using the even and the
odd kernel)?

Regards,
Andor

```
 0
Reply andor.bariska (1307) 11/16/2006 2:09:57 PM

```Andor wrote:
> robert bristow-johnson wrote:
>
> > Andor wrote:
> > >
> > > are you claiming that x(n) = x[n]?
> >
> > yes, for n = integer.
> >
> > > I tried your formula in a maths
> > > program, and it seems that x(t) is periodic with period 1, and does not
> > > at all interpolate x[n] (at any scale).
> >
> > it should be periodic with period N.
>
> I just saw your mistake. It should be
>
>              N-1
>      x(t) = SUM{ x[n] * sin(pi*(t-n))/(N*tan(pi/N*(t-n))) }
>             n=0
>
> (notice how the frequency is divided by N as compared to your formula).

i'm happy to have mistakes pointed out (and i confess that i don't
understand this as throroughly as i think i should) but i don't see how
that is different from either formulae i put in this thread or in the
2001 thread.  for N even, that's the result i have, Andor.

> > > The (unique) pi-bandlimited interpolation function f(t) of the
> > > uniformly spaced discrete N-periodic data x[n] is given (for n even) by
> > >
> > > f(t) = 1/N ( a_0 + 2 sum_{k=1}^{N/2-1} ( a_k cos(2 pi k / N t)
> > >         - b_k sin(2 pi k / N t) ) + a_{N/2} cos(pi t) ),
> > >
> > > where a_k = Re[ X[k] ] and b_k = Im[ X[k] ], and X[k] = DFT[ x[n] ].
> > > This results in f(n) = x[n], and f(t + N) = f(t) for all t. For odd N,
> > > you can scratch the Nyquist cosine term and sum to (N-1)/2.
> >
> > well, if you have an arbitrary set of N values of x[n] for 0 <= n < N
> > so that x[n+N] = x[n] for all n, when N is even, there is no guarantee
> > that there is no energy in the X[N/2] bin.  what do you do with that
> > component?  i think split it in half in the only reasonable thing.
>
> Don't know what you mean.

i'm saying that, in general for the problem of bandlimited
reconstruction of a periodic discrete-time function (or "sequence")
that, for N even, we cannot count on there being no energy in the
Nyquist bin, X[N/2].  indeed for the "special case" of

{ 1    for  n = m*N     m = integer
x[n] = {
{ 0    otherwise

all X[k] = 1, including X[N/2].  so then, when creating a real
continuous-time function (assume the sampling time T = 1 so that x(n) =
x[n] for integer n), how do we construct that real c-t function?  we
know X[0]/N is the DC component, and for 1 <= k <= N/2 - 1, we know
that X[N-k] are the negative frequency components, X[k] are positive
frequency, and (if x[n] is real, then these are complex conj) they
combine to real sinusoidal components that we can add up.  what do we
do with X[N/2] (which does not exist for N odd)?  i think the only
reasonable thing to do is split it in half and put half of the
amplitude at a frequency of -(N/2)/N and the other at +(N/2)/N.  what
other reasonable thing can we do with that component?

> >
> > so, you have your a_k and b_k defined in terms of X[k] which are
> > defined in terms of x[n]. can you come up with an expression for f(t)
> > in terms of x[n]?
>
> That's not too hard. Just insert the DFT definition for X[k], then
> factor out the whole kasunkle and you get (for N even)
>
> f(t) = 1/N sum_{n=0}^{N-1} ce_{N,n}(t) x[n],
>
> where  ce_{N,n}(t) is the periodic interpolation kernel for even N,
> given by
>
> ce_{N,n}(t)  = 1  - cos(pi n) cos(pi t) + 2 sum_{k=1}^{N/2} cos(2 pi n
> k/N) cos(2 pi k / N t) + sin(2 pi n k / N) sin(2 pi k / N t)
> = 1  - cos(pi n) cos(pi t) + 2 sum_{k=1}^{N/2} cos(2 pi k/N (n-t))
> = D_{N/2}(2 pi (n-t) / N) - cos(pi (n-t),
>
> where D_M(x) is the Dirichlet kernel, ie.
>
> D_M(x) = sin( (M+1/2) x) / sin(x/2).
>
> > in that reference to 2001, i think i *did*, and the
> > result was not surprizing for N odd, but a little surprizing for N
> > even.  i used superposition and defined x[n] to be 1 for n = 0 (or an
> > integer multiple of N) and zero for all other n.
>
> For N odd I get the interpolation kernel
>
> co_{N,n(t) = D_{(N-1)/2}(2 pi (n-t) / N).
>
> This is just a consequence, as you said, of the Nyquist term, which is
> added in for the even case. By the way, both kernels, ce and co, result
> in a pi-bandlimited, periodic interpolation of the data, if applied
> naively (ie. without regard to the parity of N). Do you spot the
> difference of the two interpolation functions (using the even and the
> odd kernel)?

there is clearly a difference.  the N odd case, it looks just like
Dirichlet.  for the N even case, there is a tan() function in the
denominator instead of a sin() function.  but what makes this curious
is that in application of the Dirichlet kernal to DFT bin case, it
sin() in the denominator for any integer N, even or odd.  that
difference in form is the curiousity i don't yet have my head wrapped
around.

r b-j

```
 0
Reply rbj (4087) 11/16/2006 4:03:12 PM

```robert bristow-johnson wrote:
> Ron N. wrote:
>
> > If the signal is strongly bandlimited, then there is no content in the N/2 bin.
>
> let's say we don't know how strongly bandlimited it was originally,
> except there was nothing above Nyquist.  maybe *some* energy at
> Nyquist.
>
> >  If the signal is weakly bandlimited, then N has to approach infinity for
> > the N/2 bin to determine the content at that frequency.
>
> i don't really get that at all.  N is fixed.

If there is any content in the N/2 bin, is the energy at the exact
Nyquist frequency determinate?  Wouldn't any amplitude of
sinusoid at the Nyquist frequency produce alternating sign
samples of any equal or lower amplitude at the sample rate
for some phase?

IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M

```
 0
Reply rhnlogic (1111) 11/16/2006 7:52:17 PM

```Ron N. wrote:
> robert bristow-johnson wrote:
>> Ron N. wrote:
>>
>>> If the signal is strongly bandlimited, then there is no content in the N/2 bin.
>> let's say we don't know how strongly bandlimited it was originally,
>> except there was nothing above Nyquist.  maybe *some* energy at
>> Nyquist.
>>
>>>  If the signal is weakly bandlimited, then N has to approach infinity for
>>> the N/2 bin to determine the content at that frequency.
>> i don't really get that at all.  N is fixed.
>
> If there is any content in the N/2 bin, is the energy at the exact
> Nyquist frequency determinate?  Wouldn't any amplitude of
> sinusoid at the Nyquist frequency produce alternating sign
> samples of any equal or lower amplitude at the sample rate
> for some phase?

Of course. What's more, if it the signal isn't strictly bandlimited and
sampled for at least k/(2Fs-Fmax) (k~=1) it can be only approximately
reconstructed. The exercise is academic, but interesting nonetheless.

Jerry
--
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������
```
 0
Reply jya (12872) 11/16/2006 8:48:56 PM

```Jerry Avins wrote:
>
> Of course. What's more, if it the signal isn't strictly bandlimited and
> sampled for at least k/(2Fs-Fmax) (k~=1) it can be only approximately
> reconstructed. The exercise is academic, but interesting nonetheless.

i don't think it's ***purely*** academic (oh, maybe it is).  but this
bandlimited reconstruction of periodic discrete-time data is a
well-defined problem:

assuming your discrete-time periodic function is:

{ 1   for n = m*N  where m = any integer
x[n] = {
{ 0   otherwise

(there is no loss of generality if you understand this animal to be
linear and time-invariant.)

assuming the sampling period to be 1, the straight-forward
reconstruction formula is

+inf
x(t) = SUM{ sinc(t - m*N) }
m=-inf

it's clear that when t = n = integer, that x(t) = x[n].  we can
manipulate it to be:

+inf
x(t) = sin(pi*t) * SUM{ ((-1)^(m*N))/(pi*(t - m*N)) }
m=-inf

from that you can see that the (-1)^(m*N) factor toggles with m for odd
N and does not toggle for even N.

but from knowledge that the DFT of that periodic sequence is X[k] = 1
for all k, we can get for N odd:

x(t) = sin(pi*t)/(N*sin(pi*t/N))       N odd

but for even N you get, if you split the X[N/2] into two, one for
postive and the other for negative frequency,

x(t) = sin(pi*t)/(N*tan(pi*t/N))       N even

```
 0
Reply rbj (4087) 11/16/2006 10:17:40 PM

```robert bristow-johnson wrote:
> Jerry Avins wrote:
>> Of course. What's more, if it the signal isn't strictly bandlimited and
>> sampled for at least k/(2Fs-Fmax) (k~=1) it can be only approximately
>> reconstructed. The exercise is academic, but interesting nonetheless.
>
> i don't think it's ***purely*** academic (oh, maybe it is).  but this
> bandlimited reconstruction of periodic discrete-time data is a
> well-defined problem:
>
> assuming your discrete-time periodic function is:
>
>                { 1   for n = m*N  where m = any integer
>         x[n] = {
>                { 0   otherwise
>
> (there is no loss of generality if you understand this animal to be
> linear and time-invariant.)
>
> assuming the sampling period to be 1, the straight-forward
> reconstruction formula is
>
>                +inf
>         x(t) = SUM{ sinc(t - m*N) }
>               m=-inf
>
> it's clear that when t = n = integer, that x(t) = x[n].  we can
> manipulate it to be:
>
>                            +inf
>         x(t) = sin(pi*t) * SUM{ ((-1)^(m*N))/(pi*(t - m*N)) }
>                           m=-inf
>
> from that you can see that the (-1)^(m*N) factor toggles with m for odd
> N and does not toggle for even N.
>
> but from knowledge that the DFT of that periodic sequence is X[k] = 1
> for all k, we can get for N odd:
>
>         x(t) = sin(pi*t)/(N*sin(pi*t/N))       N odd
>
> but for even N you get, if you split the X[N/2] into two, one for
> postive and the other for negative frequency,
>
>         x(t) = sin(pi*t)/(N*tan(pi*t/N))       N even

You already pointed that out. I find it interesting to the point of
being astounding; I certainly wouldn't have guessed it. Nevertheless,
any energy in the last bin violates the Fs/2 > Fmax requirement for
exact reconstruction, which is what I meant when I called the exercise

Look: I can derive a formula for the flexure of a beam that's accurate
enough so measurement can't disprove it. (I claim no credit; it's in the
textbooks.) But it must be wrong because somewhere along the development
is the implicit assumption that the beam doesn't flex. (Specifically,
that cross sections of the beam remain parallel through the analysis.)

Engineering is like that. It doesn't bother me, but it probably drives
my mathematically minded colleagues crazy.

Jerry
--
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������
```
 0
Reply jya (12872) 11/17/2006 12:05:37 AM

```robert bristow-johnson wrote:

> Andor wrote:
...
> > I just saw your mistake. It should be
> >
> >              N-1
> >      x(t) = SUM{ x[n] * sin(pi*(t-n))/(N*tan(pi/N*(t-n))) }
> >             n=0
> >
> > (notice how the frequency is divided by N as compared to your formula).
>
> i'm happy to have mistakes pointed out (and i confess that i don't
> understand this as throroughly as i think i should) but i don't see how
> that is different from either formulae i put in this thread or in the
> 2001 thread.  for N even, that's the result i have, Andor.

No, you posted:

>             N-1
>     x(t) = SUM{ x[n] * sin(N*pi*(t-n))/(N*tan(pi*(t-n))) }
>            n=0

>     x(t+N) = x(t)

I told you where to look for the difference. It may be minor, but it
was enough not to get your interpolation formula to work when I tried.

....

> > That's not too hard. Just insert the DFT definition for X[k], then
> > factor out the whole kasunkle and you get (for N even)
> >
> > f(t) = 1/N sum_{n=0}^{N-1} ce_{N,n}(t) x[n],
> >
> > where  ce_{N,n}(t) is the periodic interpolation kernel for even N,
> > given by
> >
> > ce_{N,n}(t)  = 1  - cos(pi n) cos(pi t) + 2 sum_{k=1}^{N/2} cos(2 pi n
> > k/N) cos(2 pi k / N t) + sin(2 pi n k / N) sin(2 pi k / N t)
> > = 1  - cos(pi n) cos(pi t) + 2 sum_{k=1}^{N/2} cos(2 pi k/N (n-t))
> > = D_{N/2}(2 pi (n-t) / N) - cos(pi (n-t),
> >
> > where D_M(x) is the Dirichlet kernel, ie.
> >
> > D_M(x) = sin( (M+1/2) x) / sin(x/2).
> >
> > > in that reference to 2001, i think i *did*, and the
> > > result was not surprizing for N odd, but a little surprizing for N
> > > even.  i used superposition and defined x[n] to be 1 for n = 0 (or an
> > > integer multiple of N) and zero for all other n.
> >
> > For N odd I get the interpolation kernel
> >
> > co_{N,n(t) = D_{(N-1)/2}(2 pi (n-t) / N).
> >
> > This is just a consequence, as you said, of the Nyquist term, which is
> > added in for the even case. By the way, both kernels, ce and co, result
> > in a pi-bandlimited, periodic interpolation of the data, if applied
> > naively (ie. without regard to the parity of N). Do you spot the
> > difference of the two interpolation functions (using the even and the
> > odd kernel)?
>
> there is clearly a difference.  the N odd case, it looks just like
> Dirichlet.  for the N even case, there is a tan() function in the
> denominator instead of a sin() function.  but what makes this curious
> is that in application of the Dirichlet kernal to DFT bin case, it
> sin() in the denominator for any integer N, even or odd.  that
> difference in form is the curiousity i don't yet have my head wrapped
> around.

What do you mean by the "application of the Dirichlet kernal to DFT bin
case, ..., N even or odd" ?

What I was getting at is that if you take the kernel ce for even N and
you interpolate a an odd number of discrete points with it, you get an
anti-symmetric (about N) interpolation function. The same happens when
you take the odd kernel for even number of data points.

Regards,
Andor

```
 0
Reply andor.bariska (1307) 11/17/2006 11:32:19 AM

```Andor wrote:
> robert bristow-johnson wrote:
>
> > Andor wrote:
> ..
> > > I just saw your mistake. It should be
> > >
> > >              N-1
> > >      x(t) = SUM{ x[n] * sin(pi*(t-n))/(N*tan(pi/N*(t-n))) }
> > >             n=0
> > >
> > > (notice how the frequency is divided by N as compared to your formula).
> >
> > i'm happy to have mistakes pointed out (and i confess that i don't
> > understand this as throroughly as i think i should) but i don't see how
> > that is different from either formulae i put in this thread or in the
> > 2001 thread.  for N even, that's the result i have, Andor.
>
> No, you posted:
>
> >             N-1
> >     x(t) = SUM{ x[n] * sin(N*pi*(t-n))/(N*tan(pi*(t-n))) }
> >            n=0
>
>
> >     x(t+N) = x(t)

you're right.  in the Nov 14 post i had the scaling of the argument
bumped up by a factor of N.  i didn't even realize that.  previous and
later posts, i think i had the scaling correct.

> I told you where to look for the difference.

i was looking at other posts.  more current in this thread and earlier
in 2001.  it was a "typo" that i hadn't even been aware of.

> It may be minor, but it
> was enough not to get your interpolation formula to work when I tried.

cause it was scaled wrong.  how did it work with the proper scaling?

....
> > there is clearly a difference.  the N odd case, it looks just like
> > Dirichlet.  for the N even case, there is a tan() function in the
> > denominator instead of a sin() function.  but what makes this curious
> > is that in application of the Dirichlet kernal to DFT bin case, it
> > sin() in the denominator for any integer N, even or odd.  that
> > difference in form is the curiousity i don't yet have my head wrapped
> > around.
>
> What do you mean by the "application of the Dirichlet kernal to DFT bin
> case, ..., N even or odd" ?

if you assume the DFT to be a discrete-frequency uniform sampling of
the output of the DTFT of the same input x[n] (except, for the DTFT,
this x[n] is *zero* extended, not periodically extended), the
continuous-frequency DTFT X(e^jw) can be related to the DFT output X[k]
with this relationship:

N-1
X(e^(jw)) = SUM{ X[k] *
sin(pi*(N*w/(2*pi)-k)/(N*sin(pi/N*(N*w/(2*pi)-k))) }
k=0

("t" becomes N*w/(2*pi))  and it's a sin() in the denominator (not
tan()) whether N is even or odd.  that is at least a bit curious to me.

> What I was getting at is that if you take the kernel ce for even N and
> you interpolate a an odd number of discrete points with it, you get an
> anti-symmetric (about N) interpolation function. The same happens when
> you take the odd kernel for even number of data points.

i don't quite understand what you mean here and i dunno exactly how to

r b-j

```
 0
Reply rbj (4087) 11/17/2006 6:02:57 PM

```remember this, guys?:

robert bristow-johnson wrote:
>  given a perfectly periodic sequence, x[n] such that
>
>     x[n+N] = x[n]      for all n.
>
> so if you know one period, say
>
>     x[n]      for   0 <= n < N
>
> then you have a complete definition for x[n] for all n.  correct?
>
> so, if we were to reconstruct out of those real samples a
> continuous-time periodic signal, x(t) (let's assume the sampling period
> to be 1, with no loss of generality) so that x(t-N) = x(t) for all t,
> how is the function defined in terms of the finite set of samples x[0],
> x[1], ... x[N-1] that fully define the periodic sequence and, these
> discrete sequence should be able to fully define the continuous-time
> signal it was sampled from (assuming appropriate bandlimiting, which we
> are pushing the envelope a little).  now, usually, we think of the
> ideal interpolation formula for x(t)  is:
>
>            +inf
>     x(t) = SUM{ x[n] * sinc(t - n) }
>           n=-inf
>
>            N-1     +inf
>          = SUM{    SUM{ x[n+m*N] * sinc(t - (n+m*N)) } }
>            n=0    m=-inf
>
> but since x[n+m*N] = x[n] for any integer m, then
>
>
>            N-1     +inf
>     x(t) = SUM{    SUM{ x[n] * sinc(t - (n+m*N)) } }
>            n=0    m=-inf
>
>            N-1         +inf
>          = SUM{ x[n] * SUM{ sinc(t - n - m*N) } }
>            n=0        m=-inf
>
>            N-1
>          = SUM{ x[n] * h(t-n) }
>            n=0
>
> now this interpolation function,
>
>           +inf
>     h(t) = SUM{ sinc(t - m*N) } }
>           m=-inf
>
> is periodic with period N, h(t+N) = h(t) for all t, as we expect.  so
> what does that periodic interpolation function look like?  i've
> pondered this a while and first posted this to comp.dsp in 2001:
>
>
>
> take a look at that.   Adrian Hey got into it enough to see the thing
> that was bothering me a little.  anyway, the result i get for a closed
> for periodic h(t) is
>
>                { sin(pi*t)/(N*sin(pi*t/N))       N odd
>         h(t) = {
>                { sin(pi*t)/(N*tan(pi*t/N))       N even
>
> from above you get show
>
>           +inf
>     h(t) = SUM{ sin(pi*(t - m*N))/(pi*(t - m*N)) } }
>           m=-inf
>
>                       +inf
>          = sin(pi*t) * SUM{ 1/(pi*(t - m*N)) } }                N even
>                       m=-inf
>
>                       +inf
>          = sin(pi*t) * SUM{ ((-1)^m)/(pi*(t - m*N)) } }         N odd
>                       m=-inf
>
>
> >  I'm not sure if there is a significant difference in the two reconstruction
> > formulas for N and N+1 as N approaches infinity.  Thoughts?
>
> i just don't want to make that assumption and equality holds exactly
> for the two cases, even and odd.  one case the formula looks just like
> the Dirichlet interpolation commonly done for the FFT and the other,
> it's slightly different, but it *is* different.  in the even case, the
> tails of those sinc() functions have bumps of opposite polarity so they
> cancel themselves out more than in the odd case where the tails, though
> descreasing in amplitude as 1/x, have their bumps of the same polarity,
> so they team up.  so i'm pretty sure the formula is correct (the
> 1/tan() reduces the amplitude more than the 1/sin() as one approaches
> midway between the two main pulses.  it also came up (indirectly) with
> tthese two mathematical identities:
>
>                    +inf
>         1/tan(t) = SUM{ 1/(t - m*pi) }
>                   m=-inf
>
>                    +inf
>         1/sin(t) = SUM{ ((-1)^m)/(t - m*pi) }
>                   m=-inf
>
> which i have not been able to prove directly.
>
> if someone has it, i would like some insight for why the Dirichlet
> formula applies exactly only for N odd, not exactly for N even,
> although it applies exactly for both N odd or N even in the case of
> interpolating DFT output to get the DTFT of the time-limited x[n].
>
> do you guys see what it is that is bothering me?  or proving more
> directly the two math identities above would be gratifying.  i have not
> been able to do that directly, as of yet.

well, i suspected that this was scooped by someone else, but i didn't
expect so recently:

T. Schanze, "Sinc interpolation of discrete periodic signals", IEEE
Transactions on Signal Processing, vol. 43, pp. 1502-1503, June 1995.

i don't get IEEE, but if someone who has free access to the pdf file
wants to email it to me, i would not complain. (screw IEEE.)

http://iul.eng.fiu.edu/candocia/Publications/candocia_sp.pdf

and they get the same results as me.  dunno how the methods differ, if
they do.

just FYI,

r b-j

```
 0
Reply rbj (4087) 11/29/2006 6:07:01 AM

22 Replies
47 Views

Similar Articles

12/11/2013 1:09:44 PM
page loaded in 63705 ms. (0)

Similar Artilces:

name of fft(log(fft())) algorithm?
What is the name of the algorithm where one takes the fft of the log amplitude of the fft of a waveform? Where might one find more information (books, publications, web ...) about this procedure? It seems to be useful for detecting signals which have lots of harmonic content (some musical instrument notes). Thanks. -- Ron Nicholson rhn AT nicholson DOT com http://www.nicholson.com/rhn/ #include <canonical.disclaimer> // only my own opinions, etc. Ronald H. Nicholson, Jr. <rhn@nojunk.rahul.net> wrote in message news:<bhkgee\$6v7\$1@blue.rahul.net>... > What i...

FFT Time Scaling
Hi guys, I get something like t=1e-9; Which is something like nanoseconds. I need N(Number of samples), Fs(Sampling Frequency) & F(Frequency) to do a sinewave for FFT. However, when my t is so small, my F had to be big. Can anyone please tell me how do I scale my time correctly so I get a nanosecond-frequency graph. Here is my sample code: F=10;Fs=2048;N=2^10;T=1;t=0:T/N:T; %scaling starts... x= sin(2*pi*F*1e-9*t); subplot(2,1,1);plot(t,x); y = abs(fft(x))/N*2; f = Fs*(0:N/2)/N; subplot(2,1,2);plot(f,y(1:N/2+1)); ...

Signal Complexity effect on FFT Execution Time
I'm currently using the kiss FFT library in 32-bit fixed point mode in some software. I'm always using the same length FFT e.g. 1024-point. I want to know whether the average execution time of the FFT algorithm is likely to be dependent on the input signal waveform complexity. i.e. would you expect it to run faster for a purely DC signal, versus a complex arbitrary waveform? Thanks in advance. Does that mean that the order O( ) off the FFT algorithm is constant, and therefore the execution time depends only the execution speed of the particular mix of number arithmetic on the CPU?...

paper comparing time complexity of compression algorithms
Hi, I'm searching for a paper that compares the time complexity for various compression algorithms (notably gzip and bzip2) for text data up to 5MB. Is there some resource for that? While I'm at it: is there some paper that describes the concepts of gzip and bzip2? So far I have not been very lucky to find something appropriate. -- Knut stolze wrote: > I'm searching for a paper that compares the time complexity for various > compression algorithms (notably gzip and bzip2) for text data up to > 5MB. Is there some resource for that? Do you mean time complexity as i...

question on taking FFT of a negative-time signal?
Hi all, I want to ask about taking FFT of a signal discrete-time whose indices are limited in [-6, +6] and with 13 data points. x[n]= 1, for n=-2 .. +2; 0, for other n in [-6, +6] However, in Matlab all indices start from 1, so I have to input this sequence as x=[0 0 0 0 1 1 1 1 1 0 0 0 0]; y=fftshift(fft(x)); since the indeces have been shifted, so the y has no zero imaginary part(the original input sequence is real and even so y should have zero imaginary parts) Now how to show the DFT of the original double-sided signal from -6 to 6? How to make y's imaginary parts zero? --...

time-series analysis using Math::FFT
Hi All, I'm trying to generate a real-valued time-series with a power-spectrum having a slope of -1 (in log-log) (called 1 over f noise). So, I start in the frequency domain and define the real and imaginary spectral components with the slope I want, and I use the Math::FFT invcdft() function to invert that complex spectrum to the time domain. It works quite well, but so far I've been generating complex time-series and tossing away the imaginary part. What I should be doing is generating a real-valued time-series by setting the negative frequency components to be the compl...

Recommend Compression Algorithm for Student Real-Time Videoconferencing Project
Hi, I am a university student in a Real-Time Embedded Systems class.A partner and I are working on developing a real-time video conferencing system using 2 Pentium systems (yes, that's original Pentium) running the VxWorks real-time operating system. I recently spent some time investigating compression algorithm choices, and I decided to use arithmetic compression, as it seemed to provide a good balance between compression ratio and complexity of coding. To elaborate, I tested a couple of codecs I found at http://datacompression.info on a test image and found that the result was about 3...

Bitwise 2K7
BITWISE is an annual online programming contest. The contest is organized by the Computer Science and Engineering Department Society of IIT Kharagpur, on the second Sunday of February every year. The contest is time constrained and you would be expected to submit solutions to some of the toughest programming and algorithms challenges in a short span of 12 hours. Prizes worth 120,000 Rs or \$2600 at stake. Visit http://www.bitwise.iitkgp.ernet.in for more details. Registrations close on February 4th. ...

Possible new faster algorithms for FFT of 3^n and 6^n sizes.
Hello, I think I may have discovered new faster algorithms for doing FFTs on vectors of length 3^n and 6^n. Complete source code plus a derivation may be found at: http://locklessinc.com/articles/non_power_of_2_fft/ Basically, the trick is to use the first sixth root of unity as a complex axis instead of the imaginary number i. Converting into this form takes O(3n) operations, as does converting back. The advantage is that multiplying numbers by third or sixth roots of unity in this form becomes trivial. The result is that large numbers of operations can be removed for FFTs of r...

FFT+inverse FFT
Hey! I'm a beginner at IDL and have problem with FFT. I'm trying to perform 2d-FFT but the code doesn't work properly even on test images. So I create an image, make the Fourier transform, then the inverse Fourier transform and finally I expect to get the initial image. But the resulting image is the initial one, reversed with respect to the center. My code: nx=256L x1=findgen(nx)-nx/2.0+1.0 x2=findgen(nx)-nx/2.0+1.0 ytest=fltarr(nx,nx) for i=0l,nx-1 do begin for j=0l,nx-1 do begin if (x1[i] le 20.0 and x1[i] ge 0.0 and x2[j] le 20.0 and x2[j] ge 0.0) then begin...

time defference betweem two time when time is given in numeric
i want time defferance between two times,,, which given in numeric formate,,, &nbsp; vi si attached,.,, with,, &nbsp; if any one can help me... :smileysad: time difference.vi: http://forums.ni.com/attachments/ni/170/187064/1/time difference.vi Hiii, Conselis &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Thanks for the reply man, yes thats wat i couldnt understand that it is already in the numeric format and i just have to change the format ...

Converting FFT to inverse-FFT
I'm thinking about having a play with a software-based radio, based on a heavily hacked-up radio and an IF-to-AF down-converter (basically, tap the IF, downconvert to AF, then use a sound card to digitise it). In any case, enough about the hardware -- that's not the issue. I've got some code for an FFT from the O'Reilly "C++ Cookbook" (section 11.17, example 11-33): template<class Iter_T> void fft(Iter_T a, Iter_T b, int log2n) { typedef typename iterator_traits<Iter_T>::value_type complex; const complex J(0, 1); int n = 1 <<...

Perl time and Mysql time
HI, All I have a problem to compare the time between current time in Perl and MySQL time, I use to compare the time according to the Year, after that the month, and day, and hour and minutes. The following is the way on how I compare the time if (current_year < data_year) then ERROR_YEAR elsif (current_year >= data_year) then OKAY_YEAR if(OKAY_YEAR) then if(current_month < data_month) then ERROR_MONTH elseif(current_month >= data_month) then OKAY_MONTH if(OKAY_MONTH) then if(current_day < data_day) then ERROR_DAY elseif(current_day >= data_day) then OKAY_DAY if(OKAY...

Time origin of "Global Start Time" in Output Node of Time Loop
Hi All, &nbsp; Please, do you know how the time returned by Global Time Start (after converting in milliseconds) in the Output Node of a Timed Loop is related to the time returned by ?Tick Count (ms)? (if the latter is read at the very start of the loop)? &nbsp; The look similar but they are not the same. &nbsp; Is it right that the time returned by Time in the Node of an Event Structure is the value of ?Tick Count (ms)? when the event takes place? &nbsp; Have an awesome day, &nbsp; LucaQ ...

FFT
Hi everyone, i've to develop a FFT code in VHDL which could be for 256 point or generic for more points... . Has anybody synthetizable VHDL code? Thank you! you have it below mentiond link , but the code is in verilog ;) http://www.opencores.org/projects.cgi/web/cf_fft/overview ALI bird.of.thrown@gmail.com wrote: > Hi everyone, i've to develop a FFT code in VHDL which could be for 256 > point or generic for more points... . Has anybody synthetizable VHDL > code? Thank you! Go to Tyder website www.tyder.com Bob bird.of.thrown@gmail.com wrote: > Hi everyone, i've t...

cookie expire time and time zones
Hi I have asked this question in alt.php as the time() function as used in setcookie belongs to php - or does it belong equally in the javascript camp - bit confused about that. Anyway, can anyone here put me straight on the following: I had a look at the time() function came across this: "To clarify, it seems this function returns the time of the computer's clock and does not do any timezone adjustments to return GMT, so you are given the local time. The description says that it's supposed to return the number of seconds from 1970 12am GMT, when the seconds are actually counte...

How to see if a time is within two other times.
I need to modify a script in such a way that it checks the current time (according to the server) to determine if the current time falls within a particular time span such as midnight to 4:00 am. For example: if (current_time > earliest_time_request_accepted && current_time < latest_time_request_accepted) { ...process request... } else { print "please try your request at a different time."; } I struggle with date-time values in perl. Ninja67 wrote: > I need to modify a script in such a way that it checks the current time > (according to the server) to de...

time coversions and effect of time drift.
Hi, I am looking for functions in 'C' to convert the struct timeval into double, add milliseconds to struct timeval. Does anybody know how to do it. What is the effect of "time drift" in time in linux. How can this be taken care of ?. Scenario ( ) { StartTime = gettimeofday ( ) ; PlayTime = StartTime + 2millseconds ; while (1) { Do Some Work ; Now = gettimeofday ( ) ; If (Now == PlayTime) ...

Time limit for NTP to do timing correction??
It is said that there is a limit of the time difference that NTP would correct the timing between the server and client. That is, if the time difference is more than the limit, NTP would just stop its service and quit without doing any time correction. Any one knows what is this limit for NTP Release 4 (for Microsoft Windows NT) ? And, how to change this limit? Cheers :> Crystal wrote: > It is said that there is a limit of the time difference that NTP would > correct the timing between the server and client. That is, if the time > difference is more than the limit, NTP would just ...

Processing Time Vs Interrupt Time
Im using ez430-RF2500T. When the board is linked to the PC via Zigbee, it would start to convert analog data to digital using ADC interrupt. The digital data will be processed before sending it to the PC. What i want to know is whether my processing time is faster than interrupt time? Is there a way to test the speed? The reason for it is because i have 2 channels. Each channel goes through different proccessing functions. Thus, I want to make sure that the correct analog data goes thru the function. On Jan 12, 1:14=A0pm, "f0rep1ay" <gl...@Hotmail.com> wrote: > What i ...