# Lab3: Inverse Discrete Fourier Transform (iDFT)

We have successfully implemented DFT transforming signals from time domain to frequency domain. However, can we transform these signals back to time domain without losing any information? Why are DFT important for signal and information processing? In this lab, we will learn Inverse Discrete Fourier Transform that recovers the original signal from its counterpart in the frequency domain. We will first prove a theorem that tells a signal can be recovered from its DFT by taking the Inverse DFT, and then code a Inverse DFT class in Python to implement this process.

We will then introduce an important application of DFT and Inverse DFT that is signal reconstruction and compression. We will use DFT and Inverse DFT Python classes to approximate some signals we have seen in previous labs, such as square pulse and triangular pulse, and study how well these approximations are compared with the original signal. We will further deal with the real-world signal – our voice. We will code a Python class that can record and play our own voice, based on which we will implement DFT and Inverse DFT for voice compression and masking. We will end up with an interesting problem allowing you to uncover secret messages from a signal that you may consider normal.

• Click here to download the assignment.

• Due on February 8 by 11:59pm.

### Computation of iDFT

In this first part of the lab, we will consider the inverse discrete Fourier transform (iDFT) and its practical implementation. As demonstrated in the lab assignment, the iDFT of the DFT of a signal $\bbx$ recovers the original signal $\bbx$ without loss of information. We begin by proving Theorem 1 that formally states this fact.

#### Proof of Theorem 1

Given a discrete signal $x:[0,N-1]\to\mbC$, let $X=\ccalF(x):\mbZ\to\mbC$ be the DFT of $x$ and $\tdx=\ccalF^{-1}(X):[0,N-1]\to\mbC$ be the iDFT of $X$. From the definition of the iDFT, we have \begin{align}\label{eqn_lab_idft_idft_def} \tdx(\tdn) = {\frac{1}{\sqrt{N}}} \sum_{{k=0}}^{{N-1}}{X(k)}e^{j2\pi{k}{\tdn}/N} \end{align} Now substituting the definition of the DFT for $X(k)$ in \eqref{eqn_lab_idft_idft_def} yields \begin{align}\label{eqn_lab_idft_dft_def} \tdx(\tdn) = {\frac{1}{\sqrt{N}}} \sum_{{k=0}}^{{N-1}}\Big(\frac{1}{\sqrt{N}} \sum_{{n=0}}^{{N-1}}{x(n)}e^{-j2\pi{k}{n}/N}\Big)e^{j2\pi{k}{\tdn}/N} \end{align} We may exchange the order of the summation, so that we first sum over $k$, and then pull out $x(n)$ since it is independent of $k$, i.e. \begin{align}\label{eqn_proof_theorem1_1} \tdx(\tdn) = \sum_{{n=0}}^{{N-1}} x(n) \Big( \sum_{{k=0}}^{{N-1}} {\frac{1}{\sqrt{N}}} e^{-j2\pi{k}{n}/N} {\frac{1}{\sqrt{N}}} e^{j2\pi{k}{\tdn}/N} \Big) \end{align} Due to the orthonormality proved in 2.4 of Lab 1, we obtain \begin{align}\label{eqn_proof_theorem1_2} \sum_{{k=0}}^{{N-1}} {\frac{1}{\sqrt{N}}} e^{-j2\pi{k}{n}/N} {\frac{1}{\sqrt{N}}} e^{j2\pi{k}{\tdn}/N} = \delta(n – \tdn) \end{align} Therefore, \eqref{eqn_proof_theorem1_1} reduces to \begin{align}\label{eqn_proof_theorem1_3} \tdx(\tdn) = \sum_{{n=0}}^{{N-1}} x(n) \delta(n – \tdn) = x(n) \end{align} with $\tdn = n$ since the only nonnegative term in the sum is when $\tdn = n$.

In the following, We will implement the iDFT in practice and employ it together with the DFT for signal reconstruction and compression on different signals, such as the square pulse, the triangular pulse, etc.

#### Signal Reconstruction

The original signal $x$ can be recovered exactly by using $N$ summands in the iDFT expression. However, we can also choose to approximate the signal $x$ by the signal $\tilde{x}_K$ which we define by truncating the DFT sum to the first $K$ terms as \begin{align}\label{eq_truncated_reconstruction} \tilde{x}_K(n) := \frac{1}{\sqrt{N}} \left[ X(0)+ \sum_{k=1}^{K} \left( X(k)e^{ j2\pi kn/N} + X(-k)e^{-j2\pi kn/N} \right) \right]. \end{align} As we increase $K$, i.e., adding more DFT coefficients in the truncated sum, we make the approximation closer to the actual signal. Based on the relation between the signal and its DFT we have learned from last lab assignment, we conclude that if we have a signal that varies slowly, a representation with just a few coefficients is sufficient, while for signals that vary faster, we need to add more coefficients to obtain a reasonable approximation.

We than first implement the signal reconstruction of a square pulse of duration $T=32$s sampled at a rate $f_s=8$Hz and length $T_0=4$s. According to the definition, the original signal and its DFT are shown in the following figures.