Introducing HoloCalc

Delta-Sigma ADC Basics

Delta-sigma ADCs. Not a new technology by any means, yet still they are regarded by many embedded engineers as mysterious and magical. In this post, I’ll go through the basics of delta-sigma ADCs, and delta-sigma modulation on a higher level.

Understanding delta-sigma ADCs’ benefits compared to different ADCs (SARs, dual slope, etc) will require a broader understanding of delta-sigma modulation and its application in creating an ADC. The block diagram below describes a delta-sigma modulator (DSM) on a high level.

The input signal goes through a subtractor, taking the difference of the input and the output signal (fed through an impulse generator). Remember, this output is a binary density stream! When the output signal is 0, the differences passes the input signal straight through to the integrator. This integrator continues to sum the input until it triggers the compare that follows it (at 0), at which point the output changes from a 0 to Vref. We can think of this as one, for simplicity, but keep in mind that this block diagram is not implementation specific, so 1 may not make sense for every case. When the output signal changes to Vref, the impulse block it passes through causes a very large, negative result from the difference, and thus creates a step down in the integrator’s output, causing the compare result to go to 0 again. All of this can be a little difficult to imagine, so the figure below demonstrates the DSM modulating a DC signal. In theory, the output goes high for an infinitesimally small amount of time, but let’s assume that this is a clocked digital system with a non-infinite impulse function so that we have a useable output.

This difference of sums (delta-sigma, ho-ho!) creates a delta-sigma modulated density stream whose duty cycle is equal to Signal In/Vref. So, if Signal In is 0.5 Vref, we will see a 50% duty cycle delta-sigma modulated density stream at the output.

I can imagine you saying, “OK, that’s cool, but I thought we were talking about delta-sigma ADCs?” We are, though! This delta-sigma modulation is most of the work required to make a delta-sigma ADC. To make this delta-sigma modulator into an ADC, we must simply count the density output and supply a periodic sample pulse to capture the counter’s result and reset it. This relationship is laid out simply in the block diagram below.

This reveals one of the great benefits of the delta-sigma ADC: the process of delta-sigma modulating the input into a density stream and summing it in a counter reduces aliasing of high frequency signals into the pass band greatly. This means the delta-sigma ADC is more resistant to out-of-band noise than other types of ADC.

A practical (simple) implementation of the delta-sigma ADC is implemented below. As we can see, the elements from the basic DSM block diagram are created here in their analog counterparts.

In coming posts, I’ll talk about the benefits and drawbacks of delta-sigma ADCs as compared to other common ADCs (SAR, dual slope, etc.), and also how better, higher order delta-sigma ADCs can be made. Thanks for reading!

Digital/Density Hardware Discrete Fourier Transform – The Basics

I’ve been on a bit of a bender with density signals lately, so today I’m writing about a method for doing Discrete Fourier Transforms (DFTs) using digital logic and density signals. Before I get started, I have to give credit where it is rightfully due: much of my learning about density signals so far has come from a series of articles by a colleague of mine, Dave Van Ess. They’re a great read, and give wonderful insight into a different way of thinking about signal processing. Also, the core idea of mixing density signals to facilitate a DFT is also his, this post will merely be an exploration of the process on a larger scale, as well as possible applications of the process.

There are many tools for signal processing of density signals (some more useful than others), but only a few will be used in this post: multiplication (aka mixing), modulation, and filtering (aka decimation, aka quantification, aka counting).

Multiplication (Mixing)

As you may or may not know, multiplying two signals in time “mixes” them. For non-sinusoidal signals, mixing is somewhat difficult to picture, but when at least one of the two signals is a sinusoid, it becomes much easier. If we take signal one with most of its spectral energy centered around f1, and signal two, which is a pure sinusoid at f2, and mix them, we would see the same spectrum form signal one, but shifted by plus and minus f2. If we assume the two signals are sinusoidal, we’d see this in the time domain, and this in the frequency domain. What you really need to know is that you can mix a signal down to baseband (aka 0 Hz) to effectively filter and quantify the amount of signal at the mixing frequency. This is also called demodulation, and is usually used for tone detection, SONAR, and a multitude of other cool applications.

Anyway! Multiplication, which is traditionally done in large digital multipliers in hardware, can be done in a single logic gate in density. It should be noted, though, that 0 in density doesn’t equate to 0; 0 in-fact equates to -Vref, where as 1 equates to +Vref. This can usually be ignored, but makes the first quadrant of the multiply make sense: 0 times 0 is 1. 1*0 is 0, 0*1 is 0, and 1*1 is 1. This functionality is equivalent to an XNOR gate, meaning we can mix density signals with just this XNOR gate.

Modulation (Analog or Digital to Density)

Modulation is largely covered in an earlier blog post I wrote. In short, it is the process of converting a digital signal to a density signal. There are many ways of doing this, but delta-sigma modulation (the modulator shown below) is the best in this application.

Filtering (Density to Digital)

Filtering is the process of quantifying a density signal into a digital signal. Traditionally, quantification of a density signal is traditionally done in a counter, which doesn’t really sound much like a filter. But it is! Counting the density stream removes the high frequency variations that “come out in the wash” when counted and quantified, thus making this counting of the density signal acts as a low-pass filter. Other more clever forms of filtering (converting from density to digital) are likely possible, but are not explored in this post. The diagram below shows an example counter, with the density stream controlling its enable, a clock driving it at the density data rate, and another signal representing the decimation rate controlling the reset. In theory, this decimation signal would also be inverted and tied to the gate of a latch or flip flop following the counter output, so that the final digital value could be captured. It is important to note that the input signal is at the data rate, and the output data is at the decimated rate. For example, if we are outputting a full-scale 8-bit value, we will be counting 256 separate density bits to quantify it. This means our output data rate will be 256 times slower than our input data rate.

This post is getting a bit long, so I’ll leave it off here. If you’re clever, you might be able to pick it out from the diagram at the top of this post, otherwise, I’ll be posting the rest of the process soon. Thanks for reading!

Density Signals and Delta-Sigma Modulation, Part I

Recently I’ve been quite taken by the idea of density signals. These are similar to digital signals, but are instead represented by a single bit for any given point in time. A very common example of this is the output of a pulse-width modulator (PWM), which may drive an RC low-pass filter to create a simple digital to analog converter (DAC), facilitate some motor control, etc. PWMs are commonly made with a single counter with a compare. The continually counting counter’s compare output will be high during a given pulse width based on the compare result, and thus give the desired duty cycle. Let’s say we want to create a DAC from this PWM. We can do this as described above, by tying a resistor and capacitor to the output to create a low-pass filter. The capacitor will act as the energy storage for the DAC, and the PWM’s duty cycle will define the output voltage of the DAC, assuming a sufficiently quick period for PWM. The diagram below demonstrates this configuration.

Very simply, the counter produces a signal of sufficiently high frequency such that the filter output is effectively a DC representation of the duty cycle described by the following equation.

This is pretty cool and all, and allows us to create a decent DAC. We can create analog signals using this PWM by changing the compare value in time, at a rate of at most once per counter period. Again, this is called pulse width modulation, and it allows us to convert a digital signal – the one that controls the counter compare value – into a density signal, a string of bits whose duty cycle (or density!) describes its amplitude. This conversion is between a single, quantized value and a string of bits representing this value is called modulation. So, what is this delta-sigma modulation, and why is it so cool? Well, let’s look at a different way to make this DAC as s demonstration.

Let’s say that, instead of using a counter with a compare, we instead use an adder and a register to create our density signal. This is done by registering the adder output and feeding it back into one of its inputs, and taking our digital duty cycle value (as a fraction of the adder width) and feeding it into the other adder input. The overflow output of the adder will be our density stream output. This whole circuit is shown in the following diagram.

Ok, so what does this do? Let’s look at a simple example: we will use a common 8-bit adder, and we will use a duty cycle of 50%. To do this, we place 128 in the duty cycle register, which causes the adder to overflow every other operation. For a duty cycle of 25%, we use 256/4 = 64, which causes the adder to overflow every 4 operations. For a duty cycle of 75%, we use 256*3/4 = 192, which causes the adder to overflow 3 out of every four operations. Why is this desirable? Because it moves the modulation frequency as high as possible for each given duty cycle, ensuring that digital feed-through at the filter output is minimized, giving you a maximally smooth output. This modulation scheme is called Delta-Sigma Modulation (DSM). It is useful for DAC creation, but is particularly useful in analog to digital converters (ADCs), as I will discuss in a later blog post.

To test these claims, I’ve created a couple simple python classes for the PWM and DSM, and tested them with a modulation period of 256 and a duty cycle of 1/8. The time domain results are as expected, with the PWM producing a single high and single low pulse for each period, and the DSM producing many high and low pulses, as frequently as possible for this decimation period, as shown in the below plots.

Of particular interest is the resulting frequency spectrum, though. We can see in the below diagram that the PWM has many more low-frequency components, which are much more likely to get through the RC low-pass filter in our DAC. The DSM, on the other hand, has its energy in much higher frequencies, which are much less likely to bleed through the low-pass filter. We see this in the figure below.

DSM DACs are pretty cool, but DSM ADCs are much more impressive, and as the embedded world grows to embrace them, understanding them will be integral in utilizing them well. I will explore these in a future blog post, as well as an exploration of signal processing on density signals. Thanks for reading!

Simulating Noise in Python

You know what’s great? Simulating stuff, especially simulating a whole system. There is one problem that usually shows up, though: how do you supply realistic data, similar to that you’re seeing on your scope? You can gather samples from the scope and feed it to the simulation, but doing tests on multiple data sets becomes tiresome and isn’t a robust solution.

So, how do you generate random noise for your simulation? You can use the python random package, but the random functions give you spectrally generic results (flat, Gaussian, etc.). What we want to do is take white, spectrally flat noise as an input and filter it to control its frequency spectrum. Sounds pretty simple, but how do we create this magical filter with a completely arbitrary frequency response?

Before we get too caught up in thinking about complex filters for a specific use case, it would be good to recall the FIR filter. It’s a simple filter that implements a weighted average to do its filtering. Arriving at the filter coefficients is somewhat of a mystery to some people: these coefficients are usually found by using some filtering toolbox somewhere so people don’t have to worry their pretty little heads about how the filter actually works. Luckily, the FIR filter is much easier to understand than its IIR relative. The FIR filter is uniquely useful in this case because of how its filtering is related to its coefficients: the filter’s coefficients are simply a summation of sine waves at the frequencies in the pass band. Due to the rectangular nature of commonly desired filter spectrums (pass-bands), this summation usually ends up taking the shape of a sinc pulse. The figure below shows the sine wave frequencies that define the pass-band for an arbitrary filter, and the following figure shows the summation of these sine waves.

Due to the discrete nature of the sine wave summation, the sinc pulse is somewhat deformed, but still adequately demonstrates typical FIR coefficients. Thinking a little bit more about this, we realize that an FIR filter is really just convolution of your data with a summation of all the sine waves of frequencies inside the pass band. Knowing this, we can step back a bit: if every signal is a summation of sine waves of varying frequencies, and we have a signal whose spectrum we are trying to use to filter data, why not just use the data itself as the FIR filter coefficients? The solution for this problem doesn’t even require messing around with FFTs and IFFTs. Now, our block diagram for the system is clear:

All right, now, making it in Python! You’ll need numpy and scipy to follow through this example. Matplotlib is also used for plotting purposes. First, we’ll need to create an FIR filter class. An FIR filter class exists in scipy, but it contains a lot of unneeded bloat for this application, and creating the class may help us understand FIR filters a little better. Firstly, FIR filters have two attributes: coefficients and state variables. State variables are stored data within the filter; for FIR filters, it is merely the last N inputs to the filter, where N is the number of coefficients used in the filter. So, our class will start out as:

class firFilter:

    coefficients = numpy.array([])

    stateVariables = numpy.array([])

The filter class needs only two functions: __init__() and processSample(). The first is the constructor the for the class, which puts everything in the right place and sets up all the important variables, in this case assigning the filter coefficients and initializing the state variable list. __init__() should look like:

def __init__(self, filterCoeffs):
    if (type(filterCoeffs) == numpy.ndarray):
        # Save input filter coefficients
        self.coefficients = filterCoeffs
    # Initialize filter state variables
    self.stateVariables = numpy.array([0]*len(filterCoeffs))
    else:
        raise TypeError("Wrong type for filterCoeffs, "+
                "should be numpy.ndarray.")

This allows anyone utilizing the class to create filters of arbitrary length. Next, the processSample() function needs to do simply that: take an input value, process the filter, and return the result. This amounts to popping the oldest sample from the state variables list and appending the newest sample. Thanks to some optimizations in numpy, processing the filter can be done with a simple matrix multiplication and sum. The processSample() function will look like:

def processSample(self, inputSample):

    # Add new sample to state variables, remove oldest one
    self.stateVariables = numpy.append(numpy.delete(self.stateVariables, 0),
    inputSample)

    # Calculate filter output
    return sum(numpy.multiply(self.coefficients, self.stateVariables))

Simple, right? Now that we’ve created our FIR class, we’ll need to create the noise shaping class that utilizes it. It will need an instance of our new FIR class, as well as an array to hold the sampled noise data. It’ll start out like:

class shaper:

    # This list of doubles controls signal amplitude across the frequency
    # spectrum.
    sampleNoise =numpy.array( [])

    # This is te FIR filter instance used to filter noise
    noiseFilter = None

Similar to the FIR class, this one will only need a couple functions: __init__() and getNoise(). __init__() (the class constructor) will need the noise sample as a list, and will construct the FIR filter instance:

def __init__(self, sampleData):
    # Check sampleData is of correct type
    if (type(sampleData) in [list, numpy.ndarray]):
        self.sampleNoise = numpy.array(sampleData)

    else:
        raise TypeError("Incorrect type for sample data"+
                        ".  It should be numpy.ndarray or list.")

    self.noiseFilter = firFilter(self.sampleNoise)

The getNoise() is even simpler. It requires no input, and supplies a random, spectrally shaped noise sample:

def getNoise(self):
    return self.noiseFilter.processSample(random.random())

Now, we can test our hypothesis! To start, the sampled “noise” will be a sine wave of arbitrary frequency. This will make verification much easier, and it’s very easy to generate. It looks like:

Now, we can insert some code at the end of our python file to test out the noise generator:

mySampleData = [numpy.sin(numpy.pi*a/10) for a in range(0, 1024)]

x = shaper(sampleData = mySampleData)

from matplotlib import pyplot as pp
import scipy

for i in range(0, 5):
    data = []
 for i in range(0, 1024):
        data.append(x.getNoise())

    pp.subplot(2, 1, 1)
    pp.plot(data)
    pp.title("Generated Noise")

    pp.subplot(2, 1, 2)
    pp.plot(abs(scipy.fft(data)))
    pp.title("Generated Noise Spectrum")

pp.show()

This will generate 5 sets of simulated noise. The length of noise generated can be arbitrary, but to avoid confusion, the output data will be of the same length as the input (different lengths makes the FFT result different between source and simulation data). A single instance of this simulated noise looks like:

And 5 samples of this generated noise looks like:

As we can see, we’ve succeeded in creating a noise of arbitrary frequency spectrum. Now we can add this noise to our input signal (or even simulate our input signal!) with a single function call: shaper.getNoise(). When using this class, make sure that you sample the noise data at the same rate that the system you’re simulating does, or decimate it down to the correct rate! Using a different sampling rate will stretch or squish the noise spectrum and make it inaccurate.

Thanks for reading!

Knowledge as Interconnected Nodes

In this article I will rant about a subject that I know nothing about. I think I’ve got some pretty good ideas, though.

What does it mean to know something? To know what a Lenovo Laptop is? To know how to play the guitar? Knowing something is very base in our minds as human beings, so basic that we barely question what it means to know something. How does our mind piece together data and conclude “I know X”? At the most basic level, via experience. The brain perceives events via its sensors – eyes, ears, tongue, skin, etc. – and stores data regarding those events in memory. Let’s say you ate some cake. It was one of those generic platter cakes you find at Safeway, so it was a bit dry and the frosting was sickly-sweet. The frosting was mostly white, but red letters spelled out a crude but funny in-joke for your co-worker, whose birthday you were celebrating. That last bit wasn’t so much a descriptor of the cake, but its importance will become apparent later. Now, when you think of cakes, specifically cheap platter cakes, what are the important characteristics you remember? Sweetness (sometimes too much!), rectangular shape, spongey inside that’s not as sweet, etc. Thinking of abstracted things (like a non-specific platter cake) doesn’t link to a bunch of pictures of cakes you’ve saved in your mind, it links to ideas that you’ve linked to platter cakes in the past. You can imagine each of these abstract objects as a node, whose defining characteristics are manifest as connections of certain strength or proximity to other nodes that characterize it.

Think of the platter cake as the node of interest: we know platter cakes. Platter cakes are connected to various nodes: it has a strong connection to sweet, a strong connection to celebration, and somewhat weaker connection to gross, etc. You can imagine that the abstract idea of platter cakes is portrayable as a long list of connected nodes and their affinities. For example, through a very convoluted memory of my own, platter cakes are also tied to 9/11. That 9/11 node connects to many other nodes, some of which may be ideas, some of which may be memories, but looking into the node that is 9/11 my brain automatically explores the other paths to a certain extent, filling out the idea of 9/11 that takes it past a series of characters to a collection of memories, ideas, and feelings. This description elicits images of the brain being a computer in a vast net of nodes (ideas, memories, etc) chasing nets around and receiving external stimulus via its sensors that may push it towards certain nodes, or even create new nodes.

This idea of knowledge as a connection of nodes also explains the “Eureka!” momemts that people experience. Their brain is sitting there, racing around its node-track, when some external stimulus pushes the brain in a certain direction. Perhaps it is puzzling about why objects are intrinsicly drawn towards the earth, and suddenly an apple strikes them in the head. In reaction, the brain examines the situation, checking out nodes connected to apples, etc, creating connections between nodes where it sees them, when suddenly, the track is completed! The disconnect between one set of nodes (theory) and another set of nodes (reality) had been connected via a short route! The brain races to compare other nodes in the close proximity, and discovers other connections that can be made. Sometimes, this leads the person to experiment more, gathering more data, and creating more connections until the idea is more complete and explainable to others in a way that will allow them to create the necessary nodes and connections. This even sheds some light on why two people that both “know about the same things” have trouble having in-depth communications about them. This is particularly true in the more abstract engineering practices.

Engineering itself is very much centered on individual contributors coming together to figure out problems. The problems discussed on the broad spectrum are usually not very abstract and are easy to imagine. Those problems share connections with very common nodes and connections, like those involving system architecture and communication. But, when the problem becomes deeper, and the separate parties have come to understand the same idea in different ways (described the same phenomena with different nodes and interconnects), it becomes difficult for them to have efficient conversation, as they spend time and effort fitting the other person’s ideas into their own web of nodes. When companies impose standards or hold large training sessions, engineers can much more easily discuss the topics due to the commonality of their node placement and interconnection.

Sangria de Mayo and the Importance of Branding

Sangria de Mayo is a wonderful holiday that my friends and I love to celebrate. It involves participants concocting and bringing their own custom batches of sangria, a classic summertime alcoholic beverage. Invariably, the best sangrias are designed from the ground up with a core motivation in mind. This post is not about designing sangria, though. It’s not about design choices at all. It’s about marketing.

Sangria de Mayo was a recent pleasure of mine, as I’ve only attended the event in this year and the one previous. Lets talk about the first one. In keeping with my recent graduation from Washington State University, I figured I would show up to this party and show people how it was done right. Sangria? More like an opportunity to get people to drink hard A and wine at the same time. So, I concocted the most imperceptibly alcoholic sangria I could – a mixture of Merlot, greapfruit, limes, lemons, vodka, and everclear. Honestly, the taste that masked the alcohol was bearable at best. In my excitement, I decided the beast needed a name: the hammer. I’m sure you can infer why. The real surprise was its amazing success: I arrived at a party with a healthy supply of competitors; there were many flavors of delicious (sometimes beautiful) sangrias, and yet, mine was the first to run out. Puzzling, in a singular instance.

Fast forward to a year later (tonight). Sangria de Mayo is happening again, and I’d like to make a good showing. Last time, though, my sangria was a bit abrasive: it was very much “in your face”. You had to want it. Instead, I chose to go for a white zinfandel base with sugar, fizzy energy mix, dissolved sugar, mikes hard lemonade, and everclear. Even more everclear than last time. And honestly, it was pretty good. In keeping with its predecessor, and the pacman naming theme, I named the batch “Mrs. The Hammer”. That’s all distracting from the point, though. I showed up to the gala about 2 hours after it started (I can’t even call it fashionably late at that point – maybe Diablo 3 late?) and my batch of sangria was spent within the hour. I received laments from other sangria makers that theirs hadn’t gone so quickly, even though they had shown up before I did. Why was my sangria so popular in the presence of other, tastier sangrias?

The answer is marketing. Others brought their sangria in a plastic drink carafe, others in emptied water containers, etc. The most extensive labeling in theirs was sharpie on plastic in Spanish. Mrs. The Hammer, though, was scrawled dangerously on a strip of white duct-tape in rough letters. Customers (party-goers) saw the label and felt something: something dangerous, something mysterious, and something that would obviously make them have a fuck load of fun. Without even considering the marketing I did in person, the package itself screams “yeah, this will get you crunk. And you will like it.” Add to that the mystique of the genesis story, and the subtle description of its making leading gradually from the white zinfandel to the raspberries and eventually to the everclear. The sangria is the embodiment of that girl/guy you don’t want to date, but god damn do you want to go have a night out with. The branding is consistent, it speaks to the target audience at the party (people trying to have a good time), and it creates something for people to talk about to each other. Even if they are disdainful, it still furthers the mystique of Mrs. The Hammer. It’s the naughty one. It’s the one that, secretly or not, everyone wants. It’s branding.

And that’s the story of why my probably mediocre sangria always gets finished first.

Coverflows on Android

You know what’s a sweet user interface element? Coverflows. They aren’t that great for what they were initially used for: selecting albums to listen to based on their album cover. Turns out people really do know what albums are called, or just want to see the artist/track title. But! You know what they are great for? Selecting objects (in the software sense) with the identifier as a picture instead of text. This is primarily limited to selecting photos, and even then, some may say that a simple grid is more utilitarian for this task, and I would tend to agree, but this doesn’t address a big problem with selecting from a grid: it’s ugly! Google tried to do what it could with the Gallery app, but the grid of picture stacks still looks plain. It also separates different categories (stacks) in a way that isn’t ideal. Anyway, for the applications I am pursuing, I want something that places more emphasis on the content of each picture, which has led me to the coverflow.

The first, and largest, problem with this is: there isn’t any sort of standard coverflow implementation that has been made for android yet! I’ve seen examples in which people expand the Gallery view – which by default displays a horizontal list of pictures – such that it would rotate the pictures based on their position. This has a variety of problems associated with it, though:

Object spacing within the list is constant. What you want is to have rotated images have increased density. This way, you can see the edge of many pictures to give the user more information about what is further down the line in the list.
The gallery extension is very slow! Seriously. My Galaxy SII couldn’t handle a 5 picture list. And yes, the bitmaps being displayed were of appropriate resolution.
The extension of the gallery, while convenient, isn’t constructed around the objective of creating a coverflow. Things like minimum object spacing, maximum object rotation, focal length, etc. are all very awkward adjustments to make.

So! What does this mean? That I have to create a coverflow package, of course! Due to the overtly 3D nature of the coverflow view, OpenGL ES2.0 will be utilized to create a lighter weight coverflow view with proper rendering of elements. The topology of the package will be:

Coverflow (extends GLSurfaceView)
This will be the top level class through which users will interface with the coverflow, setting separation, rotation shaping, picture size, etc.
- CoverflowRenderer (extends GLSurfaceView.Renderer)
  This object will handle rendering of the coverflow, and will receive configuration specs from the parent Coverflow class. It does the heavy lifting and will contain all the ugly code we don’t want the use to have to mess with.
- CoverflowSquare
  The coverflow square class will contain all pertinent data required for each square in the coverflow: path to the picture to be displayed, size, byte buffers for rendering in OpenGL, etc. It will contain limited APIs for updating byte buffers.

So far, I’ve got a cursory version of each of these made. The coverflow renders the list with unity separation between pictures, rotates pictures based on position, and has a single pole IIR filter implemented to mimic the critically damped spring settling effect for when a user flicks it. Oh! It also ensures that it settles on an integer position, thus ensuring that a square is dead on, or “selected”. The view is very snappy and is working exactly as expected. Here is a washed out laptop webcam recording of the coverflow in aciton:

Going forward, I plan to clean up the code to increase usability, and implement more features to make the coverflow as pretty as it deserves to be. When it gets to a respectable point, I’ll post the code somewhere so that others can utilize this view as well.

Thanks for reading!

Algorithm for Determining Optimal Multiplication via Shifts, Adds, and Subtracts

Single pole IIR filters are a quick and dirty way to filter data in time or resource limited processing systems. These are particularly useful in embedded systems that don’t have access to dedicated multipliers. These single pole IIR filters can be computed in only a handful of cycles in modern cores that have single cycle multipliers, but more limited cores without multipliers must be configured in a more cunning fashion to keep calculation time low.

The filter coefficient A is a factor of 1, assuming a stable filter. The process for calculating these filters is simple:

w1 = xn – yn-1
w2 = A * w1
yn = yn-1 + w2

The multiply in this process is the tough part. The classical definition of multiplication is a series of additions. With numbers greater than 2, this process becomes inefficient very quickly. Luckily, shifts allow for quick multiplies or divides by powers of two. This can be expoited to implement multiplies or divides by other values via additions or subtractions of shifted data. This allows us to create filters with cut-off frequencies in much finer locations.

Now comes the extra credit. I was recently inspired to implement one of these filters in an extremely limited processing core, in which timing was uniquely limited by the system’s ADC sampling rate. This timing limitation motivates a limited multiplication process. As a human, finding the optimal organization of shifts, adds, and subtracts would not be hard for a given value. For example, if I required an A value of 7/16. The simple solution would be the addition of three shifted values; a shift right by 2, a shift right by 3, and a shift right by 4 could be added together to attain 7/16. After little investigation, we can see that this may be optimized into the subtraction of a shift right by 4 from a shift right by 1. In this way, we can represent a multiplication by a series of positive or negative divisions by powers of two. For example, we can represent 7/16 as [0.5, -0.0625].

This is all well and good, but now assume that we want to be able to calculate these optimal multiplies for arbitrary values of A – for arbitrary cut-off frequencies. This is of particular interest if you are creating a tool for use by others, that do not necessarily want to know the nitty-gritty of how to create the filter itself. After some thought, it can be seen that this series of scaling values can be calculated successively.

First, the necessary number of bits required for a given accuracy must be calculated. Once this has been calculated, an integer representation of the scaling value, as a fixed point number, may be calculated. After this, the scaling list discussed before can be calculated by merely successively selecting the added or subtracted dividing power of two that brings the current remainder closest to zero. For example, if we were to programmatically perform this process for a coefficient of 7/16:

7/16 – 1/16 = 6/16

7/16 – 2/16 = 5/16

7/16 – 4/16 = 3/16

7/16 – 8/16 = -1/16

7/16 – 16/16 = -9/16

It is apparent from the above calculations that subtracting 8/16, equivalent to a right shift of 1, brings the result closest to zero. This does not yet yield a sufficiently accurate result, so we will take the remainder from the last calculation and perform it again:

-1/16 + 1/16 = 0/16

-1/16 + 2/16 = 1/16

-1/16 + 4/16 = 3/16

-1/16 + 8/16 = 7/16

-1/16 + 16/16 = 15/16

With an addition of 1/16, a shift right of 4, we reach zero, giving us a result of zero. We invert the values selected to undo the negation implicit in this process to get a list of scaling values [0.5, -0.0625], just as we determined before. Lets pop the stack a few times to get back to the application layer. When applying this method with an accuracy requirement of 0.1%, and attenuation values with granularity in the thousandths, I found that the largest number of values in these scaling lists was only 5, which is great news for the application of this multiplication scheme for single pole IIR filters.

Hello world!

Ah, the genesis of my own website. This site will become a place for me to showcase my abilities, share my thoughts, and post my better composed photos.

Hopefully, I won’t be looking back at this post, thinking about how I should have posted more frequently!

full stack

Electrical engineer, Android developer, rock skipping enthusiast.