Blogs

The Risk In Using Frequency Domain Curves To Evaluate Digital Integrator Performance

Rick LyonsSeptember 24, 201921 comments

This blog shows the danger in evaluating the performance of a digital integration network based solely on its frequency response curve. If you plan on implementing a digital integrator in your signal processing work I recommend you continue reading this blog.

Background

Typically when DSP practitioners want to predict the accuracy performance of a digital integrator they compare how closely that integrator's frequency response matches the frequency response of an ideal integrator [1,2]. Traditionally the assumption is: The closer a particular integrator's frequency response matches the frequency response of an ideal integrator the more accurate will be that integrator.

This article is available in PDF format for easy printing

Years ago I accepted this assumption but I now believe it is not justified and I support my claim with a number of counter-examples presented in this blog. Let's begin by examining the frequency response of a theoretically ideal digital integrator and a few popular digital integrators.

Digital Integrator Frequency Responses

An ideal digital integrator has a frequency response described by:

   

where the frequency variable is $‑\pi ≤ \omega ≤ \pi$ measured in radians/sample. The positive-frequency ideal |HIdeal($\omega$)| magnitude response, shown as the dotted curves in Figure 1, is the response to which all digital integrator responses are compared. For example, the |HRect($\omega$)| frequency magnitude response of the Rectangular Rule integrator is also shown in Figure 1. Figure 1(b) shows the lower right side of Figure 1(a) in more detail.

Characterizing other popular digital integrators, the frequency magnitude responses of the Rectangular Rule, Trapezoidal Rule, Simpson's 1/3 Rule, Tick's Rule, and what I call the "Al-Alaoui Method" digital integrators are shown in Figure 2. (I include the Al-Alaoui Method integrator here because it has gained some attention in recent years [3].) The difference equations and frequency response expressions for these five integrators are presented in Appendix A.

So, again, DSP practitioners typically assume the most accurate integrator is the one whose frequency response most closely matches the frequency response of an ideal integrator. To make such comparisons easier, Figure 3 shows the percent error, versus frequency, between the various integrators and an ideal integrator as computed by:

   

OK, examine Figure 3 carefully. That figure implies that if an integrator's input signal only contains spectral energy in the range of, say, 0 ≤ $\omega$ ≤ 0.65$\pi$ radians/sample then we should rank our five integrators' accuracy performances as shown in Table 1.

The Fallacy of Table 1

We might stop at this point and, based on Table 1, assume we have a reliable grasp on the relative accuracy performance of various popular digital integrators. But to do so would put us on a train bound for Failure City.

I support that last statement with the following examples of definite integral results for the seven Test Signal's described in Appendix B. Let's first consider estimating the definite integral of what I call Test Signal# 4, as described in Appendix B, being y = sin(x) + 0.25 from x = 0 to x = 4 radians. That is, we want to use our five digital integrators to estimate the following definite integral:

   

When we apply Test Signal# 4 to our five integrators their results are listed in the center column of Table 2.

The rightmost column of Table 2 was computed using:

   

Notice how our measured accuracy ranking of our five digital integrators in the left column of Table 2 is very different than the left column of Table 1. This tells us our initial Table 1 assumptions of integrator accuracy should now be viewed with great suspicion.

The integration accuracy percent absolute error results for Test Signal# 4, the rightmost column of Table 2, are represented by the center column of symbols in Figure 4. Our five digital integrators' accuracy error results for the remaining six Test Signals in Appendix B are also shown in Figure 4.

We see in Figure 4 that in general, but not always, the Simpson's 1/3 Rule integration method produced more accurate results than the other four digital integrators. In addition, surprisingly, given its minimal frequency-domain error curve in Figure 3 the Al-Alaoui integration method performed rather poorly.

Conclusion

My empirical testing, whose results are given in Figure 4, shows that: A digital integrator's accuracy performance is not solely a function of its frequency-domain response. It's performance is also profoundly dependent upon the integrator's input signal. Thus our naive integrator performance ranking in Table 1, based solely on the frequency-domain error curves in Figure 3, is not valid.

When I say "dependent upon the integrator's input signal" I mean dependent, in an unpredictable way, on the input signal's:

  • Bandwidth
  • Monotonicity
  • Beginning-sample and end-sample values
  • Number of samples
  • Number of derivative polarity changes
  • Etc.
  • References

    [1] Dyer, S. and Dyer, J., "Numerical Integration", IEEE Instrumentation & Measurement Magazine, April, 2008, pp. 47‑49. Available online: https://www.researchgate.net/publication/3421163_bythenumbers_-_Numerical_integration

    [2] Arias-Trujillo, J., Blázquez, R., and López-Querol, S., "Frequency-Domain Assessment of Integration Schemes for Earthquake Engineering Problems", Hindawi Publishing Corporation Mathematical Problems in Engineering, Volume 2015, Article ID 259530. Available online: http://downloads.hindawi.com/journals/mpe/2015/259530.pdf

    [3] Al-Alaoui, M., "Novel Digital Integrator and Differentiator", Electronic Letters, Feb. 18, 1993, Vol. 29, No. 4, pp. 376‑379. Available online: https://feaweb.aub.edu.lb/research/dsaf/Publications/12.pdf

    Appendix A: Digital Integrators

    This appendix describes the five digital integrators whose accuracy performance is investigated in this blog.

    Rectangular Rule Integration

    The Rectangular Rule (also called the "Backward Rectangular Rule") integration method is defined by the following difference equation:

    Trapezoidal Rule Integration

    The Trapezoidal Rule (also known as the "Tustin Rule") integration method is defined by the following difference equation:

    Al-Alaoui Integration

    The Al-Alaoui integration method is defined by the following difference equation:

    Simpson's 1/3 Rule Integration

    The Simpson's 1/3 Rule integration method is defined by the following difference equation:

    Tick's Rule Integration

    The Tick's Rule integration method is defined by the following difference equation:

    Appendix B: Test Signals

    The seven discrete Test Signals applied to our five digital integrators are shown by the dots in the top y(x) panels of Figure B‑1. Each integrator estimates the definite integral defined by:

       

    where signal y is a function of independent variable x. The a and b limits values for each Test Signal are given in Figure B‑1. For reference, below each 25‑sample discrete y(x) sequence in Figure B‑1 is its positive-frequency |Y($\omega$)| spectral magnitude where frequency variable $\omega$ is measured in radians/sample.

    These seven test signals were chosen because their true definite integrals are easily found using integral calculus.


    Previous post by Rick Lyons:
       Reduced-Delay IIR Filters

    [ - ]
    Comment by LT1September 24, 2019

    Rick:

    First comment from a Long-Time Lurker.  Thanks for your many excellent postings.

    I believe you meant to say from x = 0 to x = 4 radians in 25 steps.

    The results certainly depend on the signal shape.  

    You probably thought it was too obvious to state that the results for any given signal also depend on the ratio of the sample rate to the bandwidth of the signal.  For example, your signal 4 using Simpsons with 100 samples results in 2.288e-6 percent error (compared to the integral in DP) for 100 samples over 0:4 radians.

    LT1 

    [ - ]
    Comment by Rick LyonsSeptember 25, 2019

    Hi LT1. Thanks for "catching" that typo of mine!

    Your last paragraph is absolutely correct and has caused me to add a few words of text to my 'Conclusion' section. In my integrator accuracy modeling I found that the an innocent-looking change to a test input signal may have a very noticeable, and to me unpredictable, change in the integrator's output value.

    LT1, did you know there is a way to predict the maximum error when using the Trapezoidal Rule integrator to integrate a discrete version of a mathematical function. That prediction doesn't give us the error in integrating a math function, but rather gives us a value for which the integration error will never exceed. Unfortunately that error "bound" analysis requires that we first use calculus to find the 2nd derivative of the input math function.

    I wonder if that Trapezoidal Rule error bound analysis can, somehow, be used to predict the max error when integrating real-world signals such as the output of an accelerometer.

    [ - ]
    Comment by LT1September 25, 2019

    Rick,

      Yes, Et= (-h^3/12)f''(xi), but I much prefer Simpsons for which

      Es= (-h^3/90)f''''(xi) with h the panel size and xi an interior point between the limits of integration.

      I wonder why one would need the integral of position, but as a non-nav guy, I can't be of any help (sorry), except perhaps to say I always reach for Simpsons because of the behavior implied above. I avoid higher order (4th +) polynomial approximations because of the susceptability to noise and measurement error (oscillations).

    LT1

    PS, I was logged in and hit submit reply earlier, but it told me that I had to be logged in to reply and sent my reply to the bit bucket in the sky.  Frustrating!  Then I logged out and logged back in to generate this.  

    [ - ]
    Comment by Rick LyonsSeptember 26, 2019

    Hi LT1. Just for my own education, what does the phrase "non-nav" mean?

    Sorry you had trouble posting a Reply. I've had some of my replies disappear in the past because, in the middle of typing a Reply I clicked on another web page window. Now I'm much more careful when typing a new Reply.

    [ - ]
    Comment by LT1September 27, 2019

    Hi Rick,

      Sorry for the abbreviation.  I should have simply said that I have no experience with navigation systems.

      Thanks for the hint.

    LT1   

    [ - ]
    Comment by kazSeptember 25, 2019

    Hi Rick,


    Thanks for the blog.

    I don't see any comment on dc gain in any of the integrators. For example the rectangular case has dc gain of 45 dB. Wouldn't a practical integrator need control of this gain. This is where loop alpha factor comes into action.

    Regards

    Kaz

    [ - ]
    Comment by dszaboSeptember 25, 2019

    Would the dc gain for the rectangular case not be infinite

    [ - ]
    Comment by kazSeptember 25, 2019

    yes it is infinite but I quoted 45 dB near dc as a concession

    [ - ]
    Comment by Rick LyonsSeptember 26, 2019

    Hi kaz. Yes, you're right. The integrators' z-transforms have a pole at z = 1, right on the unit circle. So their unit impulse responses are non-zero and infinite in length and this gives the integrators a DC gain of infinity. But because these integrators are used to integrate a finite-length sequence of samples, the integrators' single output value will be finite in value.

    [ - ]
    Comment by kazSeptember 29, 2019

    Hi Rick,

    A couple of points.

    1) The ideal integrator is the one that does my job.

    I don't see there is a specific meaning for ideal.

    2) If we take any set of filters targeting same cutoff e.g LP FIR, we end up with different transition curves. As such the output for a given input will be affected by how that input is sliced under the transition curve.

    Kaz

    [ - ]
    Comment by Rick LyonsSeptember 29, 2019

    Hi kaz.

    Please forgive me. I don't understand your Sept. 29, 2019 Comment.


    [ - ]
    Comment by niarnSeptember 29, 2019

    Hi Rick,

    I have no experience in numerical integration so sorry for the naive questions.

    In your 'benchmark' Simpsons 1/3 is performing best, I was wondering if results would look different if you used a denser sampling of the x-axis. Would you expect the relative rating of the integrators to be dependent on the 'sampling frequency'?

    Should one be concerned about stability issues considering the pole at z=1? I previously remember you wrote something on the stability of the Goertzel filter which also has a pole on the unit circle.

    Why is it that there is no trapezoidal differentiator or tick's rule differentiator that is just the inverse of the integration rules? 

    [ - ]
    Comment by Rick LyonsSeptember 30, 2019
    Hi niarn.

    Your questions are not at all naive. They're darned good questions. Questions like yours are how discoveries are made!

    [Question#1] Well, we should expect the accuracy performance of the integrators to improve if we increase the number of data samples (increase the samplng frequency) in our integration estimations. And that turns out to be true.

    The left panel below is my blog's Figure 4 accuracy results for 25 data samples. The right panel shows the improved accuracy results for 49 data samples (double the Figure 4 sampling frequency). In the right panel the Log%|Error| for the Simpson integrator for Test Signal# 1 is more negative than -6 so its blue diamond symbol isn't shown in that plot.

    trap_51006.jpg

    At first I didn't expect the relative accuracy ratings of the integrators to be dependent on the sampling frequency, but I was wrong. In the above right panel we see the percent error of the integrators is more negative (reduced error, improved accuracy) than they were in the left panel. But the amount of error reduction is not the same for all the integrators and not the same for all the seven Test Signals. Notice how the relative accuracy results is very different in the two panels for Test Signal# 5 and Test Signal# 7.

    [Question# 2] No, there's no worry about stability with these integrators. The integrators' z-transforms have a pole at z = 1, right on the unit circle. So their unit impulse responses are non-zero and infinite in length. But the impulse response sample values do not increase as time passes so the integrators are "marginally stable." But because these integrators are used to integrate a finite-length sequence of samples, the integrators' single output value will be finite in value.

    [Question# 3] Now that is a GREAT question. Sadly, I don't have an answer for you. But after I'm finished watching 'WWE Smackdown' on the boob tube I'll try to come up with an answer.
    [ - ]
    Comment by niarnOctober 1, 2019

    Thanks Rick, 

    As we can see from your Fig 2 and 3 we should expect larger differences in performance the more high frequency content is in the input. Also it could be interesting to see if all the different rules actually converge to the true value as sampling frequency goes to infinity.

    I believe there are applications where such integrators are not used on short input sequences but could run on very long input sequences (such as an audio input stream). And I think that Goertzel filters 'normally' has the pole(s) adjusted off the unit circle by a tiny value for stability reasons. So I was just wondering if the same would apply to the integrators. But for some reason this seems to not be the case.

    Looking forward to read your blog on trapezoidal differentiator ;)

    [ - ]
    Comment by Rick LyonsOctober 1, 2019
    Hi niarn. (I'm replying to your October 1 Comment.)

    Yes, the different integration methods do converge toward a true definite integral value as sampling frequency is increased.

    Years ago I thought a Goertzel filter was only marginally stable. But I was wrong. A Goertzel filter is guaranteed-stable as I explained at:

    https://www.dsprelated.com/showarticle/796.php

    There's no worry about stability with the integrators in my blog as I explained in my above Sept. 30 reply to your Question# 2.

    I'm experimenting with your notions of Trapezoidal and Simpson differentiators. But I making no useful progress so far.


    [ - ]
    Comment by niarnOctober 4, 2019

    Hi Rick,

    Not sure if you are looking into this anymore but I just want to mention something regarding stability and then you can correct if something is invalid/incorrect.

    The Goertel filter and the trapezoidal integrator are equivalent (same transfer functions) for the case when the Goertzel is configured for the DC bin (pole at 1) and their impulse responses are constant. For the case that the Goertzel is not computing the DC bin its impulse response oscillates forever with no decay. No stability issues as long as we make sure that coefficient quantization does not push the pole outside the unit circle and a bounded input results in a bounded output. However in contrast to the trapezoidal integrator the Goertzel needs multiplication with its coefficient to its state variable (y[n-1]) this is not needed in the trapezoidal integrator. So if the center frequency of the Goertzel is close to DC then numerical stability can be an issue because of round-off errors.

    From a DSP point of view I think that both the Trapezoidal integrator and the 'Trapezoidal differentiator' should somehow be treated with some caution when it comes to stability. Because they both have their poles on the unit circle their steady-state responses and transient-responses are merged, the transient (not sure if this is the correct name as it continues forever) doesn't die out. What I mean by this is that if stability of a filter is thought of as 'the filter not generating tones not present in the input' then both the Trapezoidal integrator and the 'Trapezoidal differentiator' can be thought of as not stable. The Trapezoidal integrator generates a DC offset and the 'Trapezoidal differentiator' generates a tone at fs/2 (nyquist). This tone added by the 'Trapezoidal differentiator' is perhaps what leaves it very inattractive as the output looks very noisy.

    A pole on the unit circle is a tricky thing.

    [ - ]
    Comment by Rick LyonsOctober 5, 2019
    Hi niarn. Regarding your 2nd paragraph, the trapezoidal integrator and the Goertzel filter never have the same z-domain transfer function. The denominator polynomials of their transfer functions have different orders. Also, the poles of a Goertzel filter can never be outside the z-plane's unit circle.

    Regarding your 3rd paragraph, neither the trapezoidal integrator nor the Goertzel filter will ever be unstable. Stability of a filter is *NOT* thought of as 'the filter not generating tones not present in the input'. The concept of network "linearity" is associated with a filter not generating tones not present in the input.
    [ - ]
    Comment by niarnOctober 6, 2019

    Hi Rick. Sorry, yes you are correct. It's the rectangular integrator and the Goertzel (as specified in eq [5] here on wiki https://en.wikipedia.org/wiki/Goertzel_algorithm) that are equivalent at DC. Just wanted to mention that there is a possibility of numerical stability but I don't think there is any point in discussing this. And you are of course correct that I should not have used the term unstable in the 2nd paragraph.

    [ - ]
    Comment by Rick LyonsOctober 7, 2019

    Hi niarn. Thanks for the wiki Goertzel web link.  I don't recall ever visiting that interesting web page before.

    [ - ]
    Comment by yatesSeptember 29, 2019

    Rick,

    I thought a perfect digital integrator was trivial: H(z) = 1 / (1 - z^(-1)). It appears you are trying to make a digital filter that mimics the frequency response of a perfect analog filter from 0 to Fs/2. That could be useful for some purposes, but is it "ideal?"

    --Randy

    [ - ]
    Comment by Rick LyonsSeptember 30, 2019

    Hi Randy. (Hope you're doin' well.)

    Your H(z) equation is identical to my Eq. (A-2).

    The point of my blog is to contradict the traditional belief that the "best" digital integrator is the one whose freq magnitude response most closely matches an ideal integrator's 1/(j times omega) freq magnitude response (my blog's Eq. (1)).

    The proof that such a belief is not valid is the performance of the Al-Alaoui Method integrator. The Al-Alaoui integrator's freq magnitude response most closely matches an ideal integrator's freq magnitude response, as shown by my blog's Figure 2, but the Al-Alaoui integrator's accuracy performance is among the worst of all the integrators.

    To post reply to a comment, click on the 'reply' button attached to each comment. To post a new comment (not a reply to a comment) check out the 'Write a Comment' tab at the top of the comments.

    Registering will allow you to participate to the forums on ALL the related sites and give you access to all pdf downloads.

    Sign up

    I agree with the terms of use and privacy policy.

    Try our occasional but popular newsletter. VERY easy to unsubscribe.
    or Sign in