# Connexions

You are here: Home » Content » Fast Algorithms for the DCT

### Lenses

What is a lens?

#### Definition of a lens

##### Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

##### What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

##### Who can create a lens?

Any individual member, a community, or a respected organization.

##### What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

#### In these lenses

• eScience, eResearch and Computational Problem Solving

This module is included inLens: eScience, eResearch and Computational Problem Solving
By: Jan E. OdegardAs a part of collection: "Image Coding"

Click the "eScience, eResearch and Computational Problem Solving" link to see all content selected in this lens.

### Recently Viewed

This feature requires Javascript to be enabled.

# Fast Algorithms for the DCT

Module by: Nick Kingsbury. E-mail the author

Summary: This module introduces a fast algorithms for the DCT.

The basic nn-point DCT requires n2 n 2 multiplications and n(n1) n n 1 additions to calculate y=Tx y T x (64 mults and 56 adds for n=8 n 8 ).

From the figure in our discussion of DCT, it is clear that symmetries exist in the DCT basis functions. These can be exploited to reduce the computation load of the DCT.

All the odd rows of TT in this equation from our discussion of DCT possess even symmetry about their centres and all the even rows possess odd symmetry. Hence we may form:

i,i=14:(ui=xi+x9i)(vi=xix9i) i i 1 4 u i x i x 9 i v i x i x 9 i
(1)
and then form the odd and even terms in yy from two 4×4 4 4 transforms:
(( y1 y3 y5 y7 )= T left , odd u)(( y2 y4 y6 y8 )= T left , even v) y 1 y 3 y 5 y 7 T left , odd u y 2 y 4 y 6 y 8 T left , even v
(2)
where T left , odd T left , odd and T left , even T left , even are the 44x 44 matrices formed by the left halves of the odd and even rows of TT.

This reduces the computation to 8 add/subtract operations for Equation 1 and 2×16 2 16 mults and 2×12 2 12 adds for Equation 2 - almost halving the total computation load.

The matrix T left , even T left , even cannot easily be simplified much further, but T left , odd T left , odd can, as it possesses the same symmetries as TT (it is equivalent to a 4-point DCT matrix). Hence we may use the same technique on this matrix to reduce the 16 mults and 12 adds for this product to 4 add/subtract operations followed by a pair of 22 x 22 matrix products, requiring 2×4 2 4 mults and 2×2 2 2 adds. Finally two of these mults may be saved since one of the 22 x 22matrices is just a scaled add/subtract matrix (like the Haar transform).

The total computation load for the 8×8 8 8 DCT then becomes:

• 8+12+4+2+2=28 8 12 4 2 2 28 add/subtract operations;
• 16+4+2=22 16 4 2 22 multiply operations.
More complicated algorithms exist (JPEG Book, sections 4.3.2 to 4.3.5) which reduce the number of multiplies further. However these all require more intermediate results to be stored. In modern DSP chips this can cost more CPU cycles than the extra multiplications which can often be done simultaneously with additions. Hence the simple approach given above is frequently optimal.

## Content actions

PDF | EPUB (?)

### What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

### Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

#### Definition of a lens

##### Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

##### What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

##### Who can create a lens?

Any individual member, a community, or a respected organization.

##### What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks