Computing an FFT of Complex-Valued Data Using a Real-Only FFT Algorithm
Someone recently asked me if I knew of a way to compute a fast Fourier transform (FFT) of complex-valued input samples using an FFT algorithm that accepts only real-valued input data. Knowing of no way to do this, I rifled through my library of hardcopy FFT articles looking for help. I found nothing useful that could be applied to this problem.
After some thinking, I believe I have a solution to this problem. Here is my idea:
Let's say our original input data is the complex-valued sequence...
Unit Testing for Embedded Algorithms
Happy Holidays! For my premier article, I am writing about my favorite technique to use when designing and developing software- unit testing. Unit testing is a best practice when designing software. It allows the designer to verify the behavior of the software units before the entire system is complete, and it facilitates the change and growth of the software system because the developer can verify that the changes will not affect the behavior of other parts of the system. I have used...
Using Mason's Rule to Analyze DSP Networks
There have been times when I wanted to determine the z-domain transfer function of some discrete network, but my algebra skills failed me. Some time ago I learned Mason's Rule, which helped me solve my problems. If you're willing to learn the steps in using Mason's Rule, it has the power of George Foreman's right hand in solving network analysis problems.
This blog discusses a valuable analysis method (well known to our analog control system engineering brethren) to obtain the z-domain...
The Nature of Circles
What do you mean?When calculating the mean of a list of numbers, the obvious approach is to sum them and divide by how many there are.
Suppose I give you a list of two numbers:
- 0
- 359
What is their mean? The obvious answer is 179.5.
If I told you that the numbers were compass bearings in degrees, what would your answer be then? Does 179.5 seem correct?
In the case of compass bearings, 0 is the same direction as 360. When talking about angles in the DSP world, we often talk about...
Simultaneously Computing a Forward FFT and an Inverse FFT Using a Single FFT
Most of us are familiar with the processes of using a single N-point complex FFT to: (1) perform a 2N-point FFT on real data, and (2) perform two independent N-point FFTs on real data [1–5]. In case it's of interest to someone out there, this blog gives the algorithm for simultaneously computing a forward FFT and an inverse FFT using a single radix-2 FFT.
Our algorithm is depicted by the seven steps, S1 through S7, shown in Figure 1. In that figure, we compute the x(n) inverse FFT of...
Multiplierless Exponential Averaging
This blog discusses an interesting approach to exponential averaging. To begin my story, a traditional exponential averager (also called a "leaky integrator"), shown in Figure 1(a), is commonly used to reduce noise fluctuations that contaminate relatively constant-amplitude signal measurements.
Figure 1 Exponential averaging: (a) standard network; (b) single-multiply network.That exponential averager's difference equation is
y(n) = αx(n) + (1 –...Computing the Group Delay of a Filter
I just learned a new method (new to me at least) for computing the group delay of digital filters. In the event this process turns out to be interesting to my readers, this blog describes the method. Let's start with a bit of algebra so that you'll know I'm not making all of this up.
Assume we have the N-sample h(n) impulse response of a digital filter, with n being our time-domain index, and that we represent the filter's discrete-time Fourier transform (DTFT), H(ω), in polar form...
Computing Large DFTs Using Small FFTs
It is possible to compute N-point discrete Fourier transforms (DFTs) using radix-2 fast Fourier transforms (FFTs) whose sizes are less than N. For example, let's say the largest size FFT software routine you have available is a 1024-point FFT. With the following trick you can combine the results of multiple 1024-point FFTs to compute DFTs whose sizes are greater than 1024.
The simplest form of this idea is computing an N-point DFT using two N/2-point FFT operations. Here's how the trick...
Linear-phase DC Removal Filter
This blog describes several DC removal networks that might be of interest to the dsprelated.com readers.
Back in August 2007 there was a thread on the comp.dsp newsgroup concerning the process of removing the DC (zero Hz) component from a time-domain sequence [1]. Discussed in that thread was the notion of removing a signal's DC bias by subtracting the signal's moving average from that signal, as shown in Figure 1(a).
Figure 1.
At first I thought...
Correlation without pre-whitening is often misleading
White LiesCorrelation, as one of the first tools DSP users add to their tool box, can automate locating a known signal within a second (usually larger) signal. The expected result of a correlation is a nice sharp peak at the location of the known signal and few, if any, extraneous peaks.
A little thought will show this to be incorrect: correlating a signal with itself is only guaranteed to give a sharp peak if the signal's samples are uncorrelated --- for example if the signal is composed...
Digging into an Audio Signal and the DSP Process Pipeline
In this post, I'll look at the benefits of using multiple perspectives when handling signals.A Pre-existing Audio FileLet's say we have an audio file of interest. Let's load it into Audacity and zoom in a little (using View → Zoom → Zoom In, multiple times). The figure illustrates the audio signal: just a basic single-tone signal.
By continuing to zoom into the signal, we eventually get to the point of seeing individual samples as illustrated below. Notice that I've marked one...
Exact Near Instantaneous Frequency Formulas Best at Peaks (Part 1)
IntroductionThis is an article that is a another digression from trying to give a better understanding of the Discrete Fourier Transform (DFT). Although it is not as far off as the last blog article.
A new family of formulas for calculating the frequency of a single pure tone in a short interval in the time domain is presented. They are a generalization of Equation (1) from Rick Lyons' recent blog article titled "Sinusoidal Frequency Estimation Based on Time-Domain Samples"[1]. ...
Computing Chebyshev Window Sequences
Chebyshev windows (also called Dolph-Chebyshev, or Tchebyschev windows), have several useful properties. Those windows, unlike the fixed Hanning, Hamming, or Blackman window functions, have adjustable sidelobe levels. For a given user-defined sidelobe level and window sequence length, Chebyshev windows yield the most narrow mainlobe compared to any fixed window functions.
However, for some reason, detailed descriptions of how to compute Chebyshev window sequences are not readily available...
A Remarkable Bit of DFT Trivia
I recently noticed a rather peculiar example of discrete Fourier transform (DFT) trivia; an unexpected coincidence regarding the scalloping loss of the DFT. Here's the story.
DFT SCALLOPING LOSS As you know, if we perform an N-point DFT on N real-valued time-domain samples of a discrete sine wave, whose frequency is an integer multiple of fs/N (fs is the sample rate in Hz), the peak magnitude of the sine wave's positive-frequency spectral component will be
where A is the peak amplitude...
Exploring Human Hearing Range
Human Hearing RangeIn this post, I'll look at an interesting aspect of Audacity – using it to explore the threshold of human hearing. In my book Digital Signal Processing: A Gentle Introduction with Audio Examples, I go into this topic and I include a side note on the amazing hearing range of our canine companions.
Creating a Test Audio FileAudacity allows for the generation of a variety of test signals. If you click the Generate->Tone menu, it looks something like...
Multimedia Processing with FFMPEG
FFMPEG is a set of libraries and a command line tool for encoding and decoding audio and video in many different formats. It is a free software project for manipulating/processing multimedia data. Many open source media players are based on FFMPEG libraries.
Multiplying Two Binary Numbers
I just encountered what I think is an interesting technique for multiplying two integer numbers. Perhaps some of the readers here will also find it interesting.
Here's the technique: assume we want to multiply 18 times 17. We start by writing 18 and 17, side-by-side in column A and column B, as shown at the top of Figure 1. Next we divide the 18 at the top of column A by two, retaining only the integer part of the division, and double the 17 at the top of column B. The results of those two...
Implementing a full-duplex UART using the TMS320VC33 serial port
Although the TMS320VC33 serial port was designed to be used as a synchronous port, it can also be used as an asynchronous port under software control. This post describes the hardware and software needed to use a TMS320VC33 serial port as a full-duplex UART port. A schematic diagram and a lengthy code listing are provided to illustrate the solution. This note discusses the implementation of an interrupt-driven, full-duplex, asynchronous serial interface, 9600-baud UART with 8 data bits, 1...
Simultaneously Computing a Forward FFT and an Inverse FFT Using a Single FFT
Most of us are familiar with the processes of using a single N-point complex FFT to: (1) perform a 2N-point FFT on real data, and (2) perform two independent N-point FFTs on real data [1–5]. In case it's of interest to someone out there, this blog gives the algorithm for simultaneously computing a forward FFT and an inverse FFT using a single radix-2 FFT.
Our algorithm is depicted by the seven steps, S1 through S7, shown in Figure 1. In that figure, we compute the x(n) inverse FFT of...
Instant CIC
Summary:
A floating point model for a CIC decimator, including the frequency response.
Description:
A CIC filter relies on a peculiarity of its fixed-point implementation: Normal operation involves repeated internal overflows that have no effect to the output signal, as they cancel in the following stage.
One way to put it intuitively is that only the speed (and rate of change) of every little "wheel" in the clockworks carries information, but its absolute position is...
Instant CIC
Summary:
A floating point model for a CIC decimator, including the frequency response.
Description:
A CIC filter relies on a peculiarity of its fixed-point implementation: Normal operation involves repeated internal overflows that have no effect to the output signal, as they cancel in the following stage.
One way to put it intuitively is that only the speed (and rate of change) of every little "wheel" in the clockworks carries information, but its absolute position is...
Impulse Response Approximation
Recently, I stumbled upon a stepped-triangular (ST) approximation that can be implemented as a cascade of recursive running sum (RRS) filters. The following is a short introduction to the stepped-triangular approximation.The stepped-triangular approximation was introduced by Jovanovic-Dolecek and Mitra [1] as a quantized approximation of a low-pass filter (LPF). Figure 1 shows an example of the approximation.
[Figure 1: Stepped Approximation of a LPF...
Correlation without pre-whitening is often misleading
White LiesCorrelation, as one of the first tools DSP users add to their tool box, can automate locating a known signal within a second (usually larger) signal. The expected result of a correlation is a nice sharp peak at the location of the known signal and few, if any, extraneous peaks.
A little thought will show this to be incorrect: correlating a signal with itself is only guaranteed to give a sharp peak if the signal's samples are uncorrelated --- for example if the signal is composed...
Least-squares magic bullets? The Moore-Penrose Pseudoinverse
Hello,
the topic of this brief article is a tool that can be applied to a variety of problems: The Moore-Penrose Pseudoinverse.While maybe not exactly a magic bullet, it gives us least-squares optimal solutions, and that is under many circumstances the best we can reasonably expect.
I'll demonstrate its use on a short example. More details can be found for example on Wikipedia, or the Matlab documentation...
Simultaneously Computing a Forward FFT and an Inverse FFT Using a Single FFT
Most of us are familiar with the processes of using a single N-point complex FFT to: (1) perform a 2N-point FFT on real data, and (2) perform two independent N-point FFTs on real data [1–5]. In case it's of interest to someone out there, this blog gives the algorithm for simultaneously computing a forward FFT and an inverse FFT using a single radix-2 FFT.
Our algorithm is depicted by the seven steps, S1 through S7, shown in Figure 1. In that figure, we compute the x(n) inverse FFT of...
There's No End to It -- Matlab Code Plots Frequency Response above the Unit Circle
Reference [1] has some 3D plots of frequency response magnitude above the unit circle in the Z-plane. I liked them enough that I wrote a Matlab function to plot the response of any digital filter this way. I’m not sure how useful these plots are, but they’re fun to look at. The Matlab code is listed in the Appendix.This post is available in PDF format for easy...
A Complex Variable Detective Story – A Disconnect Between Theory and Implementation
Recently I was in the middle of a pencil-and-paper analysis of a digital 5-tap FIR filter having complex-valued coefficients and I encountered a surprising and thought-provoking problem. So that you can avoid the algebra difficulty I encountered, please read on.
A Surprising Algebra Puzzle
I wanted to derive the H(ω) equation for the frequency response of my FIR digital filter whose complex coefficients were h0, h1, h2, h3, and h4. I could then test the validity of my H(ω)...
Exploring Human Hearing Range
Human Hearing RangeIn this post, I'll look at an interesting aspect of Audacity – using it to explore the threshold of human hearing. In my book Digital Signal Processing: A Gentle Introduction with Audio Examples, I go into this topic and I include a side note on the amazing hearing range of our canine companions.
Creating a Test Audio FileAudacity allows for the generation of a variety of test signals. If you click the Generate->Tone menu, it looks something like...
Implementing a full-duplex UART using the TMS320VC33 serial port
Although the TMS320VC33 serial port was designed to be used as a synchronous port, it can also be used as an asynchronous port under software control. This post describes the hardware and software needed to use a TMS320VC33 serial port as a full-duplex UART port. A schematic diagram and a lengthy code listing are provided to illustrate the solution. This note discusses the implementation of an interrupt-driven, full-duplex, asynchronous serial interface, 9600-baud UART with 8 data bits, 1...
Exact Near Instantaneous Frequency Formulas Best at Peaks (Part 1)
IntroductionThis is an article that is a another digression from trying to give a better understanding of the Discrete Fourier Transform (DFT). Although it is not as far off as the last blog article.
A new family of formulas for calculating the frequency of a single pure tone in a short interval in the time domain is presented. They are a generalization of Equation (1) from Rick Lyons' recent blog article titled "Sinusoidal Frequency Estimation Based on Time-Domain Samples"[1]. ...