Linear Feedback Shift Registers for the Uninitiated, Part X: Counters and Encoders
Last time we looked at LFSR output decimation and the computation of trace parity.
Today we are starting to look in detail at some applications of LFSRs, namely counters and encoders.
CountersI mentioned counters briefly in the article on easy discrete logarithms. The idea here is that the propagation delay in an LFSR is smaller than in a counter, since the logic to compute the next LFSR state is simpler than in an ordinary counter. All you need to construct an LFSR is
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...
Linear Feedback Shift Registers for the Uninitiated, Part VIII: Matrix Methods and State Recovery
Last time we looked at a dsPIC implementation of LFSR updates. Now we’re going to go back to basics and look at some matrix methods, which is the third approach to represent LFSRs that I mentioned in Part I. And we’re going to explore the problem of converting from LFSR output to LFSR state.
Matrices: Beloved Historical DregsElwyn Berlekamp’s 1966 paper Non-Binary BCH Encoding covers some work on
Linear Feedback Shift Registers for the Uninitiated, Part VII: LFSR Implementations, Idiomatic C, and Compiler Explorer
The last four articles were on algorithms used to compute with finite fields and shift registers:
- multiplicative inverse
- discrete logarithm
- determining characteristic polynomial from the LFSR output
Today we’re going to come back down to earth and show how to implement LFSR updates on a microcontroller. We’ll also talk a little bit about something called “idiomatic C” and a neat online tool for experimenting with the C compiler.
Lazy Properties in Python Using Descriptors
This is a bit of a side tangent from my normal at-least-vaguely-embedded-related articles, but I wanted to share a moment of enlightenment I had recently about descriptors in Python. The easiest way to explain a descriptor is a way to outsource attribute lookup and modification.
Python has a bunch of “magic” methods that are hooks into various object-oriented mechanisms that let you do all sorts of ridiculously clever things. Whether or not they’re a good idea is another...
Linear Feedback Shift Registers for the Uninitiated, Part VI: Sing Along with the Berlekamp-Massey Algorithm
The last two articles were on discrete logarithms in finite fields — in practical terms, how to take the state \( S \) of an LFSR and its characteristic polynomial \( p(x) \) and figure out how many shift steps are required to go from the state 000...001 to \( S \). If we consider \( S \) as a polynomial bit vector such that \( S = x^k \bmod p(x) \), then this is equivalent to the task of figuring out \( k \) from \( S \) and \( p(x) \).
This time we’re tackling something...
Linear Feedback Shift Registers for the Uninitiated, Part V: Difficult Discrete Logarithms and Pollard's Kangaroo Method
Last time we talked about discrete logarithms which are easy when the group in question has an order which is a smooth number, namely the product of small prime factors. Just as a reminder, the goal here is to find \( k \) if you are given some finite multiplicative group (or a finite field, since it has a multiplicative group) with elements \( y \) and \( g \), and you know you can express \( y = g^k \) for some unknown integer \( k \). The value \( k \) is the discrete logarithm of \( y \)...
Linear Feedback Shift Registers for the Uninitiated, Part IV: Easy Discrete Logarithms and the Silver-Pohlig-Hellman Algorithm
Last time we talked about the multiplicative inverse in finite fields, which is rather boring and mundane, and has an easy solution with Blankinship’s algorithm.
Discrete logarithms, on the other hand, are much more interesting, and this article covers only the tip of the iceberg.
What is a Discrete Logarithm, Anyway?Regular logarithms are something that you’re probably familiar with: let’s say you have some number \( y = b^x \) and you know \( y \) and \( b \) but...
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...
Linear Feedback Shift Registers for the Uninitiated, Part II: libgf2 and Primitive Polynomials
Last time, we looked at the basics of LFSRs and finite fields formed by the quotient ring \( GF(2)[x]/p(x) \).
LFSRs can be described by a list of binary coefficients, sometimes referred as the polynomial, since they correspond directly to the characteristic polynomial of the quotient ring.
Today we’re going to look at how to perform certain practical calculations in these finite fields. I maintain a Python library on bitbucket called...
R1C1R2C2: The Two-Pole Passive RC Filter
I keep running into this circuit every year or two, and need to do the same old calculations, which are kind of tiring. So I figured I’d just write up an article and then I can look it up the next time.
This is a two-pole passive RC filter. Doesn’t work as well as an LC filter or an active filter, but it is cheap. We’re going to find out a couple of things about its transfer function.
First let’s find out the transfer function of this circuit:
Not very...
Byte and Switch (Part 1)
Imagine for a minute you have an electromagnet, and a microcontroller, and you want to use the microcontroller to turn the electromagnet on and off. Sounds pretty typical, right?We ask this question on our interviews of entry-level electrical engineers: what do you put between the microcontroller and the electromagnet?We used to think this kind of question was too easy, but there are a surprising number of subtleties here (and maybe a surprising number of job candidates that were missing...
Lost Secrets of the H-Bridge, Part IV: DC Link Decoupling and Why Electrolytic Capacitors Are Not Enough
Those of you who read my earlier articles about H-bridges, and followed them closely, have noticed there's some unfinished business. Well, here it is. Just so you know, I've been nervous about writing the fourth (and hopefully final) part of this series for a while. Fourth installments after a hiatus can bring bad vibes. I mean, look what it did to George Lucas: now we have Star Wars Episode I: The Phantom Menace and
How to Build a Fixed-Point PI Controller That Just Works: Part II
In Part I we talked about some of the issues around discrete-time proportional-integral (PI) controllers:
- various forms and whether to use the canonical form for z-transforms (don't do it!)
- order of operation in the integral term: whether to scale and then integrate (my recommendation), or integrate and then scale.
- saturation and anti-windup
In this part we'll talk about the issues surrounding fixed-point implementations of PI controllers. First let's recap the conceptual structure...
Lessons Learned from Embedded Code Reviews (Including Some Surprises)
My software team recently finished a round of code reviews for some of our motor controller code. I learned a lot from the experience, most notably why you would want to have code reviews in the first place.
My background is originally from the medical device industry. In the United States, software in medical devices gets a lot of scrutiny from the Food and Drug Administration, and for good reason; it’s a place for complexity to hide latent bugs. (Can you say “
Linear Feedback Shift Registers for the Uninitiated, Part I: Ex-Pralite Monks and Finite Fields
Later there will be, I hope, some people who will find it to their advantage to decipher all this mess.
— Évariste Galois, May 29, 1832
I was going to call this short series of articles “LFSRs for Dummies”, but thought better of it. What is a linear feedback shift register? If you want the short answer, the Wikipedia article is a decent introduction. But these articles are aimed at those of you who want a little bit deeper mathematical understanding,...
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:
10 Circuit Components You Should Know
Chefs have their miscellaneous ingredients, like condensed milk, cream of tartar, and xanthan gum. As engineers, we too have quite our pick of circuits, and a good circuit designer should know what's out there. Not just the bread and butter ingredients like resistors, capacitors, op-amps, and comparators, but the miscellaneous "gadget" components as well.
Here are ten circuit components you may not have heard of, but which are occasionally quite useful.
1. Multifunction gate (
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...
Scorchers, Part 3: Bare-Metal Concurrency With Double-Buffering and the Revolving Fireplace
This is a short article about one technique for communicating between asynchronous processes on bare-metal embedded systems.
Q: Why did the multithreaded chicken cross the road?
A: to To other side. get the
There are many reasons why concurrency is
Lost Secrets of the H-Bridge, Part IV: DC Link Decoupling and Why Electrolytic Capacitors Are Not Enough
Those of you who read my earlier articles about H-bridges, and followed them closely, have noticed there's some unfinished business. Well, here it is. Just so you know, I've been nervous about writing the fourth (and hopefully final) part of this series for a while. Fourth installments after a hiatus can bring bad vibes. I mean, look what it did to George Lucas: now we have Star Wars Episode I: The Phantom Menace and
Which MOSFET topology?
A recent electronics.StackExchange question brings up a good topic for discussion. Let's say you have a power supply and a 2-wire load you want to be able to switch on and off from the power supply using a MOSFET. How do you choose which circuit topology to choose? You basically have four options, shown below:
From left to right, these are:
High-side switch, N-channel MOSFET High-side switch, P-channel MOSFET Low-side switch, N-channel...How to Build a Fixed-Point PI Controller That Just Works: Part II
In Part I we talked about some of the issues around discrete-time proportional-integral (PI) controllers:
- various forms and whether to use the canonical form for z-transforms (don't do it!)
- order of operation in the integral term: whether to scale and then integrate (my recommendation), or integrate and then scale.
- saturation and anti-windup
In this part we'll talk about the issues surrounding fixed-point implementations of PI controllers. First let's recap the conceptual structure...
Important Programming Concepts (Even on Embedded Systems) Part IV: Singletons
Other articles in this series:
- Part I: Idempotence
- Part II: Immutability
- Part III: Volatility
- Part V: State Machines
- Part VI: Abstraction
Today’s topic is the singleton. This article is unique (pun intended) in that unlike the others in this series, I tried to figure out a word to use that would be a positive concept to encourage, as an alternative to singletons, but
Round Round Get Around: Why Fixed-Point Right-Shifts Are Just Fine
Today’s topic is rounding in embedded systems, or more specifically, why you don’t need to worry about it in many cases.
One of the issues faced in computer arithmetic is that exact arithmetic requires an ever-increasing bit length to avoid overflow. Adding or subtracting two 16-bit integers produces a 17-bit result; multiplying two 16-bit integers produces a 32-bit result. In fixed-point arithmetic we typically multiply and shift right; for example, if we wanted to multiply some...
Lost Secrets of the H-Bridge, Part III: Practical Issues of Inductor and Capacitor Ripple Current
We've been analyzing the ripple current in an H-bridge, both in an inductive load and the DC link capacitor. Here's a really quick recap; if you want to get into more details, go back and read part I and part II until you've got equations coming out of your ears. I promise there will be a lot less grungy math in this post. So let's get most of it out of the way:
Switches QAH and QAL are being turned on and off with pulse-width modulation (PWM), to produce an average voltage DaVdc on...
Two Capacitors Are Better Than One
I was looking for a good reference for some ADC-driving circuits, and ran across this diagram in Walt Jung’s Op-Amp Applications Handbook:
And I smiled to myself, because I immediately remembered a circuit I hadn’t used for years. Years! But it’s something you should file away in your bag of tricks.
Take a look at the RC-RC circuit formed by R1, R2, C1, and C2. It’s basically a stacked RC low-pass filter. The question is, why are there two capacitors?
I...
Byte and Switch (Part 2)
In part 1 we talked about the use of a MOSFET for a power switch. Here's a different circuit that also uses a MOSFET, this time as a switch for signals:
We have a thermistor Rth that is located somewhere in an assembly, that connects to a circuit board. This acts as a variable resistor that changes with temperature. If we use it in a voltage divider, the midpoint of the voltage divider has a voltage that depends on temperature. Resistors R3 and R4 form our reference resistance; when...
Ten Little Algorithms, Part 4: Topological Sort
Other articles in this series:
- Part 1: Russian Peasant Multiplication
- Part 2: The Single-Pole Low-Pass Filter
- Part 3: Welford's Method (And Friends)
- Part 5: Quadratic Extremum Interpolation and Chandrupatla's Method
- Part 6: Green’s Theorem and Swept-Area Detection
Today we’re going to take a break from my usual focus on signal processing or numerical algorithms, and focus on...
Lazy Properties in Python Using Descriptors
This is a bit of a side tangent from my normal at-least-vaguely-embedded-related articles, but I wanted to share a moment of enlightenment I had recently about descriptors in Python. The easiest way to explain a descriptor is a way to outsource attribute lookup and modification.
Python has a bunch of “magic” methods that are hooks into various object-oriented mechanisms that let you do all sorts of ridiculously clever things. Whether or not they’re a good idea is another...
