Subject: Re: Computational complexity of DCT.

From: [email-masked] (Gary Sullivan)
Date: Thu, 2 Jun 1994 16:10:48 GMT

In article <[email-masked]> [email-masked] (Bill Davidson) writes:
>I am going through the Pennebaker/Mitchell JPEG book and I'm trying to
>understand the DCT as well as possible.  I think that the place that
>I'm getting hung up is the extension of a 1-D DCT to a 2-D DCT.  For
>reference I'm looking at pages 40-42.  They give the definition of the
>2-D FDCT as:
>
>                    7   7
>                   ___ ___
>         C(v) C(u) \   \
>S(v,u) = ---- ----  \   \  s(y,x)cos[(2x+1)u*pi/16]cos[(2y+1)v*pi/16]
>          2    2    /   /
>                   /__ /__
>                   y=0 x=0
>
>They also mention that you can work all the cosine stuff into pre
>computed constants.  That makes sense to me and would give:
>
>          7   7
>         ___ ___
>         \   \
>S(v,u) =  \   \  s(y,x)constant(v,u,y,x)
>          /   /
>         /__ /__
>         y=0 x=0
>
>To me this looks like 64 multiplies and 63 adds for every DCT
>coeficient and so would give 64*64=4096 multiplies and 64*63=4032 adds
>for the entire DCT.
>
>However, Pennebaker/Mitchell give the upper bound as 1024 multiplies
>and 896 adds for the reference DCT.  They talk about "separable 1-D
>format" for this and that seems to be where I'm getting lost.
>Apparently it's a natural extension to them but to me, it's not.
>
>Help!
>
>--Bill Davidson
>

First, compute eight 8x1 transforms, per

                7                                7
               ___                              ___
         C(v)  \                                \
T(v,x) = ----   \   s(y,x) cos[(2y+1)v*pi/16]  = \  s(y,x) constant(v,y)
          2     /                                /
               /__                              /__
               y=0                              y=0

which takes 64 terms * (8 multiplies + 7 adds)

Then transform the other dimension, per

                7                                7
               ___                              ___
         C(u)  \                                \
S(v,u) = ----   \   T(v,x) cos[(2x+1)u*pi/16]  = \  T(v,x) constant(u,x)
          2     /                                /
               /__                              /__
               x=0                              x=0

which takes     64 terms * (8 multiplies +   7 adds),

for a total of 128 terms * (8 multiplies +   7 adds)
                       = 1024 multiplies + 896 adds

(There are, of course, faster ways than this)

-- 
---------------------------------
Gary Sullivan  ([email-masked])