Spectral analysis and modulation, part 1: The DFT and FFT

Part 2 covers the basics of power spectrum analysis.

Background
In many cases when analyzing signals or trying to find features of signals, transformation to the frequency plane is advantageous, i.e. dealing with, for instance, kilohertz and megahertz rather than milliseconds and microseconds. In this chapter, some common methods for spectral analysis of temporal signals will be presented.

Another topic addressed in this chapter is modulation. Quite often in analog and digital telecommunication systems, the information signals cannot be transmitted as is. They have to be encoded (modulated) onto a carrier signal, suited for the transmission media in question. Some common modulation methods are demonstrated.

Objectives
In this chapter we will discuss:

• Discrete Fourier transform (DFT) and fast Fourier transform (FFT)
• Windowing techniques, spectrum estimation and periodogram averaging
• Auto-correlation, cross-correlation, auto-covariance and cross-covariance
• Parametric spectrum analysis, auto-regressive (AR), moving average (MA) and auto-regressive moving average (ARMA) models
• Wavelet analysis
• Amplitude shift keying (ASK), frequency shift keying (FSK) and phase shift keying (PSK)
• Phasors, complex modulation and in phase/quadrature phase (I/Q)modulators
• The Hilbert transform.

5.1 Discrete Fourier transform and fast Fourier transform
The discrete Fourier transform (DFT) (Burrus and Parks, 1985) from the time domain to the frequency domain representation, is derived from the time DFT

The spectrum produced using this transform is periodic with the sampling frequency ω_s and for real input signals x(n), the spectrum always has "even" symmetry along the real axis and "odd" symmetry on the imaginary axis. In practice, we cannot calculate this sum, since it contains an infinite number of samples. This problem is only solved by taking a section of N samples of the sequence x(n). To achieve this, x(n) is multiplied by a windowing sequence Ψ(n) obtaining the windowed input signal x_N(n). Since multiplication in the time domain corresponds to convolution in the frequency domain, the time DFT of the windowed sequence will be

where Ψ(ω) is the spectrum of the windowing sequence Ψ(n) and ∗ denotes convolution. The ideal windowing sequence would have a rectangular spectrum, distorting the desired spectrum as little as possible and avoiding spectral "leakage". Unfortunately, a rectangular frequency response is practically impossible to achieve, therefore we must settle for some compromise. For example, commonly used windowing sequences are Rectangular, Bartlett, Hanning, Hamming and Kaiser–Bessel windows (Oppenheimer and Schafer, 1975).

Now, let us assume we have chosen an appropriate windowing sequence. Next we must determine how many frequency points should be used for calculation of the transform in order to maintain a reasonable accuracy. There is no simple answer, but in most cases good results are obtained using as many equally spaced frequency points as the number of samples in the windowed input signal, i.e. N. Hence the spacing between the frequency points will be ω_s/N.Now, inserting this into equation (5.1), the DFT in its most common form can be derived

where the twiddle factor is

Unfortunately, the number of complex computations needed to perform the DFT is proportional to N². The acronym FFT (fast Fourier transform), refers to a group of algorithms, all very similar, which uses fewer computational steps to efficiently compute the DFT.The number of steps are typically proportional to N lb(N), where lb(x) = log₂(x) is the logarithm base 2. Reducing the number of computational steps is of course important if the transform has to be computed in a real-time system. Fewer steps implies faster processing time, hence higher sampling rates are possible. Now, there are essentially two tricks employed to obtain this "sped-up version" of DFT:

1. When calculating the sum (equation (5.3)) for k = 0, 1, 2, …, N , many complex multiplications are repeated. By doing the calculations in a "smarter" order, many calculated complex products can be stored and reused.

2. Further, the twiddle factor (5.4) is periodic, and only N factors need to be computed. This can, of course, be done in advance and the values can be stored in a table.