Linear Feedback Shift Registers for the Uninitiated, Part IX: Decimation, Trace Parity, and Cyclotomic Cosets

Jason Sachs December 3, 2017

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

Jason Sachs November 21, 2017

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 Dregs

Elwyn 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

Jason Sachs November 13, 2017

The last four articles were on algorithms used to compute with finite fields and shift registers:

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

Jason Sachs November 7, 2017

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

Jason Sachs October 18, 2017

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

Jason Sachs October 1, 2017

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

Jason Sachs September 16, 2017

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

Jason Sachs September 9, 2017

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

Jason Sachs July 17, 2017

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...


Linear Feedback Shift Registers for the Uninitiated, Part I: Ex-Pralite Monks and Finite Fields

Jason Sachs July 3, 20174 comments

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,...


Byte and Switch (Part 1)

Jason Sachs April 26, 201112 comments

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...


Zebras Hate You For No Reason: Why Amdahl's Law is Misleading in a World of Cats (And Maybe in Ours Too)

Jason Sachs February 27, 20171 comment

I’ve been wasting far too much of my free time lately on this stupid addicting game called the Kittens Game. It starts so innocently. You are a kitten in a catnip forest. Gather catnip.

And you click on Gather catnip and off you go. Soon you’re hunting unicorns and building Huts and studying Mathematics and Theology and so on. AND IT’S JUST A TEXT GAME! HTML and Javascript, that’s it, no pictures. It’s an example of an


Analog-to-Digital Confusion: Pitfalls of Driving an ADC

Jason Sachs November 19, 20115 comments

Imagine the following scenario:You're a successful engineer (sounds nice, doesn't it!) working on a project with three or four circuit boards. More than even you can handle, so you give one of them over to your coworker Wayne to design. Wayne graduated two years ago from college. He's smart, he's a quick learner, and he's really fast at designing schematics and laying out circuit boards. It's just that sometimes he takes some shortcuts... but in this case the circuit board is just something...


Ten Little Algorithms, Part 1: Russian Peasant Multiplication

Jason Sachs March 21, 20155 comments

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:

Important Programming Concepts (Even on Embedded Systems) Part V: State Machines

Jason Sachs January 5, 20158 comments

Other articles in this series:

Oh, hell, this article just had to be about state machines, didn’t it? State machines! Those damned little circles and arrows and q’s.

Yeah, I know you don’t like them. They bring back bad memories from University, those Mealy and Moore machines with their state transition tables, the ones you had to write up...


Help, My Serial Data Has Been Framed: How To Handle Packets When All You Have Are Streams

Jason Sachs December 11, 201110 comments

Today we're going to talk about data framing and something called COBS, which will make your life easier the next time you use serial communications on an embedded system -- but first, here's a quiz:

Quick Diversion, Part I: Which of the following is the toughest area of electrical engineering? analog circuit design digital circuit design power electronics communications radiofrequency (RF) circuit design electromagnetic...

Understanding and Preventing Overflow (I Had Too Much to Add Last Night)

Jason Sachs December 4, 2013

Happy Thanksgiving! Maybe the memory of eating too much turkey is fresh in your mind. If so, this would be a good time to talk about overflow.

In the world of floating-point arithmetic, overflow is possible but not particularly common. You can get it when numbers become too large; IEEE double-precision floating-point numbers support a range of just under 21024, and if you go beyond that you have problems:

for k in [10, 100, 1000, 1020, 1023, 1023.9, 1023.9999, 1024]: try: ...

How to Build a Fixed-Point PI Controller That Just Works: Part I

Jason Sachs February 26, 20127 comments

This two-part article explains five tips to make a fixed-point PI controller work well. I am not going to talk about loop tuning -- there are hundreds of articles and books about that; any control-systems course will go over loop tuning enough to help you understand the fundamentals. There will always be some differences for each system you have to control, but the goals are the same: drive the average error to zero, keep the system stable, and maximize performance (keep overshoot and delay...


Which MOSFET topology?

Jason Sachs September 1, 20119 comments

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...

Two Capacitors Are Better Than One

Jason Sachs February 15, 20155 comments

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...