DCT-IV using IFFT

Hello, 

I am trying to use IFFT to calculate the IDCT(Type 4). Can any one
please explain how I am supposed to go about it. I am familiar with
the procedure required to evaluate IDCT (Type  I ) using IFFT but
cannot seem to figure out how it is going to work for IDCT Type - 4.

Thanks, 

-Mugdha

Mugdha,

Is this a homework problem?

The DCV-IV is obtained by shifting the frequencies of the DCT basis
functions by pi/2N while having the same scaling factor for all basis
functions. Any particular reason you need to use the DCT-IV (if this
is not a homework)? If your application involves signal coding the DCT
would probably be a better choice.

--smb

Hi, 
Thanks for your reply. Actually I am trying to replace a function
(that is a part of a library) which calculates the DCT4 (for a
TMS320C55x), by something faster . There are existing libraries (for
TMS320C55x) which provide optimized FFT code and I was wondering if
using this FFT code to calculate the DCT4 might be able to speed up
the calculation of the DCT4 than what it is right now. So i need it to
be specially DCT4.  I tried looking for any kind documentation for
doing the same but did not come across any. If anyone has any pointers
to exisiting literature that I could use please let me know.

Thanks again. 
Cheers
-Mugdha 


mugdha@bach.as.arizona.edu (Mugdha Oltikar) wrote in message news:<6abeb654.0405270240.1b37d511@posting.google.com>...
> Hello, 
> 
> I am trying to use IFFT to calculate the IDCT(Type 4). Can any one
> please explain how I am supposed to go about it. I am familiar with
> the procedure required to evaluate IDCT (Type  I ) using IFFT but
> cannot seem to figure out how it is going to work for IDCT Type - 4.
> 
> Thanks, 
> 
> -Mugdha

> I am trying to use IFFT to calculate the IDCT(Type 4). Can any one
> please explain how I am supposed to go about it. I am familiar with
> the procedure required to evaluate IDCT (Type  I ) using IFFT but
> cannot seem to figure out how it is going to work for IDCT Type - 4.

See the Paper "Split Radix Algorothms for Discrete Trigonometric
Transforms" by Gerlind Plonka and Manfred Tasche
http://www.uni-duisburg.de/FB11/STAFF/PLONKA/splitradix2.ps

mugdha@bach.as.arizona.edu (Mugdha Oltikar) writes:

> Hello, 
> 
> I am trying to use IFFT to calculate the IDCT(Type 4). Can any one
> please explain how I am supposed to go about it. I am familiar with
> the procedure required to evaluate IDCT (Type  I ) using IFFT but
> cannot seem to figure out how it is going to work for IDCT Type - 4.

Hi Mugdha,

I am sorry that I cannot help you with your question, but I was hoping
you could explain to me what an "IDCT Type -4" is? It is obviously some
some of inverse discrete-cosine transform, but where are these types
defined?
-- 
Randy Yates
Sony Ericsson Mobile Communications
Research Triangle Park, NC, USA
randy.yates@sonyericsson.com, 919-472-1124

Randy Yates wrote:

> mugdha@bach.as.arizona.edu (Mugdha Oltikar) writes:

>>I am trying to use IFFT to calculate the IDCT(Type 4).

(snip)

> I am sorry that I cannot help you with your question, but I was hoping
> you could explain to me what an "IDCT Type -4" is? It is obviously some
> some of inverse discrete-cosine transform, but where are these types
> defined?

I have "Techniques & Standards for Image Video & Audio Coding",
K.R. Rao and J.J Hwang which describes them.

The difference is the position at which the samples are
taken, if you consider it as a sampling problem.  The points
are still equally spaced, but the boundary conditions matter.

(I believe that for an infinite number of points they will
all be the same.)

For DCT IV, the forward and inverse sample points are odd
multiples of pi/(4 N).

> Hi Mugdha,
>
> I am sorry that I cannot help you with your question, but I was hoping
> you could explain to me what an "IDCT Type -4" is? It is obviously some
> some of inverse discrete-cosine transform, but where are these types
> defined?
> -- 
> Randy Yates
> Sony Ericsson Mobile Communications
> Research Triangle Park, NC, USA
> randy.yates@sonyericsson.com, 919-472-1124

Hello Randy,

Try page 12 of the following paper, and you will see 8 DCTs and 8 DSTs
defined:

http://www.ece.cmu.edu/~pueschel/papers/dttalgo.pdf

-- 
Clay S. Turner, V.P.
Wireless Systems Engineering, Inc.
Satellite Beach, Florida 32937
(321) 777-7889
www.wse.biz
csturner@wse.biz

mugdha@bach.as.arizona.edu (Mugdha Oltikar) wrote...
> I am trying to use IFFT to calculate the IDCT(Type 4). Can any one
> please explain how I am supposed to go about it. I am familiar with
> the procedure required to evaluate IDCT (Type  I ) using IFFT but
> cannot seem to figure out how it is going to work for IDCT Type - 4.

Our FFTW library (www.fftw.org) has an implementation of the DCT-IV
that works like this (i.e., via an equal size real-data FFT).  There
are a few different algorithms to choose from.  The simplest that I
know of is:

S. C. Chan and K. L. Ho, "Direct methods for computing discrete
sinusoidal transforms," IEE Proceedings F 137 (6), 433-442 (1990).

which re-expresses it as an equal-size DCT-II or DCT-III, which you
can then re-express as a real-data DFT by a variety of means, e.g. the
one on FFTPACK, also described in John Makhoul, "A fast cosine
transform in one and two dimensions," IEEE Trans. on Acoust. Speech
and Sig. Proc., ASSP-28 (1), 27-34 (1980).  However, this Chan/Ho
algorithm has a serious flaw: its rms numerical errors grow as
O(sqrt(n)), vs. O(sqrt(log n)) for the Cooley-Tukey FFT.

To get O(sqrt(log n)) errors for the DCT-IV for *even* sizes, FFTW
uses the method from:

Zhongde Wang, "On computing the discrete Fourier and cosine
transforms," IEEE Trans. Acoust. Speech Sig. Proc. ASSP-33 (4),
1341-1344 (1985).

to re-express it as a pair of DCT-III (or DCT-II) problems, which are
then solved as above.   For accurate treatment of odd sizes, we use
the algorithm from S. C. Chan and K. L. Ho, "Fast algorithms for
computing the discrete cosine transform," IEEE Trans. Circuits Systems
II: Analog & Digital Sig. Proc. 39 (3), 185-190 (1992) [ this paper
has errors, however...see our source code ].

The problem of algorithms with poor numerical characteristics seems to
be widespread in the DCT literature.  For example, the standard
algorithm to re-express the DCT-I as a real-FFT of the same size (used
in FFTPACK, Numerical Recipes, etc.), is also "unstable" (i.e.,
O(sqrt(n)) errors).  On the other hand, you are usually safe with any
algorithm that is essentially Cooley-Tukey specialized for the
symmetries of the DCT (algorithms that recursively break a DCT into
smaller DCTs tend to be of this type).

Of course, FFTPACK has been around for 30 years and I've never heard
of anyone complain about the O(sqrt(n)) errors in its DCT-I code. 
Probably, this is because most people only compute DCTs of relatively
small datasets.

Cordially,
Steven G. Johnson

PS. For people in this thread wondering what a DCT IV is, see e.g.
http://en.wikipedia.org/wiki/Discrete_cosine_transform  ...the
different types of DCT all correspond to DFTs of real-even data, with
various half-sample shifts in the input and output, with
correspondingly different boundary conditions.  The main application
of the DCT-IV that I've seen is for the MDCT (any DCT-IV algorithm
trivially gives you an MDCT algorithm), but I'd be interested in
hearing of other uses.