FFT vs DCT

robert bristow-johnson wrote:


>> Also, on that last formula  X[2*k] * e^(j*2*pi*k/N), what do 'e' and
>> 'j' represent?  Are they constants?
> 
> oh dear. i wonder what will happen when Vlad sees this.

Those are hieroglyphs:
"e" means "the one with the tail"
"j" means "get down from the tree"

> natural log of e is 1 and j^2 = -1.

http://radio-weblogs.com/0001263/junk/Q209354%20-%20HOWTO.html

On 9/26/11 4:27 PM, Vladimir Vassilevsky wrote:
>
>
> robert bristow-johnson wrote:
>
>
>>> Also, on that last formula X[2*k] * e^(j*2*pi*k/N), what do 'e' and
>>> 'j' represent? Are they constants?
>>
>> oh dear. i wonder what will happen when Vlad sees this.
>
> Those are hieroglyphs:
> "e" means "the one with the tail"
> "j" means "get down from the tree"
>
>> natural log of e is 1 and j^2 = -1.
>
> http://radio-weblogs.com/0001263/junk/Q209354%20-%20HOWTO.html

i'm mildly entertained.

thanks, Vlad.  appears that you have partisans on both sides.

i'm not even sure i didn't fill the OP's brain with a bunch of crap, but 
i *think* i remembered the salient points of the DCT correctly.  never 
actually used a DCT for anything.

L8r,

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

On Sep 26, 12:55&#4294967295;pm, Jerry Avins <j...@ieee.org> wrote:
> On 9/26/2011 11:15 AM, Raeldor wrote:
>
> > You Again?
>
> > You know, I feel a little sorry for you. &#4294967295;It's obvious you've been
> > bullied or abused at some point and now feel like you need to prove
> > yourself by name-calling people who are taking an interest in a
> > subject you know something about. &#4294967295;It doesn't make you look any
> > smarter, it just makes you look like someone who needs help. &#4294967295;I've met
> > people like you before. &#4294967295;You might know a lot, and you might even be
> > smart, but you will never be content until you start treating people
> > with respect, because no matter how much you know or how clever you
> > are they'll never respect YOU until you do.
>
> Vlad, like me, he has little patience for those who ask here before
> looking for elementary answers in likely places. We differ mostly in my
> ignoring lazy questioners and his berating them.
>
> "Is DCT basically the same as an FFT that operates on real numbers?" is
> a classic stupid question. It is stupid as a question to others because
> it can be easily answered by looking up (say, in MathWorld or Wikipedia)
> what DCT and FFT are. Asking others to do your scut work is a sign of
> disrespect. You don't get respect without showing respect.
>
> Jerry
> --
> Engineering is the art of making what you want from things you can get.

So, it might seem to YOU that it's a question that can be easily
answered by looking in somewhere like Wikipedia, but I can tell you
that I've read the articles there several times, and it's not easily
answered when you don't have a math or DSP heavy background.  A lot of
these articles seem to say one thing, and then contradict it again a
few sentences later.  Either that, or they use terminology which,
while very essential, can often be overlooked or misinterpreted by
someone from a different background (for me, I am a programmer).  I'm
not asking others to do my work, believe me, I've read this stuff,
implemented, tested, experimented, and have been for several months,
but sometimes I need to go back and confirm that even my BASIC
understanding of some of this stuff has not sent me on the wrong
track.  I do not ask these questions intending to be disrespectful or
lazy, I ask them because I hope to get a more helpful laymens-terms
answer from people who frequent this board because they may actually
care to help others understand.

Jerry Avins <jya@ieee.org> wrote:

(snip)
> Vlad, like me, he has little patience for those who ask here before 
> looking for elementary answers in likely places. We differ mostly in my 
> ignoring lazy questioners and his berating them.

He does take a little getting used to.

> "Is DCT basically the same as an FFT that operates on real numbers?" is 
> a classic stupid question. It is stupid as a question to others because 
> it can be easily answered by looking up (say, in MathWorld or Wikipedia) 
> what DCT and FFT are. Asking others to do your scut work is a sign of 
> disrespect. You don't get respect without showing respect.

I don't think it is quite that obvious.  There are sources that
describe it well, but also many that don't.  I understood both for
a long time before finally reading the distinction in "Numerical
Recipes."  (Many don't like the programs in the book, but the
descriptions are usually pretty readable.  They leave in details
that some other sources gloss over.)

The distinction is boundary conditions.  The FFT (DFT) has periodic
boundary conditions.  The DST has the boundary condition that the
function goes to zero at each end.  The DCT has the derivative go
to zero at each end.  You then use the appropriate number of the
appropriate basis functions (or infinite in the continuous case).

More specifically to their use in DSP, the DCT works best when
dividing a signal up and transforming each piece separately.
The boundaries are less visible (in an image) or audible (in the
audio case) than either DFT or DST.  

I do remember watching the 2008 Olympics opening ceremony, and
at one time noticing the interesting visual effect where the
image had a square pattern in it, a few seconds before realizing
that it was an artifact of the compression system.  In rapid scene
changes there aren't enough bits to fully code the DCT, such that
the separate cells become very visible (usually for only a short time).

-- glen

On Mon, 26 Sep 2011 15:24:23 -0700 (PDT), Raeldor <raeldor@gmail.com>
wrote:

>On Sep 26, 12:55=A0pm, Jerry Avins <j...@ieee.org> wrote:
>> On 9/26/2011 11:15 AM, Raeldor wrote:
>>
>> > You Again?
>>
>> > You know, I feel a little sorry for you. =A0It's obvious you've been
>> > bullied or abused at some point and now feel like you need to prove
>> > yourself by name-calling people who are taking an interest in a
>> > subject you know something about. =A0It doesn't make you look any
>> > smarter, it just makes you look like someone who needs help. =A0I've me=
>t
>> > people like you before. =A0You might know a lot, and you might even be
>> > smart, but you will never be content until you start treating people
>> > with respect, because no matter how much you know or how clever you
>> > are they'll never respect YOU until you do.
>>
>> Vlad, like me, he has little patience for those who ask here before
>> looking for elementary answers in likely places. We differ mostly in my
>> ignoring lazy questioners and his berating them.
>>
>> "Is DCT basically the same as an FFT that operates on real numbers?" is
>> a classic stupid question. It is stupid as a question to others because
>> it can be easily answered by looking up (say, in MathWorld or Wikipedia)
>> what DCT and FFT are. Asking others to do your scut work is a sign of
>> disrespect. You don't get respect without showing respect.
>>
>> Jerry
>> --
>> Engineering is the art of making what you want from things you can get.
>
>So, it might seem to YOU that it's a question that can be easily
>answered by looking in somewhere like Wikipedia, but I can tell you
>that I've read the articles there several times, and it's not easily
>answered when you don't have a math or DSP heavy background.  A lot of
>these articles seem to say one thing, and then contradict it again a
>few sentences later.  Either that, or they use terminology which,
>while very essential, can often be overlooked or misinterpreted by
>someone from a different background (for me, I am a programmer).  I'm
>not asking others to do my work, believe me, I've read this stuff,
>implemented, tested, experimented, and have been for several months,
>but sometimes I need to go back and confirm that even my BASIC
>understanding of some of this stuff has not sent me on the wrong
>track.  I do not ask these questions intending to be disrespectful or
>lazy, I ask them because I hope to get a more helpful laymens-terms
>answer from people who frequent this board because they may actually
>care to help others understand.

To add a little to what Glen wrote, the difference is essentially the
basis function (i.e., the waveform that the transform is using to
correlate against for each output sample).   In a DFT/FFT a
complex-valued rotating vector is used so that the real and imaginary
components are the cosine and sine functions.   In a DST only the sine
component is used, in a DCT only the cosine component is used.

Understanding the impacts and utlities of the different basis
functions and how they affect the usage of the transforms gets into a
lot of detail, but Glen captured some of the key issues.

You've already assessed that having a real-valued basis function
(i.e., a cosine instead of a complex-valued basis function like in the
DFT/FFT) means that it works well with real-valued signals, like audio
or video streams.

You should be able to search around and find the definitions of even
and odd functions and therefore even and off symmetry, and then
relating that to the sine and cosine waveforms.   The different
symmetries lead to different properties of the transforms, again
that's what Glen touched on.   Since the FFT includes both the sine
and cosine components in its basis functions it is the more general
transform from that perspective.

Everybody was new at this stuff sometime, and most of us have to delve
into disciplines that we don't know much about from time to time.  So
everybody has to ask newby or "dumb" questions occasionally in order
to learn more quickly.  This place has gotten worse at responding to
them over the years, but if you're patient you should be able to get
your questions answered.  It does help to arm yourself with as much
preliminary research as you can, though.




Eric Jacobsen
http://www.ericjacobsen.org
http://www.dsprelated.com/blogs-1//Eric_Jacobsen.php

On 9/26/2011 4:27 PM, Vladimir Vassilevsky wrote:

   ...

> Those are hieroglyphs:
> "e" means "the one with the tail"
> "j" means "get down from the tree"

I think you have that wrong. "e" is a glyph for Pacman. "j" is the one 
with the tail. It's a lemur mostly hidden by the tree.

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

On 9/26/2011 6:24 PM, Raeldor wrote:

   ...

> So, it might seem to YOU that it's a question that can be easily
> answered by looking in somewhere like Wikipedia, but I can tell you
> that I've read the articles there several times, and it's not easily
> answered when you don't have a math or DSP heavy background.  A lot of
> these articles seem to say one thing, and then contradict it again a
> few sentences later.  Either that, or they use terminology which,
> while very essential, can often be overlooked or misinterpreted by
> someone from a different background (for me, I am a programmer).  I'm
> not asking others to do my work, believe me, I've read this stuff,
> implemented, tested, experimented, and have been for several months,
> but sometimes I need to go back and confirm that even my BASIC
> understanding of some of this stuff has not sent me on the wrong
> track.  I do not ask these questions intending to be disrespectful or
> lazy, I ask them because I hope to get a more helpful laymens-terms
> answer from people who frequent this board because they may actually
> care to help others understand.

When you dig into an article that confuses you, cite the confusing parts 
instead of asking what could seem like a dumb or lazy question. What you 
wanted to know is actually fairly deep. It is about using the algorithm 
of an FFT to actually perform a different transform by some pre- and 
post processing. That doesn't makes the transforms the same.

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

On 9/26/2011 6:27 PM, glen herrmannsfeldt wrote:
> Jerry Avins<jya@ieee.org>  wrote:
>
> (snip)
>> Vlad, like me, he has little patience for those who ask here before
>> looking for elementary answers in likely places. We differ mostly in my
>> ignoring lazy questioners and his berating them.
>
> He does take a little getting used to.
>
>> "Is DCT basically the same as an FFT that operates on real numbers?" is
>> a classic stupid question. It is stupid as a question to others because
>> it can be easily answered by looking up (say, in MathWorld or Wikipedia)
>> what DCT and FFT are. Asking others to do your scut work is a sign of
>> disrespect. You don't get respect without showing respect.
>
> I don't think it is quite that obvious.

What the difference is may not be obvious, but their being somehow 
different is. I suppose one's view depends on his interpretation od 
"somewhat".

>                                        There are sources that
> describe it well, but also many that don't.  I understood both for
> a long time before finally reading the distinction in "Numerical
> Recipes."  (Many don't like the programs in the book, but the
> descriptions are usually pretty readable.  They leave in details
> that some other sources gloss over.)

Yes, NR is a good source.

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

Jerry Avins <jya@ieee.org> wrote:
(snip, I wrote)
>> I don't think it is quite that obvious.

> What the difference is may not be obvious, but their being somehow 
> different is. I suppose one's view depends on his interpretation od 
> "somewhat".

Also, things seem more obvious after you learn them, but some I
can still remember not knowing.  I knew about the Fourier series
some years before I got to college.  Then, sometime in college
physics (9:00 AM Monday morning) my TA tried to explain the
Fourier transform as the limit of the Fourier series.  Somehow
that was completely non-obvious at the time.  (Partly probably
that I wasn't so awake yet.)  So I specifically remember not
knowing it, and then sometime later finally learning it.

I also remember from the same class, a homework problem on
the friction of a rope wrapped around a tree, the day before
we learned the solution to the differential equation in
math class.

>>                                        There are sources that
>> describe it well, but also many that don't.  I understood both for
>> a long time before finally reading the distinction in "Numerical
>> Recipes."  (Many don't like the programs in the book, but the
>> descriptions are usually pretty readable.  They leave in details
>> that some other sources gloss over.)

> Yes, NR is a good source.

I think so, but many don't like it.  Well, mostly they don't like
the programs.  If you think of the programs as examples to help
learn the explanation, I think they aren't so bad.  If you try
to use them without understanding them, maybe they aren't so good.

-- glen

On Sep 26, 6:10 pm, Jerry Avins <j...@ieee.org> wrote:
> On 9/26/2011 6:24 PM, Raeldor wrote:
>
>    ...
>
>
>
>
>
>
>
>
>
> > So, it might seem to YOU that it's a question that can be easily
> > answered by looking in somewhere like Wikipedia, but I can tell you
> > that I've read the articles there several times, and it's not easily
> > answered when you don't have a math or DSP heavy background.  A lot of
> > these articles seem to say one thing, and then contradict it again a
> > few sentences later.  Either that, or they use terminology which,
> > while very essential, can often be overlooked or misinterpreted by
> > someone from a different background (for me, I am a programmer).  I'm
> > not asking others to do my work, believe me, I've read this stuff,
> > implemented, tested, experimented, and have been for several months,
> > but sometimes I need to go back and confirm that even my BASIC
> > understanding of some of this stuff has not sent me on the wrong
> > track.  I do not ask these questions intending to be disrespectful or
> > lazy, I ask them because I hope to get a more helpful laymens-terms
> > answer from people who frequent this board because they may actually
> > care to help others understand.
>
> When you dig into an article that confuses you, cite the confusing parts
> instead of asking what could seem like a dumb or lazy question. What you
> wanted to know is actually fairly deep. It is about using the algorithm
> of an FFT to actually perform a different transform by some pre- and
> post processing. That doesn't makes the transforms the same.
>
> Jerry
> --
> Engineering is the art of making what you want from things you can get.

Thanks for all the positive replies.  You're right, I probably should
have been more specific, but I was at a point where I was starting to
even doubt my limited understanding.

So, I tried Robert's suggestions, but the output still looks a little
inconsistent (and I think incorrect).  I think it may be because the
FFT library I am using may expect the data in a slightly different
format.  To do a basic FFT on a set of real data 0...n, the library
requires the data to be transformed into an 'even-odd' array.  This is
done by a function vDSP_ctoz, which takes an array of real numbers and
transforms it into a COMPLEX_SPLIT type, which basically contains 2
arrays realp[] and imagp[].  The result of the transformation call
puts the even values into the realp[] array, and the odd values into
the imagp[] array.  I don't think these are actually complex numbers,
because the FFT call is a real-valued FFT function, I think it's just
using these arrays to order the data so that the even numbers come
first followed by the odd.  What isn't clear to me is if I still need
to do this after I have created the mirrored data as Robert suggested.

Also, another thing is that Robert's explanation of having to mirror
the data tied in with what I was reading in the FFTW documentation,
but the Wikipedia article for DCT-II says that the data must also be
interlaced with zero values, I quote...

This transform is exactly equivalent (up to an overall scale factor of
2) to a DFT of 4N real inputs of even symmetry where the even-indexed
elements are zero. That is, it is half of the DFT of the 4N inputs yn,
where y2n = 0, y2n + 1 = xn for , and y4N - n = yn for 0 < n < 2N.

Which wasn't mentioned in Robert's explanation.  So, I'm not sure
whether I should be passing in 2N values or 4N values.

Thanks