News for hackers. Stuff that matters.
Re:IIR filters can be evaluated in parallel by saagarjha on Saturday February 16, 2019 @08:05AM (#19178396)
Thanks for the explanation; this clears up the mathematics behind the operation. Follow up question, though: why would you want to do this? Is this some sort of digital signal processing procedure?
Re:IIR filters can be evaluated in parallel by panic on Saturday February 16, 2019 @08:33AM (#19178475)
Yeah; say for example you're trying to recognize a swipe with a certain velocity on a touchscreen:

    def touchDown():
        velocity = 0
        lastTime = now
    def touchMoved(from, to):
        velocity = (to - from) / (now - lastTime)
        lastTime = now
    def touchFinished():
        if velocity.x > threshold:
            performGesture()
You test it out, and discover that the gesture is kind of flaky. Sometimes it works properly, but just as often it fails when it feels like it should have worked. It turns out that maintaining a constant velocity is hard—as your finger moves across the screen, the velocity can fluctuate around between samples. The test in touchFinished() looks at only the last sample taken, which is often the worst, as your finger has just lifted off from the screen.

So instead of just looking at the last velocity, you keep track of a "smoothedVelocity" which averages your velocity samples together:

    def touchDown():
        smoothedVelocity = 0
        lastTime = now
    def touchMoved(from, to):
        velocity = (to - from) / (now - lastTime)
        smoothedVelocity = 0.25 * velocity + 0.75 * smoothedVelocity
        lastTime = now
    def touchFinished():
        if smoothedVelocity.x > threshold:
            performGesture()
With this change, your smoothedVelocity moves a bit toward the measured velocity with each sample, but won't jump directly there. This feels a lot more predictable. Stopping your finger momentarily as it lifts off the screen won't stop the gesture from being performed, for example.

The smoothedVelocity code implements a low-pass IIR filter (it filters out the high-frequency fluctuations while letting the lower-frequency motion pass through). You could also imagine just keeping the last 2 velocities and averaging them together at the end: that would be an FIR filter.

Re:IIR filters can be evaluated in parallel by ttoinou on Saturday February 16, 2019 @12:41PM (#19179767)
Good example. I would add that you don't need to understand DSP and IIR to understand that particular example (IIR with only one memory case), it's only a 1D barycenter between previous version and last weighted value.
Re:IIR filters can be evaluated in parallel by dbcurtis on Saturday February 16, 2019 @12:35PM (#19179729)
In DSP when you implement a filter you typically have conflicting requirements. If you have a particular transfer function you wish to approximate, FIR is one choice. It is relatively easy to synthesize, and has linear phase response, and no ringing (Finite Impulse Response is the name, after all). However, it may take many more “taps” (delay stages) to implement as compared to an IIR. Sometimes, you care about the extra resources required (making it fit into your FPGA) but more often you can not tolerate the latency of all of those delay stages.

With IIR, you typically have much lower latency because it requires many fewer stages to get the same-ish transfer function. Tradeoffs: ringing, perhaps problematic phase response, more complicated synthesis problem.

Re:IIR filters can be evaluated in parallel by skybrian on Saturday February 16, 2019 @03:49PM (#19180858)
It sounds like IIR is about reusing previous calculations? But you don't actually want every previous sample to affect the result; it's more a side-effect of how the calculation is done?
Re:IIR filters can be evaluated in parallel by magicalhippo on Saturday February 16, 2019 @11:34AM (#19179372)
This is off the top of my head.

When you want to filter some data you often start by defining the response you're after, for example for a sub-woofer output you might want a low-pass filter that cuts off frequencies higher than 250 Hz.

Then you use some math to figure out the filter coefficients that will give you that response. For many (all?) filters you can get away with far fewer coefficients, often orders of magnitude like 4 vs 1024, if you go for an IIR filter rather than a FIR filter. This of course makes it far cheaper computationally to implement.

IIR filters have some downsides though compared to FIR, for one an impulse "never goes away" (at least in theory) since there's always some of it begin fed back into the next step. It's also difficult to make them have linear phase response, which can be important in certain settings.