Everyday DSP for Programmers: DC and Impulsive Noise Removal

For the last installment of Everyday DSP for Programmers, we'll take a look at how to remove unwanted cruft from a signal. Real-world signals can come with all kinds of unwanted noise and biases. A DC bias can wreak havoc on many DSP algorithms because the bias accumulates in the algorithm and saturates the output. The bias doesn't even have to be pure DC to cause problems. The low frequency hum of power lines is pervasive, and most electronic signals ride on top of a 60 Hz sine wave in the US and 50 Hz in Europe. Other data sources can have their own biases that need to be removed.

Another insidious type of noise is impulsive noise. Sometimes called spikes, sparkles, fliers, or outliers, these high-intensity deviations from normal input values can be hard to remove from a signal without affecting the values around them. Averaging tends to spread them out when they should be simply removed from the input signal altogether.

We'll explore how to remove both of these undesirable signal components, starting with DC removal.

Everyday DSP for Programmers: Frequency Detection

Up until now we've seen two ways to detect the frequency of a signal. If the signal has a dominant frequency, we can measure that frequency by counting zero crossings, and if there's more frequency content, we can use a DFT to measure the full frequency spectrum of the signal. If we're looking for frequency peaks, we can use spectral peak detection to calculate exact frequency values from the quantized frequency bins of the DFT.

Now we'll explore another way to detect a specific frequency in a signal using a type of filter called an Infinite Impulse Response (IIR) filter. There is a huge variety of IIR filters—the exponential average is an example of one that we've already seen—and in this case, the type of filter we'll use for detecting frequencies is called a complex resonator. We can use the DFT to help analyze the frequency response of the complex resonator, but first let's see why we would want to use it.

Everyday DSP for Programmers: FIR Filters

Now that we have this shiny new tool called the DFT, it's time to look more closely at Finite Impulse Response (FIR) filters. We can use the DFT to create and analyze FIR filters so that we can better understand how they behave with different signals.

To review, an FIR filter is named as such because when it is applied to an impulse function, the response is complete (i.e. it has reached and will remain at zero) within a finite number of samples. An FIR filter consists of an array of values, called taps, and to apply the filter to a signal, the taps are overlapped with a block of samples with each sample multiplied by a tap. Then, the results are added together to get a single filtered sample. The filter is advanced by one sample and the process is repeated for the next filtered sample. This process is called convolution, as we covered way back in the post on averaging.

We would use a filter when we want to remove some part of the signal before analyzing what's left. Normally we want to remove high-frequency noise, and a filter that does this is called a low-pass filter because it only allows low frequencies to get through it. We can also design high-pass filters that remove low-frequency bias from a signal or band-pass filters that only allow certain frequency ranges of interest through. All of these types of filters have similar design processes, so we'll focus on the low-pass filter. Let's try to design a perfect low-pass FIR filter.

Everyday DSP for Programmers: Spectral Peak Detection

For the last couple of weeks we've been looking at how the DFT works and some example DFTs. Throughout those posts we've been using signals with frequencies that fit nicely into the frequency bins of the DFT. Now we're going to see what happens when the signal frequency isn't so clean and how to deal with it. We want a simple algorithm for detecting the main frequency values of the signal without paying too high of a price in computation. This type of algorithm is called spectral peak detection. Let's get started.

Everyday DSP for Programmers: The DFT in Use

Last week we built up the DFT (Discrete Fourier Transform) from fundamentals, and while that exercise provides a good way to remember how to calculate the DFT and how the DFT works under the hood, looking at some examples is a good way to get a sense of how the DFT behaves with different types of signals. We'll take a look at the frequency response of a few basic signals by calculating their DFTs, but first, we'll briefly explore a way to calculate the DFT much faster than we did with the direct algorithm from the last post. This optimized DFT is called the FFT (Fast Fourier Transform), and if you can conform your problem to its restrictions, it's the transform that you want to use because, well, it's fast.

Everyday DSP for Programmers: The Discrete Fourier Transform

Last week we covered how to measure the frequency of a periodic signal with a single dominant frequency. This week we'll cover a way to measure the full frequency spectrum of a signal that can have any number of frequencies in it, up to the Nyquist frequency, of course. This tool is called the Discrete Fourier Transform (DFT), and we can derive it from the basic concepts of sine waves, signal transforms, and averaging.

The DFT may seem like a complicated, confusing thing at first, but fundamentally, it's actually fairly straightforward, if a bit tedious to calculate by hand. We'll explore the DFT by building it from the ground up using a signal with some known frequencies in it as a starting point. That way, we'll have a way to check that the results we're getting are reasonable. As for the tedious parts, we can write code to take care of that.

Everyday DSP for Programmers: Frequency Measurement

In DSP, when you're not calculating averages, you're calculating frequencies. Much of DSP involves frequency analysis, and for that task we have the Fourier Transform, a calculation that translates a signal from the time domain to the frequency domain. We don't always have the resources or the need to resort to that heavy handed operation, though. Sometimes the signal we're dealing with is made up of a single frequency that varies over time, and the value of that frequency is what's of the most interest. That is what we'll be exploring today.

Everyday DSP for Programmers: Signal Envelopes

Sometimes we don't care so much about the exact details of a signal as we do about whether a signal is even present or not. If the signal is periodic, it can be difficult to directly detect when the signal is there and when it goes away because when it is present, it's oscillating between various values. In cases like these, what we want to calculate is the envelope of the signal, which gives us the information about whether the signal is there or not and what its approximate amplitude is. As an added bonus, calculating a signal envelope can be done in real-time, so other DSP functions can be done on the signal as soon as it's detected.

Everyday DSP for Programmers: Edge Detection

Up until now we've been learning about the fundamental concepts and basic tools of digital signal processing (DSP). Now we're going to use those tools to solve a common problem in DSP: edge detection. When you think of edge detection, you probably immediately think of image processing and finding edges in photographs or a video signal. It's true that there are plenty of edge detection applications in image processing, especially with some of the new technologies being developed for self-driving cars, facial recognition, and automatic photo processing, but edge detection is useful in a much wider range of applications than that.

Anywhere you need to monitor a signal for a change of state is a likely candidate for edge detection. That would include the feedback systems in robotic motion, industrial automation, touch screens and other touch inputs, pressure sensors in car airbag safety systems, accelerometers in any toy or gadget that senses motion, and the list goes on. Sometimes, the relevant signal in these systems varies within a well-defined range, and the edge is easy to detect by setting a fixed threshold. If the signal crosses the threshold, the system detects an edge and does what it needs to do.

Other times edge detection is not so simple. If the signal drifts around over long periods of time, or the threshold for the occurrence of an edge doesn't necessarily happen at the same value every time, it's difficult or impossible to set a fixed threshold for detecting an edge. In cases like this, we need to do some further processing to build up a signal that we can assign a fixed threshold to for detecting edges. That's the kind of problem we'll attempt to solve here, detecting edges in a signal where the edges tend to happen anywhere within its range. Let's start by generating a representative signal that would be somewhat difficult to process.

Everyday DSP for Programmers: Signal Variance

After covering averaging in the last two posts, the natural next thing to look at is how much the signal varies around the average. This property of a signal is called signal variance, and there are a couple different ways to calculate it, depending on how the average has been calculated. Let's see how variance can be calculated and what it tells us about a signal.

Everyday DSP for Programmers: Step Response of Averaging

Last week we took a look at different kinds of averaging, and used them to analyze historical gas prices. Looking at a complex signal like gas prices gives us a nice comparison of the behaviors of the various averaging methods, but that only gives us an idea of what averaging does for one specific signal. What if we want to understand what the different averaging methods do in a more general way?

One way to analyze the different methods is by applying them to the fundamental signals. The output that results from applying an averaging function to one of the fundamental signals is called the response of the function. If the signal is the DC signal, it's called the DC response. If the signal is the step function, it's called the step response, and so on. We'll look at the step response in more detail, but first, let's briefly discuss the responses of the different averaging functions to each of the fundamental signals.

Everyday DSP for Programmers: Averaging

After finishing up the introductory concepts of DSP last week, we've now moved firmly into the digital, sampled domain, and we're going to start taking a look at the programming algorithms that are commonly used in DSP. Fundamentally, digital signal processing has a lot in common with statistics. When we start analyzing signals, some of the first tools we look at using are based in statistical analysis: maximum and minimum values, averages, and variances.

Maximums and minimums mostly come into play when bounding and normalizing signals. If you want to find the amplitude of a signal, then you'll scan through the samples to find the extreme values. It's fairly straightforward, and there's no need to delve into them until they're needed.

Averages are another story, though. Not all averages are created equal, and different types of averages are more useful in different situations. We'll take a look at five types of averages in this post, including the full, block, moving, exponential, and filter averages. To ground the discussion a bit, let's apply these different averages to a real-world dataset. Gas prices are something that most people watch pretty closely, and it happens to be a series with some interesting characteristics, so let's go with that. I'll use the weekly U.S. regular reformulated retail gasoline prices from the last twenty years, made available online through the EIA.gov website.

Everyday DSP for Programmers: Sampling Theory

It's time to tackle sampling theory. The last couple posts dealt with concepts that are equally applicable to the analog and digital worlds of signal processing, but once a signal has been sampled, we have landed squarely in digital signal processing because the signal has been digitized. Sampling theory sounds like a big, scary thing that takes months of study to comprehend and makes your brain melt. It isn't. Sure, it can get complicated if you dig down deep enough, but we're going to steer clear of those dark trenches and focus on the high-level concepts that will build up your intuition for the issues surrounding digital signals.

Everyday DSP for Programmers: Transforms

Programmers work with signals all the time. We may not normally think of the data we're working with as signals, but treating it that way and learning some basic ways of processing those signals can come in quite handy. Last week I went over the basic signal types that are commonly used in digital signal processing. Today, I'll cover the basic ways we can change a signal using a set of transforms.

These transforms can be used in a variety of ways to accomplish different goals when processing signals, and we'll look at a few use cases as we go through the transforms. We'll need an example signal to apply these transforms to, and I can think of no better signal to use than the workhorse of DSP—the sine wave. The basic equation for a sine wave is

f(t) = sin(t)

Where t is the variable of time, marching forever forward. This basic equation will get embellished with other parameters as we explore the different transforms. We'll start off with the simplest of the transforms.

Everyday DSP for Programmers: Basic Signals

Digital Signal Processing (DSP) is a field that can be incredibly useful to almost any programmer.  When you think about DSP, you probably think of complex computational tasks for audio filtering, image processing, or video editing, but DSP is much more general than that.

The name 'DSP' aptly describes what it is. It has to do with the digital domain, which is directly applicable to any kind of programming. It deals with signals, which includes much more than the normal audio and video signals we normally think about as signals. Any series of data points that changes over time is a signal. That means a stock's price history is a signal, your kid's height over time is a signal, and the number of users on a website is a signal. Signals are all around us, and we deal with them every day. Finally, DSP involves processing those signals in some way to either transform the signal into something more useful for a given purpose or extract desirable information from the signal. Encoding that processing in a fast, automated program is a natural fit for what a programmer does.