Thread Subject: DFT the same as sampled Foureir transform?

Hi all,

I have the following question regarding the relation between DFT and Foureir
Transform.

Suppose I have a sequence of discrete time signal x0, x1, x2, ... xn, ...
(possibly infinite length), uniformly spaced in time, with spacing T; that's
to say, x0 is the signal value at time 0, x1 is the signal value at time
1*T, x2 is the signal value at time 2*T, ...

and the DFT of this sequence is F1(v).

Also, for this sequence of signal, I have an ordinary Foureir Transform
F2(v), I guess it's called DTFT.

I plan to sample the F2(v) to obtain the discrete version of the F2(v) and
call it F3(v).

My question is:

Under what condition and for what kind of signal x's do the DFT F1(v) and
sampled version of ordinary FT F3(v) equate? I want F1(v) and F3(v) to be
exactly the same... what conditions shall I impose?

Thanks!

"Mike" <meatheadIV@gmail.com> wrote in message
news:f33fqk$2f8$1@news.Stanford.EDU...
> Hi all,
>
> I have the following question regarding the relation between DFT and
> Foureir Transform.
>
> Suppose I have a sequence of discrete time signal x0, x1, x2, ... xn, ...
> (possibly infinite length), uniformly spaced in time, with spacing T;
> that's to say, x0 is the signal value at time 0, x1 is the signal value at
> time 1*T, x2 is the signal value at time 2*T, ...
>
> and the DFT of this sequence is F1(v).
>
> Also, for this sequence of signal, I have an ordinary Foureir Transform
> F2(v), I guess it's called DTFT.
>
> I plan to sample the F2(v) to obtain the discrete version of the F2(v) and
> call it F3(v).
>
> My question is:
>
> Under what condition and for what kind of signal x's do the DFT F1(v) and
> sampled version of ordinary FT F3(v) equate? I want F1(v) and F3(v) to be
> exactly the same... what conditions shall I impose?
>
> Thanks!

I have this diagram below which I think will help answer your question.

http://12000.org/my_notes/transforms/index.htm

Nasser

Mike wrote:
> Hi all,
>
> I have the following question regarding the relation between DFT and Foureir
> Transform.

Your misspelling is too consistent to by a typo. The guy's name was
Fourier!


> Suppose I have a sequence of discrete time signal x0, x1, x2, ... xn, ...
> (possibly infinite length), uniformly spaced in time, with spacing T; that's
> to say, x0 is the signal value at time 0, x1 is the signal value at time
> 1*T, x2 is the signal value at time 2*T, ...
>
> and the DFT of this sequence is F1(v).

You are mixing up all kinds of objects here.

For infinite length sequences that are square-summable and represent
evenly sampled bandlimited finite-energy signals, you can use the DTFT
(if it converges), or the z-transform. For periodic, discrete and
infinitely long sequences the z-transform doesn't converge, and you
need the DFS (discrete Fourier series).

For finite length vectors, you can use the DFT (discrete Fourier
transform). The DFS and the DFT are closely related.

There are infinitely many distinct sequences x[n] with DTFT X(w) where
the inverse DFT y of the unifomly sampled DTFT, namely

y = IDFT{ X(2 pi k/N) }, k=0,1,...,N-1,

are all equal. For some of them, you have y[n] = x[n], n=0,1,...,N-1,
for others you don't.

Did this help?

Regards,
Andor

Andor wrote:
> Mike wrote:
>> Hi all,
>>
>> I have the following question regarding the relation between DFT and Foureir
>> Transform.
>
> Your misspelling is too consistent to be a typo. The guy's name was
> Fourier!

And it's pronounced Foo-ree-yay or Foor-yay). Maybe that will help.

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

On 24 May, 09:45, "Mike" <meathea...@gmail.com> wrote:
> Hi all,
>
> I have the following question regarding the relation between DFT and Foureir
> Transform.

Fourier. After Jean Baptiste Joseph Fourier. Read his biography

http://www-history.mcs.st-andrews.ac.uk/Mathematicians/Fourier.html

and maybe you get enough respect for him to spell his name correctly.

> Suppose I have a sequence of discrete time signal x0, x1, x2, ... xn, ...
> (possibly infinite length), uniformly spaced in time, with spacing T; that's
> to say, x0 is the signal value at time 0, x1 is the signal value at time
> 1*T, x2 is the signal value at time 2*T, ...
>
> and the DFT of this sequence is F1(v).

Wrong. The DFT is not defined for a sequence of "possibly
infinite length." The DFT is defined for discrete-time sequences
of *finite* length.

> Also, for this sequence of signal,

What is a "sequence of signal"?

> I have an ordinary Foureir Transform
> F2(v), I guess it's called DTFT.

No, you don't. I have no idea what a "sequence of signal" is.
The Dirscrete-Time Fourier transform is defined for a discrete-
time sequence of *infinite* length.

> I plan to sample the F2(v) to obtain the discrete version of the F2(v) and
> call it F3(v).

No need to do that, the discrete-time signals are already
"sampled". Sampling is a way to convert from a contionuous-time
signal to a discrete-time signal. This can be done for signals
of either finite of (formally) infinite duration in time.

> My question is:
>
> Under what condition and for what kind of signal x's do the DFT F1(v) and
> sampled version of ordinary FT F3(v) equate? I want F1(v) and F3(v) to be
> exactly the same... what conditions shall I impose?

There is an answer to such questions. Not the one you expect
or will be happy to hear, but an answer to questions such as
yours exists. Now, I took very great care to avoid "your
question" in the past sentence, because you don't have
the necessary basis to formulate the proper question.
Before asking again, take your time to read up on, and
contemplate, the different variations of the Fourier transform.

You will have four cases to consider:

1) Countinuos time, infinite duration
2) Continuous time, finite duration
3) Discrete time, infinite duration
4) Discrete time, finite duration

Once you have done that, you will be able to formulate
a question which makes sense and, consequently, can be
answered in a meaningful way.

Rune

"Andor" <andor.bariska@gmail.com> wrote in message
news:1179998515.753120.45840@h2g2000hsg.googlegroups.com...
> Mike wrote:
>> Hi all,
>>
>> I have the following question regarding the relation between DFT and
>> Foureir
>> Transform.
>
> Your misspelling is too consistent to by a typo. The guy's name was
> Fourier!
>
>
>> Suppose I have a sequence of discrete time signal x0, x1, x2, ... xn, ...
>> (possibly infinite length), uniformly spaced in time, with spacing T;
>> that's
>> to say, x0 is the signal value at time 0, x1 is the signal value at time
>> 1*T, x2 is the signal value at time 2*T, ...
>>
>> and the DFT of this sequence is F1(v).
>
> You are mixing up all kinds of objects here.
>
> For infinite length sequences that are square-summable and represent
> evenly sampled bandlimited finite-energy signals, you can use the DTFT
> (if it converges), or the z-transform. For periodic, discrete and
> infinitely long sequences the z-transform doesn't converge, and you
> need the DFS (discrete Fourier series).
>
> For finite length vectors, you can use the DFT (discrete Fourier
> transform). The DFS and the DFT are closely related.
>
> There are infinitely many distinct sequences x[n] with DTFT X(w) where
> the inverse DFT y of the unifomly sampled DTFT, namely
>
> y = IDFT{ X(2 pi k/N) }, k=0,1,...,N-1,
>
> are all equal. For some of them, you have y[n] = x[n], n=0,1,...,N-1,
> for others you don't.
>
> Did this help?
>
> Regards,
> Andor
>

Thanks Andor! It's midnight so I was too sleepy. Yes, it should be
"Fourier". Thanks for pointing it out!

I agree my question is not well-posed. Here is a reformulation:

Given a continuous time signal x(t), infinitely long. Sample it to obtain
discrete time sequence x0, x1, x2, ..., xn, ..., infinitely long, with
uniform samples spaced at T apart.

Now I do two things:

(1) Truncate the above sequence to make it finite, x0, x1, ..., xn, and take
the DFT of the truncated sequence. Call the DFT F1(v). (Capitalized letters
denote spectrum domain)

(2) Without truncation, taking the DTFT of the infinitely long sequence x0,
x1, ..., xn, .... Call the DTFT F2(v). And then take one period of F2(v),
since it is periodic, and then sample F2(v) in the frequency domain to
discretize it. Call the result F3(v), which is the discretized version of
the one period of F2(v).

---------------------

Both (1) and (2) yield vectors of length n in the spectrum domain,
representing the discretized version of the spectrum.

My question is: under what conditions do these two vectors of discretized
spectrum equate?

Thanks again!

"Nasser Abbasi" <nma@12000.org> wrote in message
news:Zlc5i.36415$AR3.18889@newsfe07.phx...
>
> "Mike" <meatheadIV@gmail.com> wrote in message
> news:f33fqk$2f8$1@news.Stanford.EDU...
>> Hi all,
>>
>> I have the following question regarding the relation between DFT and
>> Foureir Transform.
>>
>> Suppose I have a sequence of discrete time signal x0, x1, x2, ... xn, ...
>> (possibly infinite length), uniformly spaced in time, with spacing T;
>> that's to say, x0 is the signal value at time 0, x1 is the signal value
>> at time 1*T, x2 is the signal value at time 2*T, ...
>>
>> and the DFT of this sequence is F1(v).
>>
>> Also, for this sequence of signal, I have an ordinary Foureir Transform
>> F2(v), I guess it's called DTFT.
>>
>> I plan to sample the F2(v) to obtain the discrete version of the F2(v)
>> and call it F3(v).
>>
>> My question is:
>>
>> Under what condition and for what kind of signal x's do the DFT F1(v) and
>> sampled version of ordinary FT F3(v) equate? I want F1(v) and F3(v) to be
>> exactly the same... what conditions shall I impose?
>>
>> Thanks!
>
> I have this diagram below which I think will help answer your question.
>
> http://12000.org/my_notes/transforms/index.htm
>
> Nasser


Thanks Nasser!

"Rune Allnor" <allnor@tele.ntnu.no> wrote in message
news:1180021783.330512.237760@w5g2000hsg.googlegroups.com...
> On 24 May, 09:45, "Mike" <meathea...@gmail.com> wrote:
>> Hi all,
>>
>> I have the following question regarding the relation between DFT and
>> Foureir
>> Transform.
>
> Fourier. After Jean Baptiste Joseph Fourier. Read his biography
>
> http://www-history.mcs.st-andrews.ac.uk/Mathematicians/Fourier.html
>
> and maybe you get enough respect for him to spell his name correctly.
>
>> Suppose I have a sequence of discrete time signal x0, x1, x2, ... xn, ...
>> (possibly infinite length), uniformly spaced in time, with spacing T;
>> that's
>> to say, x0 is the signal value at time 0, x1 is the signal value at time
>> 1*T, x2 is the signal value at time 2*T, ...
>>
>> and the DFT of this sequence is F1(v).
>
> Wrong. The DFT is not defined for a sequence of "possibly
> infinite length." The DFT is defined for discrete-time sequences
> of *finite* length.
>
>> Also, for this sequence of signal,
>
> What is a "sequence of signal"?
>
>> I have an ordinary Foureir Transform
>> F2(v), I guess it's called DTFT.
>
> No, you don't. I have no idea what a "sequence of signal" is.
> The Dirscrete-Time Fourier transform is defined for a discrete-
> time sequence of *infinite* length.
>
>> I plan to sample the F2(v) to obtain the discrete version of the F2(v)
>> and
>> call it F3(v).
>
> No need to do that, the discrete-time signals are already
> "sampled". Sampling is a way to convert from a contionuous-time
> signal to a discrete-time signal. This can be done for signals
> of either finite of (formally) infinite duration in time.
>
>> My question is:
>>
>> Under what condition and for what kind of signal x's do the DFT F1(v) and
>> sampled version of ordinary FT F3(v) equate? I want F1(v) and F3(v) to be
>> exactly the same... what conditions shall I impose?
>
> There is an answer to such questions. Not the one you expect
> or will be happy to hear, but an answer to questions such as
> yours exists. Now, I took very great care to avoid "your
> question" in the past sentence, because you don't have
> the necessary basis to formulate the proper question.
> Before asking again, take your time to read up on, and
> contemplate, the different variations of the Fourier transform.
>
> You will have four cases to consider:
>
> 1) Countinuos time, infinite duration
> 2) Continuous time, finite duration
> 3) Discrete time, infinite duration
> 4) Discrete time, finite duration
>
> Once you have done that, you will be able to formulate
> a question which makes sense and, consequently, can be
> answered in a meaningful way.
>
> Rune
>


Thanks Rune! It's midnight so I was too sleepy. Yes, it should be "Fourier".
Thanks for pointing it out!

I agree my question is not well-posed. Here is a reformulation:

Given a continuous time signal x(t), infinitely long. Sample it to obtain
discrete time sequence x0, x1, x2, ..., xn, ..., infinitely long, with
uniform samples spaced at T apart.

Now I do two things:

(1) Truncate the above sequence to make it finite, x0, x1, ..., xn, and take
the DFT of the truncated sequence. Call the DFT F1(v). (Capitalized letters
denote spectrum domain)

(2) Without truncation, taking the DTFT of the infinitely long sequence x0,
x1, ..., xn, .... Call the DTFT F2(v). And then take one period of F2(v),
since it is periodic, and then sample F2(v) in the frequency domain to
discretize it. Call the result F3(v), which is the discretized version of
the one period of F2(v).

---------------------

Both (1) and (2) yield vectors of length n in the spectrum domain,
representing the discretized version of the spectrum.

My question is: under what conditions do these two vectors of discretized
spectrum equate?

Thanks again!

"Mike" <meatheadIV@gmail.com> writes:
> [...]
> I agree my question is not well-posed. Here is a reformulation:
>
> Given a continuous time signal x(t), infinitely long. Sample it to obtain
> discrete time sequence x0, x1, x2, ..., xn, ..., infinitely long, with
> uniform samples spaced at T apart.
>
> Now I do two things:
>
> (1) Truncate the above sequence to make it finite, x0, x1, ..., xn, and take
> the DFT of the truncated sequence. Call the DFT F1(v). (Capitalized letters
> denote spectrum domain)
>
> (2) Without truncation, taking the DTFT of the infinitely long sequence x0,
> x1, ..., xn, .... Call the DTFT F2(v). And then take one period of F2(v),
> since it is periodic, and then sample F2(v) in the frequency domain to
> discretize it. Call the result F3(v), which is the discretized version of
> the one period of F2(v).
>
> ---------------------
>
> Both (1) and (2) yield vectors of length n in the spectrum domain,
> representing the discretized version of the spectrum.
>
> My question is: under what conditions do these two vectors of discretized
> spectrum equate?

When x(t) is periodic with period n*T.
--
% Randy Yates % "Maybe one day I'll feel her cold embrace,
%% Fuquay-Varina, NC % and kiss her interface,
%%% 919-577-9882 % til then, I'll leave her alone."
%%%% <yates@ieee.org> % 'Yours Truly, 2095', *Time*, ELO
http://home.earthlink.net/~yatescr

On 24 May, 18:56, "Mike" <meathea...@gmail.com> wrote:
> "Rune Allnor" <all...@tele.ntnu.no> wrote in message
>
> news:1180021783.330512.237760@w5g2000hsg.googlegroups.com...
>
>
>
>
>
> > On 24 May, 09:45, "Mike" <meathea...@gmail.com> wrote:
> >> Hi all,
>
> >> I have the following question regarding the relation between DFT and
> >> Foureir
> >> Transform.
>
> > Fourier. After Jean Baptiste Joseph Fourier. Read his biography
>
> >http://www-history.mcs.st-andrews.ac.uk/Mathematicians/Fourier.html
>
> > and maybe you get enough respect for him to spell his name correctly.
>
> >> Suppose I have a sequence of discrete time signal x0, x1, x2, ... xn, ...
> >> (possibly infinite length), uniformly spaced in time, with spacing T;
> >> that's
> >> to say, x0 is the signal value at time 0, x1 is the signal value at time
> >> 1*T, x2 is the signal value at time 2*T, ...
>
> >> and the DFT of this sequence is F1(v).
>
> > Wrong. The DFT is not defined for a sequence of "possibly
> > infinite length." The DFT is defined for discrete-time sequences
> > of *finite* length.
>
> >> Also, for this sequence of signal,
>
> > What is a "sequence of signal"?
>
> >> I have an ordinary Foureir Transform
> >> F2(v), I guess it's called DTFT.
>
> > No, you don't. I have no idea what a "sequence of signal" is.
> > The Dirscrete-Time Fourier transform is defined for a discrete-
> > time sequence of *infinite* length.
>
> >> I plan to sample the F2(v) to obtain the discrete version of the F2(v)
> >> and
> >> call it F3(v).
>
> > No need to do that, the discrete-time signals are already
> > "sampled". Sampling is a way to convert from a contionuous-time
> > signal to a discrete-time signal. This can be done for signals
> > of either finite of (formally) infinite duration in time.
>
> >> My question is:
>
> >> Under what condition and for what kind of signal x's do the DFT F1(v) and
> >> sampled version of ordinary FT F3(v) equate? I want F1(v) and F3(v) to be
> >> exactly the same... what conditions shall I impose?
>
> > There is an answer to such questions. Not the one you expect
> > or will be happy to hear, but an answer to questions such as
> > yours exists. Now, I took very great care to avoid "your
> > question" in the past sentence, because you don't have
> > the necessary basis to formulate the proper question.
> > Before asking again, take your time to read up on, and
> > contemplate, the different variations of the Fourier transform.
>
> > You will have four cases to consider:
>
> > 1) Countinuos time, infinite duration
> > 2) Continuous time, finite duration
> > 3) Discrete time, infinite duration
> > 4) Discrete time, finite duration
>
> > Once you have done that, you will be able to formulate
> > a question which makes sense and, consequently, can be
> > answered in a meaningful way.
>
> > Rune
>
> Thanks Rune! It's midnight so I was too sleepy. Yes, it should be "Fourier".
> Thanks for pointing it out!
>
> I agree my question is not well-posed. Here is a reformulation:
>
> Given a continuous time signal x(t), infinitely long. Sample it to obtain
> discrete time sequence x0, x1, x2, ..., xn, ..., infinitely long, with
> uniform samples spaced at T apart.
>
> Now I do two things:
>
> (1) Truncate the above sequence to make it finite, x0, x1, ..., xn, and take
> the DFT of the truncated sequence. Call the DFT F1(v). (Capitalized letters
> denote spectrum domain)
>
> (2) Without truncation, taking the DTFT of the infinitely long sequence x0,
> x1, ..., xn, .... Call the DTFT F2(v). And then take one period of F2(v),
> since it is periodic, and then sample F2(v) in the frequency domain to
> discretize it. Call the result F3(v), which is the discretized version of
> the one period of F2(v).
>
> ---------------------
>
> Both (1) and (2) yield vectors of length n in the spectrum domain,
> representing the discretized version of the spectrum.
>
> My question is: under what conditions do these two vectors of discretized
> spectrum equate?

IFF your infinitely long sequence is truly periodic AND
you happen to truncate it so that you have exactly one
period worth of data, then -- and only then -- your DFT
and your DTFT are equal.

There are only three problems with this:

1) Real-life data series from infinite-duration processes
   are never truly priodic.
2) Even if they are *almost* periodic, you can't expect
   to sample exactly one period's worth of data.
3) You are stuck with the DFT as a computational tool
   anyway, since it is highly impragtical to implement
   infinite summations and sample infinite amounts
   of data.

Rune

Randy Yates <yates@ieee.org> writes:

> "Mike" <meatheadIV@gmail.com> writes:
>> [...]
>> I agree my question is not well-posed. Here is a reformulation:
>>
>> Given a continuous time signal x(t), infinitely long. Sample it to obtain
>> discrete time sequence x0, x1, x2, ..., xn, ..., infinitely long, with
>> uniform samples spaced at T apart.
>>
>> Now I do two things:
>>
>> (1) Truncate the above sequence to make it finite, x0, x1, ..., xn, and take
>> the DFT of the truncated sequence. Call the DFT F1(v). (Capitalized letters
>> denote spectrum domain)
>>
>> (2) Without truncation, taking the DTFT of the infinitely long sequence x0,
>> x1, ..., xn, .... Call the DTFT F2(v). And then take one period of F2(v),
>> since it is periodic, and then sample F2(v) in the frequency domain to
>> discretize it. Call the result F3(v), which is the discretized version of
>> the one period of F2(v).
>>
>> ---------------------
>>
>> Both (1) and (2) yield vectors of length n in the spectrum domain,
>> representing the discretized version of the spectrum.
>>
>> My question is: under what conditions do these two vectors of discretized
>> spectrum equate?
>
> When x(t) is periodic with period n*T.

PS: You probably meant to label the sequences x0, x1, ..., x(n-1), making
n samples.
--
% Randy Yates % "Remember the good old 1980's, when
%% Fuquay-Varina, NC % things were so uncomplicated?"
%%% 919-577-9882 % 'Ticket To The Moon'
%%%% <yates@ieee.org> % *Time*, Electric Light Orchestra
http://home.earthlink.net/~yatescr

"Randy Yates" <yates@ieee.org> wrote in message
news:m37iqydu5z.fsf@ieee.org...
> "Mike" <meatheadIV@gmail.com> writes:
>> [...]
>> I agree my question is not well-posed. Here is a reformulation:
>>
>> Given a continuous time signal x(t), infinitely long. Sample it to obtain
>> discrete time sequence x0, x1, x2, ..., xn, ..., infinitely long, with
>> uniform samples spaced at T apart.
>>
>> Now I do two things:
>>
>> (1) Truncate the above sequence to make it finite, x0, x1, ..., xn, and
>> take
>> the DFT of the truncated sequence. Call the DFT F1(v). (Capitalized
>> letters
>> denote spectrum domain)
>>
>> (2) Without truncation, taking the DTFT of the infinitely long sequence
>> x0,
>> x1, ..., xn, .... Call the DTFT F2(v). And then take one period of F2(v),
>> since it is periodic, and then sample F2(v) in the frequency domain to
>> discretize it. Call the result F3(v), which is the discretized version of
>> the one period of F2(v).
>>
>> ---------------------
>>
>> Both (1) and (2) yield vectors of length n in the spectrum domain,
>> representing the discretized version of the spectrum.
>>
>> My question is: under what conditions do these two vectors of discretized
>> spectrum equate?
>
> When x(t) is periodic with period n*T.
> --
> % Randy Yates % "Maybe one day I'll feel her cold
> embrace,
> %% Fuquay-Varina, NC % and kiss her
> interface,
> %%% 919-577-9882 % til then, I'll leave her
> alone."
> %%%% <yates@ieee.org> % 'Yours Truly, 2095', *Time*, ELO
> http://home.earthlink.net/~yatescr

Thanks Randy! The original signal x(t) is not periodic. I guess my next
question is:

How to handle such a situation and get an approximation error that is as
small as possible?

"Rune Allnor" <allnor@tele.ntnu.no> wrote in message
news:1180026933.108924.307690@u30g2000hsc.googlegroups.com...
> On 24 May, 18:56, "Mike" <meathea...@gmail.com> wrote:
>> "Rune Allnor" <all...@tele.ntnu.no> wrote in message
>>
>> news:1180021783.330512.237760@w5g2000hsg.googlegroups.com...
>>
>>
>>
>>
>>
>> > On 24 May, 09:45, "Mike" <meathea...@gmail.com> wrote:
>> >> Hi all,
>>
>> >> I have the following question regarding the relation between DFT and
>> >> Foureir
>> >> Transform.
>>
>> > Fourier. After Jean Baptiste Joseph Fourier. Read his biography
>>
>> >http://www-history.mcs.st-andrews.ac.uk/Mathematicians/Fourier.html
>>
>> > and maybe you get enough respect for him to spell his name correctly.
>>
>> >> Suppose I have a sequence of discrete time signal x0, x1, x2, ... xn,
>> >> ...
>> >> (possibly infinite length), uniformly spaced in time, with spacing T;
>> >> that's
>> >> to say, x0 is the signal value at time 0, x1 is the signal value at
>> >> time
>> >> 1*T, x2 is the signal value at time 2*T, ...
>>
>> >> and the DFT of this sequence is F1(v).
>>
>> > Wrong. The DFT is not defined for a sequence of "possibly
>> > infinite length." The DFT is defined for discrete-time sequences
>> > of *finite* length.
>>
>> >> Also, for this sequence of signal,
>>
>> > What is a "sequence of signal"?
>>
>> >> I have an ordinary Foureir Transform
>> >> F2(v), I guess it's called DTFT.
>>
>> > No, you don't. I have no idea what a "sequence of signal" is.
>> > The Dirscrete-Time Fourier transform is defined for a discrete-
>> > time sequence of *infinite* length.
>>
>> >> I plan to sample the F2(v) to obtain the discrete version of the F2(v)
>> >> and
>> >> call it F3(v).
>>
>> > No need to do that, the discrete-time signals are already
>> > "sampled". Sampling is a way to convert from a contionuous-time
>> > signal to a discrete-time signal. This can be done for signals
>> > of either finite of (formally) infinite duration in time.
>>
>> >> My question is:
>>
>> >> Under what condition and for what kind of signal x's do the DFT F1(v)
>> >> and
>> >> sampled version of ordinary FT F3(v) equate? I want F1(v) and F3(v) to
>> >> be
>> >> exactly the same... what conditions shall I impose?
>>
>> > There is an answer to such questions. Not the one you expect
>> > or will be happy to hear, but an answer to questions such as
>> > yours exists. Now, I took very great care to avoid "your
>> > question" in the past sentence, because you don't have
>> > the necessary basis to formulate the proper question.
>> > Before asking again, take your time to read up on, and
>> > contemplate, the different variations of the Fourier transform.
>>
>> > You will have four cases to consider:
>>
>> > 1) Countinuos time, infinite duration
>> > 2) Continuous time, finite duration
>> > 3) Discrete time, infinite duration
>> > 4) Discrete time, finite duration
>>
>> > Once you have done that, you will be able to formulate
>> > a question which makes sense and, consequently, can be
>> > answered in a meaningful way.
>>
>> > Rune
>>
>> Thanks Rune! It's midnight so I was too sleepy. Yes, it should be
>> "Fourier".
>> Thanks for pointing it out!
>>
>> I agree my question is not well-posed. Here is a reformulation:
>>
>> Given a continuous time signal x(t), infinitely long. Sample it to obtain
>> discrete time sequence x0, x1, x2, ..., xn, ..., infinitely long, with
>> uniform samples spaced at T apart.
>>
>> Now I do two things:
>>
>> (1) Truncate the above sequence to make it finite, x0, x1, ..., xn, and
>> take
>> the DFT of the truncated sequence. Call the DFT F1(v). (Capitalized
>> letters
>> denote spectrum domain)
>>
>> (2) Without truncation, taking the DTFT of the infinitely long sequence
>> x0,
>> x1, ..., xn, .... Call the DTFT F2(v). And then take one period of F2(v),
>> since it is periodic, and then sample F2(v) in the frequency domain to
>> discretize it. Call the result F3(v), which is the discretized version of
>> the one period of F2(v).
>>
>> ---------------------
>>
>> Both (1) and (2) yield vectors of length n in the spectrum domain,
>> representing the discretized version of the spectrum.
>>
>> My question is: under what conditions do these two vectors of discretized
>> spectrum equate?
>
> IFF your infinitely long sequence is truly periodic AND
> you happen to truncate it so that you have exactly one
> period worth of data, then -- and only then -- your DFT
> and your DTFT are equal.
>
> There are only three problems with this:
>
> 1) Real-life data series from infinite-duration processes
> are never truly priodic.
> 2) Even if they are *almost* periodic, you can't expect
> to sample exactly one period's worth of data.
> 3) You are stuck with the DFT as a computational tool
> anyway, since it is highly impragtical to implement
> infinite summations and sample infinite amounts
> of data.
>
> Rune
>

Thanks Rune! The original signal x(t) is not periodic. I guess my next
question is:

How to handle such a situation and get an approximation error that is as
small as possible?

On 24 May, 19:20, "Mike" <meathea...@gmail.com> wrote:
> "Rune Allnor" <all...@tele.ntnu.no> wrote in message
>
> news:1180026933.108924.307690@u30g2000hsc.googlegroups.com...
>
>
>
>
>
> > On 24 May, 18:56, "Mike" <meathea...@gmail.com> wrote:
> >> "Rune Allnor" <all...@tele.ntnu.no> wrote in message
>
> >>news:1180021783.330512.237760@w5g2000hsg.googlegroups.com...
>
> >> > On 24 May, 09:45, "Mike" <meathea...@gmail.com> wrote:
> >> >> Hi all,
>
> >> >> I have the following question regarding the relation between DFT and
> >> >> Foureir
> >> >> Transform.
>
> >> > Fourier. After Jean Baptiste Joseph Fourier. Read his biography
>
> >> >http://www-history.mcs.st-andrews.ac.uk/Mathematicians/Fourier.html
>
> >> > and maybe you get enough respect for him to spell his name correctly.
>
> >> >> Suppose I have a sequence of discrete time signal x0, x1, x2, ... xn,
> >> >> ...
> >> >> (possibly infinite length), uniformly spaced in time, with spacing T;
> >> >> that's
> >> >> to say, x0 is the signal value at time 0, x1 is the signal value at
> >> >> time
> >> >> 1*T, x2 is the signal value at time 2*T, ...
>
> >> >> and the DFT of this sequence is F1(v).
>
> >> > Wrong. The DFT is not defined for a sequence of "possibly
> >> > infinite length." The DFT is defined for discrete-time sequences
> >> > of *finite* length.
>
> >> >> Also, for this sequence of signal,
>
> >> > What is a "sequence of signal"?
>
> >> >> I have an ordinary Foureir Transform
> >> >> F2(v), I guess it's called DTFT.
>
> >> > No, you don't. I have no idea what a "sequence of signal" is.
> >> > The Dirscrete-Time Fourier transform is defined for a discrete-
> >> > time sequence of *infinite* length.
>
> >> >> I plan to sample the F2(v) to obtain the discrete version of the F2(v)
> >> >> and
> >> >> call it F3(v).
>
> >> > No need to do that, the discrete-time signals are already
> >> > "sampled". Sampling is a way to convert from a contionuous-time
> >> > signal to a discrete-time signal. This can be done for signals
> >> > of either finite of (formally) infinite duration in time.
>
> >> >> My question is:
>
> >> >> Under what condition and for what kind of signal x's do the DFT F1(v)
> >> >> and
> >> >> sampled version of ordinary FT F3(v) equate? I want F1(v) and F3(v) to
> >> >> be
> >> >> exactly the same... what conditions shall I impose?
>
> >> > There is an answer to such questions. Not the one you expect
> >> > or will be happy to hear, but an answer to questions such as
> >> > yours exists. Now, I took very great care to avoid "your
> >> > question" in the past sentence, because you don't have
> >> > the necessary basis to formulate the proper question.
> >> > Before asking again, take your time to read up on, and
> >> > contemplate, the different variations of the Fourier transform.
>
> >> > You will have four cases to consider:
>
> >> > 1) Countinuos time, infinite duration
> >> > 2) Continuous time, finite duration
> >> > 3) Discrete time, infinite duration
> >> > 4) Discrete time, finite duration
>
> >> > Once you have done that, you will be able to formulate
> >> > a question which makes sense and, consequently, can be
> >> > answered in a meaningful way.
>
> >> > Rune
>
> >> Thanks Rune! It's midnight so I was too sleepy. Yes, it should be
> >> "Fourier".
> >> Thanks for pointing it out!
>
> >> I agree my question is not well-posed. Here is a reformulation:
>
> >> Given a continuous time signal x(t), infinitely long. Sample it to obtain
> >> discrete time sequence x0, x1, x2, ..., xn, ..., infinitely long, with
> >> uniform samples spaced at T apart.
>
> >> Now I do two things:
>
> >> (1) Truncate the above sequence to make it finite, x0, x1, ..., xn, and
> >> take
> >> the DFT of the truncated sequence. Call the DFT F1(v). (Capitalized
> >> letters
> >> denote spectrum domain)
>
> >> (2) Without truncation, taking the DTFT of the infinitely long sequence
> >> x0,
> >> x1, ..., xn, .... Call the DTFT F2(v). And then take one period of F2(v),
> >> since it is periodic, and then sample F2(v) in the frequency domain to
> >> discretize it. Call the result F3(v), which is the discretized version of
> >> the one period of F2(v).
>
> >> ---------------------
>
> >> Both (1) and (2) yield vectors of length n in the spectrum domain,
> >> representing the discretized version of the spectrum.
>
> >> My question is: under what conditions do these two vectors of discretized
> >> spectrum equate?
>
> > IFF your infinitely long sequence is truly periodic AND
> > you happen to truncate it so that you have exactly one
> > period worth of data, then -- and only then -- your DFT
> > and your DTFT are equal.
>
> > There are only three problems with this:
>
> > 1) Real-life data series from infinite-duration processes
> > are never truly priodic.
> > 2) Even if they are *almost* periodic, you can't expect
> > to sample exactly one period's worth of data.
> > 3) You are stuck with the DFT as a computational tool
> > anyway, since it is highly impragtical to implement
> > infinite summations and sample infinite amounts
> > of data.
>
> > Rune
>
> Thanks Rune! The original signal x(t) is not periodic. I guess my next
> question is:
>
> How to handle such a situation and get an approximation error that is as
> small as possible

There is nothing you can do about there being an error;
you are left with options about directing where to take
the damage. The classical example is window functions
in FIR filter design. The ideal (DTFT) transfer function
is easy to state; you DTF approximation involves two
approximation errors, namely transition bands and side
lobes. You can not avoid any of them, but you can use
window functions to contol their relative effect on
your data, everything else being constant:

1) Narrow transition bandwidth <-> high side lobes
2) Low sidelobes <-> large transition bandwidth

This engineering. There is the utopic goal everyone
would like to achieve, on one hand, and on the other
there are all the practical details which prevent
you from actual achievement and instead plunges you
into mere damage control.

Rune

"Randy Yates" <yates@ieee.org> wrote in message
news:m3lkferv9e.fsf@ieee.org...
> Randy Yates <yates@ieee.org> writes:
>
>> "Mike" <meatheadIV@gmail.com> writes:
>>> [...]
>>> I agree my question is not well-posed. Here is a reformulation:
>>>
>>> Given a continuous time signal x(t), infinitely long. Sample it to
>>> obtain
>>> discrete time sequence x0, x1, x2, ..., xn, ..., infinitely long, with
>>> uniform samples spaced at T apart.
>>>
>>> Now I do two things:
>>>
>>> (1) Truncate the above sequence to make it finite, x0, x1, ..., xn, and
>>> take
>>> the DFT of the truncated sequence. Call the DFT F1(v). (Capitalized
>>> letters
>>> denote spectrum domain)
>>>
>>> (2) Without truncation, taking the DTFT of the infinitely long sequence
>>> x0,
>>> x1, ..., xn, .... Call the DTFT F2(v). And then take one period of
>>> F2(v),
>>> since it is periodic, and then sample F2(v) in the frequency domain to
>>> discretize it. Call the result F3(v), which is the discretized version
>>> of
>>> the one period of F2(v).
>>>
>>> ---------------------
>>>
>>> Both (1) and (2) yield vectors of length n in the spectrum domain,
>>> representing the discretized version of the spectrum.
>>>
>>> My question is: under what conditions do these two vectors of
>>> discretized
>>> spectrum equate?
>>
>> When x(t) is periodic with period n*T.
>
> PS: You probably meant to label the sequences x0, x1, ..., x(n-1), making
> n samples.
> --
> % Randy Yates % "Remember the good old 1980's, when
> %% Fuquay-Varina, NC % things were so uncomplicated?"
> %%% 919-577-9882 % 'Ticket To The Moon'
> %%%% <yates@ieee.org> % *Time*, Electric Light Orchestra
> http://home.earthlink.net/~yatescr

Thanks, Randy! You are right!

"Mike" <meatheadIV@gmail.com> writes:
> [...]
> How to handle such a situation and get an approximation error that is as
> small as possible?

Man if I could do that I'd be richer than Gates. Because I could take
n samples of the stock market and predict what it's going to do in the
future.

You're asking for the impossible. The DFT doesn't "know" anything outside
of its n-sample window. Thus your signal might behave wildly differently
outside this interval and yet the DFT will still blindly report that those
n samples are periodic.

The only possible "fix" is to somehow involve more data than the n samples.
As Rune said, there are also windowing techniques for "smoothing" those
n (or more) samples so that the edge effects are mitigated, but the DFT
(and FFT) can know NOTHING outside of those n samples.
--
% Randy Yates % "Remember the good old 1980's, when
%% Fuquay-Varina, NC % things were so uncomplicated?"
%%% 919-577-9882 % 'Ticket To The Moon'
%%%% <yates@ieee.org> % *Time*, Electric Light Orchestra
http://home.earthlink.net/~yatescr

"Randy Yates" <yates@ieee.org> wrote in message
news:m3y7jeqdr4.fsf@ieee.org...
> "Mike" <meatheadIV@gmail.com> writes:
>> [...]
>> How to handle such a situation and get an approximation error that is as
>> small as possible?
>
> Man if I could do that I'd be richer than Gates. Because I could take
> n samples of the stock market and predict what it's going to do in the
> future.
>
> You're asking for the impossible. The DFT doesn't "know" anything outside
> of its n-sample window. Thus your signal might behave wildly differently
> outside this interval and yet the DFT will still blindly report that those
> n samples are periodic.
>
> The only possible "fix" is to somehow involve more data than the n
> samples.
> As Rune said, there are also windowing techniques for "smoothing" those
> n (or more) samples so that the edge effects are mitigated, but the DFT
> (and FFT) can know NOTHING outside of those n samples.
> --
> % Randy Yates % "Remember the good old 1980's, when
> %% Fuquay-Varina, NC % things were so uncomplicated?"
> %%% 919-577-9882 % 'Ticket To The Moon'
> %%%% <yates@ieee.org> % *Time*, Electric Light Orchestra
> http://home.earthlink.net/~yatescr

Thanks Randy! Let me check my understanding:

Since my infinitely long sequence is not periodic nor finite duration, let
me truncate it to x0, ..., x_{n-1}. These samples are really what I care
about. The rest of the infinitely long sequence is not useful to me.

This is effectively multiplying the original sequence with a rectangular
window.

If I could take one period of DTFT F2(v), modify it in accordance with the
multiplication of the rectangular window in time domain, and then sample it
to form F3(v), I will be fine.

I understand that multiplying a rectangle window in time domain correponds
to convolution with a sinc() function in frequency domain. I am not sure if
I can do this convolution on F3(v) with a discretized sinc() function, or I
have to do it on F2(v) which is continous and periodic in v.

If I can do the discrete convolution on F3(v) with no error, that would be
great!

"Rune Allnor" <allnor@tele.ntnu.no> wrote in message
news:1180028666.373894.83650@q75g2000hsh.googlegroups.com...
> On 24 May, 19:20, "Mike" <meathea...@gmail.com> wrote:
>> "Rune Allnor" <all...@tele.ntnu.no> wrote in message
>>
>> news:1180026933.108924.307690@u30g2000hsc.googlegroups.com...
>>
>>
>>
>>
>>
>> > On 24 May, 18:56, "Mike" <meathea...@gmail.com> wrote:
>> >> "Rune Allnor" <all...@tele.ntnu.no> wrote in message
>>
>> >>news:1180021783.330512.237760@w5g2000hsg.googlegroups.com...
>>
>> >> > On 24 May, 09:45, "Mike" <meathea...@gmail.com> wrote:
>> >> >> Hi all,
>>
>> >> >> I have the following question regarding the relation between DFT
>> >> >> and
>> >> >> Foureir
>> >> >> Transform.
>>
>> >> > Fourier. After Jean Baptiste Joseph Fourier. Read his biography
>>
>> >> >http://www-history.mcs.st-andrews.ac.uk/Mathematicians/Fourier.html
>>
>> >> > and maybe you get enough respect for him to spell his name
>> >> > correctly.
>>
>> >> >> Suppose I have a sequence of discrete time signal x0, x1, x2, ...
>> >> >> xn,
>> >> >> ...
>> >> >> (possibly infinite length), uniformly spaced in time, with spacing
>> >> >> T;
>> >> >> that's
>> >> >> to say, x0 is the signal value at time 0, x1 is the signal value at
>> >> >> time
>> >> >> 1*T, x2 is the signal value at time 2*T, ...
>>
>> >> >> and the DFT of this sequence is F1(v).
>>
>> >> > Wrong. The DFT is not defined for a sequence of "possibly
>> >> > infinite length." The DFT is defined for discrete-time sequences
>> >> > of *finite* length.
>>
>> >> >> Also, for this sequence of signal,
>>
>> >> > What is a "sequence of signal"?
>>
>> >> >> I have an ordinary Foureir Transform
>> >> >> F2(v), I guess it's called DTFT.
>>
>> >> > No, you don't. I have no idea what a "sequence of signal" is.
>> >> > The Dirscrete-Time Fourier transform is defined for a discrete-
>> >> > time sequence of *infinite* length.
>>
>> >> >> I plan to sample the F2(v) to obtain the discrete version of the
>> >> >> F2(v)
>> >> >> and
>> >> >> call it F3(v).
>>
>> >> > No need to do that, the discrete-time signals are already
>> >> > "sampled". Sampling is a way to convert from a contionuous-time
>> >> > signal to a discrete-time signal. This can be done for signals
>> >> > of either finite of (formally) infinite duration in time.
>>
>> >> >> My question is:
>>
>> >> >> Under what condition and for what kind of signal x's do the DFT
>> >> >> F1(v)
>> >> >> and
>> >> >> sampled version of ordinary FT F3(v) equate? I want F1(v) and F3(v)
>> >> >> to
>> >> >> be
>> >> >> exactly the same... what conditions shall I impose?
>>
>> >> > There is an answer to such questions. Not the one you expect
>> >> > or will be happy to hear, but an answer to questions such as
>> >> > yours exists. Now, I took very great care to avoid "your
>> >> > question" in the past sentence, because you don't have
>> >> > the necessary basis to formulate the proper question.
>> >> > Before asking again, take your time to read up on, and
>> >> > contemplate, the different variations of the Fourier transform.
>>
>> >> > You will have four cases to consider:
>>
>> >> > 1) Countinuos time, infinite duration
>> >> > 2) Continuous time, finite duration
>> >> > 3) Discrete time, infinite duration
>> >> > 4) Discrete time, finite duration
>>
>> >> > Once you have done that, you will be able to formulate
>> >> > a question which makes sense and, consequently, can be
>> >> > answered in a meaningful way.
>>
>> >> > Rune
>>
>> >> Thanks Rune! It's midnight so I was too sleepy. Yes, it should be
>> >> "Fourier".
>> >> Thanks for pointing it out!
>>
>> >> I agree my question is not well-posed. Here is a reformulation:
>>
>> >> Given a continuous time signal x(t), infinitely long. Sample it to
>> >> obtain
>> >> discrete time sequence x0, x1, x2, ..., xn, ..., infinitely long, with
>> >> uniform samples spaced at T apart.
>>
>> >> Now I do two things:
>>
>> >> (1) Truncate the above sequence to make it finite, x0, x1, ..., xn,
>> >> and
>> >> take
>> >> the DFT of the truncated sequence. Call the DFT F1(v). (Capitalized
>> >> letters
>> >> denote spectrum domain)
>>
>> >> (2) Without truncation, taking the DTFT of the infinitely long
>> >> sequence
>> >> x0,
>> >> x1, ..., xn, .... Call the DTFT F2(v). And then take one period of
>> >> F2(v),
>> >> since it is periodic, and then sample F2(v) in the frequency domain to
>> >> discretize it. Call the result F3(v), which is the discretized version
>> >> of
>> >> the one period of F2(v).
>>
>> >> ---------------------
>>
>> >> Both (1) and (2) yield vectors of length n in the spectrum domain,
>> >> representing the discretized version of the spectrum.
>>
>> >> My question is: under what conditions do these two vectors of
>> >> discretized
>> >> spectrum equate?
>>
>> > IFF your infinitely long sequence is truly periodic AND
>> > you happen to truncate it so that you have exactly one
>> > period worth of data, then -- and only then -- your DFT
>> > and your DTFT are equal.
>>
>> > There are only three problems with this:
>>
>> > 1) Real-life data series from infinite-duration processes
>> > are never truly priodic.
>> > 2) Even if they are *almost* periodic, you can't expect
>> > to sample exactly one period's worth of data.
>> > 3) You are stuck with the DFT as a computational tool
>> > anyway, since it is highly impragtical to implement
>> > infinite summations and sample infinite amounts
>> > of data.
>>
>> > Rune
>>
>> Thanks Rune! The original signal x(t) is not periodic. I guess my next
>> question is:
>>
>> How to handle such a situation and get an approximation error that is as
>> small as possible
>
> There is nothing you can do about there being an error;
> you are left with options about directing where to take
> the damage. The classical example is window functions
> in FIR filter design. The ideal (DTFT) transfer function
> is easy to state; you DTF approximation involves two
> approximation errors, namely transition bands and side
> lobes. You can not avoid any of them, but you can use
> window functions to contol their relative effect on
> your data, everything else being constant:
>
> 1) Narrow transition bandwidth <-> high side lobes
> 2) Low sidelobes <-> large transition bandwidth
>
> This engineering. There is the utopic goal everyone
> would like to achieve, on one hand, and on the other
> there are all the practical details which prevent
> you from actual achievement and instead plunges you
> into mere damage control.
>
> Rune
>

Thanks Rune! Let me check my understanding:

Since my infinitely long sequence is not periodic nor finite duration, let
me truncate it to x0, ..., x_{n-1}. These samples are really what I care
about. The rest of the infinitely long sequence is not useful to me.

This is effectively multiplying the original sequence with a rectangular
window.

If I could take one period of DTFT F2(v), modify it in accordance with the
multiplication of the rectangular window in time domain, and then sample it
to form F3(v), I will be fine.

I understand that multiplying a rectangle window in time domain correponds
to convolution with a sinc() function in frequency domain. I am not sure if
I can do this convolution on F3(v) with a discretized sinc() function, or I
have to do it on F2(v) which is continous and periodic in v.

If I can do the discrete convolution on F3(v) with no error, that would be
great!

"Randy Yates" <yates@ieee.org> wrote in message
news:m3y7jeqdr4.fsf@ieee.org...
> "Mike" <meatheadIV@gmail.com> writes:
>> [...]
>> How to handle such a situation and get an approximation error that is as
>> small as possible?
>
> Man if I could do that I'd be richer than Gates. Because I could take
> n samples of the stock market and predict what it's going to do in the
> future.
>
> You're asking for the impossible. The DFT doesn't "know" anything outside
> of its n-sample window. Thus your signal might behave wildly differently
> outside this interval and yet the DFT will still blindly report that those
> n samples are periodic.
>
> The only possible "fix" is to somehow involve more data than the n
> samples.
> As Rune said, there are also windowing techniques for "smoothing" those
> n (or more) samples so that the edge effects are mitigated, but the DFT
> (and FFT) can know NOTHING outside of those n samples.
> --
> % Randy Yates % "Remember the good old 1980's, when
> %% Fuquay-Varina, NC % things were so uncomplicated?"
> %%% 919-577-9882 % 'Ticket To The Moon'
> %%%% <yates@ieee.org> % *Time*, Electric Light Orchestra
> http://home.earthlink.net/~yatescr

For your suggestion, I don't have issue with making the number of samples as
large as possible, and hope for the fact that the infinitely long sequence
x(t) dies down after a very large t. Let's call that truncation position the
big N, and the truncated sequence is x0, x1, ..., x_{N-1}.

But I really only need the small n portion of the data. I may have to set
x_n, x_{n+1}, ..., x_{N-1} to be zero, then that complicates my operations
on F2(v) and F3(v) correspondingly ...

On 24 May, 20:51, "Mike" <meathea...@gmail.com> wrote:
> "Rune Allnor" <all...@tele.ntnu.no> wrote in message
>
> news:1180028666.373894.83650@q75g2000hsh.googlegroups.com...

>
> > There is nothing you can do about there being an error;
> > you are left with options about directing where to take
> > the damage. The classical example is window functions
> > in FIR filter design. The ideal (DTFT) transfer function
> > is easy to state; you DTF approximation involves two
> > approximation errors, namely transition bands and side
> > lobes. You can not avoid any of them, but you can use
> > window functions to contol their relative effect on
> > your data, everything else being constant:
>
> > 1) Narrow transition bandwidth <-> high side lobes
> > 2) Low sidelobes <-> large transition bandwidth
>
> > This engineering. There is the utopic goal everyone
> > would like to achieve, on one hand, and on the other
> > there are all the practical details which prevent
> > you from actual achievement and instead plunges you
> > into mere damage control.
>
> > Rune
>
> Thanks Rune! Let me check my understanding:
>
> Since my infinitely long sequence is not periodic nor finite duration, let
> me truncate it to x0, ..., x_{n-1}. These samples are really what I care
> about. The rest of the infinitely long sequence is not useful to me.

Correct.

> This is effectively multiplying the original sequence with a rectangular
> window.

Correct.

> If I could take one period of DTFT F2(v),

Except you don't have access to F2(v). In your terminology,
the only data you have access to is F3(v).

> modify it in accordance with the
> multiplication of the rectangular window in time domain, and then sample it
> to form F3(v), I will be fine.

You don't need to do any of this; it is embedded in
the fact that you only have a finite data record
available.

> I understand that multiplying a rectangle window in time domain correponds
> to convolution with a sinc() function in frequency domain. I am not sure if
> I can do this convolution on F3(v) with a discretized sinc() function, or I
> have to do it on F2(v) which is continous and periodic in v.

It's already done. Try this exercise with matlab:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function plotsinespectrum(N)

tv = (0:N-1); % Time base, sampling frequency = 1
sv = sin(2*pi*0.2*tv); % Sinusoidal with frquency 0.2

S= abs(fft(sv,max(N,1024))); % Compute interpolated spectrum
M = max(N,1024);
fv = (0:M-1)/M; % Frequency vector

plot(fv,S)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

subplot(4,1,1)
plotsinespectrum(32);

subplot(4,1,2)
plotsinespectrum(64);

subplot(4,1,3)
plotsinespectrum(256);

subplot(4,1,4)
plotsinespectrum(16384);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Anything that strikes you here?


> If I can do the discrete convolution on F3(v) with no error, that would be
> great!

You don't have to do anything. It's all there, already.

Rune

On 24 Mai, 19:15, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 24 May, 18:56, "Mike" <meathea...@gmail.com> wrote:
>
>
>
>
>
> > "Rune Allnor" <all...@tele.ntnu.no> wrote in message
>
> >news:1180021783.330512.237760@w5g2000hsg.googlegroups.com...
>
> > > On 24 May, 09:45, "Mike" <meathea...@gmail.com> wrote:
> > >> Hi all,
>
> > >> I have the following question regarding the relation between DFT and
> > >> Foureir
> > >> Transform.
>
> > > Fourier. After Jean Baptiste Joseph Fourier. Read his biography
>
> > >http://www-history.mcs.st-andrews.ac.uk/Mathematicians/Fourier.html
>
> > > and maybe you get enough respect for him to spell his name correctly.
>
> > >> Suppose I have a sequence of discrete time signal x0, x1, x2, ... xn, ...
> > >> (possibly infinite length), uniformly spaced in time, with spacing T;
> > >> that's
> > >> to say, x0 is the signal value at time 0, x1 is the signal value at time
> > >> 1*T, x2 is the signal value at time 2*T, ...
>
> > >> and the DFT of this sequence is F1(v).
>
> > > Wrong. The DFT is not defined for a sequence of "possibly
> > > infinite length." The DFT is defined for discrete-time sequences
> > > of *finite* length.
>
> > >> Also, for this sequence of signal,
>
> > > What is a "sequence of signal"?
>
> > >> I have an ordinary Foureir Transform
> > >> F2(v), I guess it's called DTFT.
>
> > > No, you don't. I have no idea what a "sequence of signal" is.
> > > The Dirscrete-Time Fourier transform is defined for a discrete-
> > > time sequence of *infinite* length.
>
> > >> I plan to sample the F2(v) to obtain the discrete version of the F2(v)
> > >> and
> > >> call it F3(v).
>
> > > No need to do that, the discrete-time signals are already
> > > "sampled". Sampling is a way to convert from a contionuous-time
> > > signal to a discrete-time signal. This can be done for signals
> > > of either finite of (formally) infinite duration in time.
>
> > >> My question is:
>
> > >> Under what condition and for what kind of signal x's do the DFT F1(v) and
> > >> sampled version of ordinary FT F3(v) equate? I want F1(v) and F3(v) to be
> > >> exactly the same... what conditions shall I impose?
>
> > > There is an answer to such questions. Not the one you expect
> > > or will be happy to hear, but an answer to questions such as
> > > yours exists. Now, I took very great care to avoid "your
> > > question" in the past sentence, because you don't have
> > > the necessary basis to formulate the proper question.
> > > Before asking again, take your time to read up on, and
> > > contemplate, the different variations of the Fourier transform.
>
> > > You will have four cases to consider:
>
> > > 1) Countinuos time, infinite duration
> > > 2) Continuous time, finite duration
> > > 3) Discrete time, infinite duration
> > > 4) Discrete time, finite duration
>
> > > Once you have done that, you will be able to formulate
> > > a question which makes sense and, consequently, can be
> > > answered in a meaningful way.
>
> > > Rune
>
> > Thanks Rune! It's midnight so I was too sleepy. Yes, it should be "Fourier".
> > Thanks for pointing it out!
>
> > I agree my question is not well-posed. Here is a reformulation:
>
> > Given a continuous time signal x(t), infinitely long. Sample it to obtain
> > discrete time sequence x0, x1, x2, ..., xn, ..., infinitely long, with
> > uniform samples spaced at T apart.
>
> > Now I do two things:
>
> > (1) Truncate the above sequence to make it finite, x0, x1, ..., xn, and take
> > the DFT of the truncated sequence. Call the DFT F1(v). (Capitalized letters
> > denote spectrum domain)
>
> > (2) Without truncation, taking the DTFT of the infinitely long sequence x0,
> > x1, ..., xn, .... Call the DTFT F2(v). And then take one period of F2(v),
> > since it is periodic, and then sample F2(v) in the frequency domain to
> > discretize it. Call the result F3(v), which is the discretized version of
> > the one period of F2(v).
>
> > ---------------------
>
> > Both (1) and (2) yield vectors of length n in the spectrum domain,
> > representing the discretized version of the spectrum.
>
> > My question is: under what conditions do these two vectors of discretized
> > spectrum equate?
>
> IFF your infinitely long sequence is truly periodic AND
> you happen to truncate it so that you have exactly one
> period worth of data, then -- and only then -- your DFT
> and your DTFT are equal.

That statement is clearly wrong. If the infinitely long sequence is
periodic, then you cannot compute its DTFT (the sum doesn't converge).
You can compute it's DFS, which is trivially related to the DFT of one
period of the sequence. However, for infinite sequences which have a
DTFT (which is what Mike was talking about), one can state the
following lemma:

Let x[m], where m ranges over all integers, be a square-summable
sequence, and X(w) its DTFT. Furthermore, let y[n], n=0,1,...N-1 be a
finite vector, and Y[k] the DFT of y[n]. Then

X(2 pi k/N) = Y[k], k=0,1,...,N-1,

if, and only if,

y[n] = sum_{r=-infinity}^infinity x[n+r N].

Regards,
Andor

On 24 May, 21:49, Andor <andor.bari...@gmail.com> wrote:
> On 24 Mai, 19:15, Rune Allnor <all...@tele.ntnu.no> wrote:

> > IFF your infinitely long sequence is truly periodic AND
> > you happen to truncate it so that you have exactly one
> > period worth of data, then -- and only then -- your DFT
> > and your DTFT are equal.
>
> That statement is clearly wrong. If the infinitely long sequence is
> periodic, then you cannot compute its DTFT (the sum doesn't converge).
> You can compute it's DFS, which is trivially related to the DFT of one
> period of the sequence.

There are several definitions of the DTFT. If we restrict
the discussion to energy signals, then you are right, as
the characteristic of an energy signal is

sum |x[n]|^2 < inf [1]
 n

where the sum goes from -infinite to infinite. However,
the DTFT is also defined for power signal, which satisfy
(view with fixed-width font to get formulas right)

          k+N 1
  lim sum --- |x[n]|^2 < inf [2]
 N->inf n=k N

This form is the reason why it makes sense to speak of the
FT of a sine or a cosine. It is a standard excercise in
DSP texts to show that the discrete spectrum becomes
continuous in the limit, as N increases towards infinity.

> However, for infinite sequences which have a
> DTFT (which is what Mike was talking about), one can state the
> following lemma:
>
> Let x[m], where m ranges over all integers, be a square-summable
> sequence, and X(w) its DTFT.

You need to specify in what sense it is square integrable,
form [1] or form [2] above.

> Furthermore, let y[n], n=0,1,...N-1 be a
> finite vector,

... OK ...

> and Y[k] the DFT of y[n]. Then
>
> X(2 pi k/N) = Y[k], k=0,1,...,N-1,
>
> if, and only if,
>
> y[n] = sum_{r=-infinity}^infinity x[n+r N].

I don't see this. Can you elaborate? It seems to me
as if you are saying that the DFT of a sinusoidal
on the form

c[n] = cos(2pi kn/N), k< N/2; k,n,N integers,

does not exist. The obvious counterargument to your claim
is to posulate that there exists an infinite periodic
extension c'[n] of c[n] such that

        r
c[n] = sum c'[n+ rN]
      r=-inf

Inserting this in your formula, setting n = 0, we get

              inf
c[0] = 1 =/= sum 1 = inf
             r=-inf

which obviously is a contradicion.

Rune

On 24 Mai, 22:12, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 24 May, 21:49, Andor <andor.bari...@gmail.com> wrote:
>
> > On 24 Mai, 19:15, Rune Allnor <all...@tele.ntnu.no> wrote:
> > > IFF your infinitely long sequence is truly periodic AND
> > > you happen to truncate it so that you have exactly one
> > > period worth of data, then -- and only then -- your DFT
> > > and your DTFT are equal.
>
> > That statement is clearly wrong. If the infinitely long sequence is
> > periodic, then you cannot compute its DTFT (the sum doesn't converge).
> > You can compute it's DFS, which is trivially related to the DFT of one
> > period of the sequence.
>
> There are several definitions of the DTFT.

The DTFT of a sequenc x[n] is defined as

X(w) = sum_{n=-infinity}^infinity x[n] exp(-j w n).

Which other definitions were you referring to?

...

> sum |x[n]|^2 < inf [1]
> n

...

> k+N 1
> lim sum --- |x[n]|^2 < inf [2]
> N->inf n=k N

...

> > However, for infinite sequences which have a
> > DTFT (which is what Mike was talking about), one can state the
> > following lemma:
>
> > Let x[m], where m ranges over all integers, be a square-summable
> > sequence, and X(w) its DTFT.
>
> You need to specify in what sense it is square integrable,
> form [1] or form [2] above.

As with DTFT, I only know of one definition for a sequence to be
"square-summable" (your [1]).

>
> > Furthermore, let y[n], n=0,1,...N-1 be a
> > finite vector,
>
> ... OK ...
>
> > and Y[k] the DFT of y[n]. Then
>
> > X(2 pi k/N) = Y[k], k=0,1,...,N-1,
>
> > if, and only if,
>
> > y[n] = sum_{r=-infinity}^infinity x[n+r N].
>
> I don't see this. Can you elaborate? It seems to me
> as if you are saying that the DFT of a sinusoidal
> on the form
>
> c[n] = cos(2pi kn/N), k< N/2; k,n,N integers,
>
> does not exist.

That would be a rather silly thing to say. Luckily, I said nothing
even close. I thought the statement of the lemma is clear. Which part
to you want elaboration on?

"Rune Allnor" <allnor@tele.ntnu.no> wrote in message
news:1180034963.056815.225880@q69g2000hsb.googlegroups.com...
> On 24 May, 20:51, "Mike" <meathea...@gmail.com> wrote:
>> "Rune Allnor" <all...@tele.ntnu.no> wrote in message
>>
>> news:1180028666.373894.83650@q75g2000hsh.googlegroups.com...
>
>>
>> > There is nothing you can do about there being an error;
>> > you are left with options about directing where to take
>> > the damage. The classical example is window functions
>> > in FIR filter design. The ideal (DTFT) transfer function
>> > is easy to state; you DTF approximation involves two
>> > approximation errors, namely transition bands and side
>> > lobes. You can not avoid any of them, but you can use
>> > window functions to contol their relative effect on
>> > your data, everything else being constant:
>>
>> > 1) Narrow transition bandwidth <-> high side lobes
>> > 2) Low sidelobes <-> large transition bandwidth
>>
>> > This engineering. There is the utopic goal everyone
>> > would like to achieve, on one hand, and on the other
>> > there are all the practical details which prevent
>> > you from actual achievement and instead plunges you
>> > into mere damage control.
>>
>> > Rune
>>
>> Thanks Rune! Let me check my understanding:
>>
>> Since my infinitely long sequence is not periodic nor finite duration,
>> let
>> me truncate it to x0, ..., x_{n-1}. These samples are really what I care
>> about. The rest of the infinitely long sequence is not useful to me.
>
> Correct.
>
>> This is effectively multiplying the original sequence with a rectangular
>> window.
>
> Correct.
>
>> If I could take one period of DTFT F2(v),
>
> Except you don't have access to F2(v). In your terminology,
> the only data you have access to is F3(v).
>
>> modify it in accordance with the
>> multiplication of the rectangular window in time domain, and then sample
>> it
>> to form F3(v), I will be fine.
>
> You don't need to do any of this; it is embedded in
> the fact that you only have a finite data record
> available.
>


Thanks a lot Rune! I will digest and play with your exercise to gain a
better understanding...

I just want to clarify that my headache is that I don't have x(t) and x0,
... xn, ... and hence the truncated version x0, ..., x_{N-1}, and the useful
truncated version x_0, ..., x_{n-1}.

All I have is F2(v) in closed form. I can manipulate it and sample it an any
form to obtain a good F3(v), which hopefully represent the DFT/FFT of x_0,
..., x_{N-1}.

That's the problem -- I don't have the signals in time domain...

Any more thoughts?

On 24 May, 22:25, Andor <andor.bari...@gmail.com> wrote:
> On 24 Mai, 22:12, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> > On 24 May, 21:49, Andor <andor.bari...@gmail.com> wrote:
>
> > > On 24 Mai, 19:15, Rune Allnor <all...@tele.ntnu.no> wrote:
> > > > IFF your infinitely long sequence is truly periodic AND
> > > > you happen to truncate it so that you have exactly one
> > > > period worth of data, then -- and only then -- your DFT
> > > > and your DTFT are equal.
>
> > > That statement is clearly wrong. If the infinitely long sequence is
> > > periodic, then you cannot compute its DTFT (the sum doesn't converge).
> > > You can compute it's DFS, which is trivially related to the DFT of one
> > > period of the sequence.
>
> > There are several definitions of the DTFT.
>
> The DTFT of a sequenc x[n] is defined as
>
> X(w) = sum_{n=-infinity}^infinity x[n] exp(-j w n).
>
> Which other definitions were you referring to?

There is one which looks like

X(w) = lim_{N-> inf} sum_{n=-N}^N 1/(2N +1) x[n] exp(-j w n).

I am sure you have seen it: You need it if you want to
compute the DTFT of an infinitely long sinusoidal...

> ...
>
> > sum |x[n]|^2 < inf [1]
> > n
>
> ...
>
> > k+N 1
> > lim sum --- |x[n]|^2 < inf [2]
> > N->inf n=k N
>
> ...
>
> > > However, for infinite sequences which have a
> > > DTFT (which is what Mike was talking about), one can state the
> > > following lemma:
>
> > > Let x[m], where m ranges over all integers, be a square-summable
> > > sequence, and X(w) its DTFT.
>
> > You need to specify in what sense it is square integrable,
> > form [1] or form [2] above.
>
> As with DTFT, I only know of one definition for a sequence to be
> "square-summable" (your [1]).



> > > Furthermore, let y[n], n=0,1,...N-1 be a
> > > finite vector,
>
> > ... OK ...
>
> > > and Y[k] the DFT of y[n]. Then
>
> > > X(2 pi k/N) = Y[k], k=0,1,...,N-1,
>
> > > if, and only if,
>
> > > y[n] = sum_{r=-infinity}^infinity x[n+r N].
>
> > I don't see this. Can you elaborate? It seems to me
> > as if you are saying that the DFT of a sinusoidal
> > on the form
>
> > c[n] = cos(2pi kn/N), k< N/2; k,n,N integers,
>
> > does not exist.
>
> That would be a rather silly thing to say.

I am glad to hear we agree.

> Luckily, I said nothing
> even close. I thought the statement of the lemma is clear. Which part
> to you want elaboration on?

The part I misunderstood. If you say you didn't claim
what I countered, yhen I obviously midunderstood your
claim in the first place. Why don't you show me where
I went wrong?

Rune

On 24 Mai, 22:32, Rune Allnor <all...@tele.ntnu.no> wrote:
...
> > > > Let x[m], where m ranges over all integers, be a square-summable
> > > > sequence, and X(w) its DTFT.
> > > > Furthermore, let y[n], n=0,1,...N-1 be a
> > > > finite vector,
> > > > and Y[k] the DFT of y[n]. Then
>
> > > > X(2 pi k/N) = Y[k], k=0,1,...,N-1,
>
> > > > if, and only if,
>
> > > > y[n] = sum_{r=-infinity}^infinity x[n+r N].
>
> > > I don't see this. Can you elaborate? It seems to me
> > > as if you are saying that the DFT of a sinusoidal
> > > on the form
>
> > > c[n] = cos(2pi kn/N), k< N/2; k,n,N integers,
>
> > > does not exist.
>
> > That would be a rather silly thing to say.
>
> I am glad to hear we agree.
>
> > Luckily, I said nothing
> > even close. I thought the statement of the lemma is clear. Which part
> > to you want elaboration on?
>
> The part I misunderstood. If you say you didn't claim
> what I countered, yhen I obviously midunderstood your
> claim in the first place. Why don't you show me where
> I went wrong?

I don't know what you misunderstood or where you went wrong. Your
statement and the lemma didn't seem connected at all.

You have the DTFT X(w) of some sequence x[n]. You now sample the DTFT
on N evenly spaced points around the unit circle. Then you take the
inverse DFT y of those N points, and you ask yourself: how is the
finite vector y[n] related to the infinitely long sequence x[n]? The
lemma answers this question.

Note the close similarity to sampling and alising of this situation.
However, the sampling takes place in the frequency domain, and the
aliasing in the time domain.

Regards,
Andor

On 24 May, 22:52, Andor <andor.bari...@gmail.com> wrote:
> On 24 Mai, 22:32, Rune Allnor <all...@tele.ntnu.no> wrote:
> ...

> > > > > Let x[m], where m ranges over all integers, be a square-summable
> > > > > sequence, and X(w) its DTFT.
> > > > > Furthermore, let y[n], n=0,1,...N-1 be a
> > > > > finite vector,
> > > > > and Y[k] the DFT of y[n]. Then
>
> > > > > X(2 pi k/N) = Y[k], k=0,1,...,N-1,
>
> > > > > if, and only if,
>
> > > > > y[n] = sum_{r=-infinity}^infinity x[n+r N].
>
> > > > I don't see this. Can you elaborate? It seems to me
> > > > as if you are saying that the DFT of a sinusoidal
> > > > on the form
>
> > > > c[n] = cos(2pi kn/N), k< N/2; k,n,N integers,
>
> > > > does not exist.
>
> > > That would be a rather silly thing to say.
>
> > I am glad to hear we agree.
>
> > > Luckily, I said nothing
> > > even close. I thought the statement of the lemma is clear. Which part
> > > to you want elaboration on?
>
> > The part I misunderstood. If you say you didn't claim
> > what I countered, yhen I obviously midunderstood your
> > claim in the first place. Why don't you show me where
> > I went wrong?
>
> I don't know what you misunderstood or where you went wrong. Your
> statement and the lemma didn't seem connected at all.

You based your argument on (cut'n pase from a few
lines above):

y[n] = sum_{r=-infinity}^infinity x[n+r N].

Agreed?

You somehow relate the finite-length y[n] to the
infinite-length x[n].

Agreed?

I started with the finite-length

c[n] = cos(2pi kn/N), k< N/2; k,n,N integers

Agreed?

I tried to relate to your argument by extending
it to infinity as c'[n] where n takes the integer
values from -inf to +inf, but where the formula
otherwise is the same for c[n].

No problems there, I hope?

>From that basis I derive a contradction, and
expressed it in a way I am certain you are
able to follow.

So, since I started from a claim of yours and
ended up with a contradiction we both agree
is obvious, one of us has either misunderstood
something or made a bad turn somewhere. I am
one of those who try to learn from my mistakes.
I just ask you to point to where I went wrong.

> You have the DTFT X(w) of some sequence x[n]. You now sample the DTFT
> on N evenly spaced points around the unit circle.

Where did the unit circle come from? I thought we
were talking about time-domain signals? Your definitions
are clear-cut to me:

"Let x[m], where m ranges over all integers, be a square-summable
 sequence, and X(w) its DTFT."

and then you go on to talk about this y[n]. Where did
"sampling on the unit circle" enter the picture?

> Then you take the
> inverse DFT y of those N points, and you ask yourself: how is the
> finite vector y[n] related to the infinitely long sequence x[n]? The
> lemma answers this question.

I still don't understand what you mean, and the
lemma still leads to a contradiction.

Rune

On 24 Mai, 23:17, Rune Allnor <allnor@tele.ntnu.no> wrote:
> On 24 May, 22:52, Andor <andor.bari...@gmail.com> wrote:
>
>
>
>
>
> > On 24 Mai, 22:32, Rune Allnor <all...@tele.ntnu.no> wrote:
> > ...
> > > > > > Let x[m], where m ranges over all integers, be a square-summable
> > > > > > sequence, and X(w) its DTFT.
> > > > > > Furthermore, let y[n], n=0,1,...N-1 be a
> > > > > > finite vector,
> > > > > > and Y[k] the DFT of y[n]. Then
>
> > > > > > X(2 pi k/N) = Y[k], k=0,1,...,N-1,
>
> > > > > > if, and only if,
>
> > > > > > y[n] = sum_{r=-infinity}^infinity x[n+r N].
>
> > > > > I don't see this. Can you elaborate? It seems to me
> > > > > as if you are saying that the DFT of a sinusoidal
> > > > > on the form
>
> > > > > c[n] = cos(2pi kn/N), k< N/2; k,n,N integers,
>
> > > > > does not exist.
>
> > > > That would be a rather silly thing to say.
>
> > > I am glad to hear we agree.
>
> > > > Luckily, I said nothing
> > > > even close. I thought the statement of the lemma is clear. Which part
> > > > to you want elaboration on?
>
> > > The part I misunderstood. If you say you didn't claim
> > > what I countered, yhen I obviously midunderstood your
> > > claim in the first place. Why don't you show me where
> > > I went wrong?
>
> > I don't know what you misunderstood or where you went wrong. Your
> > statement and the lemma didn't seem connected at all.
>
> You based your argument on (cut'n pase from a few
> lines above):
>
> y[n] = sum_{r=-infinity}^infinity x[n+r N].
>
> Agreed?
>
> You somehow relate the finite-length y[n] to the
> infinite-length x[n].
>
> Agreed?
>
> I started with the finite-length
>
> c[n] = cos(2pi kn/N), k< N/2; k,n,N integers
>
> Agreed?
>
> I tried to relate to your argument by extending
> it to infinity as c'[n] where n takes the integer
> values from -inf to +inf, but where the formula
> otherwise is the same for c[n].
>
> No problems there, I hope?

Yes, problem here. I said the sequence x[n] has to be square-summable.
No periodic sequence is square-summable, and it also doesn't have a
DTFT. You arrived at non-sense by assuming non-sense.

>
> >From that basis I derive a contradction, and
>
> expressed it in a way I am certain you are
> able to follow.
>
> So, since I started from a claim of yours and
> ended up with a contradiction we both agree
> is obvious, one of us has either misunderstood
> something or made a bad turn somewhere. I am
> one of those who try to learn from my mistakes.
> I just ask you to point to where I went wrong.

That's clear now I hope.

>
> > You have the DTFT X(w) of some sequence x[n]. You now sample the DTFT
> > on N evenly spaced points around the unit circle.
>
> Where did the unit circle come from? I thought we
> were talking about time-domain signals? Your definitions
> are clear-cut to me:
>
> "Let x[m], where m ranges over all integers, be a square-summable
> sequence, and X(w) its DTFT."
>
> and then you go on to talk about this y[n]. Where did
> "sampling on the unit circle" enter the picture?

Where I say:

"X(2 pi k/N) = Y[k], k=0,1,...,N-1, "

That is sampling the DTFT on evenly spaced points around the unit
circle.

>
> > Then you take the
> > inverse DFT y of those N points, and you ask yourself: how is the
> > finite vector y[n] related to the infinitely long sequence x[n]? The
> > lemma answers this question.
>
> I still don't understand what you mean, and the
> lemma still leads to a contradiction.

Sorry to not be able to help you.

BTW, did you also just recieve a DSP job offer from a US company
requiring top secret clearance?

Regards,
Andor

On 24 May, 23:25, Andor <andor.bari...@gmail.com> wrote:
> On 24 Mai, 23:17, Rune Allnor <all...@tele.ntnu.no> wrote:
>
>
>
>
>
> > On 24 May, 22:52, Andor <andor.bari...@gmail.com> wrote:
>
> > > On 24 Mai, 22:32, Rune Allnor <all...@tele.ntnu.no> wrote:
> > > ...
> > > > > > > Let x[m], where m ranges over all integers, be a square-summable
> > > > > > > sequence, and X(w) its DTFT.
> > > > > > > Furthermore, let y[n], n=0,1,...N-1 be a
> > > > > > > finite vector,
> > > > > > > and Y[k] the DFT of y[n]. Then
>
> > > > > > > X(2 pi k/N) = Y[k], k=0,1,...,N-1,
>
> > > > > > > if, and only if,
>
> > > > > > > y[n] = sum_{r=-infinity}^infinity x[n+r N].
>
> > > > > > I don't see this. Can you elaborate? It seems to me
> > > > > > as if you are saying that the DFT of a sinusoidal
> > > > > > on the form
>
> > > > > > c[n] = cos(2pi kn/N), k< N/2; k,n,N integers,
>
> > > > > > does not exist.
>
> > > > > That would be a rather silly thing to say.
>
> > > > I am glad to hear we agree.
>
> > > > > Luckily, I said nothing
> > > > > even close. I thought the statement of the lemma is clear. Which part
> > > > > to you want elaboration on?
>
> > > > The part I misunderstood. If you say you didn't claim
> > > > what I countered, yhen I obviously midunderstood your
> > > > claim in the first place. Why don't you show me where
> > > > I went wrong?
>
> > > I don't know what you misunderstood or where you went wrong. Your
> > > statement and the lemma didn't seem connected at all.
>
> > You based your argument on (cut'n pase from a few
> > lines above):
>
> > y[n] = sum_{r=-infinity}^infinity x[n+r N].
>
> > Agreed?
>
> > You somehow relate the finite-length y[n] to the
> > infinite-length x[n].
>
> > Agreed?
>
> > I started with the finite-length
>
> > c[n] = cos(2pi kn/N), k< N/2; k,n,N integers
>
> > Agreed?
>
> > I tried to relate to your argument by extending
> > it to infinity as c'[n] where n takes the integer
> > values from -inf to +inf, but where the formula
> > otherwise is the same for c[n].
>
> > No problems there, I hope?
>
> Yes, problem here. I said the sequence x[n] has to be square-summable.
> No periodic sequence is square-summable, and it also doesn't have a
> DTFT. You arrived at non-sense by assuming non-sense.

Ah, but then all of a sudden you agree with the
conclusion I drew from your lemma (cut'n paste
from the top of this mail):

you are saying that the DFT of a sinusoidal
on the form

c[n] = cos(2pi kn/N), k< N/2; k,n,N integers,

does not exist

> > I just ask you to point to where I went wrong.
>
> That's clear now I hope.

You have made it clear that the DTFT of a cosine
does not exist.

Rune

Andor <andor.bariska@gmail.com> writes:
> [...]
> Yes, problem here. I said the sequence x[n] has to be square-summable.
> No periodic sequence is square-summable, and it also doesn't have a
> DTFT. You arrived at non-sense by assuming non-sense.

Andor,

I think you're being overly pedantic and confusing the OP with statements
that contradict what myself and others have said.

Most of us here are aware of the problems representing the spectra of
infinite-energy waveforms, and have used the Dirac delta function to
get around them. Can one not do the same here? Albeit we should be
speaking of the *area* of the pulse at a frequency rather than
its value.
--
% Randy Yates % "Midnight, on the water...
%% Fuquay-Varina, NC % I saw... the ocean's daughter."
%%% 919-577-9882 % 'Can't Get It Out Of My Head'
%%%% <yates@ieee.org> % *El Dorado*, Electric Light Orchestra
http://home.earthlink.net/~yatescr

Mike wrote:

   ...

> Since my infinitely long sequence is not periodic nor finite duration, let
> me truncate it to x0, ..., x_{n-1}. These samples are really what I care
> about. The rest of the infinitely long sequence is not useful to me.
>
> This is effectively multiplying the original sequence with a rectangular
> window...

... and making the resulting sequence periodic with a period equal to
the window duration.

   ...

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

On 24 Mai, 23:40, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 24 May, 23:25, Andor <andor.bari...@gmail.com> wrote:
>
>
>
>
>
> > On 24 Mai, 23:17, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> > > On 24 May, 22:52, Andor <andor.bari...@gmail.com> wrote:
>
> > > > On 24 Mai, 22:32, Rune Allnor <all...@tele.ntnu.no> wrote:
> > > > ...
> > > > > > > > Let x[m], where m ranges over all integers, be a square-summable
> > > > > > > > sequence, and X(w) its DTFT.
> > > > > > > > Furthermore, let y[n], n=0,1,...N-1 be a
> > > > > > > > finite vector,
> > > > > > > > and Y[k] the DFT of y[n]. Then
>
> > > > > > > > X(2 pi k/N) = Y[k], k=0,1,...,N-1,
>
> > > > > > > > if, and only if,
>
> > > > > > > > y[n] = sum_{r=-infinity}^infinity x[n+r N].
>
> > > > > > > I don't see this. Can you elaborate? It seems to me
> > > > > > > as if you are saying that the DFT of a sinusoidal
> > > > > > > on the form
>
> > > > > > > c[n] = cos(2pi kn/N), k< N/2; k,n,N integers,
>
> > > > > > > does not exist.
>
> > > > > > That would be a rather silly thing to say.
>
> > > > > I am glad to hear we agree.
>
> > > > > > Luckily, I said nothing
> > > > > > even close. I thought the statement of the lemma is clear. Which part
> > > > > > to you want elaboration on?
>
> > > > > The part I misunderstood. If you say you didn't claim
> > > > > what I countered, yhen I obviously midunderstood your
> > > > > claim in the first place. Why don't you show me where
> > > > > I went wrong?
>
> > > > I don't know what you misunderstood or where you went wrong. Your
> > > > statement and the lemma didn't seem connected at all.
>
> > > You based your argument on (cut'n pase from a few
> > > lines above):
>
> > > y[n] = sum_{r=-infinity}^infinity x[n+r N].
>
> > > Agreed?
>
> > > You somehow relate the finite-length y[n] to the
> > > infinite-length x[n].
>
> > > Agreed?
>
> > > I started with the finite-length
>
> > > c[n] = cos(2pi kn/N), k< N/2; k,n,N integers
>
> > > Agreed?
>
> > > I tried to relate to your argument by extending
> > > it to infinity as c'[n] where n takes the integer
> > > values from -inf to +inf, but where the formula
> > > otherwise is the same for c[n].
>
> > > No problems there, I hope?
>
> > Yes, problem here. I said the sequence x[n] has to be square-summable.
> > No periodic sequence is square-summable, and it also doesn't have a
> > DTFT. You arrived at non-sense by assuming non-sense.
>
> Ah, but then all of a sudden you agree with the
> conclusion I drew from your lemma (cut'n paste
> from the top of this mail):
>
> you are saying that the DFT of a sinusoidal
> on the form
>
> c[n] = cos(2pi kn/N), k< N/2; k,n,N integers,
>
> does not exist
>
> > > I just ask you to point to where I went wrong.
>
> > That's clear now I hope.
>
> You have made it clear that the DTFT of a cosine
> does not exist.

Quote:

"you are saying that the DFT of a sinusoidal..."

Notice the three capital letters.

Second quote:
"You have made it clear that the DTFT of a cosine..."

Notice the four capital letters.

Now you may believe my little lemma or not, it doesn't matter. Maths
is not about belief.


Regards,
Andor

On 25 Mai, 00:06, Randy Yates <y...@ieee.org> wrote:
> Andor <andor.bari...@gmail.com> writes:
> > [...]
> > Yes, problem here. I said the sequence x[n] has to be square-summable.
> > No periodic sequence is square-summable, and it also doesn't have a
> > DTFT. You arrived at non-sense by assuming non-sense.
>
> Andor,
>
> I think you're being overly pedantic and confusing the OP with statements
> that contradict what myself and others have said.

I stated a lemma. I stated the conditions necessary for the lemma.
Somebody gave a "counter-example" to the lemma, but violated the
conditions necessary for the lemma to be true. I pointed out to the
somebody that he violated the conditions of the lemma, therefore he
arrived at a contradiction to the lemma.

Overly pedantic?

On 25 Mai, 00:06, Randy Yates <y...@ieee.org> wrote:
> Andor <andor.bari...@gmail.com> writes:
> > [...]
> > Yes, problem here. I said the sequence x[n] has to be square-summable.
> > No periodic sequence is square-summable, and it also doesn't have a
> > DTFT. You arrived at non-sense by assuming non-sense.
>
> Andor,
>
> I think you're being overly pedantic and confusing the OP with statements
> that contradict what myself and others have said.

Actually, Randy, I have only countered the wrong advice that both you
and Rune have given.

Mike's original question was this:

Mike wrote:
> Given a continuous time signal x(t), infinitely long.
> Sample it to obtain discrete time sequence x0, x1, x2,
> ..., xn, ..., infinitely long, with
> uniform samples spaced at T apart.
>
> Now I do two things:
>
> (1) Truncate the above sequence to make it finite,
> x0, x1, ..., xn, and take
> the DFT of the truncated sequence. Call the DFT F1(v).
> (Capitalized letters denote spectrum domain)
>
> 2) Without truncation, taking the DTFT of the infinitely
> long sequence x0, x1, ..., xn, .... Call the DTFT F2(v).
> And then take one period of F2(v), since it is periodic,
> and then sample F2(v) in the frequency domain to discretize
> it. Call the result F3(v), which is the discretized version
> of the one period of F2(v).

To elaborate: Let's say that the spectrum of F2(v) is being sampled at
N uniformly distributed points. Then F3 is discrete, and we must use a
discrete variable as argument. For example:

F3[k] = F2(2 pi k / N), k=0,1,...,N-1.

The same goes for F1, ie. F1 = F1[k], k=0,1,...,N-1.

>
> Both (1) and (2) yield vectors of length n in the spectrum
> domain, representing the discretized version of the
> spectrum.
>
> My question is: under what conditions do these two vectors
> of discretized spectrum equate?

So what Mike wants is to have F1[k] = F3[k]. Using the lemma I gave
before, we see that this is the case if the signal x[n] satisfies the
condition

x[n] = sum_{r=-infinity}^infinty x[n + r N], for n = 0,1,...,N-1.

Try a numeric example with N=2 and the following sequence x[n]:

x[n] = {... x[-3]=0, x[-2]=1/2, x[-1]=0,
x[0]=1, x[1]=-1,
x[2]=1/2, x[3]=0, .... }

The ellipses mean that x[n] = 0 for n <= -3 and n >= 3. Then the DFT
of x[0] and x[1] is equal to F1[k] = (1,3). The DTFT of x[n] is equal
to

F2(v) = 1/2 exp(2 j v) + 1 - exp(-j v) + 1/2 exp(- 2 j v).

So

F1[0] := F2(0) = 1/2 + 1 - 1 + 1/2 = 1,
and
F1[1] := F2(pi) = 1/2 + 1 + 1 + 1/2 = 3, ie. we have F1[k] = F3[k],
for k=0,1.

Regards,
Andor

...
> Try a numeric example with N=2 and the following sequence x[n]:

Oh man, I really screwed up this example. The corrected version
follows:

> x[n] = {... x[-3]=0, x[-2]=1/2, x[-1]=0,
> x[0]=1, x[1]=-1,
> x[2]=-1/2, x[3]=0, .... }
>
> The ellipses mean that x[n] = 0 for n <= -3 and n >= 3. Then the DFT
> of x[0] and x[1] is equal to F1[k] = (0,2). The DTFT of x[n] is equal
> to
>
> F2(v) = 1/2 exp(2 j v) + 1 - exp(-j v) - 1/2 exp(- 2 j v).
>
> So
>
> F1[0] := F2(0) = 1/2 + 1 - 1 - 1/2 = 0,
> and
> F1[1] := F2(pi) = 1/2 + 1 + 1 - 1/2 = 2, ie. we have F1[k] = F3[k],
> for k=0,1.

The condition for F1[k] = F3[k], for k=0,1,...,N-1 for some N, is that

x[n] = sum_{r=-infinity}^infinty x[n + r N], for n = 0,1,...,N-1.

Subtracting x[n] from both sides and re-arranging we get

sum_{r=1}^infinity x[n + r N] = sum_{r=1}^infinity x[n - r N], for n =
0,1,...,N-1.

Colloquially speaking, this means that the sum of the subsampled and
negative indexed values of x[n] has to be equal to the corresponding
sum of the larger-than-(N-1) indexed values of x[n]. The non-zero
values of x[n] for n =/= 0,1,...,N-1 can be arbitrarily large, they
just have to cancel in the above sense.

Regards,
Andor

well, here is an example of Google Groups completely dropping a post.
i noticed that happened to other folks here in the past. i hope i can
remember most of what i meant to say:

On May 24, 3:49 pm, Andor <andor.bari...@gmail.com> wrote:
> On 24 Mai, 19:15, Rune Allnor <all...@tele.ntnu.no> wrote:
>
...
>
> > IFF your infinitely long sequence is truly periodic AND
> > you happen to truncate it so that you have exactly one
> > period worth of data, then -- and only then -- your DFT
> > and your DTFT are equal.
>
> That statement is clearly wrong.

i agree with Andor.

> If the infinitely long sequence is
> periodic, then you cannot compute its DTFT (the sum doesn't converge).

yeah, but we deal with that problem with Dirac impulse functions just
as we do for the regular old continuous Fourier Transform. it's not a
big deal (except that it's a female canine to sample a Dirac delta
function, i guess that's a sorta big deal in the present context).

DTFT is to Z as Fourier is to Laplace.

> You can compute it's DFS, which is trivially related to the DFT of one
> period of the sequence.

i'm of the partisan persuasion that the DFT *is* the DFS. there is no
practical, conceptual, or meaningful difference between the two. the
DFT invertibly maps one periodic sequence of period N (of which you
only need N numbers to fully define such a sequence) in some domain to
another periodic sequence of period N in the reciprocal domain and the
iDFT does the same. that means, when you pass N numbers to the DFT it
"assumes" (if i am allowed to anthropomorphize) that those N numbers
represent one period of an infinite and periodic sequence. that
further means that the DFT inherently periodically extends the data
passed to it.

> However, for infinite sequences which have a
> DTFT (which is what Mike was talking about), one can state the
> following lemma:
>
> Let x[m], where m ranges over all integers, be a square-summable
> sequence, and X(w) its DTFT. Furthermore, let y[n], n=0,1,...N-1 be a
> finite vector, and Y[k] the DFT of y[n]. Then
>
> X(2*pi*k/N) = Y[k], k=0,1,...,N-1,
>
> if, and only if,
>
> y[n] = sum_{r=-infinity}^infinity x[n+r*N].

and this is also correct. and, in my partisan belief, Andor didn't
even have to limit the integer k to be 0 <= k < N. that's because, in
my partisan philosophy, there is no reason for either y[n] or Y[k] to
be finite sequences, only that they are fully describable by a finite
sequence (or "vector" if that is what you wanna call it) for it to be
passed to the DFT. often we think of x[n] as being a rectangularly
windowed copy of y[n] (for 0 <= n < N), but the above is more
general. there are an infinite number of possible x[n] that would
satisfy the conditions for such and the above is the necessary and
sufficient general expression.

r b-j

On 25 May, 07:59, Andor <andor.bari...@gmail.com> wrote:

> Now you may believe my little lemma or not, it doesn't matter. Maths
> is not about belief.

If you say so. Then maths it will be.

I said, in an earlier post, that there are four variations of
the Fourier transform to consider. These are (view with fixed
width font):


  Data domain Duration Name Acronym Condition

1 Continuous Infinite Fourier Transform FT Norm {x(t)} < inf
2 Continuous Finite Fourier Series FS Norm {x(t)} < inf
3 Discrete Infinite Discrete Time FT DTFT Norm {x[n]} < inf
4 Discrete Finite Discrete FT DFT Norm {x[n]} < inf

The various Forurier transforms are

                inf
FT: X(w) = integral x(t) exp(jwt) dt
               -inf

                a
FS: X(k) = integral x(t) exp(jw_kt) dt -inf < a < b < inf
               -b

              inf
DTFT: X(w) = sum x[n] exp(jwn)
             n=-inf

              N-1
DFT: X[k] = sum x[n] exp(j2pi nk/N)
              n=0

all of which are valid under the constraint on the form Norm{x} <
inf.

If understand your opinions as expressed in this and earlier threads
correctly, you acknowledge exactly one such norm for discrete-time
data:

E{x} = sum |x[n]|^2 < inf [1]

the sum being taken over n from -inf to inf for case 3) data, and
from 0 to N-1 for case 4) data. The constraint [1] holds trivially
for case 4) data as long as max{|x[n]|} < inf, which is usually
the case.

The striking feature with the various forms of the Fourier Transform
is that the complex exponential function appers in one form or
another in every variation of the transform. This is not surprisng,
as the objective of computing it is to express the data x in terms
of a set of exponential basis functions.

Let's see, then, what happens if we try to take the DTFT (case 3))
of this very same exponential function. Note that in the following,
only constraint imposed on the frequency w is that it is real-valued.
I don't assume or use any property. x'[n] means "complex conjugate
of x[n]":

x[n] = exp(jwn) [2]

|x[n]|^2 = x[n]x'[n] = exp(jwn)exp(-jwn) = 1 [3]

                         N
E{x[n]} = lim sum |x[n]|^2 [4.a]
               N->inf n=-N

                         N
            = lim sum 1 [4.b]
               N->inf n=-N


            = lim (2N + 1)
[4.c]
               N->inf

            = inf [4]


This is a very awkward situation, inasmuch as that the exponential
function we find so useful, and which is the reason why we are
interested in the Fourier tranform in the first place, are not
contained in the set of permittable solutions in cases 2) and 3),
if Norm {x} is on the form [1] or its equivalent integral form.

As you so conveniently stated, this is maths, not opinion or belief.
The only possible conclusion is that the DTFT and the norm [1] do
not work, as a pair.

We are doing this excercise to get hold of a form of the Fourier
transfrm which works in case 3), and the only degree of freedom
one has to play with is the norm which governs what functions
can be used.

Postulate, then, another candidate norm:

                 1 N
P{x} = lim --- sum |x[n]|^2 [5]
       N-> inf N n=-N

Try this norm with the above excercise. The only difference is
that there is a 1/N term squeezed between the "lim" and "sum",
to arrive at an expression instead of [4.c] as

                   1
P{x} = lim ---(2N + 1)
[6.a]
          N->inf N

                        1
     = lim 2 + --- [6.b]
          N->inf N

     = 2 < inf. [6]

With the norm P{x} it is easy to get the complex exponentials to
fit into the picture.

You may want to braden your horizon a bit before you go on
discussing the various forms of the Fourier tranform in the future.

Rune

On May 25, 12:41 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 25 May, 07:59, Andor <andor.bari...@gmail.com> wrote:
>
> > Now you may believe my little lemma or not, it doesn't matter. Maths
> > is not about belief.
>
> If you say so. Then maths it will be.
>
> I said, in an earlier post, that there are four variations of
> the Fourier transform to consider. These are (view with fixed
> width font):
>
> Data domain Duration Name Acronym Condition
>
> 1 Continuous Infinite Fourier Transform FT Norm {x(t)} < inf
> 2 Continuous Finite Fourier Series FS Norm {x(t)} < inf
> 3 Discrete Infinite Discrete Time FT DTFT Norm {x[n]} < inf
> 4 Discrete Finite Discrete FT DFT Norm {x[n]} < inf
>
> The various Forurier transforms are
>
> inf
> FT: X(w) = integral x(t) exp(jwt) dt
> -inf
>
> a
> FS: X(k) = integral x(t) exp(jw_kt) dt -inf < a < b < inf
> -b



this could be stated a little better (the a,b, thing is messed up),
like

                       a + 2*pi/w0
  FS: X[k] = w0/(2 pi) integral x(t) exp(j k w0 t) dt
                           a

                               for -inf < a < inf


> inf
> DTFT: X(w) = sum x[n] exp(jwn)
> n=-inf
>
> N-1
> DFT: X[k] = sum x[n] exp(j2pi nk/N)
> n=0
>
> all of which are valid under the constraint on the form Norm{x} <
> inf.
>
> If understand your opinions as expressed in this and earlier threads
> correctly, you acknowledge exactly one such norm for discrete-time
> data:
>
> E{x} = sum |x[n]|^2 < inf [1]
>
> the sum being taken over n from -inf to inf for case 3) data, and
> from 0 to N-1 for case 4) data. The constraint [1] holds trivially
> for case 4) data as long as max{|x[n]|} < inf, which is usually
> the case.
>
> The striking feature with the various forms of the Fourier Transform
> is that the complex exponential function appers in one form or
> another in every variation of the transform. This is not surprisng,
> as the objective of computing it is to express the data x in terms
> of a set of exponential basis functions.
>
> Let's see, then, what happens if we try to take the DTFT (case 3))
> of this very same exponential function. Note that in the following,
> only constraint imposed on the frequency w is that it is real-valued.
> I don't assume or use any property. x'[n] means "complex conjugate
> of x[n]":
>
> x[n] = exp(jwn) [2]
>
> |x[n]|^2 = x[n]x'[n] = exp(jwn)exp(-jwn) = 1 [3]
>
> N
> E{x[n]} = lim sum |x[n]|^2 [4.a]
> N->inf n=-N
>
> N
> = lim sum 1 [4.b]
> N->inf n=-N
>
> = lim (2N + 1)
> [4.c]
> N->inf
>
> = inf [4]
>
> This is a very awkward situation, inasmuch as that the exponential
> function we find so useful, and which is the reason why we are
> interested in the Fourier tranform in the first place, are not
> contained in the set of permittable solutions in cases 2) and 3),
> if Norm {x} is on the form [1] or its equivalent integral form.

this is why we have Dirac impulse functions and why we fight over
them. this infinite norm thing here doesn't bother me.

> As you so conveniently stated, this is maths, not opinion or belief.
> The only possible conclusion is that the DTFT and the norm [1] do
> not work, as a pair.
>
> We are doing this excercise to get hold of a form of the Fourier
> transfrm which works in case 3), and the only degree of freedom
> one has to play with is the norm which governs what functions
> can be used.
>
> Postulate, then, another candidate norm:
>
> 1 N
> P{x} = lim --- sum |x[n]|^2 [5]
> N-> inf N n=-N
>
> Try this norm with the above excercise. The only difference is
> that there is a 1/N term squeezed between the "lim" and "sum",
> to arrive at an expression instead of [4.c] as
>
> 1
> P{x} = lim ---(2N + 1)
> [6.a] N->inf N
>
>
> 1
> = lim 2 + --- [6.b]
> N->inf N
>
> = 2 < inf. [6]
>
> With the norm P{x} it is easy to get the complex exponentials to
> fit into the picture.
>
> You may want to braden your horizon a bit before you go on
> discussing the various forms of the Fourier tranform in the future.

Rune, i wouldn't be so confident.

all this (above) is fine and good (and maybe even correct, i'll look
it over some more), but you said:

> On 24 Mai, 19:15, Rune Allnor <all...@tele.ntnu.no> wrote:
> > IFF your infinitely long sequence is truly periodic AND
> > you happen to truncate it so that you have exactly one
> > period worth of data, then -- and only then -- your DFT
> > and your DTFT are equal.

and Andor said:

On May 24, 3:49 pm, Andor <andor.bari...@gmail.com> wrote:
> Let x[m], where m ranges over all integers, be a square-summable
> sequence, and X(w) its DTFT. Furthermore, let y[n], n=0,1,...N-1 be a
> finite vector, and Y[k] the DFT of y[n]. Then
>
> X(2*pi*k/N) = Y[k], k=0,1,...,N-1,
>
> if, and only if,
>
> y[n] = sum_{r=-infinity}^infinity x[n+r*N].

i still fail to see how this statement of Andors is refuted nor how
your previous statement is correct.

r b-j

On 25 May, 19:10, robert bristow-johnson <r...@audioimagination.com>
wrote:
> On May 25, 12:41 pm, Rune Allnor <all...@tele.ntnu.no> wrote:

> > You may want to braden your horizon a bit before you go on
> > discussing the various forms of the Fourier tranform in the future.
>
> Rune, i wouldn't be so confident.

That statement is adriect comment to Andor's refusal to accept
any norm except the E{x} norm. I have my own view about
Dirac's delta, which I am pretty certain differs from
yours, but that's not a topic I am prepared to discuss.
*My* focus in this thread, what the exchange with Andor
is concerned, has been the condidtions for the DTFT to
exist. The DFT is trivial. In order to understand how
the results of a DFT computations are related to a DTFT
concept (did I get the acronyms right this time?), one
needs to go through the basics in a bit more depth.

Rune

On May 25, 1:30 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 25 May, 19:10, robert bristow-johnson <r...@audioimagination.com>
> wrote:
>
> > On May 25, 12:41 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
> > > You may want to braden your horizon a bit before you go on
> > > discussing the various forms of the Fourier tranform in the future.
>
> > Rune, i wouldn't be so confident.
>
> That statement is a direct comment to Andor's refusal to accept
> any norm except the E{x} norm.

i thought it was about which of these two statements are correct:

On 24 Mai, 19:15, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> IFF your infinitely long sequence is truly periodic AND
> you happen to truncate it so that you have exactly one
> period worth of data, then -- and only then -- your DFT
> and your DTFT are equal.

On May 24, 3:49 pm, Andor <andor.bari...@gmail.com> wrote:
>
> Let x[m], where m ranges over all integers, be a square-summable
> sequence, and X(w) its DTFT. Furthermore, let y[n], n=0,1,...N-1 be a
> finite vector, and Y[k] the DFT of y[n]. Then
>
> X(2*pi*k/N) = Y[k], k=0,1,...,N-1,
>
> if, and only if,
>
> y[n] = sum_{r=-infinity}^infinity x[n+r*N].

both make pretty unambiguous claims that appear to me to be
incompatible with each other. so, which is correct?


> I have my own view about
> Dirac's delta, which I am pretty certain differs from
> yours, but that's not a topic I am prepared to discuss.

well, we know that. i only brought it up because of the problem that
sin() or cos() are not infinitely square summable which means,
depending on how anal one gets, that there is no Fourier Transform of
a sinusoid (or of DC). but, somehow, we still deal with sinusoids and
DC in the frequency domain anyway. that's the only reason i brought
it up.

> *My* focus in this thread, what the exchange with Andor
> is concerned, has been the condidtions for the DTFT to
> exist. The DFT is trivial.

yet we (here on comp.dsp) still fight sectarian wars over it (as we do
over the Dirac delta).

> In order to understand how
> the results of a DFT computations are related to a DTFT
> concept (did I get the acronyms right this time?), one
> needs to go through the basics in a bit more depth.

but what Andor said about the relationship between the two is
basically correct. i can't find a single thing wrong with it.
whereas what you said about that relationship was unnecessarily
restrictive. what made your statement incorrect was where you say:
"IFF" and "-- and only then --". that such a restriction is required
for mathematical correctness is itself incorrect.

r b-j

On 25 May, 20:34, robert bristow-johnson <r...@audioimagination.com>
wrote:
> On May 25, 1:30 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> > On 25 May, 19:10, robert bristow-johnson <r...@audioimagination.com>
> > wrote:
>
> > > On May 25, 12:41 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
> > > > You may want to braden your horizon a bit before you go on
> > > > discussing the various forms of the Fourier tranform in the future.
>
> > > Rune, i wouldn't be so confident.
>
> > That statement is a direct comment to Andor's refusal to accept
> > any norm except the E{x} norm.
>
> i thought it was about which of these two statements are correct:
>
> On 24 Mai, 19:15, Rune Allnor <all...@tele.ntnu.no> wrote:
>
>
>
> > IFF your infinitely long sequence is truly periodic AND
> > you happen to truncate it so that you have exactly one
> > period worth of data, then -- and only then -- your DFT
> > and your DTFT are equal.

This is correct. If you apply the DTFT to a signal which
happens to be exactly periodic (say, x[n]=sin[wn]), and then
compute the DFT over one period of the same signal, you
would get the same answer (possibly except for a scaling
constant). Yust try it and see.

> On May 24, 3:49 pm, Andor <andor.bari...@gmail.com> wrote:

> > Let x[m], where m ranges over all integers, be a square-summable
> > sequence, and X(w) its DTFT. Furthermore, let y[n], n=0,1,...N-1 be a
> > finite vector, and Y[k] the DFT of y[n]. Then
>
> > X(2*pi*k/N) = Y[k], k=0,1,...,N-1,
>
> > if, and only if,
>
> > y[n] = sum_{r=-infinity}^infinity x[n+r*N].
>
> both make pretty unambiguous claims that appear to me to be
> incompatible with each other. so, which is correct?

I thought I made it clear -- or maybe I phrased my
posts of yesterday too ironically -- that this claim,
combined with the E{x} norm, leads to a set of
conclusions wich in part are absurd,and otherwise
mutally contradictions.

...
> > In order to understand how
> > the results of a DFT computations are related to a DTFT
> > concept (did I get the acronyms right this time?), one
> > needs to go through the basics in a bit more depth.
>
> but what Andor said about the relationship between the two is
> basically correct. i can't find a single thing wrong with it.
> whereas what you said about that relationship was unnecessarily
> restrictive. what made your statement incorrect was where you say:
> "IFF" and "-- and only then --". that such a restriction is required
> for mathematical correctness is itself incorrect.

As I already said, just try to compute the DTFT and the DFT
for a periodic signal where the DTFT can be computed
analytically. Then try the same thing for a non-periodic
signal, which DTFT can be computed analytically. I would
suggest

x[n] = sin[wn] + sin[sqrt(2)wn]

Try and match the analytical DTFT with the computed DFT
and see if you can make it work.

Rune

On 25 May, 20:34, robert bristow-johnson <r...@audioimagination.com>
wrote:

> > IFF your infinitely long sequence is truly periodic AND
> > you happen to truncate it so that you have exactly one
> > period worth of data, then -- and only then -- your DFT
> > and your DTFT are equal.

Ah, sorry, you are right. There is one case where this
statement isn't true.

Suppose one has a signal which DTFT has two parts:

         c_n*d(w_n) w_n = n*w_0, n integer
X(w) =
         C_m*sinc_m(w) -inf <= w <= inf, m integer

where d() is Dirac's delta, C_n and c_n are complex-
valued constants and the sincs are designed such that

sinc_m(w_n) = 0 for all m.

In this case the DFT and the DTFT are not equal, as
the contributions from the sinc are never recorded
by the DFT, but the statement

DFT(k/N*w_s) = DTFT(k/N*w_s)

(i.e. the computed values of the DFT equals the
true values of the DTFT at those frequencies
where a 1:1 map between the DFT and the DTFT exists)
still holds.

Rune

On May 25, 3:21 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> > On 24 Mai, 19:15, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> > > IFF your infinitely long sequence is truly periodic AND
> > > you happen to truncate it so that you have exactly one
> > > period worth of data, then -- and only then -- your DFT
> > > and your DTFT are equal.
>
> This is correct.

no, the restriction "IFF" and "-- and only then --" is NOT correct.
it is INcorrect. taken as a whole, your statement is INcorrect.

> If you apply the DTFT to a signal which
> happens to be exactly periodic (say, x[n]=sin[wn]), and then
> compute the DFT over one period of the same signal, you
> would get the same answer (possibly except for a scaling
> constant). Just try it and see.

but that's not the point you made before. you are changing the
subject (and it's hard for me to believe that you are not aware of
that). you did NOT say:

   If [instead of "IFF"] your infinitely long sequence is
   truly periodic and you happen to truncate it so that you
   have exactly one period worth of data, then [restriction deleted]
   your DFT and your DTFT are equal.

this statement could be true, but the statement that you made
regarding your public discussion with Andor (so we witnesses get to be
arbiters of such) is not true. and Andor showed precisely why.
actually, all's that is needed to refute your first statement is a
single counter-example and Andor went above and beyond and rather than
put out a simple counter-example to refute your "-- and only then --"
claim, he offered instead the general counter-example.

Rune, he blew your argument away. your ship blown out of the water
with an Exocet missle. it's gone.

> > On May 24, 3:49 pm, Andor <andor.bari...@gmail.com> wrote:
> > > Let x[m], where m ranges over all integers, be a square-summable
> > > sequence, and X(w) its DTFT. Furthermore, let y[n], n=0,1,...N-1 be a
> > > finite vector, and Y[k] the DFT of y[n]. Then
>
> > > X(2*pi*k/N) = Y[k], k=0,1,...,N-1,
>
> > > if, and only if,
>
> > > y[n] = sum_{r=-infinity}^infinity x[n+r*N].
>
> > both make pretty unambiguous claims that appear to me to be
> > incompatible with each other. so, which is correct?
>
> I thought I made it clear -- or maybe I phrased my
> posts of yesterday too ironically -- that this claim,
> combined with the E{x} norm, leads to a set of
> conclusions wich in part are absurd,and otherwise
> mutally contradictions.

i don't see a single absurd or mutually contradictory assertion in
Andor's "lemma".


> ...
>
> > > In order to understand how
> > > the results of a DFT computations are related to a DTFT
> > > concept (did I get the acronyms right this time?), one
> > > needs to go through the basics in a bit more depth.
>
> > but what Andor said about the relationship between the two is
> > basically correct. i can't find a single thing wrong with it.
> > whereas what you said about that relationship was unnecessarily
> > restrictive. what made your statement incorrect was where you say:
> > "IFF" and "-- and only then --". that such a restriction is required
> > for mathematical correctness is itself incorrect.
>
> As I already said, just try to compute the DTFT and the DFT
> for a periodic signal where the DTFT can be computed
> analytically. Then try the same thing for a non-periodic
> signal, which DTFT can be computed analytically. I would
> suggest
>
> x[n] = sin[wn] + sin[sqrt(2)wn]
>
> Try and match the analytical DTFT with the computed DFT
> and see if you can make it work.

but Andor was placing the qualification of "square summable" to it.
your x[n] doesn't satisfy that. your X(w) has four discrete Dirac
delta functions in it and sampling a continuous-frequency function
with Dirac deltas is problematic, as we all agree. i was limiting my
comment to the correctness of two statements, one made by you and the
other made by Andor.

r b-j

On 25 May, 22:07, robert bristow-johnson <r...@audioimagination.com>
wrote:
> On May 25, 3:21 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
>
>
>
> > > On 24 Mai, 19:15, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> > > > IFF your infinitely long sequence is truly periodic AND
> > > > you happen to truncate it so that you have exactly one
> > > > period worth of data, then -- and only then -- your DFT
> > > > and your DTFT are equal.
>
> > This is correct.
>
> no, the restriction "IFF" and "-- and only then --" is NOT correct.
> it is INcorrect. taken as a whole, your statement is INcorrect.

I corrected that in a follow-up to my own post.

> this statement could be true, but the statement that you made
> regarding your public discussion with Andor (so we witnesses get to be
> arbiters of such) is not true. and Andor showed precisely why.
> actually, all's that is needed to refute your first statement is a
> single counter-example and Andor went above and beyond and rather than
> put out a simple counter-example to refute your "-- and only then --"
> claim, he offered instead the general counter-example.

> but Andor was placing the qualification of "square summable" to it.

Exactly. And I have shown why that restriction is too strict,
ref my discussion about the various Fourier transforms, and
also demonstrated why it is absurd.

Rune

On May 25, 3:46 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 25 May, 20:34, robert bristow-johnson <r...@audioimagination.com>
> wrote:
> > Rune said:
> > > IFF your infinitely long sequence is truly periodic AND
> > > you happen to truncate it so that you have exactly one
> > > period worth of data, then -- and only then -- your DFT
> > > and your DTFT are equal.
>
> Ah, sorry, you are right. There is one case where this
> statement isn't true.

there are an infinite number of cases where it is not true (the
restrictive "and only then"), and Andor's "lemma" spelled it out.

r b-j

i forgot to mention:

On May 25, 3:46 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> In this case the DFT and the DTFT are not equal, as
> the contributions from the sinc are never recorded
> by the DFT, but the statement
>
> DFT(k/N*w_s) = DTFT(k/N*w_s)
>
> (i.e. the computed values of the DFT equals the
> true values of the DTFT at those frequencies
> where a 1:1 map between the DFT and the DTFT exists)
> still holds.

the left half, "DFT(k/N*w_s)", makes no sense to me at all.

the output of the DFT is discrete. it has no definition for non-
integer argument.

r b-j

On 25 May, 22:21, robert bristow-johnson <r...@audioimagination.com>
wrote:
> i forgot to mention:
>
> On May 25, 3:46 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
>
>
>
> > In this case the DFT and the DTFT are not equal, as
> > the contributions from the sinc are never recorded
> > by the DFT, but the statement
>
> > DFT(k/N*w_s) = DTFT(k/N*w_s)
>
> > (i.e. the computed values of the DFT equals the
> > true values of the DTFT at those frequencies
> > where a 1:1 map between the DFT and the DTFT exists)
> > still holds.
>
> the left half, "DFT(k/N*w_s)", makes no sense to me at all.
>
> the output of the DFT is discrete. it has no definition for non-
> integer argument.

Exatly. The N-pt DFT produces a set of equidistant coefficents
in the spectrum which is normalized wrt to what will be the
sampling frequency if the data are sampled from a continuous-time
signal. The DTFT is periodic with period this same frequency

I introduced w_s as a normalizing frequency (which
is the sampling frequency if the data are actually sampled)
to relate the coefficients in the discrete spectrum to
the contionuous spectrum.

Rune

Hi Andor,

Andor <andor.bariska@gmail.com> writes:
> [...]
> To elaborate: Let's say that the spectrum of F2(v) is being sampled at
> N uniformly distributed points. Then F3 is discrete, and we must use a
> discrete variable as argument.

Well, I think here is exactly where the problem lies.

This is difficult to express and type over usenet, so please
bear with me.

The first problem is that when you're using the DTFT, the output
spectrum is necessarily continuous and not discrete. OK you say,
but we're sampling it, making it discrete.

Well that brings in the next problem. If x(t) is periodic, then F3(f) will have
delta functions in it. And if the period of x(t) is exactly N*T,
then when you sample in frequency at k*Fs/N, k = 0, 1, ..., N-1, then
you're sampling right on a delta function, which has no value (it blows up).

In fact you could say that such a function HAS NO DTFT since it's
infinite energy, but we can get around that with Dirac delta
functions.

So if we're using precise mathematical terminology, F3(k*Fs/N) does
not exist when x(t) is periodic.

That's why I was referring to the Dirac delta function and
infinite-energy signals. You can still make a mapping from one (the
DTFT) to the other (DFT), but you would have to use the *AREA* of the
delta function for the value of F3(k) (to use your notation). Without
this "mapping," I agree that it simply is not true that F1(k) = F3(k).

But I also would argue that this doesn't substantially change the response
to Mike. Practically speaking, the two are equivalent when x(t) is periodic
with period N*T.

Have I bridged our disconnect, or are we still in the dark?
--
% Randy Yates % "Though you ride on the wheels of tomorrow,
%% Fuquay-Varina, NC % you still wander the fields of your
%%% 919-577-9882 % sorrow."
%%%% <yates@ieee.org> % '21st Century Man', *Time*, ELO
http://home.earthlink.net/~yatescr

Sorry, but I botched the notation a bit. I was writing F3 in places where
I should've written F2. See corrections below.

--Randy

Randy Yates <yates@ieee.org> writes:

> Hi Andor,
>
> Andor <andor.bariska@gmail.com> writes:
>> [...]
>> To elaborate: Let's say that the spectrum of F2(v) is being sampled at
>> N uniformly distributed points. Then F3 is discrete, and we must use a
>> discrete variable as argument.
>
> Well, I think here is exactly where the problem lies.
>
> This is difficult to express and type over usenet, so please
> bear with me.
>
> The first problem is that when you're using the DTFT, the output
> spectrum

I.e., F2(v),

> is necessarily continuous and not discrete. OK you say,
> but we're sampling it, making it discrete.
>
> Well that brings in the next problem. If x(t) is periodic, then F3(f)

should be F2(v)

> will have
> delta functions in it. And if the period of x(t) is exactly N*T,
> then when you sample in frequency at k*Fs/N, k = 0, 1, ..., N-1, then
> you're sampling right on a delta function, which has no value (it blows up).
>
> In fact you could say that such a function HAS NO DTFT since it's
> infinite energy, but we can get around that with Dirac delta
> functions.
>
> So if we're using precise mathematical terminology, F3(k*Fs/N)

should be F2(k*Fs/N)

> does not exist when x(t) is periodic.
>
> That's why I was referring to the Dirac delta function and
> infinite-energy signals. You can still make a mapping from one (the
> DTFT) to the other (DFT), but you would have to use the *AREA* of the
> delta function for the value of F3(k) (to use your notation). Without
> this "mapping," I agree that it simply is not true that F1(k) = F3(k).
>
> But I also would argue that this doesn't substantially change the response
> to Mike. Practically speaking, the two are equivalent when x(t) is periodic
> with period N*T.
>
> Have I bridged our disconnect, or are we still in the dark?
> --
> % Randy Yates % "Though you ride on the wheels of tomorrow,
> %% Fuquay-Varina, NC % you still wander the fields of your
> %%% 919-577-9882 % sorrow."
> %%%% <yates@ieee.org> % '21st Century Man', *Time*, ELO
> http://home.earthlink.net/~yatescr

--
% Randy Yates % "How's life on earth?
%% Fuquay-Varina, NC % ... What is it worth?"
%%% 919-577-9882 % 'Mission (A World Record)',
%%%% <yates@ieee.org> % *A New World Record*, ELO
http://home.earthlink.net/~yatescr

On 25 May, 22:07, robert bristow-johnson <r...@audioimagination.com>
wrote:
> i don't see a single absurd or mutually contradictory assertion in
> Andor's "lemma".

OK. I've cut'n pasted the essential parts from some posts of
yesterday. It should contain the keys:

Me:

> sum |x[n]|^2 < inf [1]
> n
...
> k+N 1
> lim sum --- |x[n]|^2 < inf [2]
> N->inf n=k N

Andor:

> > Let x[m], where m ranges over all integers, be a square-summable
> > sequence, and X(w) its DTFT.

Me:

> You need to specify in what sense it is square integrable,
> form [1] or form [2] above.

Andor:

> As with DTFT, I only know of one definition for a sequence to be
> "square-summable" (your [1]).

The key of Andor's Lemma:

> y[n] = sum_{r=-infinity}^infinity x[n+r*N].

Can you or anyone else show me a non-trivial[*] periodic
sequence x[n], with period N, where y[n] defined as this
*is* square summable in the sense [1] above? Remember,
the summation range is infinite.

Since you can not, you necessarily have to reject the
notion of the DTFT itself, since it is based on non-trivial
periodic functions with period N.

Again, all the problems go away if one instead of [1]
above relaxes the definition of "square summable" to
[2] above.

Rune

[*] Non-trivial periodic function: A function x[n]= x[n+N]
    where not all entries are zero. For such a function,
    at least one coefficient x[m] in the range 0<= n < N
    is non-zero. Substitute into Andor's lemma:

    y[m] = sum_{r=-infinity}^infinity x[m+r*N]

                     R
         = lim sum x[m+r*N]
           R-> inf r=-R

         = lim 2R x[m]
           R-> inf

         = inf

    which means that y[m] violates the only constraint
    Andor acknowledges. The result is a contradiction.
    Rejecting the existense of the DTFT is absurd.

On May 25, 4:14 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 25 May, 22:07, robert bristow-johnson <r...@audioimagination.com>
> wrote:
>
> > On May 25, 3:21 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> > > > On 24 Mai, 19:15, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> > > > > IFF your infinitely long sequence is truly periodic AND
> > > > > you happen to truncate it so that you have exactly one
> > > > > period worth of data, then -- and only then -- your DFT
> > > > > and your DTFT are equal.
>
> > > This is correct.

lessee, here you are saying it "is correct" (with no reference to
"correcting" it in a follow-up)...

> > no, the restriction "IFF" and "-- and only then --" is NOT correct.
> > it is INcorrect. taken as a whole, your statement is INcorrect.
>
> I corrected that in a follow-up to my own post.

and here you are saying or impling it was not correct.


> > this statement could be true, but the statement that you made
> > regarding your public discussion with Andor (so we witnesses get to be
> > arbiters of such) is not true. and Andor showed precisely why.
> > actually, all's that is needed to refute your first statement is a
> > single counter-example and Andor went above and beyond and rather than
> > put out a simple counter-example to refute your "-- and only then --"
> > claim, he offered instead the general counter-example.
> > but Andor was placing the qualification of "square summable" to it.
>
> Exactly. And I have shown why that restriction is too strict,
> ref my discussion about the various Fourier transforms, and
> also demonstrated why it is absurd.

you can say "Exactly." if you want, but what you are saying is
"Exactly" to the fact of your original claim, that you were doggedly
defending, being wrong. but somehow, you're turning that around from
a concession (what it should be - hey, we *all* make mistakes) to a
continued defense, as if what you were saying was correct all along.
this strikes a few familiar neurons with me, Rune, which is why I (and
others) have had frustrating discussions with you in the past. you
need to be careful about some of the things you say (and defend as
absolute truth) and then at the times you might miss that goal, when
your statement that you doggedly defend is shown to be wrong, the
easiest thing to do is say "ooops" rather than try to twist it around
to imply that you were right all along.

the "square summable" thing is simply necessary because, if x[n] is
square summable, the DTFT of x[n] does not have any Dirac delta
(pseudo)functions in it. then it is meaningful to sample the DTFT
anywhere including sampling it at uniformly spaced points on the unit
circle. then the question to ask is how do those discrete samples of
the DTFT output compare to the DFT of some y[n] where y[n] is related
in some way to x[n] and Andor spelled that out completely and
correctly despite your previous refutation of it.

r b-j

On 25 Mai, 22:32, Randy Yates <y...@ieee.org> wrote:
> Hi Andor,
>
> Andor <andor.bari...@gmail.com> writes:
> > [...]
> > To elaborate: Let's say that the spectrum of F2(v) is being sampled at
> > N uniformly distributed points. Then F3 is discrete, and we must use a
> > discrete variable as argument.
>
> Well, I think here is exactly where the problem lies.
>
> This is difficult to express and type over usenet, so please
> bear with me.
>
> The first problem is that when you're using the DTFT, the output
> spectrum is necessarily continuous and not discrete. OK you say,
> but we're sampling it, making it discrete.
>
> Well that brings in the next problem. If x(t) is periodic, then F3(f) will have
> delta functions in it. And if the period of x(t) is exactly N*T,
> then when you sample in frequency at k*Fs/N, k = 0, 1, ..., N-1, then
> you're sampling right on a delta function, which has no value (it blows up).
>
> In fact you could say that such a function HAS NO DTFT since it's
> infinite energy, but we can get around that with Dirac delta
> functions.
>
> So if we're using precise mathematical terminology, F3(k*Fs/N) does
> not exist when x(t) is periodic.

I was going to write a lengthy piece on this, but thanks, you have
spared me the work. That is exactly the point: if you choose to expand
the definition of the DTFT using the dirac delta, you cannot sample it
on evenly spaced points in the frequency domain, because on those
points, the value is not defined. However, Mike was exactly refering
to this scenario of sampling the DTFT. It may therefore be safe to
assume he was excluding periodic sequences, which were put forwards as
an answer to his question both by you and Rune.

>
> That's why I was referring to the Dirac delta function and
> infinite-energy signals. You can still make a mapping from one (the
> DTFT) to the other (DFT), but you would have to use the *AREA* of the
> delta function for the value of F3(k) (to use your notation). Without
> this "mapping," I agree that it simply is not true that F1(k) = F3(k).
>
> But I also would argue that this doesn't substantially change the response
> to Mike. Practically speaking, the two are equivalent when x(t) is periodic
> with period N*T.
>
> Have I bridged our disconnect, or are we still in the dark?

At least we seem to be on the same wavelength :-). Did you understand
my general condition for sequences to have a DTFT that passes through
the DFT of the first N samples? Did you have a look at my example?

Regards,
Andor

On 25 Mai, 22:14, robert bristow-johnson <r...@audioimagination.com>
wrote:
> On May 25, 3:46 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> > On 25 May, 20:34, robert bristow-johnson <r...@audioimagination.com>
> > wrote:
> > > Rune said:
> > > > IFF your infinitely long sequence is truly periodic AND
> > > > you happen to truncate it so that you have exactly one
> > > > period worth of data, then -- and only then -- your DFT
> > > > and your DTFT are equal.
>
> > Ah, sorry, you are right. There is one case where this
> > statement isn't true.
>
> there are an infinite number of cases where it is not true (the
> restrictive "and only then"), and Andor's "lemma" spelled it out.

He doesn't believe the lemma :-), so there really is no point in
arguing.

Regards,
Andor

On 25 May, 23:38, robert bristow-johnson <r...@audioimagination.com>
wrote:
> On May 25, 4:14 pm, Rune Allnor <all...@tele.ntnu.no> wrote:


> > > > This is correct.
>
> lessee, here you are saying it "is correct" (with no reference to
> "correcting" it in a follow-up)...

Robert, it is friday night and I am at sea, well into my
4th week of the tour and have little to do except staying
awake. But even this exchange with you is starting to
become boring.

> > > no, the restriction "IFF" and "-- and only then --" is NOT correct.
> > > it is INcorrect. taken as a whole, your statement is INcorrect.
>
> > I corrected that in a follow-up to my own post.
>
> and here you are saying or impling it was not correct.

No. I am sayiong that the first statement was incomplete.
If you read and contemplate my claim and the correction,
you will see that what the DFT picks up from the DTFT does
not change, but in my correction I open up for that there
may be sinc-type contributions in the spectrum which the
DFT can not record. On the other hand, we know from
samoling theory that sinc interpolation in time domain
is consistent with the spectrum being periodic in frequency
domain. If the same turns out to be true here -- I don't
know, I have not done the arithmetics -- there would be
nothing in my correction to contradic the first claim that
the infinite duration sequence must be periodic.

> you can say "Exactly." if you want, but what you are saying is
> "Exactly" to the fact of your original claim, that you were doggedly
> defending, being wrong.

The claim was incomplete, not wrong. There is a difference.
And I am not "doggedly defending" anything. I post my claims
for anyone to see, making the effort (despite the odd typo)
that they are comprehensable and checkable. I have made
enough enemies around USENET for people to have a lion's
feast on any claim I should make which turned out to be
undefendable.

> but somehow, you're turning that around from
> a concession (what it should be - hey, we *all* make mistakes) to a
> continued defense, as if what you were saying was correct all along.

I, as well as everybody else, make mistakes. Some are
insignificant, others are not. Andor, for instance,
pointed out a glitch between "DFT" and "DTFT".
Those kinds of glitches don't mean my views are
undefendable. It means I have to work harder to
make my points clear.

> this strikes a few familiar neurons with me, Rune, which is why I (and
> others) have had frustrating discussions with you in the past.

Why frustrating? Challenging, yes. I find it very
stimulating to exchange views with intelligent,
competent people.

> you
> need to be careful about some of the things you say (and defend as
> absolute truth) and then at the times you might miss that goal, when
> your statement that you doggedly defend is shown to be wrong, the
> easiest thing to do is say "ooops" rather than try to twist it around
> to imply that you were right all along.

Well, the two most powerful phrases in a man's vocabulary
are "I don't know" and "I was wrong". Once you use either
one of those, you have made progress in your knowledge and
wisdom.

You should try them.

Rune


> the "square summable" thing is simply necessary because, if x[n] is
> square summable, the DTFT of x[n] does not have any Dirac delta
> (pseudo)functions in it. then it is meaningful to sample the DTFT
> anywhere including sampling it at uniformly spaced points on the unit
> circle. then the question to ask is how do those discrete samples of
> the DTFT output compare to the DFT of some y[n] where y[n] is related
> in some way to x[n] and Andor spelled that out completely and
> correctly despite your previous refutation of it.
>
> r b-j

On 25 Mai, 22:50, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 25 May, 22:07, robert bristow-johnson <r...@audioimagination.com>
> wrote:
>
> > i don't see a single absurd or mutually contradictory assertion in
> > Andor's "lemma".
>
> OK. I've cut'n pasted the essential parts from some posts of
> yesterday. It should contain the keys:
>
> Me:
>
>
>
> > sum |x[n]|^2 < inf [1]
> > n
> ...
> > k+N 1
> > lim sum --- |x[n]|^2 < inf [2]
> > N->inf n=k N
>
> Andor:
>
> > > Let x[m], where m ranges over all integers, be a square-summable
> > > sequence, and X(w) its DTFT.
>
> Me:
>
> > You need to specify in what sense it is square integrable,
> > form [1] or form [2] above.
>
> Andor:
>
> > As with DTFT, I only know of one definition for a sequence to be
> > "square-summable" (your [1]).
>
> The key of Andor's Lemma:
>
> > y[n] = sum_{r=-infinity}^infinity x[n+r*N].
>
> Can you or anyone else show me a non-trivial[*] periodic
> sequence x[n], with period N, where y[n] defined as this
> *is* square summable in the sense [1] above? Remember,
> the summation range is infinite.

Rune, you are completely missing the statement of the lemma. Not y[n]
has to be square-summable (it trivially is, being only a finite length
vector), but x[n] has to be square-summable! This precludes x[n] being
periodic.


> Since you can not, you necessarily have to reject the
> notion of the DTFT itself, since it is based on non-trivial
> periodic functions with period N.
>
> Again, all the problems go away if one instead of [1]
> above relaxes the definition of "square summable" to
> [2] above.

All the problems go away once you understand that lemma.

Regards,
Andor

On May 25, 5:51 pm, Andor <andor.bari...@gmail.com> wrote:
> On 25 Mai, 22:14, robert bristow-johnson <r...@audioimagination.com>
> wrote:
>
> > On May 25, 3:46 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> > > On 25 May, 20:34, robert bristow-johnson <r...@audioimagination.com>
> > > wrote:
> > > > Rune said:
> > > > > IFF your infinitely long sequence is truly periodic AND
> > > > > you happen to truncate it so that you have exactly one
> > > > > period worth of data, then -- and only then -- your DFT
> > > > > and your DTFT are equal.
>
> > > Ah, sorry, you are right. There is one case where this
> > > statement isn't true.
>
> > there are an infinite number of cases where it is not true (the
> > restrictive "and only then"), and Andor's "lemma" spelled it out.
>
> He doesn't believe the lemma :-),

or he's not admitting to it (which would be a concession that seems to
be anathema to Rune).

> so there really is no point in arguing.

i know. it's a deja-vu. i gave it a hard effort. i'm frustrated
with it. i'll just leave it alone. Rune is clearly not in the same
league as Beanie or eBob, but it appears to me that they sometimes
play the same game. Rune can have the last word as far as i'm
concerned.

r b-j

On 25 May, 23:57, Andor <andor.bari...@gmail.com> wrote:
> On 25 Mai, 22:50, Rune Allnor <all...@tele.ntnu.no> wrote:

> > The key of Andor's Lemma:
>
> > > y[n] = sum_{r=-infinity}^infinity x[n+r*N].
>
> > Can you or anyone else show me a non-trivial[*] periodic
> > sequence x[n], with period N, where y[n] defined as this
> > *is* square summable in the sense [1] above? Remember,
> > the summation range is infinite.
>
> Rune, you are completely missing the statement of the lemma. Not y[n]
> has to be square-summable (it trivially is, being only a finite length
> vector), but x[n] has to be square-summable! This precludes x[n] being
> periodic.

That's my point. On two different occations have I commented on
the fact that the sum over x is infinite. And the consequence
is that the DTFT because of that, has to be invalid if you want
to use it with periodic functions. And what is the purpose of
the DTFT? Express arbitrary functions in terms of periodic
functions.

Which is what I find absurd.

> > Since you can not, you necessarily have to reject the
> > notion of the DTFT itself, since it is based on non-trivial
> > periodic functions with period N.
>
> > Again, all the problems go away if one instead of [1]
> > above relaxes the definition of "square summable" to
> > [2] above.
>
> All the problems go away once you understand that lemma.

I understand the lemma. You admitted as much above, by your
statement of x[n] being periodic, above. The question is
whether you understand the implication of that lemma.

Rune

On 26 May, 02:22, robert bristow-johnson <r...@audioimagination.com>
wrote:
> On May 25, 5:51 pm, Andor <andor.bari...@gmail.com> wrote:
>
> or he's not admitting to it (which would be a concession that seems to
> be anathema to Rune).

It wasn't me who first made the statement in this therad
that one needs to separate between maths and beliefs.

> > so there really is no point in arguing.
>
> i know. it's a deja-vu. i gave it a hard effort. i'm frustrated
> with it. i'll just leave it alone. Rune is clearly not in the same
> league as Beanie or eBob, but it appears to me that they sometimes
> play the same game. Rune can have the last word as far as i'm
> concerned.

Robert, your frustration might ease off a bit if you address
my arguments and not my person. Everything is there, spelled
out as best I can within the limitations of text-based
USENET posts. All you need to do is to read my posts.

Rune

On 26 Mai, 02:40, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 25 May, 23:57, Andor <andor.bari...@gmail.com> wrote:
>
> > On 25 Mai, 22:50, Rune Allnor <all...@tele.ntnu.no> wrote:
> > > The key of Andor's Lemma:
>
> > > > y[n] = sum_{r=-infinity}^infinity x[n+r*N].
>
> > > Can you or anyone else show me a non-trivial[*] periodic
> > > sequence x[n], with period N, where y[n] defined as this
> > > *is* square summable in the sense [1] above? Remember,
> > > the summation range is infinite.
>
> > Rune, you are completely missing the statement of the lemma. Not y[n]
> > has to be square-summable (it trivially is, being only a finite length
> > vector), but x[n] has to be square-summable! This precludes x[n] being
> > periodic.
>
> That's my point. On two different occations have I commented on
> the fact that the sum over x is infinite. And the consequence
> is that the DTFT because of that, has to be invalid if you want
> to use it with periodic functions. And what is the purpose of
> the DTFT? Express arbitrary functions in terms of periodic
> functions.
>
> Which is what I find absurd.
>
> > > Since you can not, you necessarily have to reject the
> > > notion of the DTFT itself, since it is based on non-trivial
> > > periodic functions with period N.
>
> > > Again, all the problems go away if one instead of [1]
> > > above relaxes the definition of "square summable" to
> > > [2] above.
>
> > All the problems go away once you understand that lemma.
>
> I understand the lemma. You admitted as much above, by your
> statement of x[n] being periodic, above.

:-)

x[n] IS NOT PERIODIC!

On 25 Mai, 22:21, robert bristow-johnson <r...@audioimagination.com>
wrote:
> i forgot to mention:
>
> On May 25, 3:46 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
>
>
>
> > In this case the DFT and the DTFT are not equal, as
> > the contributions from the sinc are never recorded
> > by the DFT, but the statement
>
> > DFT(k/N*w_s) = DTFT(k/N*w_s)
>
> > (i.e. the computed values of the DFT equals the
> > true values of the DTFT at those frequencies
> > where a 1:1 map between the DFT and the DTFT exists)
> > still holds.
>
> the left half, "DFT(k/N*w_s)", makes no sense to me at all.
>
> the output of the DFT is discrete. it has no definition for non-
> integer argument.

The funny thing is, the right half makes no sense either for the
generalized DTFT of periodic signals.

Since the generalized DTFT of periodic signals is always a
periodically weighted dirac train, sampling it at N uniform points in
the spectrum (N the period of the signal) always returns infinity (or
undefined, depending on how you want the value of the dirac delta to
be at 0).

So much for broadening the horizon about Fourier transforms ....

Regards,
Andor

On 26 May, 10:04, Andor <andor.bari...@gmail.com> wrote:
> On 26 Mai, 02:40, Rune Allnor <all...@tele.ntnu.no> wrote:
>
>
>
>
>
> > On 25 May, 23:57, Andor <andor.bari...@gmail.com> wrote:
>
> > > On 25 Mai, 22:50, Rune Allnor <all...@tele.ntnu.no> wrote:
> > > > The key of Andor's Lemma:
>
> > > > > y[n] = sum_{r=-infinity}^infinity x[n+r*N].
>
> > > > Can you or anyone else show me a non-trivial[*] periodic
> > > > sequence x[n], with period N, where y[n] defined as this
> > > > *is* square summable in the sense [1] above? Remember,
> > > > the summation range is infinite.
>
> > > Rune, you are completely missing the statement of the lemma. Not y[n]
> > > has to be square-summable (it trivially is, being only a finite length
> > > vector), but x[n] has to be square-summable! This precludes x[n] being
> > > periodic.
>
> > That's my point. On two different occations have I commented on
> > the fact that the sum over x is infinite. And the consequence
> > is that the DTFT because of that, has to be invalid if you want
> > to use it with periodic functions. And what is the purpose of
> > the DTFT? Express arbitrary functions in terms of periodic
> > functions.
>
> > Which is what I find absurd.
>
> > > > Since you can not, you necessarily have to reject the
> > > > notion of the DTFT itself, since it is based on non-trivial
> > > > periodic functions with period N.
>
> > > > Again, all the problems go away if one instead of [1]
> > > > above relaxes the definition of "square summable" to
> > > > [2] above.
>
> > > All the problems go away once you understand that lemma.
>
> > I understand the lemma. You admitted as much above, by your
> > statement of x[n] being periodic, above.
>
> :-)
>
> x[n] IS NOT PERIODIC!- Hide quoted text -

OK, for the sake of argument, I accept that you disregard the
DTFT as a useful tool for periodic functions. Let's see
wehere else it fails, according to your criterion:

DC: x[n] = x

sum_{r=-infinity}^infinity x[n+r*N]

             inf
  = lim sum x = lim Rx = inf
    R->inf r= -inf R->inf

Do you accept that the DTFT works for signals whuch have
a non-vanishing DC component?

If "no", what, in your mind, is the reason why the
DTFT (and the FT, for that matter) is still taught
in both maths and engineering classes? According
to your arguments they don't work. Yet, virtually
all electronic devices and DSP applications -- even
the ones that work -- are based on them.

Where is the flaw? In the concepts of DTFT and FT?
Elsewhere?

Rune

On 26 Mai, 18:04, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 26 May, 10:04, Andor <andor.bari...@gmail.com> wrote:
>
>
>
>
>
> > On 26 Mai, 02:40, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> > > On 25 May, 23:57, Andor <andor.bari...@gmail.com> wrote:
>
> > > > On 25 Mai, 22:50, Rune Allnor <all...@tele.ntnu.no> wrote:
> > > > > The key of Andor's Lemma:
>
> > > > > > y[n] = sum_{r=-infinity}^infinity x[n+r*N].
>
> > > > > Can you or anyone else show me a non-trivial[*] periodic
> > > > > sequence x[n], with period N, where y[n] defined as this
> > > > > *is* square summable in the sense [1] above? Remember,
> > > > > the summation range is infinite.
>
> > > > Rune, you are completely missing the statement of the lemma. Not y[n]
> > > > has to be square-summable (it trivially is, being only a finite length
> > > > vector), but x[n] has to be square-summable! This precludes x[n] being
> > > > periodic.
>
> > > That's my point. On two different occations have I commented on
> > > the fact that the sum over x is infinite. And the consequence
> > > is that the DTFT because of that, has to be invalid if you want
> > > to use it with periodic functions. And what is the purpose of
> > > the DTFT? Express arbitrary functions in terms of periodic
> > > functions.
>
> > > Which is what I find absurd.
>
> > > > > Since you can not, you necessarily have to reject the
> > > > > notion of the DTFT itself, since it is based on non-trivial
> > > > > periodic functions with period N.
>
> > > > > Again, all the problems go away if one instead of [1]
> > > > > above relaxes the definition of "square summable" to
> > > > > [2] above.
>
> > > > All the problems go away once you understand that lemma.
>
> > > I understand the lemma. You admitted as much above, by your
> > > statement of x[n] being periodic, above.
>
> > :-)
>
> > x[n] IS NOT PERIODIC!- Hide quoted text -
>
> OK, for the sake of argument, I accept that you disregard the
> DTFT as a useful tool for periodic functions. Let's see
> wehere else it fails, according to your criterion:
>
> DC: x[n] = x
>
> sum_{r=-infinity}^infinity x[n+r*N]
>
> inf
> = lim sum x = lim Rx = inf
> R->inf r= -inf R->inf
>
> Do you accept that the DTFT works for signals whuch have
> a non-vanishing DC component?
>
> If "no", what, in your mind, is the reason why the
> DTFT (and the FT, for that matter) is still taught
> in both maths and engineering classes? According
> to your arguments they don't work. Yet, virtually
> all electronic devices and DSP applications -- even
> the ones that work -- are based on them.
>
> Where is the flaw? In the concepts of DTFT and FT?
> Elsewhere?

The flaw is your non-understanding of my arguments.

Regards,
Andor

On 27 May, 13:30, Andor <andor.bari...@gmail.com> wrote:
> On 26 Mai, 18:04, Rune Allnor <all...@tele.ntnu.no> wrote:
>
>
>
>
>
> > On 26 May, 10:04, Andor <andor.bari...@gmail.com> wrote:
>
> > > On 26 Mai, 02:40, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> > > > On 25 May, 23:57, Andor <andor.bari...@gmail.com> wrote:
>
> > > > > On 25 Mai, 22:50, Rune Allnor <all...@tele.ntnu.no> wrote:
> > > > > > The key of Andor's Lemma:
>
> > > > > > > y[n] = sum_{r=-infinity}^infinity x[n+r*N].
>
> > > > > > Can you or anyone else show me a non-trivial[*] periodic
> > > > > > sequence x[n], with period N, where y[n] defined as this
> > > > > > *is* square summable in the sense [1] above? Remember,
> > > > > > the summation range is infinite.
>
> > > > > Rune, you are completely missing the statement of the lemma. Not y[n]
> > > > > has to be square-summable (it trivially is, being only a finite length
> > > > > vector), but x[n] has to be square-summable! This precludes x[n] being
> > > > > periodic.
>
> > > > That's my point. On two different occations have I commented on
> > > > the fact that the sum over x is infinite. And the consequence
> > > > is that the DTFT because of that, has to be invalid if you want
> > > > to use it with periodic functions. And what is the purpose of
> > > > the DTFT? Express arbitrary functions in terms of periodic
> > > > functions.
>
> > > > Which is what I find absurd.
>
> > > > > > Since you can not, you necessarily have to reject the
> > > > > > notion of the DTFT itself, since it is based on non-trivial
> > > > > > periodic functions with period N.
>
> > > > > > Again, all the problems go away if one instead of [1]
> > > > > > above relaxes the definition of "square summable" to
> > > > > > [2] above.
>
> > > > > All the problems go away once you understand that lemma.
>
> > > > I understand the lemma. You admitted as much above, by your
> > > > statement of x[n] being periodic, above.
>
> > > :-)
>
> > > x[n] IS NOT PERIODIC!- Hide quoted text -
>
> > OK, for the sake of argument, I accept that you disregard the
> > DTFT as a useful tool for periodic functions. Let's see
> > wehere else it fails, according to your criterion:
>
> > DC: x[n] = x
>
> > sum_{r=-infinity}^infinity x[n+r*N]
>
> > inf
> > = lim sum x = lim Rx = inf
> > R->inf r= -inf R->inf
>
> > Do you accept that the DTFT works for signals whuch have
> > a non-vanishing DC component?
>
> > If "no", what, in your mind, is the reason why the
> > DTFT (and the FT, for that matter) is still taught
> > in both maths and engineering classes? According
> > to your arguments they don't work. Yet, virtually
> > all electronic devices and DSP applications -- even
> > the ones that work -- are based on them.
>
> > Where is the flaw? In the concepts of DTFT and FT?
> > Elsewhere?
>
> The flaw is your non-understanding of my arguments.

I can only interpret this as if you mean that the whole
maths establishment is wrong about the DTFT, and has
been so for, what, a couple of centuries? That you have
detected a flaw in a very useful tool, which has gone
undetected by the combined maths community since the
times of Cauchy, Riemann and Lebesgue?

If this is really what you mean -- and I truly don't
believe that you do -- I can only say I am very sad
on your behalf.

Rune

On May 25, 8:43 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 26 May, 02:22, robert bristow-johnson <r...@audioimagination.com>
> wrote:
>
> > On May 25, 5:51 pm, Andor <andor.bari...@gmail.com> wrote:
>
> > or he's not admitting to it (which would be a concession that seems to
> > be anathema to Rune).
>
> It wasn't me who first made the statement in this therad
> that one needs to separate between maths and beliefs.

yes, it was Andor saying that to you and it is since been shown to be
particularly meaningful and relavent to this discussion. i completely
agree with Andor's application of that statement and particularly
where he applied it.

> > > so there really is no point in arguing.
>
> > i know. it's a deja-vu. i gave it a hard effort. i'm frustrated
> > with it. i'll just leave it alone. Rune is clearly not in the same
> > league as Beanie or eBob, but it appears to me that they sometimes
> > play the same game. Rune can have the last word as far as i'm
> > concerned.

he can have the last word after this.

> Robert, your frustration might ease off a bit if you address
> my arguments and not my person.

i have only done that.

> Everything is there,

yes, and what "Everything" shows is that Andor had it right from the
beginning (i'll bet that i posted something similar in another
conversation here years ago, but i won't bother checking for it), you
said he was clearly wrong, but in fact he was clearly correct and it
appears that you are trying to hedge or turn that into something
else.

Andor was correct, Rune. you were just wrong. your arguments do
nothing to change that.

> spelled
> out as best I can within the limitations of text-based
> USENET posts. All you need to do is to read my posts.

i have and i evaluated them. and i see a pattern taking form.

r b-j

On 28 May, 06:32, robert bristow-johnson <r...@audioimagination.com>
wrote:

> > Everything is there,
>
> yes, and what "Everything" shows is that Andor had it right from the
> beginning (i'll bet that i posted something similar in another
> conversation here years ago, but i won't bother checking for it), you
> said he was clearly wrong, but in fact he was clearly correct and it
> appears that you are trying to hedge or turn that into something
> else.
>
> Andor was correct, Rune. you were just wrong. your arguments do
> nothing to change that.

Robert. Do you ever use either of the concept of "stationry
noise" or "stationary signals" when you work with DSP?
Do you agree with me that the definition of such signals
are that the statistics never changes? So if we take, say,
the simple Gaussian zero mean signal with variance s (to
keep avoiding wirting s^2 everywhere), the expected variance
for each sample is

Var[x[n]] = s = E[x[n]^2]= |x[n]|^2 n integer

Right? Let's see how such a signal fits in with the norm
you and Andor is so proud of (view with fixed-width font):

           N N
lim sum E[x[n]^2] = lim sum s
N-> inf n=-N N->inf n=-N


= lim (2N-1)s = inf.
  N->inf

[Note that I only said "Gaussian" noise; not "white."]

So according to Andor's argument it would not make sense
to speak about the spectrum of such a signal, regalrdless
of it being non-periodic.

How does this fit in to your pattern?

Rune

On May 28, 12:12 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 28 May, 06:32, robert bristow-johnson <r...@audioimagination.com>
> wrote:
>
> > > Everything is there,
>
> > yes, and what "Everything" shows is that Andor had it right from the
> > beginning (i'll bet that i posted something similar in another
> > conversation here years ago, but i won't bother checking for it), you
> > said he was clearly wrong, but in fact he was clearly correct and it
> > appears that you are trying to hedge or turn that into something
> > else.
>
> > Andor was correct, Rune. you were just wrong. your arguments do
> > nothing to change that.
>
> Robert. Do you ever use either of the concept of "stationry
> noise" or "stationary signals" when you work with DSP?
> Do you agree with me that the definition of such signals
> are that the statistics never changes? So if we take, say,
> the simple Gaussian zero mean signal with variance s (to
> keep avoiding wirting s^2 everywhere), the expected variance
> for each sample is
>
> Var[x[n]] = s = E[x[n]^2]= |x[n]|^2 n integer
>
> Right? Let's see how such a signal fits in with the norm
> you and Andor is so proud of (view with fixed-width font):
>

i'm not proud of any norm. this is changing the subject. all's i am
saying is that "Andor's lemma" (i don't want to credit him to much
with it, since i'm sure it's in some text or another, and i recall
making a similar point in times long past) needed this square-summable
thing at the outset for the DTFT, which leaves out perfectly periodic
components in x[n]. no big deal.


> N N
> lim sum E[x[n]^2] = lim sum s
> N-> inf n=-N N->inf n=-N
>
> = lim (2N-1)s = inf.
> N->inf
>
> [Note that I only said "Gaussian" noise; not "white."]

i know. it doesn't make a lot of sense to use the word "white" for
sampled signals without qualification (it might be "white" up to
Nyquist).


just for your information, although i've continued to say that this
your point here is non-sequitur, but now i think it might be useful to
point out that it is common in communications systems texts to
categorize signals in to two gross classes: finite energy signals
(what Andor is talking about) and finite power (but infinite energy)
signals, such as DC, sinusoids, and random processes. when the topic
is a finite energy signals, a euclidian inner product would look like:

              +inf
   <u, v> = SUM{ u[n] * conj(v[n]) }
             n=-inf

and the derived norm would be

           +inf
   <u> = SUM{ u[n] }
          n=-inf

and energy

   <|u|^2> = <u, u>

now that's a finite energy signal. if the above functionals do not
exist (evaluate to finite numbers), it's not a finite energy signal.


for finite power signals, it's the same thing, but there is a little
normalization to put in the summations.


                         N/2-1
   <u, v> = lim 1/N SUM{ u[n] * conj(v[n]) }
           N->+inf n=-N/2

and the derived norm would be the DC component

                      N/2-1
   <u> = lim 1/N SUM{ u[n] }
        N->+inf n=-N/2


and power is similarly.

   <|u|^2> = <u, u>


now, these random processes (like the Gaussian) are finite power, not
finite energy signals.

you were applying the wrong norm to your example, Rune. you used a
finite energy norm applied to a finite and non-zero power signal.
nonetheless, it is just a distraction from the correct thing that
Andor said and the incorrect thing that you said.

>
> How does this fit in to your pattern?
>

the pattern is, that you were shown to be wrong and you can't seem to
admit it. you don't have to, it's a free USENET, but eventually
people might want to move on from it.

r b-j

There has already been lots of traffic in this thread and a--- to me,
being no DSP practitioner--- amazing confusion. I think I have worked
out an answer; you are welcome to tear it apart.

"Mike" <meatheadIV@gmail.com> writes:
> .......
>
> I agree my question is not well-posed. Here is a reformulation:
>
> Given a continuous time signal x(t), infinitely long. Sample it to obtain
> discrete time sequence x0, x1, x2, ..., xn, ..., infinitely long, with
> uniform samples spaced at T apart.
>
> Now I do two things:
>
> (1) Truncate the above sequence to make it finite, x0, x1, ..., xn, and take
> the DFT of the truncated sequence. Call the DFT F1(v). (Capitalized letters
> denote spectrum domain)
>
> (2) Without truncation, taking the DTFT of the infinitely long sequence x0,
> x1, ..., xn, .... Call the DTFT F2(v). And then take one period of F2(v),
> since it is periodic, and then sample F2(v) in the frequency domain to
> discretize it. Call the result F3(v), which is the discretized version of
> the one period of F2(v).
>
> ---------------------
>
> Both (1) and (2) yield vectors of length n in the spectrum domain,
> representing the discretized version of the spectrum.
>
> My question is: under what conditions do these two vectors of discretized
> spectrum equate?

The problem with this question is the OP's confidence in ``sampling a
Fourier tranform''. FTs are distributions in general and taking the
value of a distribution at some point is no well defined concept.

[For better readability, you might want to feed this article from here
up to the footer to plain TeX and read it's output.]

%This chunk of lines is not intended for human readers.
\def\verb #1{\hbox {\rm \hskip 1em#1\hskip 1em}}%
\let\ptexexp\exp\def\exp #1{\mathop {\rm e}\nolimits ^{#1}}%
\def\emph #1{{\sl #1}}%
\def\math #1{$#1$}%
\def\mref #1{(#1) }%
\parindent=0pt\parskip=1.0ex\relax
\catcode `@=0%

In DSP, they speak about at least four ``different kinds'' of Fourier
transforms. To make clear what I am speaking about, I willl add a fith:
the FT of a distribution. The good news is, that the FT of a
distribution @emph{always} exists and that there is only a single kind of
FT for distributions.

Following the presentation by Lighthill, ``Introduction to Fourier
Analysis and Generalised Functions''--- this booklet may not be
beautifull from the mathematican's point of view, but I think, to
everybody with an understanding and love of classical analysis it will
be an enjoyable reading--- a distribution is an equivalence class of
sequences of functions, where each sequence and each function meets
certain requirements.

Let @math{f} be a distribution and @math{(f_n)} be a sequence
representing it, where the index @math{n} runs over the natural
numbers. Then @math{g_n} is said to be the FT of @math{f_n} if

$$
g_n(y) = \int_{-\infty}^\infty f_n(x) \exp{-2\pi ixy} dx \eqno 1
$$

where this is an ordinary integral and the requirements to @math{f_n}
are such that this integral exists.

By the FT thus defined we map @math{(f_n)} to @math{(g_n)}.

Q: does @math{(g_n)} represent a distribution?
A: yes!

Q: if @math{(a_n)} and @math{(b_n)} are both representations of
@math{f}, then, do the sequences obtained from these sequences by FT
represent the same distribution?
A: yes.

Thus for distribution @math{f} the FT @math{g} represent by @math{(g_n)}
is well defined and we use the intuitive notation

$$
g(y) = \int_{-\infty}^\infty f(x) \exp{-2\pi ixy} dx \eqno 2
$$

but from what was said above, it should be clear, that the semantics of
this ``integral'' is not what little schoolboys might expect.


Now I will state a problem similar to what the OP seems to have
intended and show the solution.

Let @math{\phi} be a complex valued function on the real line with
period @math{2L}. Let @math{N} be a natural number and @math{x_n :=
2Ln/N} where @math{n} runs over the set of integers. Let @math{f_n
:= \phi (x_n)}. Then @math{(f_n)} is a periodic sequence and we have

$$
f_{n+N} = f_n \verb{for any integer @math{n}} \eqno 3
$$

Now we construct two distributions: The first is the ``delta-comb''
obtained from @math{(f_n)}, the second is the trigonometric polynomial
of degree @math{N-1} obtained by interpolating the subsequence
@math{(f_n)} where @math{0 \le n<N}.

$$
f(x) := \sum_{n=-\infty}^\infty f_n \delta(x-x_n) \eqno 4
$$$$
f^{(N-1)}(x) := \sum_{n=0}^{N-1} c_n \exp{\pi ixn/L} \eqno 5
$$$$
\verb{where}
f^{(N-1)}(x_n) = f_n \verb{for @math{0\le n < N}}
$$

Now we can show that

a) Both, @math{f} and @math{f^{(N-1)}} are well defined distributions.

b) Their FTs exist and are equal up to normalization factors on the
   intervall @math{[0,1/2L)}.
   
It can be shown that @mref{4} converges to a distribution iff there
exists some natural number @math{M} such that limes @math{|f_n|/|n|^M =
0} for magnitude @math{n} towards infinity. By Fourier transforming
@mref4 it is immedeatly clear that the Fourier series

$$
\sum_{n=-\infty}^\infty f_n \exp{2\pi inx} \eqno 6
$$

converges to a distribution under the same condition--- compare this to
the much more stringent requirements when dealing with ordinary
functions!

Showing that @mref 5 defines a distribution is next to trivial.


Now do the FTs. By @mref 2 we may write

$$
g(y) = \int_{-\infty}^\infty f(x) \exp{-2\pi ixy} dx
$$$$
 = \int_{-\infty}^\infty
\sum_{n=-\infty}^\infty f_n \delta(x-x_n)%
\exp{-2\pi ixy} dx \eqno 7
$$

Making use of @mref 3 and the relation

$$
\sum_{n=-\infty}^\infty \delta(x-nT)%
 = 1/T \sum_{n=-\infty}^\infty \exp{-2\pi ixn/T}
$$

the FT @mref{7} becomes

$$
g(y) = 1/(2L) \sum_{n=0}^{N-1} f_n \exp{-2\pi iyx_n}%
\sum_{m=-\infty}^\infty \delta(y - m/(2L)) \eqno 8
$$


As a first step of calculating the FT of the trigonometric polynomial
@mref 5, we calculte the coefficients @math{c_n}; this is essentialy
what is known by DFT. For any @math{n} where @math{0\le n<N}, we have

$$
c_n = 1/N \sum_{m=0}^{N-1} f_m \exp{-2\pi inm/N} \eqno{10}
$$

As the FT of @math{\exp{2\pi icx}} is @math{\delta(y-c)}, when Fourier
transforming @mref 5 we get

$$
g^{(N-1)} (y) = 1/N \sum_{n=0}^{N-1} f_n \exp{-2\pi iyx_n} %
\sum_{m=0}^{N-1} \delta(y - m/(2L)) \eqno{11}
$$

Comparing @mref{11} to @mref{8} we see, that the two FTs are equal up to
a factor on the intervall @math{0\le y < 1/2L}.

\bye

--
hw

On 28 May, 21:51, robert bristow-johnson <r...@audioimagination.com>
wrote:
> On May 28, 12:12 pm, Rune Allnor <all...@tele.ntnu.no> wrote:

> just for your information, although i've continued to say that this
> your point here is non-sequitur, but now i think it might be useful to
> point out that it is common in communications systems texts to
> categorize signals in to two gross classes: finite energy signals
> (what Andor is talking about) and finite power (but infinite energy)
> signals, such as DC, sinusoids, and random processes. when the topic
> is a finite energy signals, ...

At last we are getting somewhere!

If you go back to the beginning of this thread, you will see that
my starting point was exactly what you have came up with:

http://groups.google.co.uk/group/comp.dsp/msg/afc9a2f5160a8192?hl=en&

My whole objective in this thread has been to show that Andor,
by refusing to accept any other norm than sum |x[n]|^2, is in
deep trouble because he is unable to treat half the useful
signals which fly around. I have attempted to show his troubles
by expanding on his views and drawing conclusion from them,
arrive at absurd conclusions etc, to demonstrate that there
was something missing in the set of tools he accepted.

I was thinking of doing a scan of the textbooks when I return
home in a couple days, to dig up the differences between
energy signals and power signal. I appreciate that you saved
me the effort.

Rune

robert bristow-johnson <rbj@audioimagination.com> writes:
> [...]
> all's i am saying is that "Andor's lemma" (i don't want to credit
> him to much with it, since i'm sure it's in some text or another,
> and i recall making a similar point in times long past) needed this
> square-summable thing at the outset for the DTFT, which leaves out
> perfectly periodic components in x[n].

That's true, but so what? The standard Fourier transform does too
(via the Dirichlet conditions) but we always get around it with
delta functions.

So I guess it's just a matter of which definition (of the Fourier
transform, or of the DTFT) you use. I see no reason to doggedly
stick with the one(s) that requires square-summability when you
can get more mileage out of it (them) using delta functions.

At least I think this is the gist of you's guys' arguing. Could
be off.
--
% Randy Yates % "Rollin' and riding and slippin' and
%% Fuquay-Varina, NC % sliding, it's magic."
%%% 919-577-9882 %
%%%% <yates@ieee.org> % 'Living' Thing', *A New World Record*, ELO
http://home.earthlink.net/~yatescr

robert bristow-johnson wrote:
(snip)

> just for your information, although i've continued to say that this
> your point here is non-sequitur, but now i think it might be useful to
> point out that it is common in communications systems texts to
> categorize signals in to two gross classes: finite energy signals
> (what Andor is talking about) and finite power (but infinite energy)
> signals, such as DC, sinusoids, and random processes.
(snip)

As far as Fourier Transforms, I usually consider

periodic <--> discrete

and

non-periodic <--> continuous

as transform pairs.

It would seem easy for an infinite signal to have an infinite
energy but finite energy density (power).

-- glen

Meanwhile I took my calculation a little further and arived at an easy
expressable relation between the DFT and the DTFT of the infinite,
periodic signal. Thus the answer to Mike's question is essentially
``yes''; this was already said by Rune Allnor in
<1180026933.108924.307690@u30g2000hsc.googlegroups.com>

Manipulating Eq.8 from my previous article, where the expression is up
to normalization factors equal to the DTFT, further, we see that this
is a periodic delta-comb, where the length of a period is N/2L and
the coefficients to the deltas are those obtained from the DFT.

--
hw

On May 28, 4:32 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 28 May, 21:51, robert bristow-johnson <r...@audioimagination.com>
> wrote:
>
> > On May 28, 12:12 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
> > just for your information, although i've continued to say that this
> > your point here is non-sequitur, but now i think it might be useful to
> > point out that it is common in communications systems texts to
> > categorize signals in to two gross classes: finite energy signals
> > (what Andor is talking about) and finite power (but infinite energy)
> > signals, such as DC, sinusoids, and random processes. when the topic
> > is a finite energy signals, ...
>
> At last we are getting somewhere!
>
> If you go back to the beginning of this thread, you will see that
> my starting point was exactly what you have came up with:
>
> http://groups.google.co.uk/group/comp.dsp/msg/afc9a2f5160a8192?hl=en&
>
> My whole objective in this thread has been to show that Andor,
> by refusing to accept any other norm than sum |x[n]|^2, is in
> deep trouble because he is unable to treat half the useful
> signals which fly around. I have attempted to show his troubles
> by expanding on his views and drawing conclusion from them,
> arrive at absurd conclusions etc, to demonstrate that there
> was something missing in the set of tools he accepted.

and i was only commenting to a specific thing that Andor said
(henceforth known as "Andor's lemma") which i said then and say now is
"correct" and that your dispute with it (that is is "clearly wrong")
was itself wrong. i am trying not to let my position leak into other
areas like what makes for a good norm or metric.

> I was thinking of doing a scan of the textbooks when I return
> home in a couple days, to dig up the differences between
> energy signals and power signal. I appreciate that you saved
> me the effort.

the one i yanked out is A. Bruce Carlson: "Communications Systems".
another of the same title, by Simon Haykin. all these are 2 or 3
decades old.

r b-j

On May 28, 4:38 pm, Randy Yates <y...@ieee.org> wrote:

> So I guess it's just a matter of which definition (of the Fourier
> transform, or of the DTFT) you use. I see no reason to doggedly
> stick with the one(s) that requires square-summability when you
> can get more mileage out of it (them) using delta functions.

neglecting scaling, i see only one definition of the DTFT and DFT.

> At least I think this is the gist of you's guys' arguing. Could
> be off.

dunno *all* of which Andor and Rune were arguing. i jumped in
regarding only one basic point:

Rune said:

> > IFF your infinitely long sequence is truly periodic AND
> > you happen to truncate it so that you have exactly one
> > period worth of data, then -- and only then -- your DFT
> > and your DTFT are equal.

then Andor said:

> That statement is clearly wrong....

and later justified it with:

> ... for infinite sequences which have a
> DTFT (which is what Mike was talking about), one can state the
> following lemma:
>
> Let x[m], where m ranges over all integers, be a square-summable
> sequence, and X(w) its DTFT. Furthermore, let y[n], n=0,1,...N-1 be a
> finite vector, and Y[k] the DFT of y[n]. Then
>
> X(2*pi*k/N) = Y[k], k=0,1,...,N-1,
>
> if, and only if,
>
> y[n] = sum_{r=-infinity}^infinity x[n+r*N].

i'm saying, upon examination, that what Andor said is correct and what
Rune said (using "IFF" and "-- and only then --") is incorrect, and
nothing Rune has offered since refutes this or even speaks to it. it
(what Rune has offered) really looks like a distraction that has a
mathematical superficiality but just doesn't speak to this. i think
it's a small and simple thing, Rune doesn't have to concede the point,
but it's odd that he doesn't when the mathematics is clear. Andor is
correct and Rune is incorrect. the point is that there are
essentially an infinite number of infinitely long x[n] that you can
have whose DFT (of a section of the x[n]) is identical to the DFT of
some y[n] (with length as long as the DFT). the latter stuff debating
square-summable and delta functions is a side issue and, AFAICS,
serves only to distract.

Rune seemed to continue to refute this point of Andor's, and i have
taken a position on this single narrow point (that Rune's refutation
of it is ineffective). That's it. nothing more and nothing less.

r b-j