PDF (letter size)

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

September 7, 2023   Compiled on September 7, 2023 at 9:26pm

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