
5.3 Fourier, Hadamard, and Cosine Transform Compression
155
The discrete cosine transform may be implemented by using a double
sized fast Fourier algorithm. To show this, consider the one-dimensional
transform in (134). We first zero-pad the data to make it IN elements long:
f
p
(m)=f(ml
m = 0, 1,..., Ν - 1
= 0, m = Ν, Ν +
1,...,2N
- 1 (140)
We can rewrite (134) as
F(u) = ψ Rejexp(; ^) f
p
(m) exp^m ^)},
u = 0, Ι,.,.,Λί - 1 (141)
The summation is clearly a 2N-element discrete Fourier transform, which
may be implented with an FFT algorithm.
As was shown recently by Chen et al. [10], it is also possible to directly
write a fast algorithm for the