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...
How Not to Reduce DFT Leakage
This blog describes a technique to reduce the effects of spectral leakage when using the discrete Fourier transform (DFT).
In late April 2012 there was a thread on the comp.dsp newsgroup discussing ways to reduce the spectral leakage problem encountered when using the DFT. One post in that thread caught my eye [1]. That post referred to a website presenting a paper describing a DFT leakage method that I'd never heard of before [2]. (Of course, not that I've heard...
Exact Near Instantaneous Frequency Formulas Best at Peaks (Part 2)
Introduction
This is an article that is a continuation of a digression from trying to give a better understanding of the Discrete Fourier Transform (DFT). It is recommended that my previous article "Exact Near Instantaneous Frequency Formulas Best at Peaks (Part 1)"[1] be read first as many sections of this article are directly dependent upon it.
A second family of formulas for calculating the frequency of a single pure tone in a short interval in the time domain is presented. It...
Harmonic Notch Filter
My basement is covered with power lines and florescent lights which makes collecting ECG and EEG data rather difficult due to the 60 cycle hum. I found the following notch filter to work very well at eliminating the background signal without effecting the highly amplified signals I was looking for.
The notch filter is based on the a transfer function with the form $$H(z)=\frac{1}{2}(1+A(z))$$ where A(z) is an all pass filter. The original paper [1] describes a method to...
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...
"Neat" Rectangular to Polar Conversion Algorithm
The subject of finding algorithms that estimate the magnitude of a complex number, without having to perform one of those pesky square root operations, has been discussed many times in the past on the comp.dsp newsgroup. That is, given the complex number R + jI in rectangular notation, we want to estimate the magnitude of that number represented by M as:
On August 25th, 2009, Jerry (Mr. Wizard) Avins posted an interesting message on this subject to the comp.dsp newsgroup (Subject: "Re:
Exact Near Instantaneous Frequency Formulas Best at Zero Crossings
IntroductionThis is an article that is the last of my digression from trying to give a better understanding of the Discrete Fourier Transform (DFT). It is along the lines of the last two.
In those articles, I presented exact formulas for calculating the frequency of a pure tone signal as instantaneously as possible in the time domain. Although the formulas work for both real and complex signals (something that does not happen with frequency domain formulas), for real signals they...
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 brief look at multipath radio channels
Summary: Discussion of multipath propagation and fading in radio links
Radio channels, their effects on communications links and how to model them are a popular topic on comp.dsp. Unfortunately, for many of us there is little or no opportunity to get any "hands-on" experience with radio-related issues, because the required RF measurement equipment is not that easily available.This article gives a very simple example of a radio link that shows multipath propagation and...
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 File
Let'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...
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.
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]. ...
