Page 119 - DSP Integrated Circuits

104 Chapter 3 Digital Signal Processing

of operations are needed? How many operations are needed compared with a
direct computation?
The two-dimensional MSDCT is denned as

where

First, an intermediate data array is computed using N steps by computing
3ne-dimensional DCTs of the rows, i.e.,

The final result is obtained by computing the DCTs for the columns in the
intermediate array.

Hence, as illustrated in Figure. 3.31, 2N one-dimensional DCTs and one
matrix transposition of the intermediate data array are needed. In a direct compu-
2
tation, 2N multiplications are needed for each pixel. We neglect multiplications
4
by constants. Thus, we have a total of 2Af multiplications per block. A computa-
3
tion, based on one-dimensional DCTs, requires only 2N multiplications per block.
Fortunately, similar results also hold for the number of additions.

Figure 3.31 Computation of two-dimensional DCT using one-dimensional DCTs

3.19.5 Fast Discrete Cosine Transforms
Fast algorithms with a computational complexity of O(Nlog%(N)), have also been
developed for the DCTs by using the divide-and-conquer principle [13, 20, 28, 42,
45]. However, in practice, the asymptotic complexity is of little interest for image
coding applications since only short sequences with N = 4 to 32 are used. Fortu-
nately, the fast algorithms that have been developed are also efficient for short