Hi,


Currently i am trying to implement imdct using DCT instead of FFT.so it ll be helpfull to me if anyone specifies me the efficient DCT implementation.



Thanks in Advance,
satish

Are you looking for an implementation, or for a description so you can implement it yourself. If it's the former, FFTW is extremely good, fast and numerically stable. It is GPL though, so it might not be the best choice for you. FFTW is used internally by many commercial programs (you can get a commercial licence from the authors) such as Matlab.

If you are looking for a description so you can implement it yourself, getting a good textbook might be the best way.

What DCT?

DCT-1, DCT-2, DCT-3, DCT-4, ... ?

Hi garf,

I want to implement imdct in AAC using combination of DCTIV and DCTII .can u pls send me implementation docs and efficient(if possible) "C" code for 1026 point implementation.

Thanks in Advance,
satish

for iMDCT ?
Then, the DCT IV is exactly what you want.

Efficient 1026 point transform?
1026 = 2^10 + 2^1
You sure?

Google for FFTW. This library can do various sorts of DCTs DSTs, too.



The DCT is usually computed via FFT! (You don't have to, but it's very fast this way)

Using FFTW, rather than your own implementation, is a good idea. It is likely to be both faster and more numerically stable than an implementation of your own. It will also have fewer bugs. Be careful, however, because FFTW is licenced under the GPL - you need to consider the licence of your own software (if you are going to distribute it) if you link to FFTW.

This doesn't mean you shouldn't try writing your own. If you want to learn, coding your own is indispensable. If you want to write good, maintainable open source software, FFTW is the way to go.

Hi,

Thanks 4 ur reply.Actually i am working on AAC of faad,in that they had already implemented imdct using FFT,but in some other document it was mentioned that imdct via DCTII is little faster than imdct using FFT,but they didnt mentioned implementation details.so am trying to implement it,but as u said if i implement using FFTW again it ll be same as that of imdct using FFT.so pls let me know if there is any other implementation.

Thanks in Advance,
satish

I was under the impression that the (i)MDCT is best computed via DCT_IV which is in turn best computed via FFT. If you find papers that suggest otherwise please mention them here.

Hi,

Yesterday i had sent PM to u which specifies the url of the fast imdct related document.Please go through the same and give me ur comments regarding that specific implementation.


Thanks in Advance,
satish

Thank you! I think other forum users will appreciate it if you mention the link in this thread. Unfortunately I have no time to analyse the paper at the moment. Also, it's not my job to do your job.

Table 1:

Assuming the authors are correct one can save n/2 multiplications with the proposed algorithm compared to the split-radix FFT approach. For window lengths of n=2048 this translates to 7168 instead of 8192 multiplications. Assuming that 50% of the decoding time is spent on multiplications due to the iMDCT (just a wild guess) you could make your decoder approx 7% faster. What about code complexity? I don't know for sure. But I'm afraid it'll increase a bit.

Hi,

Thanks 4 ur reply.sorry,i think u mis understood me.i didnt mean u to do my work,as u had good experience on different IMDCT implementations jus i asked your opinion regarding this implementation.

Thanks,
satish

What paper are you referring to?

D.-Y. Chan, J.-F. Yang, S.-Y. Chen. "Regular implementation algorithms of time domain aliasing cancellation", IEE Proceedings - Vision, Image and Signal Processing, Volume 143 No. 06, December 1996, pp. 387-392.

forseti.grainger.uiuc.edu/~iee/VIS/143_06/960818/96081800.pdf

I experimented with an implementation which split the DCT-IV into smaller DCT-IV and DCT-II. There were definitely some issues with code complexity. My first attempt using recursive functions was slower than with FFT. I imagine it could be done a bit more simply by pre-calculating all the sample rearrangement and then running the set of small DCT's. However, I chose to use the libvorbis implementation of the MDCT since it's under the Xiph BSD-style license and is faster than all other implementations I've tried. FFTW is also good, but like was mentioned before, it's under the GPL.

I quickly looked at it. The only place where this gains something is in merging the windowing function with part of the DCT. In AAC this is already impossible I think because of the window and block switching (the overlap from the previous frame has to be windowed with a different window function in the next frame, so you always need the unwindowed data). If you forget about the window merging their numbers can be beaten easily.
In my experience it also seems impossible to beat a DCT-4 (using FFT) in speed by doing it using DCT-2's and DCT-3's, at least for big block sizes.

Hi,

Thanks 4 ur reply.can u send me if u have any efficient implementation of DCT-4 using FFT(if possible),documents related to that also.

Thnaks in Advance,
satish.

LOL sure...

The DCT4 can be easily implemented using a FFT, there are numerous papers on that, even source code.
The most important part in the DCT4 is then the FFT, of which also numerous examples exist, ranging from bad to very good.

Hi,

If possible can u send me the efficient source code of DCT-4 using FFT and related docs.wot does LOL stands for?


Thanks in Advance,
satish

No

I remembered that I've responded in this discussion thread with something that may be of use for you.

I had seen that implementation before itself, but i was in search of "C"implementation.

Look, pal. Obviously you need to help yourself from now on. You have been given enough pointers to do so.

I had implemented the algorithm and in parallel i am searching for the other one to comapre with mine.