home

PDF (letter size)

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

Nasser M. Abbasi

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