The Celtic Engineer is a weekly newsletter produced by Celtic Engineering Solutions. We hope you enjoy it. If you have any suggestions for topics, would like to give feedback or want your email added to the distribution list please send an email to[email protected].
What kind of rhythm is an algo-rhythm?
An algorithm is a set of instructions. It has a starting place and an ending place and in between it explains how to do something. Often times these instructions are a calculation but they could be as plebeian as instructions on how to brush your teeth.
Etymologically speaking, the term has ties to the 9th Century Persian mathematician Al-Khwarizmi. Later it was used by our old friend Chaucer. The term really gained popularity in the 20th Century when various groups of mathematicians began using it as a tool to describe how to solve various mathematical problems including Alan Turing’s Turing machines.
Rather than being restricted to math, most engineers who find themselves writing code, software or firmware, are developing algorithms. The interesting ones are not just, ‘here is how you set up my microcontroller,’ although that is a useful and necessary thing to do. The interesting ones are the ones that solve a particular problem. It is those bits of code that are likely to be patentable.
Your 15 minutes of fame
Your phone is filled with algorithms, how important could they be right? Well, one that you might have heard of is called the quicksort algorithm and is used extensively. It was developed by Tony Hoare in 1959 and was subsequently published in 1961 in the journal Communication of the ACM. It was used in the Unix library that then was used by Java and is probably used, surprisingly frequently, in your daily life. Any time you need to sort a list, either numerically or alphabetically you are probably using this routine or one of its derivatives.
The Good, the Bad and the Ugly
Not all algorithms are created equally. Let’s take a look at a few used to trip a senor. The idea is that a voltage can vary up to a certain bound. If the voltage level crosses that boundary you want to take and action. You could do something as simple as if V>x do sub. And the first time you get a stray bit of noise on your signal you trip the senor and run off and do sub. Signals are not nice and smooth. That is kind of why there are fast blow and slow blow fuses. You don’t want to react, over react, the first time you get a trip signal. You want to be sure your signal has really crossed the line and is not just, oh, testing the waters as it were.
You go back to your computer and decide the change the algorithm so that you have to get, say 50 trips before you decide it is real. Then you realize that you are really just integrating the noise and will trip after the first 50 noise spike hit your system. You decide to put a limit on how long it will take. You have an A/D on your MCU and it can collect a sample every 50uS. You will decide your signal has crossed the threshold if you get 50 samples above the threshold in 250mS. You can collect 5,000 samples in that time so 50 represents 1% of the samples, depending on what your MCU has to do differently each loop. For example, if an interrupt comes in that will lengthen the time it takes to loop around and take another sample, in effect decreasing the number of samples in the period.
You implement your algorithm. You set up a measuring device and test your system and you find you can never reach the limit you set, but your system still trips. Let’s put a few number here to make it easier to understand. Say the limit is 100 ACU (arbitrary Celtic units). As the voltage rises you find that at about 95-96 your system says the threshold has been reached. You can play with the number of samples above the threshold (50) and you can play with the reset time (250mS) but you will never get to the threshold on your meter before your system trips.
You have improved your algorithm but it is still not doing what you want. The problem is still noise. In fact, the difference between your system and your measurement system is both the problem and the solution. Your measurement system is not reacting to every bit of noise instantaneously but rather is averaging or filtering the signal.
You could increase the filtering on your system; we all think capacitance is the solution to any problem. You are using an anti-aliasing filter, right? A variation on the problem could be to collect 50 samples and average them. Now you have introduced a big lag in your system. You have to collect 50 samples, do some math, make a decision and then you take an action. Maybe that is acceptable, or maybe not. You could increase the reaction time, reduce lag, by having a rotating buffer or queue. You add a sample and drop a sample so you always have 50 samples to average. This is more complex code but you find that you now have your system-trip and the meter agree on the voltage.
A few more problems
What do you do as the system is starting up? When they queue has only 30 samples? It is a situation you will have to deal with as a programmer.
Have you gotten all the lag out of the system you can? You might not need to worry about response time, but then again it might be critical to your system. If it is you can reduce the lag introduced by averaging all 50 sample each time. Instead of taking the 50 numbers and sending them to an averaging routine each time you collect a new sample, 49 of them are the same as last time after all, keep a running sum. When you collect a new sample add it to the sum and subtract the number you are dropping from the queue. Now you can divide by 50 (although dividing by 64 or 32 would be a LOT faster). That will save a lot of time and reduce your lag.
Not as simple as it seems
We all become experts in our part of the garden and can’t understand why someone else is having trouble, or taking time, when handling their part of the garden. It comes down to the details. When you know the challenges of someone else’s job, it is easier to understand why it takes a week to write what you think should be just a few lines of code.
This newsletter is sponsored by Celtic Engineering Solutions LLC, a design engineering firm based out of West Jordan, Utah, which can be found on the web at:www.celticengineeringsolutions.com. You can find the newsletter on the company blog, LinkedIn or by subscribing. Send your emails to The Celtic Engineer at: [email protected].