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

July 8, 2025 Compiled on July 8, 2025 at 4:40pm

\[ 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.

\[ 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*}

\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*}

\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

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*}

\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*}

\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