I am making some progress but there's something I'm not quite getting.
For example, my signal x = [1 2 3 4].
The FFT of X =
10.0000
-2.0000 - 2.0000i
-2.0000
-2.0000 + 2.0000i
I then compute the Wavelet decomposition (2 levels using Haar filter). The
wavelet coefficient after the 1st decomposition is
Approximate_Level1 = 2.1213 4.9497
Detailed_Level1 = -0.7071 -0.7071
Then I apply the wavelet decomposition a second time using the approximate
and detailed coefficients and end up with
Approximate_Level2 = 5
Approximate_Level2 = -1
Detailed_Level2 = -2
Detailed_Level2 = 0
So basically, these last 4 wavelet coefficients are on the last level of
the wavelet decomposition. The paper from Guo then indicates to compute
the DFT of the wavelet filters.
I use the wavelet coefficients and compute the DFT using the FFT for the
approximate level coeffcients and then the detailed level coefficients :
FFT([5 -1]) = 4
6
FFT([-2 0]) = -2
-2
I think I am close but I'm stuck. The paper from GUO indicates that
through butterfly operations, use the twiddle factors to compute the FFT
which should equal the results from the classic FFT that I provided on the
top. I don't know how to combine the results from here to get the desired
FFT result :
10.0000
-2.0000 - 2.0000i
-2.0000
-2.0000 + 2.0000i
Reply by glen herrmannsfeldt●March 6, 20132013-03-06
Eric Jacobsen <eric.jacobsen@ieee.org> wrote:
> On Wed, 06 Mar 2013 14:03:00 -0600, Tim Wescott <tim@seemywebsite.com>
(snip)
>>Well, my issue is with him, then. To me a "twiddle factor" is a
>> constant ssociated with a kludge that you use to iron out minor
>> differences etween theory and reality, or a calibration constant
>> that you use to iron out differences between one unit and the next.
>> It is (in my mind) about the farthest thing from the appropriate term
>> to use for the elegant and self-consistent math that you see in
>> any of the various Fourier transforms.
(snip)
> Hmm...I've found "twiddle factor" to be in pretty common use regarding
> the butterfly coefficients in an FFT stage. Wikipedia has a hint
> about the etymology:
It does seem to be the usual term, but I at least slightly agree with
what Tim said about them. In the usual use, twiddle factors are
unknown numbers, such as the position of a calibration pot.
(That is, you twiddle it until the calibration is right.)
-- glen
Reply by Eric Jacobsen●March 6, 20132013-03-06
On Wed, 06 Mar 2013 14:03:00 -0600, Tim Wescott <tim@seemywebsite.com>
wrote:
>On Wed, 06 Mar 2013 11:03:15 -0800, maury wrote:
>
>> On Wednesday, March 6, 2013 10:22:22 AM UTC-6, Tim Wescott wrote:
>>> On Wed, 06 Mar 2013 08:39:46 -0600, clutchfft wrote: > I have managed
>>> to decompose a signal via wavelet transform. I have a > signal with 256
>>> points. The transform produced 256 wavelet > coefficients. In FFT, we
>>> use the odd/even samples and combine them > through a butterfly
>>> operation using the twiddle factor = e^-i*2PI*kn/N. If by odd/even
>>> samples you mean adjoining pairs of samples, then the butterfly
>>> operations get carried out on a much more rich set of samples than that
>>> (at least if you're doing the whole bit-reversed ordering thing). And I
>>> would hardly call something as systemic and organized as the values of
>>> the Euler identity at evenly spaced locations on the circle as a
>>> "twiddle factor". -- Tim Wescott Control system and signal processing
>>> consulting www.wescottdesign.com
>>
>> Hi Tim,
>> Burris uses the term _twiddle factor_ in the paper.
>
>Well, my issue is with him, then. To me a "twiddle factor" is a constant
>associated with a kludge that you use to iron out minor differences
>between theory and reality, or a calibration constant that you use to
>iron out differences between one unit and the next. It is (in my mind)
>about the farthest thing from the appropriate term to use for the elegant
>and self-consistent math that you see in any of the various Fourier
>transforms.
>
>I suspect (particularly if it's a tutorial paper) that his intent was to
>show the similarities between wavelets and the FFT (which, it is my
>understanding, is one of the ways that you can view the FFT). But it
>still sticks sideways in my craw.
>
>--
>My liberal friends think I'm a conservative kook.
>My conservative friends think I'm a liberal kook.
>Why am I not happy that they have found common ground?
>
>Tim Wescott, Communications, Control, Circuits & Software
>http://www.wescottdesign.com
Hmm...I've found "twiddle factor" to be in pretty common use regarding
the butterfly coefficients in an FFT stage. Wikipedia has a hint
about the etymology:
http://en.wikipedia.org/wiki/Twiddle_factor
And one of Rick's articles talks about them:
http://www.dsprelated.com/showarticle/107.php
A brief search will probably yield quite a few results. I've seen
quite a few formal papers that use the term this way.
Eric Jacobsen
Anchor Hill Communications
http://www.anchorhill.com
Reply by clutchfft●March 6, 20132013-03-06
>On Wednesday, March 6, 2013 8:39:46 AM UTC-6, clutchfft wrote:
>> I have managed to decompose a signal via wavelet transform. I have a
sign=
>al with 256 points. The transform produced 256 wavelet coefficients. In
FFT=
>, we use the odd/even samples and combine them through a butterfly
operatio=
>n using the twiddle factor =3D e^-i*2PI*kn/N. The paper I am implementing
s=
>ays that we replace the odd/even samples with the wavelet coefficients and
=
>the twiddle factor would be the frequency response of the wavelet filters.
=
>I am not sure what they mean when they say frequency response of the
wavele=
>t filters. Thanks
>
>I have not had a chance to read the paper yet, but if you look at Figure
1,=
> and compare that with Figure 4, I think you should be able to determine
wh=
>at Burris means by _frequency response of the wavelet filters_
>
It seems like the frequency response of the wavelet filter is the DFT. So
for example, after wavelet transform/decomposition, we have wavelet
coefficients from the low pass filter = X and wavelet coefficients from the
high pass filter = Y.
I think the frequency response would be DFT(X) and DFT(Y). Does that make
sense?
Reply by maury●March 6, 20132013-03-06
On Wednesday, March 6, 2013 2:03:00 PM UTC-6, Tim Wescott wrote:
> On Wed, 06 Mar 2013 11:03:15 -0800, maury wrote: > On Wednesday, March 6, 2013 10:22:22 AM UTC-6, Tim Wescott wrote: >> On Wed, 06 Mar 2013 08:39:46 -0600, clutchfft wrote: > I have managed >> to decompose a signal via wavelet transform. I have a > signal with 256 >> points. The transform produced 256 wavelet > coefficients. In FFT, we >> use the odd/even samples and combine them > through a butterfly >> operation using the twiddle factor = e^-i*2PI*kn/N. If by odd/even >> samples you mean adjoining pairs of samples, then the butterfly >> operations get carried out on a much more rich set of samples than that >> (at least if you're doing the whole bit-reversed ordering thing). And I >> would hardly call something as systemic and organized as the values of >> the Euler identity at evenly spaced locations on the circle as a >> "twiddle factor". -- Tim Wescott Control system and signal processing >> consulting www.wescottdesign.com > > Hi Tim, > Burris uses the term _twiddle factor_ in the paper. Well, my issue is with him, then. To me a "twiddle factor" is a constant associated with a kludge that you use to iron out minor differences between theory and reality, or a calibration constant that you use to iron out differences between one unit and the next. It is (in my mind) about the farthest thing from the appropriate term to use for the elegant and self-consistent math that you see in any of the various Fourier transforms. I suspect (particularly if it's a tutorial paper) that his intent was to show the similarities between wavelets and the FFT (which, it is my understanding, is one of the ways that you can view the FFT). But it still sticks sideways in my craw. -- My liberal friends think I'm a conservative kook. My conservative friends think I'm a liberal kook. Why am I not happy that they have found common ground? Tim Wescott, Communications, Control, Circuits & Software http://www.wescottdesign.com
I can certainly understand your being upset. As an aside, many years ago, there was a _serious_ paper published by a physicist explaining (and defining) the _fudge factor_, _kluge factor_, and _twiddle factor_. If you can still find it, it was a bit humourous.
Reply by Tim Wescott●March 6, 20132013-03-06
On Wed, 06 Mar 2013 11:03:15 -0800, maury wrote:
> On Wednesday, March 6, 2013 10:22:22 AM UTC-6, Tim Wescott wrote:
>> On Wed, 06 Mar 2013 08:39:46 -0600, clutchfft wrote: > I have managed
>> to decompose a signal via wavelet transform. I have a > signal with 256
>> points. The transform produced 256 wavelet > coefficients. In FFT, we
>> use the odd/even samples and combine them > through a butterfly
>> operation using the twiddle factor = e^-i*2PI*kn/N. If by odd/even
>> samples you mean adjoining pairs of samples, then the butterfly
>> operations get carried out on a much more rich set of samples than that
>> (at least if you're doing the whole bit-reversed ordering thing). And I
>> would hardly call something as systemic and organized as the values of
>> the Euler identity at evenly spaced locations on the circle as a
>> "twiddle factor". -- Tim Wescott Control system and signal processing
>> consulting www.wescottdesign.com
>
> Hi Tim,
> Burris uses the term _twiddle factor_ in the paper.
Well, my issue is with him, then. To me a "twiddle factor" is a constant
associated with a kludge that you use to iron out minor differences
between theory and reality, or a calibration constant that you use to
iron out differences between one unit and the next. It is (in my mind)
about the farthest thing from the appropriate term to use for the elegant
and self-consistent math that you see in any of the various Fourier
transforms.
I suspect (particularly if it's a tutorial paper) that his intent was to
show the similarities between wavelets and the FFT (which, it is my
understanding, is one of the ways that you can view the FFT). But it
still sticks sideways in my craw.
--
My liberal friends think I'm a conservative kook.
My conservative friends think I'm a liberal kook.
Why am I not happy that they have found common ground?
Tim Wescott, Communications, Control, Circuits & Software
http://www.wescottdesign.com
Reply by maury●March 6, 20132013-03-06
On Wednesday, March 6, 2013 10:22:22 AM UTC-6, Tim Wescott wrote:
> On Wed, 06 Mar 2013 08:39:46 -0600, clutchfft wrote: > I have managed to decompose a signal via wavelet transform. I have a > signal with 256 points. The transform produced 256 wavelet > coefficients. In FFT, we use the odd/even samples and combine them > through a butterfly operation using the twiddle factor = e^-i*2PI*kn/N. If by odd/even samples you mean adjoining pairs of samples, then the butterfly operations get carried out on a much more rich set of samples than that (at least if you're doing the whole bit-reversed ordering thing). And I would hardly call something as systemic and organized as the values of the Euler identity at evenly spaced locations on the circle as a "twiddle factor". -- Tim Wescott Control system and signal processing consulting www.wescottdesign.com
Hi Tim,
Burris uses the term _twiddle factor_ in the paper.
Reply by maury●March 6, 20132013-03-06
On Wednesday, March 6, 2013 8:39:46 AM UTC-6, clutchfft wrote:
> I have managed to decompose a signal via wavelet transform. I have a signal with 256 points. The transform produced 256 wavelet coefficients. In FFT, we use the odd/even samples and combine them through a butterfly operation using the twiddle factor = e^-i*2PI*kn/N. The paper I am implementing says that we replace the odd/even samples with the wavelet coefficients and the twiddle factor would be the frequency response of the wavelet filters. I am not sure what they mean when they say frequency response of the wavelet filters. Thanks
I have not had a chance to read the paper yet, but if you look at Figure 1, and compare that with Figure 4, I think you should be able to determine what Burris means by _frequency response of the wavelet filters_
Reply by Tim Wescott●March 6, 20132013-03-06
On Wed, 06 Mar 2013 08:39:46 -0600, clutchfft wrote:
> I have managed to decompose a signal via wavelet transform. I have a
> signal with 256 points. The transform produced 256 wavelet
> coefficients. In FFT, we use the odd/even samples and combine them
> through a butterfly operation using the twiddle factor = e^-i*2PI*kn/N.
If by odd/even samples you mean adjoining pairs of samples, then the
butterfly operations get carried out on a much more rich set of samples
than that (at least if you're doing the whole bit-reversed ordering
thing). And I would hardly call something as systemic and organized as
the values of the Euler identity at evenly spaced locations on the circle
as a "twiddle factor".
--
Tim Wescott
Control system and signal processing consulting
www.wescottdesign.com
Reply by clutchfft●March 6, 20132013-03-06
>On Wednesday, March 6, 2013 10:06:58 AM UTC-6, maury wrote:
>> On Wednesday, March 6, 2013 8:39:46 AM UTC-6, clutchfft wrote: > I am
not sure what they mean when they say frequency response of the wavelet
filters. Niether do we if we don't know to which paper you refer.
>
>Are you refering to Guo and Burrus paper?
>
Yes, Guo and Burrus paper. I think the frequency response is the DFT of
the wavelet filter.