Ten Little Algorithms, Part 1: Russian Peasant Multiplication
This blog needs some short posts to balance out the long ones, so I thought I’d cover some of the algorithms I’ve used over the years. Like the Euclidean algorithm and Extended Euclidean algorithm and Newton’s method — except those you should know already, and if not, you should be locked in a room until you do. Someday one of them may save your life. Well, you never know.
Other articles in this series:
- Part 1:
Second-Order Systems, Part I: Boing!!
I’ve already written about the unexciting (but useful) 1st-order system, and about slew-rate limiting. So now it’s time to cover second-order systems.
The most common second-order systems are RLC circuits and spring-mass-damper systems.
Spring-mass-damper systems are fairly common; you’ve seen these before, whether you realize it or not. One household example of these is the spring doorstop (BOING!!):
(For what it’s worth: the spring...
Slew Rate Limiters: Nonlinear and Proud of It!
I first learned about slew rate limits when I was in college. Usually the subject comes up when talking about the nonideal behavior of op-amps. In order for the op-amp output to swing up and down quickly, it has to charge up an internal capacitor with a transistor circuit that’s limited in its current capability. So the slew rate limit \( \frac{dV}{dt} = \frac{I_{\rm max}}{C} \). And as long as the amplitude and frequency aren’t too high, you won’t notice it. But try to...
Bad Hash Functions and Other Stories: Trapped in a Cage of Irresponsibility and Garden Rakes
I was recently using the publish() function in MATLAB to develop some documentation, and I ran into a problem caused by a bad hash function.
In a resource-limited embedded system, you aren't likely to run into hash functions. They have three major applications: cryptography, data integrity, and data structures. In all these cases, hash functions are used to take some type of data, and deterministically boil it down to a fixed-size "fingerprint" or "hash" of the original data, such that...
How to Estimate Encoder Velocity Without Making Stupid Mistakes: Part II (Tracking Loops and PLLs)
Yeeehah! Finally we're ready to tackle some more clever ways to figure out the velocity of a position encoder. In part I, we looked at the basics of velocity estimation. Then in my last article, I talked a little about what's necessary to evaluate different kinds of algorithms. Now it's time to start describing them. We'll cover tracking loops and phase-locked loops in this article, and Luenberger observers in part III.
But first we need a moderately simple, but interesting, example...
Fluxions for Fun and Profit: Euler, Trapezoidal, Verlet, or Runge-Kutta?
Today we're going to take another diversion from embedded systems, and into the world of differential equations, modeling, and computer simulation.
DON'T PANIC!First of all, just pretend I didn't bring up anything complicated. We're exposed to the effects of differential equations every day, whether we realize it or not. Your car speedometer and odometer are related by a differential equation, and whether you like math or not, you probably have some comprehension of what's going on: you...
Chebyshev Approximation and How It Can Help You Save Money, Win Friends, and Influence People
Well... maybe that's a stretch. I don't think I can recommend anything to help you win friends. Not my forte.
But I am going to try to convince you why you should know about Chebyshev approximation, which is a technique for figuring out how you can come as close as possible to computing the result of a mathematical function, with a minimal amount of design effort and CPU power. Let's explore two use cases:
- Amy has a low-power 8-bit microcontroller and needs to compute \( \sqrt{x} \)...
Linear Feedback Shift Registers for the Uninitiated, Part XIII: System Identification
Last time we looked at spread-spectrum techniques using the output bit sequence of an LFSR as a pseudorandom bit sequence (PRBS). The main benefit we explored was increasing signal-to-noise ratio (SNR) relative to other disturbance signals in a communication system.
This time we’re going to use a PRBS from LFSR output to do something completely different: system identification. We’ll show two different methods of active system identification, one using sine waves and the other...
Linear Feedback Shift Registers for the Uninitiated, Part XIV: Gold Codes
Last time we looked at some techniques using LFSR output for system identification, making use of the peculiar autocorrelation properties of pseudorandom bit sequences (PRBS) derived from an LFSR.
This time we’re going to jump back to the field of communications, to look at an invention called Gold codes and why a single maximum-length PRBS isn’t enough to save the world using spread-spectrum technology. We have to cover two little side discussions before we can get into Gold...
Number Theory for Codes
Everything in the digital world is encoded. ASCII and Unicode are combinations of bits which have specific meanings to us. If we try to interpret a compiled program as Unicode, the result is a lot of garbage (and beeps!) To reduce errors in transmissions over radio links we use Error Correction Codes so that even when bits are lost we can recover the ASCII or Unicode original. To prevent anyone from understanding a transmission we can encrypt the raw data...
Linear Feedback Shift Registers for the Uninitiated, Part III: Multiplicative Inverse, and Blankinship's Algorithm
Last time we talked about basic arithmetic operations in the finite field \( GF(2)[x]/p(x) \) — addition, multiplication, raising to a power, shift-left and shift-right — as well as how to determine whether a polynomial \( p(x) \) is primitive. If a polynomial \( p(x) \) is primitive, it can be used to define an LFSR with coefficients that correspond to the 1 terms in \( p(x) \), that has maximal length of \( 2^N-1 \), covering all bit patterns except the all-zero...
Shibboleths: The Perils of Voiceless Sibilant Fricatives, Idiot Lights, and Other Binary-Outcome Tests
AS-SALT, JORDAN — Dr. Reza Al-Faisal once had a job offer from Google to work on cutting-edge voice recognition projects. He turned it down. The 37-year-old Stanford-trained professor of engineering at Al-Balqa’ Applied University now leads a small cadre of graduate students in a government-sponsored program to keep Jordanian society secure from what has now become an overwhelming influx of refugees from the Palestinian-controlled West Bank. “Sometimes they visit relatives...
Elliptic Curve Cryptography
Secure online communications require encryption. One standard is AES (Advanced Encryption Standard) from NIST. But for this to work, both sides need the same key for encryption and decryption. This is called Private Key encryption. Public Key encryption is used to create a private key between two sides that have not previously communicated. Compared to the history of encryption, Public Key methods are very recent having been started in the 1970's. Elliptic...
Polynomial Math
Elliptic Curve Cryptography is used as a public key infrastructure to secure credit cards, phones and communications links. All these devices use either FPGA's or embedded microprocessors to compute the algorithms that make the mathematics work. While the math is not hard, it can be confusing the first time you see it. This blog is an introduction to the operations of squaring and computing an inverse over a finite field which are used in computing Elliptic Curve arithmetic. ...
How to Succeed in Motor Control: Olaus Magnus, Donald Rumsfeld, and YouTube
Almost four years ago, I had this insight — we were doing it wrong! Most of the application notes on motor control were about the core algorithms: various six-step or field-oriented control methods, with Park and Clarke transforms, sensorless estimators, and whatnot. It was kind of like a driving school would be, if they taught you how the accelerator and brake pedal worked, and how the four-stroke Otto cycle works in internal combustion engines, and handed you a written...
Shibboleths: The Perils of Voiceless Sibilant Fricatives, Idiot Lights, and Other Binary-Outcome Tests
AS-SALT, JORDAN — Dr. Reza Al-Faisal once had a job offer from Google to work on cutting-edge voice recognition projects. He turned it down. The 37-year-old Stanford-trained professor of engineering at Al-Balqa’ Applied University now leads a small cadre of graduate students in a government-sponsored program to keep Jordanian society secure from what has now become an overwhelming influx of refugees from the Palestinian-controlled West Bank. “Sometimes they visit relatives...
Linear Feedback Shift Registers for the Uninitiated, Part IX: Decimation, Trace Parity, and Cyclotomic Cosets
Last time we looked at matrix methods and how they can be used to analyze two important aspects of LFSRs:
- time shifts
- state recovery from LFSR output
In both cases we were able to use a finite field or bitwise approach to arrive at the same result as a matrix-based approach. The matrix approach is more expensive in terms of execution time and memory storage, but in some cases is conceptually simpler.
This article will be covering some concepts that are useful for studying the...
Number Theory for Codes
Everything in the digital world is encoded. ASCII and Unicode are combinations of bits which have specific meanings to us. If we try to interpret a compiled program as Unicode, the result is a lot of garbage (and beeps!) To reduce errors in transmissions over radio links we use Error Correction Codes so that even when bits are lost we can recover the ASCII or Unicode original. To prevent anyone from understanding a transmission we can encrypt the raw data...
A Second Look at Slew Rate Limiters
I recently had to pick a slew rate for a current waveform, and I got this feeling of déjà vu… hadn’t I gone through this effort already? So I looked, and lo and behold, way back in 2014 I wrote an article titled Slew Rate Limiters: Nonlinear and Proud of It! where I explored the effects of two types of slew rate limiters, one feedforward and one feedback, given a particular slew rate \( R \).
Here was one figure I published at the time:
This...
Polynomial Math
Elliptic Curve Cryptography is used as a public key infrastructure to secure credit cards, phones and communications links. All these devices use either FPGA's or embedded microprocessors to compute the algorithms that make the mathematics work. While the math is not hard, it can be confusing the first time you see it. This blog is an introduction to the operations of squaring and computing an inverse over a finite field which are used in computing Elliptic Curve arithmetic. ...
Return of the Delta-Sigma Modulators, Part 1: Modulation
About a decade ago, I wrote two articles:
- Modulation Alternatives for the Software Engineer (November 2011)
- Isolated Sigma-Delta Modulators, Rah Rah Rah! (April 2013)
Each of these are about delta-sigma modulation, but they’re short and sweet, and not very in-depth. And the 2013 article was really more about analog-to-digital converters. So we’re going to revisit the subject, this time with a lot more technical depth — in fact, I’ve had to split this...
