Calculating DCT with DFT

548 Views Asked by At

The discrete cosine transform is given by

(DCT($f$))$_j$= $\sum\limits_{k=0}^{n-1}f_k cos(\frac{\pi}{2}(k+\frac{1}{2})j)$

with reference points $x_k=\frac{\pi}{2n}(2k+1)$

How do we show that (DCT$(f))_j$=2n(DFT($\hat{f}))_j$

where $\hat{f}=(0,f_0,0,f_1,...,f_{n-1},0,f_{n-1},0,f_{n-2},...,0,f_1,0,f_0)$?

1

There are 1 best solutions below

0
On BEST ANSWER

After understanding better I came up with a solution myself. The DFT($f$)$_j$ I am using is

DFT($f$)$_j = \frac{1}{n}\sum\limits_{k=0}^{n-1} f_k e^{-j2\pi\frac{1}{n}ki}$

So $2n$*DFT($\hat{f}$)$_j$ = $2n\frac{1}{4n}\sum\limits_{k=0}^{4n-1} \hat{f}_k e^{-j2\pi\frac{1}{4n}ki}$ = $\frac{1}{2}\sum\limits_{k=0}^{4n-1} \hat{f}_k e^{-j\pi\frac{1}{2n}ki}$.

Now we see that only the odd $\hat{f}_k$ matter here so we rewrite it as:

$\frac{1}{2}\sum\limits_{k=0}^{2n-1} \hat{f}_{2k+1} e^{-j\pi\frac{1}{2n}(2k+1)i}$ = $\frac{1}{2}(\sum\limits_{k=0}^{n-1} \hat{f}_{2k+1} e^{-j\pi\frac{1}{2n}(2k+1)i}$+ $\sum\limits_{k=n}^{2n-1} \hat{f}_{2k+1} e^{-j\pi\frac{1}{2n}(2k+1)i})$

Let $f=(f_0,f_1...,f_{n-1})$. We see that we can replace $\hat{f}_{2k+1}$ in the first sum with $f_k$. We then want the other sum to also "be" $f$ and let the second sum run from the end to the start meaning :

$\frac{1}{2}(\sum\limits_{k=0}^{n-1} f_k e^{-j\pi\frac{1}{2n}(2k+1)i}$+ $\sum\limits_{k=n}^{2n-1} \hat{f}_{2(2n-1-k)+1} e^{-j\pi\frac{1}{2n}(2(2n-1-k)+1)i})$

We can't put those two sums together yet, so we substitute $m=2n-1-k$ which means $k=2n-1-m$ and brings us to:

$\frac{1}{2}(\sum\limits_{k=0}^{n-1} f_k e^{-j\pi\frac{1}{2n}(2k+1)i}$+ $\sum\limits_{m=0}^{n-1} \hat{f}_{2m+1} e^{-j\pi\frac{1}{2n}(2m+1)i})$

Finally we have that for identical $m$ and $k$ that $f_k = \hat{f}_2m+1$ and we take the two sums together:

$\frac{1}{2}\sum\limits_{k=0}^{n-1} f_k (e^{-j\pi\frac{1}{2n}(2k+1)i}+e^{-j\pi\frac{1}{2n}(2(2n-1-k)+1)i})$=$\frac{1}{2}\sum\limits_{k=0}^{n-1} f_k (e^{-j\pi\frac{1}{2n}(2k+1)i}+e^{-j\pi\frac{1}{2n}(4n-2k+1)i})$ = $\frac{1}{2}\sum\limits_{k=0}^{n-1} f_k (e^{-j\pi\frac{1}{2n}(2k+1)i}+e^{-j2\pi}e^{j\pi\frac{1}{2n} (2k+1)i)}$ = $\frac{1}{2}\sum\limits_{k=0}^{n-1} f_k (e^{-j\pi\frac{1}{2n}(2k+1)i}+e^{j\pi\frac{1}{2n} (2k+1)i)}$

Now remember that $cos(x)=\frac{1}{2}(e^{ix}+e^{-ix})$ or $2cos(x)=(e^{ix}+e^{-ix})$. Concluding you have:

$\frac{1}{2}\sum\limits_{k=0}^{n-1} f_k 2cos(\frac{\pi}{2}(2k+1)j)$=$\sum\limits_{k=0}^{n-1} f_k cos(\pi(k+\frac{1}{2})j)$ which had to be shown.