home
PDF (letter size)
PDF (legal size)

## Note on how to calculate Discrete time Fourier transform for 2D data

May 25, 2020   Compiled on May 25, 2020 at 4:38am

Given data $f\left ( n,m\right ) =\begin{pmatrix} 1 & 2\\ 3 & 4 \end{pmatrix}$ To ﬁnd 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 ( \left ( r-1\right ) \left ( s-1\right ) \right ) }$ Hence for ﬁrst column in the data, which is $$\begin{pmatrix} 1\\ 3 \end{pmatrix}$$ and using $$n=2$$ in this example (same number of rows as columns). Then the above becomes\begin{align*} F\left [ s\right ] & =\frac{1}{2}\sum _{r=1}^{2}f\left [ r\right ] e^{\pi i\left ( \left ( r-1\right ) \left ( s-1\right ) \right ) }\\ & =\frac{1}{2}\left ( f\left [ 1\right ] +f\left [ 2\right ] e^{\pi i\left ( s-1\right ) }\right ) \\ & =\frac{1}{2}\left ( 1+3e^{\pi i\left ( s-1\right ) }\right ) \end{align*}

Therefore\begin{align*} F\left [ s=1\right ] & =\frac{4}{2}=2\\ F\left [ s=2\right ] & =\frac{1}{2}\left ( 1+3e^{\pi i}\right ) =\frac{1}{2}\left ( 1-3\right ) =-1 \end{align*}

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

Therefore\begin{align*} F\left [ s=1\right ] & =\frac{1}{2}\left ( 2+4\right ) =3\\ F\left [ s=2\right ] & =\frac{1}{2}\left ( 2+4e^{\pi i}\right ) =\frac{1}{2}\left ( 2-4\right ) =-1 \end{align*}

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

Therefore the DFT of the ﬁrst row becomes\begin{align*} F\left [ s=1\right ] & =\frac{1}{2}\left ( 2+3\right ) =2.5\\ F\left [ s=2\right ] & =\frac{1}{2}\left ( 2+3e^{\pi i}\right ) =\frac{1}{2}\left ( 2-3\right ) =-0.5 \end{align*}

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

which is\begin{align*} F\left [ s=1\right ] & =\frac{1}{2}\left ( -1-1\right ) =-1\\ F\left [ s=2\right ] & =\frac{1}{2}\left ( -1-e^{\pi i}\right ) =\frac{1}{2}\left ( -1+1\right ) =0 \end{align*}

Which is $$\begin{pmatrix} -2 & 1 \end{pmatrix}$$. Therefore the ﬁnal DFT is $\begin{pmatrix} 2.5 & -0.5\\ -1 & 0 \end{pmatrix}$