The Discrete Fourier Transform (DFT)

8 complex sinusoids of a discrete frequency axis

We talked about discrete frequency in a previous post. Now we explain the Discrete Fourier Transform which computes the contribution of many discrete frequencies in a given signal.

In this Figure, a continuous-time square wave was shown to be a summation of sine waves of different amplitudes. The frequency domain representation of such a square wave identifies the amplitudes of each constituent frequency (e.g., 1 for 1/T, 1/3 for 3/T, 1/5 for 5/T and so on).

Similarly, the Discrete Fourier Transform (DFT) of a signal is the tool that finds out the frequency domain amplitudes present in that signal at N equally spaced discrete frequency points of this Eq we encountered in the article about discrete frequency.

To understand how a set of sinusoids with N discrete frequencies can sum up to a discrete-time signal of an arbitrary shape, a good analogy is the RGB colour model in which red, green, and blue colours combine together in various ways to reproduce a broad range of different colours. Figure below shows the `spectral’ contents of yellow and grey colours formed by contributions [100% 100% 0%] and [50% 50% 50%] from red, green and blue colours, respectively.

Yellow and grey colours with respective contributions from red, green and blue

Similarly, the DFT finds corresponding contributions in a signal from each of the N discrete-time complex sinusoids. These reference sinusoids given by F_S \cdot k/N are called analysis frequencies. For N=8, both I and Q components of these complex analysis frequencies are shown in this Figure.

Definition


Let a complex sinusoid be defined as V[n]. Then, its conjugate V^*[n] is

    \begin{align*}             V_I[n]\: &= \cos 2\pi\frac{k}{N}n \\             V_Q[n] &= -\sin 2\pi\frac{k}{N}n           \end{align*}

What we actually want to do is correlate a finite-length signal s[n] with N complex sinusoids with frequencies k/N (where k ranges from 0 to N-1). For this purpose, we multiply s[n] with the complex sinusoid V^*[n] sample-by-sample using complex multiplication rule. Then, for s[n] with I and Q components s_I[n] and s_Q[n], the DFT S[k] with I and Q components S_I[k] and S_Q[k] is defined as

(1)   \begin{align*}             S_I[k]\: &= \sum \limits _{n=0} ^{N-1} s_I[n] \cos 2\pi\frac{k}{N}n + s_Q[n] \sin 2\pi\frac{k}{N}n \\             S_Q[k] &= \sum \limits _{n=0} ^{N-1} s_Q[n] \cos 2\pi\frac{ k}{N}n - s_I[n] \sin 2\pi\frac{k}{N}n           \end{align*}

for each k = -\frac{N}{2},-\frac{N}{2}+1,\cdots,-1,0,1,\cdots,\frac{N}{2}-1. In the above equation,

  • n is the time domain index of input samples, n=0,1,\cdots,N-1.
  • s[n] is the sequence of input samples, s_I[0], s_Q[0], s_I[1], s_Q[1], \cdots, s_I[N-1], s_Q[N-1].
  • k is the index of DFT output in frequency domain, k = -N/2,-N/2+1, \cdots,-1,0,1, \cdots,N/2-1.
  • S[k] is k-th DFT output component, S_I[-N/2], S_Q[-N/2], S_I[-N/2+1], S_Q[-N/2+1], \cdots, S_I[N/2-1], S_Q[N/2-1].
  • N is the number of data samples in time domain and number of bins in discrete frequency domain.
DFT as correlation


Observe from the definition that each S[k] output is just a sum of term-by-term products between an input signal and complex sinusoids whose frequencies are k complete cycles in an interval of N samples (or k/N cycles per sample). An example of such sinusoids was illustrated in Figure of DFT sinusoids.

Comparing with the phase rotation rule, we can observe that DFT operation is rotating a signal s[n] clockwise. But what exactly does this mean?

Remembering that frequency is defined as the rate of change of phase (sample-by-sample here) — and if s[n] contains a component of frequency +k/N — sample-by-sample de-rotation by a complex sinusoid of the same frequency but opposite direction (i.e., -k/N) results in an output as a single number due to phase canceling out at each step. That single number is naturally the amplitude of the complex sinusoid with frequency k/N, an indicator of how much that sinusoid contributes to the construction of s[n].

The whole process eventually tries to find the contribution of every such cosine/sine wave in construction of that particular input signal. In technical terms, DFT performs correlation between the input signal and reference sinusoids. We will learn about it in the article on correlation.

The relation between a signal s[n] and its Fourier Transform S[k] is usually represented as

    \begin{equation*}         s[n]~ \xrightarrow{\text{\large{F}}} ~ S[k]     \end{equation*}

As a reminder, for a sample rate of F_S=30 kHz and 64 point DFT, the fundamental frequency of the sinusoids is F_S\cdot \pm 1/N = \pm 30,000/64 = \pm 468.75 Hz represented by k=\pm 1. The other analysis frequencies are integer multiples of the fundamental frequency as

  • F_S\cdot \pm2/N = \pm937.5 Hz represented by k = \pm2
  • F_S\cdot \pm3/N = \pm1406.3 Hz represented by k = \pm3

and so on. Each frequency represents one complex sinusoid, or equivalently two real sinusoids.

Owing to this expression, DFT can also be defined for frequency bins k=[0,N-1]. However, the range k = [-N/2,N/2-1] is more natural than k=[0,N-1] since the former corresponds with our notion of a real sinusoid constituting one positive frequency and one negative frequency complex sinusoid. As an example, having two impulses in discrete frequency domain at k = 5 and k = N-5 does not seem to convey much information. However, viewing it as two impulses at k = 5 and k = -5 immediately makes one realize that the time domain signal is a real sinusoid with frequency F_S\cdot 5/N.

Inverse Discrete Fourier Transform (iDFT)


Just like DFT is used to convert a signal from time to frequency domain, Inverse Discrete Fourier Transform (iDFT) is used as an inverse process for converting a signal from frequency to time domain. iDFT is defined as

(2)   \begin{align*}         s_I[n]\: &= \frac{1}{N}\sum \limits _{k=-N/2} ^{N/2-1} S_I[k] \cos 2\pi\frac{k}{N}n - S_Q[k] \sin 2\pi\frac{k}{N}n \\         s_Q[n] &= \frac{1}{N} \sum \limits _{k=-N/2} ^{N/2-1} S_Q[k] \cos 2\pi\frac{ k}{N}n + S_I[k] \sin 2\pi\frac{k}{N}n       \end{align*}

Notice that unlike DFT where the summation is over time index n, summation in iDFT is over frequency index k. Moreover, as opposed to DFT, the complex sinusoids here have a counterclockwise direction of rotation, see phase rotation rule. iDFT is also a correlation like DFT as explained earlier with amplitude scaling as 1/N.

In words, iDFT equation states that to reconstruct a signal s[n], sum N complex sinusoids from k=-N/2 to N/2-1 after weighting them with DFT coefficients S[k].

DFT Periodicity


A natural consequence of DFT equation above is that S[k] can be proved to be periodic with period N, where periodicity of a signal was defined in article about some signal classifications. Since both k and n are integers and \cos(\cdot) and \sin(\cdot) are periodic signals,

    \begin{align*}       \cos 2\pi \frac{k+N}{N} n = \cos \left\{ 2\pi \frac{k}{N} n + 2\pi n \right\} &= \cos 2\pi \frac{k}{N} n \\       \cos 2\pi \frac{k}{N} (n+N) = \cos \left\{ 2\pi \frac{k}{N} n + 2\pi k \right\} &= \cos 2\pi \frac{k}{N} n     \end{align*}

Similar identities hold for \sin(\cdot) as well. Thus, S[k+N] can be found through DFT definition in Eq 1 as

(3)   \begin{align*}             S[k + N] = S[k]      \end{align*}

It is not surprising that the DFT is a periodic signal in frequency domain because we saw in the article about sampling how a discrete-time signal has a spectrum with infinite replicas spaced at integer multiples of sample rate F_S and we obtained the discrete frequency axis (in the discrete frequency article) by sampling the primary zone from -0.5F_S to +0.5F_S at N equally spaced intervals, as shown in this Eq. Combine it with Eq and it is clear that frequency samples k = [-N/2,N/2-1] are exactly the same as [N/2,3N/2-1], or [-3N/2,-N/2-1], and so on. As a consequence, DFT of a signal is indeed a periodic signal in frequency domain.

Is DFT input periodic?


Interestingly, similar trigonometric identities used to find S[k+N] can be utilized to obtain s[n+N] through definition of IDFT (Eq (2)) as

(4)   \begin{align*}         s[n + N] = s[n]      \end{align*}

Although the DFT of any signal s[n] can be taken without any regard to periodicity, whether the DFT structure assumes s[n] being periodic with a period N or not is a matter of debate in DSP community. Some consider it as a logical conclusion of sampling in frequency domain while some others have perfectly reasonable viewpoints of treating it as an aperiodic signal. Either approach is consistent with other insofar as the signal behaviour and interpretation of DFT output is concerned.

Since a common theme of our explanations is simplicity and periodic approach is simpler to follow, Eq (4) will be our guide. All it says is that although we know nothing about what happens with s[n] outside the range 0 to N-1, sampling the frequency axis at N discrete points from -N/2 to N/2-1 creates replicas of s[n] in time domain, just like sampling in time domain created replicas of its spectrum S(F) in frequency domain during sampling. Figure below shows an aperiodic signal s[n] and its periodic extension. I personally consider the other approach more intuitive but it involves concepts like convolution and windowing which we have not covered yet and will encounter later.

Aliases in time domain appear from sampling in frequency domain

As long as N \ge L, the DFT accurately represents the sampled frequency response of the input signal and there is no distortion. Nevertheless, for N < L, the DFT spectrum is no longer its actual sampled frequency domain representation and there will be aliasing in time domain. Obviously, common sense also dictates that taking DFT of a truncated input signal (N < L) should produce inaccurate results.

A major implication of this periodic extension is that sequence shifts for DFT purpose actually result in circular shifts. Assume N = L in the above Figure. Then, a right shift of 1 will knock the last sample at position n=N-1 out of the observation window [0,N-1] to the new position n=N. Moreover, it will bring the last sample from its previous extension at n=-1 inside the observation window to n=0. Conceptually, this is nothing but a circular shift within the window [0,N-1] as discussed in the post on transforming a signal. This DFT observation window is shown as red dotted lines within 0 to N-1.

DFT Approximation of the Actual Spectrum


A natural question at this stage is: how well does the DFT — a sampled frequency function of a sampled time domain signal — approximates the underlying Fourier transform — a continuous frequency function of a continuous time domain signal? An initial guess is that it is not much accurate because the continuous Fourier transform is an integral from -\infty to \infty while the DFT is a finite sum.

The actual answer is that this approximation is quite well. However, there are two possible sources of error.

[Truncation error] Clearly, any signal s[n] that does not have a finite length must be truncated to accommodate finite length of the DFT.
[Aliasing error] According to sampling theorem, the sample rate must be at least twice than the maximum frequency contained in s[n]. Aliasing can occur if the signal is not band-limited.

In the article on the concept of frequency, we discussed that every real signal occupies an infinite amount of bandwidth, as a signal cannot be limited in both time and frequency domains. To avoid truncation errors, a signal must be time-limited which makes its spectrum unlimited causing aliasing errors arise. To avoid aliasing errors, a signal must be band-limited with a sufficient sample rate, but such a signal cannot have finite duration causing truncation errors.

For many cases of practical interest, the amount of these errors is tolerable: with a reasonably band-limited signal that means having very small energy outside a certain frequency band, we can make the signal time-limited and sample it with an adequate sampling rate. That makes the DFT a great tool for analyzing real continuous-time signals.

Fast Fourier Transform (FFT)


A Fast Fourier Transform (FFT) is neither another type of Fourier transform, nor an approximation to the DFT. An FFT is just a faster method of computing the DFT of a signal by exploiting redundancy in DFT equations. In fact, it was FFT that made the Fourier analysis possible for majority of signal processing applications. For example, if FFT of a signal with length N=10^6 takes 1 second on a computing device, the DFT on the same platform will take approximately 28 hours!

It is then no surprise that FFT is described as "the most important numerical algorithm of our lifetime". In this text, we will not derive the exact FFT formulation and instead will use a software routine to compute the FFT when required. In Matlab, for example, the command fft(\cdot) serves this purpose.

Leave a Comment

Your email address will not be published. Required fields are marked *