DSP - DFT Discrete Cosine Transform

DCT (Discrete Cosine Transform) is an N-input sequence x(n) , 0≤n≤N-1 , as a pnear transformation or combination of complex exponentials. As a result, the DFT coefficients are in general, complex even if x(n) is real.

Suppose, we try to find out an orthogonal transformation which has N×N structure that expressed a real sequence x(n) as a pnear combination of cosine sequence. We already know that −

$X(K) = displaystylesumpmits_{n = 0}^{N-1}x(n)cosfrac{2Pi kn}{N}0leq k leq N-1$

And $x(n) = frac{1}{N}sum_{k = 0}^{N-1}x(k)cosfrac{2Pi kn}{N}0leq k leq N-1$

This is possible if N point sequence x(n) is real and even. Thus, $x(n) = x(N-n),0leq n leq (N-1)$. The resulting DFT itself is real and even. These things make it clear that we could possibly device a discrete cosine transform, for any N point real sequence by taking the 2N point DFT of an “Even extension” of sequence.

DCT is, basically, used in image and speech processing. It is also used in compression of images and speech signals.

$DFT[s(n)] = S(k) = sum_{n = 0}^{2N-1}s(n)W_{2N}^{nk},quad wherequad 0leq k leq 2N-1$

$S(k) = displaystylesumpmits_{n = 0}^{N-1}x(n)W_{2N}^{nk}+displaystylesumpmits_{n = N}^{2N-1}x(2N-n-1)W_{2N}^{nk};quad wherequad 0leq kleq 2N-1$

$Rightarrow S(k) = W_{2N}^{-k/2}+sum_{n = 0}^{N-1}x(n) [W_{2N}^{nk}W_{2N}^{k/2}+W_{2N}^{-nk}W_{2N}^{-k/2}];quad wherequad 0leq kleq 2N-1$

$Rightarrow S(k) = W_{2N}^{frac{k}{2}}sum_{n = 0}^{N-1}x(n)cos [frac{pi}{N}(n+frac{1}{2})k];quad wherequad 0leq kleq 2N-1$

DCT is defined by,

$V(k) = 2sum_{n = 0}^{N-1}x(n)cos [frac{pi}{2}(n+frac{1}{2})k]quad wherequad 0leq kleq N-1$

$Rightarrow V(k) = W_{2N}^{frac{k}{2}}S(k)quad orquad S(k) = W_{2N}^{frac{k}{2}}V(k),quad wherequad 0leq kleq N-1$

$Rightarrow V(k) = 2R[W_{2N}^{frac{k}{2}}sum_{n = 0}^{N-1}x(n)W_{2N}^{nk}],quad wherequad 0leq kleq N-1$