MATLAB Central Newsreader - Hilbert Transform

Re: Hilbert Transform

Greg Heath — Wed, 14 May 2008 15:07:38 -0400

On May 9, 6:46=A0pm, "Steven G. Johnson" <stev...@alum.mit.edu> wrote:
> On May 9, 1:09 am,Greg Heath<he...@alumni.brown.edu> wrote:
>
> > On May 8, 4:34 pm, "Andy Robb" <ajr...@hotmail.com> wrote:
>
> > > "David Egger" <egg...@sbox.tugraz.at> wrote in message
> > > Cooley-Tukey invented the modern FFT
>
> > No. Cooley-Tukey made the technique known to a wider
> > audience.
>
> > Oscar Buneman ( a German mathematician at Cambridge who
> > was interred by the British during WWII) used it during his
> > research for the allies on computer simulations of the radar
> > magnetron. He was the first to understand the inner workings
> > of the magnetron that allowed British radars to become practical.
>
> Actually, the Cooley-Tukey algorithm's earliest discoverer seems to be
> Gauss, who described the technique (including the general composite-N
> case) in his notebooks circa 1805.
>
> Subsequently, various forms of the algorithm were rediscovered
> multiple times by multiple authors (usually restricted to special
> cases like powers of 2). =A0Cooley and Tukey rediscovered it yet again
> in 1965 (including the general composite case), but deserve some
> credit not only for popularizing it but also for describing it clearly
> and identifying the O(N log N) complexity (which was not clearly
> analyzed by most, and perhaps all, previous authors).
>
> There was a nice article, "Gauss and the History of the Fast Fourier
> Transform," in 1984 by Heideman et al. that goes over a lot of this
> history (http://ieeexplore.ieee.org/xpls/abs_all.jsp?
> arnumber=3D1162257).
>
> Of course, this is a bit offtopic to the original poster, who is
> interested in the history of the application of the FFT to Hilbert
> transforms apparently. =A0But I thought I should correct the record.
>
> Regards,
> Steven G. Johnson

Another offtopic bit. PreCooley-Tukey we were simulating electron
beams, plasmas and spiral galaxies by solving Poisson's Equation
on a 48X48 grid using a 3X2^4 FFT. I think the computer was an
IBM 7070 and each simulation took ~4hrs of clock time. It would
probably take minutes on the average modern day PC.

Greg

Re: Hilbert Transform

Steven G. Johnson — Fri, 09 May 2008 22:46:08 -0400

On May 9, 1:09 am, Greg Heath <he...@alumni.brown.edu> wrote:
> On May 8, 4:34 pm, "Andy Robb" <ajr...@hotmail.com> wrote:
>
> > "David Egger" <egg...@sbox.tugraz.at> wrote in message
> > Cooley-Tukey invented the modern FFT
>
> No. Cooley-Tukey made the technique known to a wider
> audience.
>
> Oscar Buneman ( a German mathematician at Cambridge who
> was interred by the British during WWII) used it during his
> research for the allies on computer simulations of the radar
> magnetron. He was the first to understand the inner workings
> of the magnetron that allowed British radars to become practical.

Actually, the Cooley-Tukey algorithm's earliest discoverer seems to be
Gauss, who described the technique (including the general composite-N
case) in his notebooks circa 1805.

Subsequently, various forms of the algorithm were rediscovered
multiple times by multiple authors (usually restricted to special
cases like powers of 2). Cooley and Tukey rediscovered it yet again
in 1965 (including the general composite case), but deserve some
credit not only for popularizing it but also for describing it clearly
and identifying the O(N log N) complexity (which was not clearly
analyzed by most, and perhaps all, previous authors).

There was a nice article, "Gauss and the History of the Fast Fourier
Transform," in 1984 by Heideman et al. that goes over a lot of this
history (http://ieeexplore.ieee.org/xpls/abs_all.jsp?
arnumber=1162257).

Of course, this is a bit offtopic to the original poster, who is
interested in the history of the application of the FFT to Hilbert
transforms apparently. But I thought I should correct the record.

Regards,
Steven G. Johnson

Re: Hilbert Transform

David Egger — Fri, 09 May 2008 05:47:04 -0400

Greg Heath <heath@alumni.brown.edu> wrote in message
<75f62485-a221-47f2-97ba-748614faf288@b1g2000hsg.googlegroups.com>...
> On May 8, 4:34=A0pm, "Andy Robb" <ajr...@hotmail.com> wrote:
> > "David Egger" <egg...@sbox.tugraz.at> wrote in message
>
> > Cooley-Tukey invented the modern FFT
>
> No. Cooley-Tukey made the technique known to a wider
> audience.
>
> Oscar Buneman ( a German mathematician at Cambridge who
> was interred by the British during WWII) used it during his
> research for the allies on computer simulations of the radar
> magnetron. He was the first to understand the inner workings
> of the magnetron that allowed British radars to become
practical.
>
> He and his students used the technique in the early 1960s
> at the Stanford University Institute for Plasma Research.
>
> He had used the technique in the 1930s before he escaped
> from Germany. As far as he knew the technique was being
> used during the 1920s and had its origins before 1900.
>
> Hope this helps.
>
> Greg
Thank you!

I don't want to know,who found the fft algorithm Andy. I
want to know, who invented the fft approaching the Hilbert
transform,do anyone knows that and some book I could cite?

Re: Hilbert Transform

Greg Heath — Fri, 09 May 2008 05:09:10 -0400

On May 8, 4:34=A0pm, "Andy Robb" <ajr...@hotmail.com> wrote:
> "David Egger" <egg...@sbox.tugraz.at> wrote in message

> Cooley-Tukey invented the modern FFT

No. Cooley-Tukey made the technique known to a wider
audience.

Oscar Buneman ( a German mathematician at Cambridge who
was interred by the British during WWII) used it during his
research for the allies on computer simulations of the radar
magnetron. He was the first to understand the inner workings
of the magnetron that allowed British radars to become practical.

He and his students used the technique in the early 1960s
at the Stanford University Institute for Plasma Research.

He had used the technique in the 1930s before he escaped
from Germany. As far as he knew the technique was being
used during the 1920s and had its origins before 1900.

Hope this helps.

Greg

Re: Hilbert Transform

Andy Robb — Thu, 08 May 2008 20:34:03 -0400

"David Egger" <eggerd@sbox.tugraz.at> wrote in message
<fvuksv$2q3$1@fred.mathworks.com>...
> "Andy Robb" <ajrobb@hotmail.com> wrote in message
> <fvt3gt$dse$1@fred.mathworks.com>...
> > "David Egger" <eggerd@sbox.tugraz.at> wrote in message
> > <fvs88h$j98$1@fred.mathworks.com>...
> > > "Andy Robb" <ajrobb@hotmail.com> wrote in message
> > > <fvrv3v$8ja$1@fred.mathworks.com>...
> > > > "David Egger" <eggerd@sbox.tugraz.at> wrote in message
> > > > <fvriev$b1i$1@fred.mathworks.com>...
> > > >
> > > >
> > > > From memory, hilbert.m uses an FFT approach, it zeros
> > > > frequency components below 0 and double frequency
> components
> > > > between zero and Nyquist. The IFFT then produces a
complex
> > > > analytic waveform. The problems with this approach
are the
> > > > same as any FFT technique and can suffer the effects of
> > > > truncation.
> > > ---------------------------------------------------------
> > > Hey,
> > >
> > > thank you for answering!
> > > Okay, I want to keep the algorithm based on the
manipulation
> > > in the frequency domain you explained.
> > > Do you know who invented this algorithm?
> > >
> > > You said, it is an approach.So this is not an ideal
filter?
> > > Is an ideal Hilbert filter possible?
> > >
> > > You also said,the problem with this approach are the
same as
> > > in any fft approach.Could you name some of them?
> > >
> > >
> > > Regards!
> >
> > FFT is just a fast (efficient) form of DFT calculation.
> >
> > The basic requirement for a DFT to be accurate are:
> > 1. The original signal contains no component at frequencies
> > above half the sample frequency (Nyquist-Shannon*)
> > 2. The signal is either an event completely sampled over the
> > sample period or is periodic in the sample period (the start
> > and 'end' conditions must be the same)
> >
> > NOTE: the 'end' condition is the next sample AFTER the last
> > sample.
> >
> > If these conditions are not met then expect some 'ringing'
> > in the synthesised imaginary component at the ends of the
> > sample period. However, if they are met, then the Hilbert
> > transform will also be accurate.
> >
> > *By convention, Nyquist is often associated with the Nyquist
> > frequency limit. Shannon is associated with reconstruction
> > (interpolation with sinc waveform FIR filters). However,
> > they worked closely together at AT&T Bell Labs.
>
>
> Okay, thank you!
>
> So if the two conditions are satisfied, fft is equal dft?

No FFT is always DFT - just Fast (hence the extra F)

The conditions are for every good DFT.

>
> Is the hilbert transform using the fft an approach or not?

Yes - if the DFT conditions are met.
>
> And who invented the fft algorithm for Hilbert?Shannon and
> Nyquist?

Cooley-Tukey invented the modern FFT - Hilbert had already
done the rest.

Nyquist-Shannon are the godfathers of PCM

Wikipedia is good an all these.

>
>
> Greetings!!
Greeted - thanks

Re: Hilbert Transform

David Egger — Thu, 08 May 2008 10:33:03 -0400

"Andy Robb" <ajrobb@hotmail.com> wrote in message
<fvt3gt$dse$1@fred.mathworks.com>...
> "David Egger" <eggerd@sbox.tugraz.at> wrote in message
> <fvs88h$j98$1@fred.mathworks.com>...
> > "Andy Robb" <ajrobb@hotmail.com> wrote in message
> > <fvrv3v$8ja$1@fred.mathworks.com>...
> > > "David Egger" <eggerd@sbox.tugraz.at> wrote in message
> > > <fvriev$b1i$1@fred.mathworks.com>...
> > >
> > >
> > > From memory, hilbert.m uses an FFT approach, it zeros
> > > frequency components below 0 and double frequency
components
> > > between zero and Nyquist. The IFFT then produces a complex
> > > analytic waveform. The problems with this approach are the
> > > same as any FFT technique and can suffer the effects of
> > > truncation.
> > ---------------------------------------------------------
> > Hey,
> >
> > thank you for answering!
> > Okay, I want to keep the algorithm based on the manipulation
> > in the frequency domain you explained.
> > Do you know who invented this algorithm?
> >
> > You said, it is an approach.So this is not an ideal filter?
> > Is an ideal Hilbert filter possible?
> >
> > You also said,the problem with this approach are the same as
> > in any fft approach.Could you name some of them?
> >
> >
> > Regards!
>
> FFT is just a fast (efficient) form of DFT calculation.
>
> The basic requirement for a DFT to be accurate are:
> 1. The original signal contains no component at frequencies
> above half the sample frequency (Nyquist-Shannon*)
> 2. The signal is either an event completely sampled over the
> sample period or is periodic in the sample period (the start
> and 'end' conditions must be the same)
>
> NOTE: the 'end' condition is the next sample AFTER the last
> sample.
>
> If these conditions are not met then expect some 'ringing'
> in the synthesised imaginary component at the ends of the
> sample period. However, if they are met, then the Hilbert
> transform will also be accurate.
>
> *By convention, Nyquist is often associated with the Nyquist
> frequency limit. Shannon is associated with reconstruction
> (interpolation with sinc waveform FIR filters). However,
> they worked closely together at AT&T Bell Labs.

Okay, thank you!

So if the two conditions are satisfied, fft is equal dft?

Is the hilbert transform using the fft an approach or not?

And who invented the fft algorithm for Hilbert?Shannon and
Nyquist?

Greetings!!

Re: Hilbert Transform

NZTideMan — Wed, 07 May 2008 22:40:29 -0400

On May 8, 8:30=A0am, "Andy Robb" <ajr...@hotmail.com> wrote:
> "David Egger" <egg...@sbox.tugraz.at> wrote in message
>
> <fvs88h$j9...@fred.mathworks.com>...
>
>
>
>
>
> > "Andy Robb" <ajr...@hotmail.com> wrote in message
> > <fvrv3v$8j...@fred.mathworks.com>...
> > > "David Egger" <egg...@sbox.tugraz.at> wrote in message
> > > <fvriev$b1...@fred.mathworks.com>...
>
> > > From memory, hilbert.m uses an FFT approach, it zeros
> > > frequency components below 0 and double frequency components
> > > between zero and Nyquist. The IFFT then produces a complex
> > > analytic waveform. The problems with this approach are the
> > > same as any FFT technique and can suffer the effects of
> > > truncation.
> > ---------------------------------------------------------
> > Hey,
>
> > thank you for answering!
> > Okay, I want to keep the algorithm based on the manipulation
> > in the frequency domain you explained.
> > Do you know who invented this algorithm?
>
> > You said, it is an approach.So this is not an ideal filter?
> > Is an ideal Hilbert filter possible?
>
> > You also said,the problem with this approach are the same as
> > in any fft approach.Could you name some of them?
>
> > Regards!
>
> FFT is just a fast (efficient) form of DFT calculation.
>
> The basic requirement for a DFT to be accurate are:
> 1. The original signal contains no component at frequencies
> above half the sample frequency (Nyquist-Shannon*)
> 2. The signal is either an event completely sampled over the
> sample period or is periodic in the sample period (the start
> and 'end' conditions must be the same)
>
> NOTE: the 'end' condition is the next sample AFTER the last
> sample.
>
> If these conditions are not met then expect some 'ringing'
> in the synthesised imaginary component at the ends of the
> sample period. However, if they are met, then the Hilbert
> transform will also be accurate.
>
> *By convention, Nyquist is often associated with the Nyquist
> frequency limit. Shannon is associated with reconstruction
> (interpolation with sinc waveform FIR filters). However,
> they worked closely together at AT&T Bell Labs.- Hide quoted text -
>
> - Show quoted text -

Ahaaa. An expert at applying Hilbert transform!!
Maybe you can explain a basic lack of understanding I have about
calculating the Hilbert spectrum?
The freq is calculated as the derivative of the phase of the DFT, but
if the phase wanders all over the place, it results in apparently
random frequencies (some of them negative).
I've never been able to get past this point.
Can you help please?

Re: Hilbert Transform

Andy Robb — Wed, 07 May 2008 20:30:21 -0400

"David Egger" <eggerd@sbox.tugraz.at> wrote in message
<fvs88h$j98$1@fred.mathworks.com>...
> "Andy Robb" <ajrobb@hotmail.com> wrote in message
> <fvrv3v$8ja$1@fred.mathworks.com>...
> > "David Egger" <eggerd@sbox.tugraz.at> wrote in message
> > <fvriev$b1i$1@fred.mathworks.com>...
> >
> >
> > From memory, hilbert.m uses an FFT approach, it zeros
> > frequency components below 0 and double frequency components
> > between zero and Nyquist. The IFFT then produces a complex
> > analytic waveform. The problems with this approach are the
> > same as any FFT technique and can suffer the effects of
> > truncation.
> ---------------------------------------------------------
> Hey,
>
> thank you for answering!
> Okay, I want to keep the algorithm based on the manipulation
> in the frequency domain you explained.
> Do you know who invented this algorithm?
>
> You said, it is an approach.So this is not an ideal filter?
> Is an ideal Hilbert filter possible?
>
> You also said,the problem with this approach are the same as
> in any fft approach.Could you name some of them?
>
>
> Regards!

FFT is just a fast (efficient) form of DFT calculation.

The basic requirement for a DFT to be accurate are:
1. The original signal contains no component at frequencies
above half the sample frequency (Nyquist-Shannon*)
2. The signal is either an event completely sampled over the
sample period or is periodic in the sample period (the start
and 'end' conditions must be the same)

NOTE: the 'end' condition is the next sample AFTER the last
sample.

If these conditions are not met then expect some 'ringing'
in the synthesised imaginary component at the ends of the
sample period. However, if they are met, then the Hilbert
transform will also be accurate.

*By convention, Nyquist is often associated with the Nyquist
frequency limit. Shannon is associated with reconstruction
(interpolation with sinc waveform FIR filters). However,
they worked closely together at AT&T Bell Labs.

Re: Hilbert Transform

David Egger — Wed, 07 May 2008 12:45:05 -0400

"Andy Robb" <ajrobb@hotmail.com> wrote in message
<fvrv3v$8ja$1@fred.mathworks.com>...
> "David Egger" <eggerd@sbox.tugraz.at> wrote in message
> <fvriev$b1i$1@fred.mathworks.com>...
>
>
> From memory, hilbert.m uses an FFT approach, it zeros
> frequency components below 0 and double frequency components
> between zero and Nyquist. The IFFT then produces a complex
> analytic waveform. The problems with this approach are the
> same as any FFT technique and can suffer the effects of
> truncation.
---------------------------------------------------------
Hey,

thank you for answering!
Okay, I want to keep the algorithm based on the manipulation
in the frequency domain you explained.
Do you know who invented this algorithm?

You said, it is an approach.So this is not an ideal filter?
Is an ideal Hilbert filter possible?

You also said,the problem with this approach are the same as
in any fft approach.Could you name some of them?

Regards!

Re: Hilbert Transform

Doug Schwarz — Wed, 07 May 2008 12:13:46 -0400

In article <fvrv3v$8ja$1@fred.mathworks.com>,
"Andy Robb" <ajrobb@hotmail.com> wrote:

> "David Egger" <eggerd@sbox.tugraz.at> wrote in message
> <fvriev$b1i$1@fred.mathworks.com>...
> > Hey,
> >
> >
> > I unterstand the algorithm hilbert.m in Matlab.
> > But can anyone tell me:
> >
> > 1)Is this the ideal Hilbert or an approximation?
> > 2)Who invented the algorithm?
> > 3)do anyone know a book where I can find the alg.?
> >
> > Regards!
>
> I spent many years applying Hilbert transforms, often
> combining them with re-sampling techniques (Shannon et al).
>
> There are two approaches to the Hilbert transform. Both
> synthesise an imaginary component of a complex analytic
> waveform from the 'real' signal. The real component should
> be unchanged.
>
> From memory, hilbert.m uses an FFT approach, it zeros
> frequency components below 0 and double frequency components
> between zero and Nyquist. The IFFT then produces a complex
> analytic waveform. The problems with this approach are the
> same as any FFT technique and can suffer the effects of
> truncation.
>
> An alternative approach is to synthesise the imaginary
> component directly from the real component using a
> time-domain filter. From my dim and distant pass, I think
> you can see the shape of an FIR by synthesising a spectrum
> with 1i in positive frequencies and -1i in negative
> frequencies and zero in all real components (including 0 and
> Nyquist). Then take the IFFT.

The functions firls and firpm from the Signal Processing Toolbox can be
used to synthesize the imaginary component. See the help for those
functions.

--
Doug Schwarz
dmschwarz&ieee,org
Make obvious changes to get real email address.

Re: Hilbert Transform

Andy Robb — Wed, 07 May 2008 10:09:03 -0400

"David Egger" <eggerd@sbox.tugraz.at> wrote in message
<fvriev$b1i$1@fred.mathworks.com>...
> Hey,
>
>
> I unterstand the algorithm hilbert.m in Matlab.
> But can anyone tell me:
>
> 1)Is this the ideal Hilbert or an approximation?
> 2)Who invented the algorithm?
> 3)do anyone know a book where I can find the alg.?
>
> Regards!

I spent many years applying Hilbert transforms, often
combining them with re-sampling techniques (Shannon et al).

There are two approaches to the Hilbert transform. Both
synthesise an imaginary component of a complex analytic
waveform from the 'real' signal. The real component should
be unchanged.

From memory, hilbert.m uses an FFT approach, it zeros
frequency components below 0 and double frequency components
between zero and Nyquist. The IFFT then produces a complex
analytic waveform. The problems with this approach are the
same as any FFT technique and can suffer the effects of
truncation.

An alternative approach is to synthesise the imaginary
component directly from the real component using a
time-domain filter. From my dim and distant pass, I think
you can see the shape of an FIR by synthesising a spectrum
with 1i in positive frequencies and -1i in negative
frequencies and zero in all real components (including 0 and
Nyquist). Then take the IFFT.

Hilbert Transform

David Egger — Wed, 07 May 2008 06:33:03 -0400

Hey,

I unterstand the algorithm hilbert.m in Matlab.
But can anyone tell me:

1)Is this the ideal Hilbert or an approximation?
2)Who invented the algorithm?
3)do anyone know a book where I can find the alg.?

Regards!