Forums

DCT-IV using IFFT

Started by Mugdha Oltikar May 27, 2004
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.