3.1 Fast algorithms for the dct

The basic $n$ -point DCT requires $n^2$ multiplications and $n(n-1)$ additions to calculate $y=Tx$ (64 mults and 56 adds for $n=8$ ).

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

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

This reduces the computation to 8 add/subtract operations for and $2\times 16$ mults and $2\times 12$ adds for - almost halving the total computation load.

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

The total computation load for the $8\times 8$ DCT then becomes:

• $8+12+4+2+2=28$ add/subtract operations;
• $16+4+2=22$ multiply operations.