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.
First, let's consider the full average. Since the full average simply calculates the average over the entire signal, its signal response is not terribly interesting. It's a single value. The block average isn't much more interesting since it merely splits up the signal into equally sized pieces before taking the average. The result will be a decimated version of the original signal. We'll ignore these two types of averaging for this exploration.
We can also throw out the DC signal from the signal side of the matrix since no type of averaging will change a DC value. (At least it shouldn't. If it does, you should make sure your averaging function is stable and does what you think it does.) The DC response is more interesting when analyzing complex Infinite Impulse Response (IIR) filters because those can potentially be unstable with a DC signal, but none of these averaging functions are unstable.
That leaves the impulse, step, and sine signals and the moving, exponential, and FIR filter averages as potential candidates for comparison. The sine signal's response is going to depend on the frequency of the sine wave, and that type of analysis is normally done with a DFT to find the average's frequency response over a range of frequencies. We're not ready for that kind of analysis, yet, so we'll look at that in a later post.
The impulse response of an average actually has an interesting behavior. Running an impulse through an averaging function will reproduce the averaging function as a series of taps for an FIR filter. Because the impulse function is zero everywhere except for a single sample, when you apply an averaging function to it, the result at each point is the value you would need to use for that tap in the equivalent filter.
The impulse function applied to a moving average will result in a block of samples with each sample having a value of the inverse of the block size. If you then used these values as taps in a filter, multiplying each sample of a signal by the inverse of the block size and summing them together, you would get the same result as the moving average. That's because the following equations are equivalent:
(∑i=1..k s[i])/n = ∑i=1..k s[i]·(1/n)
The 1/n terms in the summation on the right hand side are the taps of a filter. Because of this property, the FIR filter will simply reproduce its taps in response to the impulse function. The exponential average will produce an exponential decay, and it never ends because the exponential decay approaches zero but never reaches it. Therefore, the exponential average is an example of a simple IIR filter.
mean[j] = ∑i=j..(j+k) s[i]/k
Where j is the jth sample and k is the block size. This operation looks like the following graph:
Click the graph to run the moving average. The block size was expanded to show the response better. Notice how the response is a line connecting the lower level at the point where the step occurs to the higher level at the point where the number of samples equivalent to the block size has been covered. At each step of the moving average another higher-valued sample is added to the average, so the averaged signal proceeds in a linear path from the old value to the new value with a delay equal to the block size.
This step response shows how the moving average removes high frequency content from the signal. The original step function has infinite frequency content at the step. The response still has some higher frequency content at the two corners, but it's less than before and the linear region has very low frequency content. We can also see the beginnings of a triangle wave in this response. If the step function was actually a square wave with a period twice as long as the block size of the moving average, the moving average would produce a perfect triangle wave. Maybe not the most efficient way to generate one, but it's useful insight into the behavior of the moving average.
mean[i] = w·s[i] + (1-w)·mean[i-1]
Where w is the weighting of the current sample and is a value between 0 and 1. For a weighting close to 0, the step response looks like this:
This graph clearly shows why it's called an exponential average because the average approaches the new value of the step function along an exponential curve. We can also see that the exponential average reacts more quickly to new inputs because the response changes much more quickly near the initial step. Then it approaches the new value more slowly over time. That is why the exponential average retained more of the bumps and spikes in the gas price signal, and it removes somewhat less of the high frequency content than the moving average does. Weightings have to be very close to zero before the exponential average won't have a sharp response to new values, and then the average approaches new values extremely slowly.
Theoretically, the exponential average never reaches the new value, and thus has an infinite response, which is why it's an IIR filter. Practically, this exponential average has nearly reached the new value within 5 or 6 time units, as represented on the graph above. It will never truly reach the new value, but it will get arbitrarily close.
y[j] = ∑i=0..(k-1) s[j-i]·h[i]
Where y[j] is the result of the filter for the jth sample, k is the number of taps, and h[i] is the ith tap. The FIR filter we looked at used a sinc function for the taps, and that filter has the following step response:
Notice how the filter doesn't respond strongly right away, instead wiggling back and forth a few times before jumping up to and overshooting the new value when the step is halfway through the filter. It then wiggles around the new value a bit before settling into it. This behavior may look familiar. If we extended the step function into a square wave with the right period, the filter response would look like the Fourier Series approximation of a square wave that we explored when covering transforms. The filter will actually generate the same waveform as the Fourier Series, but with a delay that is half the number of taps in the filter.
The taps generated from the sinc function only permit certain frequencies in the response, so that is why it has this behavior with the step function. The number of wiggles and the steepness of the transition in the center of the filter will depend on the number of taps and the frequency used in the sinc function to generate the taps. A major part of filter design is controlling these parameters to produce the desired cut-off frequency for the filter.
With that, we've pretty much covered the step response of the different averaging functions we've used. Analyzing the step response of a new filter or other DSP operation is a good practice for understanding the behavior of the algorithm you're developing. It can give you new insight or confirm that your algorithm is doing what it's supposed to do. It's a good tool to keep in your DSP toolbox. Next week we'll wrap up the statistical techniques of DSP by looking at a few ways to calculate how much a signal is changing with signal variance.
Other DSP posts:
Basic Signals
Transforms
Sampling Theory
Averaging
Step Response of Averaging
Signal Variance
Edge Detection
Signal Envelopes
Frequency Measurement
The Discrete Fourier Transform
The DFT in Use
Spectral Peak Detection
FIR Filters
Frequency Detection
DC and Impulsive Noise Removal
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.
Responding to Signals
We covered five different ways of averaging in the last post (full, block, moving, exponential, and FIR filter) and four different types of fundamental signals from the first post (DC, impulse, step, and sine). If we were to do a cross comparison of all of these signals and averaging methods, we'd end up with twenty graphs, but most of them wouldn't be too useful or interesting, so we're going to narrow them down somewhat.First, let's consider the full average. Since the full average simply calculates the average over the entire signal, its signal response is not terribly interesting. It's a single value. The block average isn't much more interesting since it merely splits up the signal into equally sized pieces before taking the average. The result will be a decimated version of the original signal. We'll ignore these two types of averaging for this exploration.
We can also throw out the DC signal from the signal side of the matrix since no type of averaging will change a DC value. (At least it shouldn't. If it does, you should make sure your averaging function is stable and does what you think it does.) The DC response is more interesting when analyzing complex Infinite Impulse Response (IIR) filters because those can potentially be unstable with a DC signal, but none of these averaging functions are unstable.
That leaves the impulse, step, and sine signals and the moving, exponential, and FIR filter averages as potential candidates for comparison. The sine signal's response is going to depend on the frequency of the sine wave, and that type of analysis is normally done with a DFT to find the average's frequency response over a range of frequencies. We're not ready for that kind of analysis, yet, so we'll look at that in a later post.
The impulse response of an average actually has an interesting behavior. Running an impulse through an averaging function will reproduce the averaging function as a series of taps for an FIR filter. Because the impulse function is zero everywhere except for a single sample, when you apply an averaging function to it, the result at each point is the value you would need to use for that tap in the equivalent filter.
The impulse function applied to a moving average will result in a block of samples with each sample having a value of the inverse of the block size. If you then used these values as taps in a filter, multiplying each sample of a signal by the inverse of the block size and summing them together, you would get the same result as the moving average. That's because the following equations are equivalent:
(∑i=1..k s[i])/n = ∑i=1..k s[i]·(1/n)
The 1/n terms in the summation on the right hand side are the taps of a filter. Because of this property, the FIR filter will simply reproduce its taps in response to the impulse function. The exponential average will produce an exponential decay, and it never ends because the exponential decay approaches zero but never reaches it. Therefore, the exponential average is an example of a simple IIR filter.
Moving Average Step Response
That leaves the step response to look at in more detail. To find the step response of an average, all we have to do is replace the gas price signal that we were looking at before with a step function, and run the averaging function over it. For the moving average, recall that the operation ismean[j] = ∑i=j..(j+k) s[i]/k
Where j is the jth sample and k is the block size. This operation looks like the following graph:
Click the graph to run the moving average. The block size was expanded to show the response better. Notice how the response is a line connecting the lower level at the point where the step occurs to the higher level at the point where the number of samples equivalent to the block size has been covered. At each step of the moving average another higher-valued sample is added to the average, so the averaged signal proceeds in a linear path from the old value to the new value with a delay equal to the block size.
This step response shows how the moving average removes high frequency content from the signal. The original step function has infinite frequency content at the step. The response still has some higher frequency content at the two corners, but it's less than before and the linear region has very low frequency content. We can also see the beginnings of a triangle wave in this response. If the step function was actually a square wave with a period twice as long as the block size of the moving average, the moving average would produce a perfect triangle wave. Maybe not the most efficient way to generate one, but it's useful insight into the behavior of the moving average.
Exponential Average Step Response
Remember, the exponential average function works like this:mean[i] = w·s[i] + (1-w)·mean[i-1]
Where w is the weighting of the current sample and is a value between 0 and 1. For a weighting close to 0, the step response looks like this:
This graph clearly shows why it's called an exponential average because the average approaches the new value of the step function along an exponential curve. We can also see that the exponential average reacts more quickly to new inputs because the response changes much more quickly near the initial step. Then it approaches the new value more slowly over time. That is why the exponential average retained more of the bumps and spikes in the gas price signal, and it removes somewhat less of the high frequency content than the moving average does. Weightings have to be very close to zero before the exponential average won't have a sharp response to new values, and then the average approaches new values extremely slowly.
Theoretically, the exponential average never reaches the new value, and thus has an infinite response, which is why it's an IIR filter. Practically, this exponential average has nearly reached the new value within 5 or 6 time units, as represented on the graph above. It will never truly reach the new value, but it will get arbitrarily close.
FIR Filter Step Response
To have a more consistent frequency response than the moving average or exponential average, we have to go to the FIR filter. Remember that the FIR filter has a set of taps that are multiplied with the signal values, and the calculation is represented asy[j] = ∑i=0..(k-1) s[j-i]·h[i]
Where y[j] is the result of the filter for the jth sample, k is the number of taps, and h[i] is the ith tap. The FIR filter we looked at used a sinc function for the taps, and that filter has the following step response:
Notice how the filter doesn't respond strongly right away, instead wiggling back and forth a few times before jumping up to and overshooting the new value when the step is halfway through the filter. It then wiggles around the new value a bit before settling into it. This behavior may look familiar. If we extended the step function into a square wave with the right period, the filter response would look like the Fourier Series approximation of a square wave that we explored when covering transforms. The filter will actually generate the same waveform as the Fourier Series, but with a delay that is half the number of taps in the filter.
The taps generated from the sinc function only permit certain frequencies in the response, so that is why it has this behavior with the step function. The number of wiggles and the steepness of the transition in the center of the filter will depend on the number of taps and the frequency used in the sinc function to generate the taps. A major part of filter design is controlling these parameters to produce the desired cut-off frequency for the filter.
With that, we've pretty much covered the step response of the different averaging functions we've used. Analyzing the step response of a new filter or other DSP operation is a good practice for understanding the behavior of the algorithm you're developing. It can give you new insight or confirm that your algorithm is doing what it's supposed to do. It's a good tool to keep in your DSP toolbox. Next week we'll wrap up the statistical techniques of DSP by looking at a few ways to calculate how much a signal is changing with signal variance.
Other DSP posts:
Basic Signals
Transforms
Sampling Theory
Averaging
Step Response of Averaging
Signal Variance
Edge Detection
Signal Envelopes
Frequency Measurement
The Discrete Fourier Transform
The DFT in Use
Spectral Peak Detection
FIR Filters
Frequency Detection
DC and Impulsive Noise Removal
0 Response to "Everyday DSP for Programmers: Step Response of Averaging "
Post a Comment