home
PDF (letter size)
PDF (legal size)

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

Nasser M. Abbasi

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 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 ( \left ( r-1\right ) \left ( s-1\right ) \right ) }\] Hence for first 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 first column of the temporary matrix in \(F\) space is \(\begin{pmatrix} 2\\ -1 \end{pmatrix} \). Now we find 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 first 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 first 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 first 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 final DFT is \[\begin{pmatrix} 2.5 & -0.5\\ -1 & 0 \end{pmatrix} \]