home

PDF (letter size)

Given data $$f(n,m)=\left(\begin{array}{cc}1& 2\\ 3& 4\end{array}\right)$$ To find its DFT, we compute the DFT of each column at a time, which generates a temporary matrix. Then compute the DFT of each row of the temporary matrix. This gives the DFT of the above.  

The DFT of 1D is given by$$F\left[s\right]=\frac{1}{n}\sum _{r=1}^{n}f\left[r\right]e^{\frac{2\pi }{n}i\left((r-1)(s-1)\right)}$$ Hence for first column in the data, which is $\left(\begin{array}{c}1\\ 3\end{array}\right)$ and using $n=2$ in this example (same number of rows as columns). Then the above becomes$$\begin{array}{rl}F\left[s\right]& =\frac{1}{2}\sum _{r=1}^{2}f\left[r\right]e^{\pi i\left((r-1)(s-1)\right)}\\ & =\frac{1}{2}(f\left[1\right]+f\left[2\right]e^{\pi i(s-1)})\\ & =\frac{1}{2}(1+3e^{\pi i(s-1)})\end{array}$$

Therefore$$\begin{array}{rl}F[s=1]& =\frac{4}{2}=2\\ F[s=2]& =\frac{1}{2}(1+3e^{\pi i})=\frac{1}{2}(1-3)=-1\end{array}$$

Hence the first column of the temporary matrix in $F$ space is $\left(\begin{array}{c}2\\ -1\end{array}\right)$. Now we find the DFT of the second column of the input which is $\left(\begin{array}{c}2\\ 4\end{array}\right)$. we have (since $n=2$ in this example)$$\begin{array}{rl}F\left[s\right]& =\frac{1}{2}\sum _{r=1}^{2}f\left[r\right]e^{\frac{2\pi }{2}i\left((r-1)(s-1)\right)}\\ & =\frac{1}{2}(f\left[1\right]+f\left[2\right]e^{\pi i(s-1)})\\ & =\frac{1}{2}(2+4e^{\pi i(s-1)})\end{array}$$

Therefore$$\begin{array}{rl}F[s=1]& =\frac{1}{2}(2+4)=3\\ F[s=2]& =\frac{1}{2}(2+4e^{\pi i})=\frac{1}{2}(2-4)=-1\end{array}$$

Hence the second column of the temporary matrix in $F$ space is $\left(\begin{array}{c}3\\ -1\end{array}\right)$ which means after first pass, the temporary matrix in $F$ space is now$$\left(\begin{array}{cc}2& 3\\ -1& -1\end{array}\right)$$ Now we apply DFT to each row of the above. This is the second pass. For the first row of the above, the DFT is $$\begin{array}{rl}F\left[s\right]& =\frac{1}{2}\sum _{r=1}^{2}f\left[r\right]e^{\frac{2\pi }{2}i\left((r-1)(s-1)\right)}\\ & =\frac{1}{2}(f\left[1\right]+f\left[2\right]e^{\pi i(s-1)})\\ & =\frac{1}{2}(2+3e^{\pi i(s-1)})\end{array}$$

Therefore the DFT of the first row becomes$$\begin{array}{rl}F[s=1]& =\frac{1}{2}(2+3)=2.5\\ F[s=2]& =\frac{1}{2}(2+3e^{\pi i})=\frac{1}{2}(2-3)=-0.5\end{array}$$

Which is $\left(\begin{array}{cc}2.5& -0.5\end{array}\right)$, and the DFT of the second is$$\begin{array}{rl}F\left[s\right]& =\frac{1}{2}\sum _{r=1}^{2}f\left[r\right]e^{\frac{2\pi }{2}i\left((r-1)(s-1)\right)}\\ & =\frac{1}{2}(f\left[1\right]+f\left[2\right]e^{\pi i(s-1)})\\ & =\frac{1}{2}(-1-e^{\pi i(s-1)})\end{array}$$

which is$$\begin{array}{rl}F[s=1]& =\frac{1}{2}(-1-1)=-1\\ F[s=2]& =\frac{1}{2}(-1-e^{\pi i})=\frac{1}{2}(-1+1)=0\end{array}$$

Which is $\left(\begin{array}{cc}-2& 1\end{array}\right)$. Therefore the final DFT is $$\left(\begin{array}{cc}2.5& -0.5\\ -1& 0\end{array}\right)$$