The Discrete Fourier Transform of Symmetric Sequences
Symmetric sequences arise often in digital signal processing. Examples include symmetric pulses, window functions, and the coefficients of most finite-impulse response (FIR) filters, not to mention the cosine function. Examining symmetric sequences can give us some insights into the Discrete Fourier Transform (DFT). An even-symmetric sequence is centered at n = 0 and xeven(n) = xeven(-n). The DFT of xeven(n) is real. Most often, signals we encounter start at n = 0, so they are not strictly speaking even-symmetric. We’ll look at the relationship between the DFT’s of such sequences and those of true even-symmetric sequences.
How the Cooley-Tukey FFT Algorithm Works | Part 4 - Twiddle Factors
The beauty of the FFT algorithm is that it does the same thing over and over again. It treats every stage of the calculation in exactly the same way. However, this. “one-size-fits-all” approach, although elegant and simple, causes a problem. It misaligns samples and introduces phase distortions during each stage of the algorithm. To overcome this, we need Twiddle Factors, little phase correction factors that push things back into their correct positions before continuing onto the next stage.
How the Cooley-Tukey FFT Algorithm Works | Part 3 - The Inner Butterfly
At the heart of the Cooley-Tukey FFT algorithm lies a butterfly, a simple yet powerful image that captures the recursive nature of how the FFT works. In this article we discover the butterfly’s role in transforming complex signals into their frequency components with efficiency and elegance. Starting with the 2-point DFT, we reveal how the FFT reuses repeated calculations to save time and resources. Using a divide-and-conquer approach, the algorithm breaks signals into smaller groups, processes them through interleaving butterfly diagrams, and reassembles the results step by step.
How the Cooley-Tukey FFT Algorithm Works | Part 2 - Divide & Conquer
The Fast Fourier Transform revolutionized the Discrete Fourier Transform by making it much more efficient. In part 1, we saw that if you run the DFT on a power-of-2 number of samples, the calculations of different groups of samples repeat themselves at different frequencies. By leveraging the repeating patterns of sine and cosine values, the algorithm enables us to calculate the full DFT more efficiently. However, the calculations of certain groups of samples repeat more often than others. In this article, we’re going to explore how the divide-and-conquer method prepares the ground for the next stage of the algorithm by grouping the samples into specially ordered pairs.
How the Cooley-Tukey FFT Algorithm Works | Part 1 - Repeating Calculations
The Fourier Transform is a powerful tool, used in many technologies, from audio processing to wireless communication. However, calculating the FT can be computationally expensive. The Cooley-Tukey Fast Fourier Transform (FFT) algorithm provides a significant speedup. It exploits the repetitive nature of calculations within the Discrete Fourier Transform (DFT), the mathematical foundation of the FT. By recognizing patterns in the DFT calculations and reusing intermediate results, the FFT vastly reduces the number of operations required. In this series of articles, we will look at how the Cooley-Tukey FFT algorithm works.
Learn to Use the Discrete Fourier Transform
Discrete-time sequences arise in many ways: a sequence could be a signal captured by an analog-to-digital converter; a series of measurements; a signal generated by a digital modulator; or simply the coefficients of a digital filter. We may wish to know the frequency spectrum of any of these sequences. The most-used tool to accomplish this is the Discrete Fourier Transform (DFT), which computes the discrete frequency spectrum of a discrete-time sequence. The DFT is easily calculated using software, but applying it successfully can be challenging. This article provides Matlab examples of some techniques you can use to obtain useful DFT’s.
Model a Sigma-Delta DAC Plus RC Filter
Sigma-delta digital-to-analog converters (SD DAC’s) are often used for discrete-time signals with sample rate much higher than their bandwidth. For the simplest case, the DAC output is a single bit, so the only interface hardware required is a standard digital output buffer. Because of the high sample rate relative to signal bandwidth, a very simple DAC reconstruction filter suffices, often just a one-pole RC lowpass. In this article, I present a simple Matlab function that models the combination of a basic SD DAC and one-pole RC filter. This model allows easy evaluation of the overall performance for a given input signal and choice of sample rate, R, and C.
DAC Zero-Order Hold Models
This article provides two simple time-domain models of a DAC’s zero-order hold. These models will allow us to find time and frequency domain approximations of DAC outputs, and simulate analog filtering of those outputs. Developing the models is also a good way to learn about the DAC ZOH function.
Decimators Using Cascaded Multiplierless Half-band Filters
In my last post, I provided coefficients for several multiplierless half-band FIR filters. In the comment section, Rick Lyons mentioned that such filters would be useful in a multi-stage decimator. For such an application, any subsequent multipliers save on resources, since they operate at a fraction of the maximum sample frequency. We’ll examine the frequency response and aliasing of a multiplierless decimate-by-8 cascade in this article, and we’ll also discuss an interpolator cascade using the same half-band filters.
Pentagon Construction Using Complex Numbers
A method for constructing a pentagon using a straight edge and a ruler is deduced from the complex values of the Fifth Roots of Unity. Analytic values for the points are also derived.
A Beginner's Guide To Cascaded Integrator-Comb (CIC) Filters
This article discusses the behavior, mathematics, and implementation of cascaded integrator-comb filters.
Minimum Shift Keying (MSK) - A Tutorial
Minimum Shift Keying (MSK) is one of the most spectrally efficient modulation schemes available. Due to its constant envelope, it is resilient to non-linear distortion and was therefore chosen as the modulation technique for the GSM cell phone...
Understanding and Relating Eb/No, SNR, and other Power Efficiency Metrics
Introduction Evaluating the performance of communication systems, and wireless systems in particular, usually involves quantifying some performance metric as a function of Signal-to-Noise-Ratio (SNR) or some similar measurement. Many systems...
A Fixed-Point Introduction by Example
Introduction The finite-word representation of fractional numbers is known as fixed-point. Fixed-point is an interpretation of a 2's compliment number usually signed but not limited to sign representation. It...
An Efficient Linear Interpolation Scheme
This article presents a computationally-efficient linear interpolation trick that requires at most one multiply per output sample.
How the Cooley-Tukey FFT Algorithm Works | Part 1 - Repeating Calculations
The Fourier Transform is a powerful tool, used in many technologies, from audio processing to wireless communication. However, calculating the FT can be computationally expensive. The Cooley-Tukey Fast Fourier Transform (FFT) algorithm provides a significant speedup. It exploits the repetitive nature of calculations within the Discrete Fourier Transform (DFT), the mathematical foundation of the FT. By recognizing patterns in the DFT calculations and reusing intermediate results, the FFT vastly reduces the number of operations required. In this series of articles, we will look at how the Cooley-Tukey FFT algorithm works.
FFT Interpolation Based on FFT Samples: A Detective Story With a Surprise Ending
This blog presents several interesting things I recently learned regarding the estimation of a spectral value located at a frequency lying between previously computed FFT spectral samples. My curiosity about this FFT interpolation process was triggered by reading a spectrum analysis paper written by three astronomers.
A Fast Real-Time Trapezoidal Rule Integrator
This article presents a computationally-efficient network for computing real?time discrete integration using the Trapezoidal Rule.
Handling Spectral Inversion in Baseband Processing
The problem of "spectral inversion" comes up fairly frequently in the context of signal processing for communication systems. In short, "spectral inversion" is the reversal of the orientation of the signal bandwidth with...
Second Order Discrete-Time System Demonstration
Discrete-time systems are remarkable: the time response can be computed from mere difference equations, and the coefficients ai, bi of these equations are also the coefficients of H(z). Here, I try to illustrate this remarkableness by converting a continuous-time second-order system to an approximately equivalent discrete-time system. With a discrete-time model, we can then easily compute the time response to any input. But note that the goal here is as much to understand the discrete-time model as it is to find the response.
