Discrete Fourier Transform

Figure 8.3: The relation between the continuous Fourier transform and the discrete Fourier transform. The panels on the left show the time domain signal and those on the right show the corresponding spectra.

The Fourier Transform (FT) of a signal $s(t)$ is defined as

$$S(w) = \int_{-\infty}^{+\infty} s(t) e^{-j\omega t} \mbox{d}t$$ (8.3.1)

Discrete Fourier Transform (DFT) is an operation to evaluate the FT of the sampled signal $s(n)$ ( $\equiv s(n\frac{1}{f_s}$)) with a finite number of samples (say $N$). It is defined as

$$S(k) = \sum_{n=0}^{N-1} s(n) e^{-j2\pi nk/N}; \;\; 0 \le k \le N-1$$ (8.3.2)

The relationship between FT and DFT and some properties of DFT are discussed here.

Consider a time series $s(n)$, which is obtained by sampling a continuous band limited signal $s(t)$ at a rate $f_s$ (see Fig. 8.3). The sampling function is a train of delta function III$(t)$. The length of the series is restricted to $N$ samples by multiplying with a rectangular window function $\Pi(t)$. The modification of the signal $s(t)$ due to these operations and the corresponding changes in the spectrum are shown in Fig. 8.3. The spectral modifications can be understood from the properties of Fourier transforms. The FT of the time series can now be written as a summation (assuming N is even)

$$S(\omega) = \int_{-\infty}^{+\infty} s(t) \sum_{n=-N/2}^{N/2-1} \delta(t - \frac{n}{f_s}) e^{-j\omega t}\mbox{d}t$$

$$= \sum_{n=-N/2}^{N/2-1} s(\frac{n}{f_s})e^{-\frac{j\omega n}{f_s}}$$ (8.3.3)

What remains is to quantize the frequency variable. For this the frequency domain is sampled such that there is no aliasing in the time domain (see Fig. 8.3). This is satisfied if $\Delta \omega$ = $2\pi f_s/N$. Thus Eq. 8.3.3 can be written as

$$S(k\Delta\omega) = \sum_{n=-N/2}^{N/2-1}s(\frac{n}{f_s})e^{-\frac{j k \Delta\omega n}{f_s}}$$ (8.3.4)

Using the relation $\Delta \omega/f_s = 2\pi/N$ and writing the variables as discrete indices we get the DFT equation. The cyclic nature of DFT (see below) allows $n$ and $k$ to range from 0 to $N-1$ instead of $-N/2$ to $N/2-1$.

Some properties that require attention are:

1. The spectral values computed for $N/2 \ge k \ge 3N/2-1$ are identical to those for $k = -N/2$ to $N/2-1$. In fact the computed values have a periodicity equal to $N\Delta \omega$ which makes the DFT cyclic in nature. This periodicity is a consequence of the sampling done in the time and frequency domain (see Fig. 8.3).
2. The sampling interval of the frequency variable $\Delta \omega$ (= $2\pi f_s/N$) is inversely proportional to the total number of samples used in the DFT. This is discussed further in Section 8.3.1.

There are several algorithms developed to reduce the number of operations in the DFT computation, which are called Fast Fourier Transform (FFT) algorithms. These algorithms reduce the time required for the computation of the DFT from $O(N^2)$ to $O(N\log(N))$. The FFT implementation used in the GMRT correlator uses Radix 4 and Radix 2 algorithms.

In the digital implementation of FFTs the quantization of the coefficients $e^{-j2\pi nk/N}$ degrades the signal to noise ratio the of spectrum. This degradation is in addition to the quantization noise introduced by the quantizer. Thus the dynamic range reduces further due to coefficient quantization. Coefficient quantization can also produce systematics in the computed spectrum. This effect also depends on the statistics of the input signal, and in general can be reduced only by using a larger number of bits for coefficient representation.