Linear Feedback Shift Registers for the Uninitiated, Part XVIII: Primitive Polynomial Generation

Jason Sachs August 6, 20182 comments

Last time we figured out how to reverse-engineer parameters of an unknown CRC computation by providing sample inputs and analyzing the corresponding outputs. One of the things we discovered was that the polynomial \( x^{16} + x^{12} + x^5 + 1 \) used in the 16-bit X.25 CRC is not primitive — which just means that all the nonzero elements in the corresponding quotient ring can’t be generated by powers of \( x \), and therefore the corresponding 16-bit LFSR with taps in bits 0, 5,...


R1C1R2C2: The Two-Pole Passive RC Filter

Jason Sachs July 28, 20181 comment

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


Linear Feedback Shift Registers for the Uninitiated, Part XVII: Reverse-Engineering the CRC

Jason Sachs July 7, 20181 comment

Last time, we continued a discussion about error detection and correction by covering Reed-Solomon encoding. I was going to move on to another topic, but then there was this post on Reddit asking how to determine unknown CRC parameters:

I am seeking to reverse engineer an 8-bit CRC. I don’t know the generator code that’s used, but can lay my hands on any number of output sequences given an input sequence.

This is something I call the “unknown oracle”...


Linear Feedback Shift Registers for the Uninitiated, Part XVI: Reed-Solomon Error Correction

Jason Sachs June 19, 2018

Last time, we talked about error correction and detection, covering some basics like Hamming distance, CRCs, and Hamming codes. If you are new to this topic, I would strongly suggest going back to read that article before this one.

This time we are going to cover Reed-Solomon codes. (I had meant to cover this topic in Part XV, but the article was getting to be too long, so I’ve split it roughly in half.) These are one of the workhorses of error-correction, and they are used in...


Linear Feedback Shift Registers for the Uninitiated, Part XV: Error Detection and Correction

Jason Sachs June 12, 2018

Last time, we talked about Gold codes, a specially-constructed set of pseudorandom bit sequences (PRBS) with low mutual cross-correlation, which are used in many spread-spectrum communications systems, including the Global Positioning System.

This time we are wading into the field of error detection and correction, in particular CRCs and Hamming codes.

Ernie, You Have a Banana in Your Ear

I have had a really really tough time writing this article. I like the...


Linear Regression with Evenly-Spaced Abscissae

Jason Sachs May 1, 20181 comment

What a boring title. I wish I could come up with something snazzier. One word I learned today is studentization, which is just the normalization of errors in a curve-fitting exercise by the sample standard deviation (e.g. point \( x_i \) is \( 0.3\hat{\sigma} \) from the best-fit linear curve, so \( \frac{x_i - \hat{x}_i}{\hat{\sigma}} = 0.3 \)) — Studentize me! would have been nice, but I couldn’t work it into the topic for today. Oh well.

I needed a little break from...


Linear Feedback Shift Registers for the Uninitiated, Part XIV: Gold Codes

Jason Sachs April 18, 2018

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


Linear Feedback Shift Registers for the Uninitiated, Part XIII: System Identification

Jason Sachs March 12, 20181 comment

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


A Wish for Things That Work

Jason Sachs January 1, 20182 comments

As the end of the year approaches, I become introspective. This year I am frustrated by bad user interfaces in software.

Actually, every year, throughout the year, I am frustrated by bad user interfaces in software. And yet here it is, the end of 2017, and things aren’t getting much better! Argh!

I wrote about this sort of thing a bit back in 2011 (“Complexity in Consumer Electronics Considered Harmful”) but I think it’s time to revisit the topic. So I’m...


Linear Feedback Shift Registers for the Uninitiated, Part XII: Spread-Spectrum Fundamentals

Jason Sachs December 29, 20171 comment

Last time we looked at the use of LFSRs for pseudorandom number generation, or PRNG, and saw two things:

  • the use of LFSR state for PRNG has undesirable serial correlation and frequency-domain properties
  • the use of single bits of LFSR output has good frequency-domain properties, and its autocorrelation values are so close to zero that they are actually better than a statistically random bit stream

The unusually-good correlation properties...


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


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

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


10 Circuit Components You Should Know

Jason Sachs November 27, 20112 comments

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 (


Byte and Switch (Part 1)

Jason Sachs April 26, 201114 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...


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


Ten Little Algorithms, Part 1: Russian Peasant Multiplication

Jason Sachs March 21, 20156 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:

How to Estimate Encoder Velocity Without Making Stupid Mistakes: Part II (Tracking Loops and PLLs)

Jason Sachs November 17, 201312 comments

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