Hi all,

I want to know whether the reference implementation of B.G.Lee's(Full
name Given below) DCT algorithm was availabe on web ? If available,
anyone please tell me the path or send me the code.

Thanks in advance,

Regards,
Ramya.

**************************************************************
Byeong Gi Lee, ``A New Algorithm to Compute the Discrete Cosine
Transform,'' IEEE Transaction On Acoustics, Speech, and Signal
Processing, Vol. ASSP-32, No. 6, pp. 1241-1243, Dec. 1984.
**************************************************************

Ramya wrote:
> I want to know whether the reference implementation of B.G.Lee's(Full
> name Given below) DCT algorithm was availabe on web ? If available,
> anyone please tell me the path or send me the code.

I don't know of any implementations of that algorithm in particular; 
most of the DCT implementations available online (such as FFTW's, 
Ooura's, or FFTPACK's) work by re-expressing it as a real-valued FFT 
(which is generally more practical because it allows you to exploit 
highly-optimized FFT implementations).  Our FFTW (fftw.org) also 
contains a generator that can produce very efficient hard-coded DCTs of 
small sizes.

Is there a reason that you want Lee's approach in particular?  Note that 
this paper is rather old, and there have been many subsequent papers on 
similar recursive DCT algorithms analogous to Cooley-Tukey (as well as 
some analogous to Prime-Factor etc.).  Claims in the Lee paper about his 
algorithm requiring half as many operations compared to "existing 
efficient algorithms" are out of date.

Cordially,
Steven G. Johnson

PS. The page numbers on your citation are wrong: it should be 1243-1245

Hi Steven,

What do you think is the fastest algorithm for 8x8 dct for software
implementation. I have been using the sparse matrix factorization
based chen-wang algorithm.  Any special advantage for using a
fft-based algorithms for computing dct, except maybe generalization.

Regards
Piyush

"Steven G. Johnson" <s...@alum.mit.edu> wrote in message
news:<40ab1870$0$579$b...@senator-bedfellow.mit.edu>...
> Ramya wrote:
> > I want to know whether the reference implementation of B.G.Lee's(Full
> > name Given below) DCT algorithm was availabe on web ? If available,
> > anyone please tell me the path or send me the code.
> 
> I don't know of any implementations of that algorithm in particular; 
> most of the DCT implementations available online (such as FFTW's, 
> Ooura's, or FFTPACK's) work by re-expressing it as a real-valued FFT 
> (which is generally more practical because it allows you to exploit 
> highly-optimized FFT implementations).  Our FFTW (fftw.org) also 
> contains a generator that can produce very efficient hard-coded DCTs of 
> small sizes.
> 
> Is there a reason that you want Lee's approach in particular?  Note that 
> this paper is rather old, and there have been many subsequent papers on 
> similar recursive DCT algorithms analogous to Cooley-Tukey (as well as 
> some analogous to Prime-Factor etc.).  Claims in the Lee paper about his 
> algorithm requiring half as many operations compared to "existing 
> efficient algorithms" are out of date.
> 
> Cordially,
> Steven G. Johnson
> 
> PS. The page numbers on your citation are wrong: it should be 1243-1245

Piyush Kaul wrote:
> What do you think is the fastest algorithm for 8x8 dct for software
> implementation. I have been using the sparse matrix factorization
> based chen-wang algorithm.  Any special advantage for using a
> fft-based algorithms for computing dct, except maybe generalization.

Re-expressing a DCT in terms of an FFT is probably never going to be the 
  fastest in principle.  In practice, you are unlikely to have enough 
engineering time to optimize DCTs in general as much as existing FFTs, 
which is why the FFT-based algorithms are attractive.  However, for a 
specific case like size-8, or 8x8, then you are better off hard-coding a 
specialized DCT.

(In fact, FFTW already uses hard-coded size-8 DCT II and III, simply 
because they seem so common.  It can automatically generate hard-coded 
DCTs of any size, but this is the only size we include by default.)

It is hard to make absolute statements about speed, but I strongly 
suspect that the optimal approach for 8x8 on a recent general-purpose 
CPU would be to just hard-code the whole thing, completely unrolled and 
mixed together.  FFTW's generator would be a good starting point for 
this, because it can already generate DCTs, can automatically produce a 
good schedule for the code, find algebraic simplifications, etcetera. 
Modifying it to generate multi-dimensional DCTs would be relatively 
easy, because you only need to input the abstract transform at the front 
end, assuming you know a little ocaml.

Steven

PS. *All* FFT and FFT-like algorithms (for the DFT, DCT, etc.) can be 
viewed as sparse matrix factorizations, so this is not a good way to 
distinguish a particular approach.  If I recall correctly, Chen-Wang, 
like most specialized DCT algorithms, is just Cooley-Tukey in disguise 
(specialized for the particular symmetry of the DCT).  In fact, this is 
how FFTW generates DCTs--it just starts with the abstract algorithm 
(Cooley-Tukey, or whatever) on the complex DFT, imposes the appropriate 
symmetries on the input and output (e.g. real and even), and 
simplifies...this is generally sufficient to achieve the same operation 
counts as the "specialized" algorithms in the literature.