The Discrete Fourier Transform (DFT) of One Variable

The Discrete Fourier Transform (DFT) is a powerful tool that allows us to analyze discrete signals in the frequency domain. It bridges the gap between continuous-time signal processing and discrete-time signal processing. Understanding how the DFT is derived from the continuous Fourier Transform (CFT) of a sampled function provides deep insights into signal analysis, sampling theory, and the limitations imposed by discrete representations.

Mathematical Concepts

1. Continuous-Time Signal and Its Fourier Transform

   A continuous-time signal $x(t)$ can be analyzed in the frequency domain using the continuous Fourier Transform (CFT):

   $$X(f) = \int_{-\infty}^{\infty} x(t) e^{-j2\pi f t} dt$$

   where:

   • $X(f)$ is the continuous frequency spectrum,
   • $f$ represents continuous frequency,
   • $j$ is the imaginary unit.

2. Sampling a Continuous-Time Signal

   Sampling involves capturing the signal $x(t)$ at discrete time intervals $T_s$ (sampling period), resulting in:

   $$x_s(t) = x(t) \cdot \sum_{n=-\infty}^{\infty} \delta(t – nT_s)$$

   where $\delta(t)$ is the Dirac delta function, and $x_s(t)$ is the sampled signal.

3. Fourier Transform of a Sampled Signal

   The Fourier Transform of the sampled signal $x_s(t)$ is given by:

   $$X_s(f) = \frac{1}{T_s} \sum_{k=-\infty}^{\infty} X\left(f – \frac{k}{T_s}\right)$$

   This expression shows that $X_s(f)$ is a periodic replication of $X(f)$ with period $\frac{1}{T_s}$.

4. Discrete-Time Signal and the Discrete Fourier Transform

   The discrete-time signal $x[n]$ is obtained by sampling $x(t)$:

   $$x[n] = x(nT_s)$$

   The DFT of $x[n]$ is defined as:

   $$X[k] = \sum_{n=0}^{N-1} x[n] e^{-j \frac{2\pi}{N} kn}$$

   where:

   • $N$ is the total number of samples,
   • $k = 0, 1, \dots, N-1$ indexes the discrete frequencies.

Derivation of the DFT from the Continuous Transform

1. Sampling in Time Domain

   Start with the continuous-time signal $x(t)$ and sample it at intervals $T_s$:

   $$x_s(t) = x(t) \cdot \sum_{n=-\infty}^{\infty} \delta(t – nT_s)$$

   The discrete-time sequence is:

   $$x[n] = x_s(nT_s) = x(nT_s)$$

2. Fourier Transform of the Sampled Signal

   The Fourier Transform of $x_s(t)$ is:

   $$X_s(f) = \int_{-\infty}^{\infty} x_s(t) e^{-j2\pi f t} dt = \sum_{n=-\infty}^{\infty} x(nT_s) e^{-j2\pi f nT_s}$$

   Recognize that this is a Fourier series representation of $X_s(f)$.

3. Relating $X_s(f)$ to $X(f)$

   Using the properties of the Dirac comb in frequency domain:

   $$X_s(f) = \frac{1}{T_s} \sum_{k=-\infty}^{\infty} X\left(f – \frac{k}{T_s}\right)$$

   This equation demonstrates that sampling in time causes replication in frequency.

4. Sampling in Frequency Domain

   To obtain discrete frequencies, sample $X_s(f)$ at $f = \frac{k}{NT_s}$:

   $$X[k] = X_s\left(\frac{k}{NT_s}\right) = \frac{1}{T_s} \sum_{m=-\infty}^{\infty} X\left(\frac{k}{NT_s} – \frac{m}{T_s}\right)$$

   Simplify the argument:

   $$\frac{k}{NT_s} – \frac{m}{T_s} = \frac{k – mN}{NT_s}$$

5. Assuming Bandlimited Signal

   If $X(f)$ is bandlimited and $f_s \geq 2f_{\text{max}}$ (Nyquist rate), the replicas do not overlap, and we can consider $m = 0$:

   $$X[k] = \frac{1}{T_s} X\left(\frac{k}{NT_s}\right)$$

6. Expressing $X[k]$ in Terms of $x[n]$

   Substitute the inverse Fourier Transform of $X(f)$:

   $$X[k] = \frac{1}{T_s} \int_{-\infty}^{\infty} x(t) e^{-j2\pi \frac{k}{NT_s} t} dt$$

   Since $x(t)$ is only known at discrete times $nT_s$:

   $$X[k] = \sum_{n=-\infty}^{\infty} x(nT_s) e^{-j2\pi \frac{k}{N} n}$$

   Limiting $n$ to $0$ to $N-1$ for finite signals:

   $$X[k] = \sum_{n=0}^{N-1} x[n] e^{-j \frac{2\pi}{N} kn}$$

   This is the standard definition of the DFT.

Example: Deriving the DFT from a Sampled Continuous Function

Continuous-Time Signal

Consider the continuous-time signal:

Let’s choose $f_0 = 50$ Hz.

Sampling Parameters

• Sampling frequency: $f_s = 200$ Hz
• Sampling period: $T_s = \frac{1}{f_s} = 0.005$ s
• Number of samples: $N = 8$

Sampling the Signal

Sample $x(t)$ at $t = nT_s$:

Compute $x[n]$ for $n = 0$ to $7$:

• $x[0] = \cos(0) = 1$
• $x[1] = \cos(\pi \cdot 1) = -1$
• $x[2] = \cos(\pi \cdot 2) = 1$
• $x[3] = \cos(\pi \cdot 3) = -1$
• $x[4] = \cos(\pi \cdot 4) = 1$
• $x[5] = \cos(\pi \cdot 5) = -1$
• $x[6] = \cos(\pi \cdot 6) = 1$
• $x[7] = \cos(\pi \cdot 7) = -1$

Compute the DFT

Using the DFT formula:

Compute $X[k]$ for $k = 0$ to $7$:

1. For $k = 0$:

   $$X[0] = \sum_{n=0}^{7} x[n] e^{-j0} = \sum_{n=0}^{7} x[n] = (1) + (-1) + (1) + (-1) + (1) + (-1) + (1) + (-1) = 0$$

2. For $k = 1$:

   $$X[1] = \sum_{n=0}^{7} x[n] e^{-j \frac{2\pi}{8} n}$$

   Compute each term:

   • $n = 0$: $x[0] e^{-j0} = 1$
   • $n = 1$: $x[1] e^{-j \frac{\pi}{4} } = -1 e^{-j \frac{\pi}{4}}$
   • $n = 2$: $x[2] e^{-j \frac{\pi}{2} } = 1 e^{-j \frac{\pi}{2}}$
   • $n = 3$: $x[3] e^{-j \frac{3\pi}{4} } = -1 e^{-j \frac{3\pi}{4}}$
   • Continue for $n = 4$ to $7$.

   Sum the terms numerically to find $X[1]$.

3. For $k = 4$:

   $$X[4] = \sum_{n=0}^{7} x[n] e^{-j \frac{2\pi}{8} 4 n} = \sum_{n=0}^{7} x[n] e^{-j \pi n}$$

   Since $e^{-j \pi n} = (-1)^n$:

   $$X[4] = \sum_{n=0}^{7} x[n] (-1)^n$$

   Compute:

   • For even $n$: $(-1)^n = 1$, $x[n] = 1$, so $x[n] (-1)^n = 1$
   • For odd $n$: $(-1)^n = -1$, $x[n] = -1$, so $x[n] (-1)^n = (-1)(-1) = 1$

   Therefore:

   $$X[4] = \sum_{n=0}^{7} 1 = 8$$

4. DFT Results

After computing $X[k]$ for all $k$:

• $X[0] = 0$
• $X[4] = 8$
• Other $X[k]$ values will be zero or near zero due to the orthogonality of the exponentials.

Interpretation

• The significant DFT coefficient at $k = 4$ corresponds to a frequency:

  $$f_k = \frac{k f_s}{N} = \frac{4 \times 200}{8} = 100 \text{ Hz}$$

• However, our original signal was at $f_0 = 50$ Hz. This discrepancy is due to aliasing, as the signal frequency is equal to half the sampling frequency ($f_s/2$).

• The frequency at $k = 4$ actually represents the aliased frequency:

  $$f_{\text{alias}} = |f_0 – n f_s| = |50 – 0 \times 200| = 50 \text{ Hz}$$

  But due to periodicity in the DFT, it appears at $k = 4$.

Understanding Aliasing

• Since $f_0 = f_s/4$, the sampled signal’s frequency content gets mirrored around $f_s/2$.
• This effect highlights the importance of choosing a sampling frequency higher than twice the highest frequency component (Nyquist rate) to avoid aliasing.

In signal processing, the relationship between the sampling interval (or sampling period) and the frequency interval is a fundamental concept that arises from the Nyquist-Shannon sampling theorem. It describes how continuous signals are represented in the discrete domain and the effects of this transformation on the frequency spectrum of the signal.

Key Concepts

1. Sampling: This is the process of converting a continuous signal (like an analog signal) into a discrete signal by taking measurements (samples) at regular intervals. The sampling interval is the time between successive samples, denoted by $T_s$.

2. Sampling Rate (Sampling Frequency): The inverse of the sampling interval $T_s$ is the sampling frequency, denoted as $f_s$:

   $$f_s = \frac{1}{T_s}$$

   It represents how many samples per second are taken from the continuous signal.

3. Frequency Domain Representation: When you sample a signal, it also affects its representation in the frequency domain. A continuous-time signal is analyzed using Fourier transform, while a discrete-time signal is analyzed using the Discrete Fourier Transform (DFT) or Fast Fourier Transform (FFT).

4. Frequency Interval (Resolution): When a signal is sampled, it is transformed into the frequency domain in discrete steps. The distance between these discrete frequency points is called the frequency interval $\Delta f$, and it is related to the total sampling time $T$, where $T = N T_s$ (with $N$ being the number of samples):

   $$\Delta f = \frac{1}{T} = \frac{1}{N T_s}$$

   The frequency interval defines how finely spaced the frequency components of the sampled signal are when transformed into the frequency domain.

Relationship Between Sampling Interval and Frequency Interval

The relationship between the sampling interval $T_s$ and the frequency interval $\Delta f$ is inversely proportional. Specifically:

• As the sampling interval $T_s$ decreases (sampling rate $f_s$ increases), the frequency interval $\Delta f$ increases. This means you capture a wider range of frequencies but with less detail per frequency step.

• As the sampling interval $T_s$ increases (sampling rate $f_s$ decreases), the frequency interval $\Delta f$ decreases, which gives a finer frequency resolution but at the cost of a smaller total frequency range.

Mathematically, this can be summarized as:

where $N$ is the number of samples, and $T_s$ is the sampling interval.

Example

Let’s consider a practical example:

• Suppose we have a signal sampled at a sampling frequency of $f_s = 1000 \, \text{Hz}$, so the sampling interval is $T_s = \frac{1}{f_s} = 0.001 \, \text{seconds}$.

• We take $N = 1000$ samples, so the total time for the samples is $T = N T_s = 1000 \times 0.001 = 1 \, \text{second}$.

• The frequency interval $\Delta f$ is calculated as:

  $$\Delta f = \frac{1}{T} = \frac{1}{1} = 1 \, \text{Hz}$$

  This means that the frequency resolution of the DFT is 1 Hz, and the frequency domain representation will have frequencies at intervals of 1 Hz (e.g., 0 Hz, 1 Hz, 2 Hz, etc.).

Now, if we increase the sampling rate to $f_s = 2000 \, \text{Hz}$ (i.e., decrease the sampling interval $T_s = 0.0005 \, \text{seconds}$) but keep $N = 1000$ samples:

• The total sampling time is $T = N T_s = 1000 \times 0.0005 = 0.5 \, \text{seconds}$.

• The frequency interval $\Delta f$ becomes:

  $$\Delta f = \frac{1}{T} = \frac{1}{0.5} = 2 \, \text{Hz}$$

  This means the frequency resolution has worsened (the spacing between frequency points has increased to 2 Hz), but we now have a larger overall frequency range.