The 2024 Embedded Online Conference

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

Linear Feedback Shift Registers for the Uninitiated, Part XI: Pseudorandom Number Generation

Jason Sachs December 20, 2017

Last time we looked at the use of LFSRs in counters and position encoders.

This time we’re going to look at pseudorandom number generation, and why you may — or may not — want to use LFSRs for this purpose.

But first — an aside:

Science Fair 1983

When I was in fourth grade, my father bought a Timex/Sinclair 1000. This was one of several personal computers introduced in 1982, along with the Commodore 64. The...

Linear Feedback Shift Registers for the Uninitiated, Part X: Counters and Encoders

Jason Sachs December 9, 2017

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.


I 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

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, 20174 comments

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, 20171 comment

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, 20171 comment

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, 20174 comments

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

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?


Byte and Switch (Part 2)

Jason Sachs May 7, 20118 comments

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

Supply Chain Games: What Have We Learned From the Great Semiconductor Shortage of 2021? (Part 2)

Jason Sachs June 18, 20223 comments

Welcome back! Today we’re going to zoom around again in some odd directions, and give a roundabout introduction to the semiconductor industry, touching on some of the following questions:

  • How do semiconductors get designed and manufactured?
  • What is the business of semiconductor manufacturing like?
  • What are the different types of semiconductors, and how does that affect the business model of these manufacturers?
  • How has the semiconductor industry evolved over...

The Least Interesting Circuit in the World

Jason Sachs October 7, 20185 comments

It does nothing, most of the time.

It cannot compute pi. It won’t oscillate. It doesn’t light up.

Often it makes other circuits stop working.

It is… the least interesting circuit in the world.

What is it?

About 25 years ago, I took a digital computer architecture course, and we were each given use of an ugly briefcase containing a bunch of solderless breadboards and a power supply and switches and LEDs — and a bunch of

Ten Little Algorithms, Part 4: Topological Sort

Jason Sachs July 5, 20151 comment

Other articles in this series:

Today we’re going to take a break from my usual focus on signal processing or numerical algorithms, and focus on...

Important Programming Concepts (Even on Embedded Systems) Part II: Immutability

Jason Sachs September 14, 20141 comment

Other articles in this series:

This article will discuss immutability, and some of its variations in the topic of functional programming.

There are a whole series of benefits to using program variables that… well, that aren’t actually variable, but instead are immutable. The impact of...

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

Slew Rate Limiters: Nonlinear and Proud of It!

Jason Sachs October 6, 2014

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

Another 10 Circuit Components You Should Know

Jason Sachs October 30, 20131 comment

It's that time again to review all the oddball goodies available in electronic components. These are things you should have in your bag of tricks when you need to design a circuit board. If you read my previous posts and were looking forward to more, this article's for you!

1. Bus switches

I can't believe I haven't mentioned bus switches before. What is a bus switch?

There are lots of different options for switches:

  • mechanical switch / relay: All purpose, two...

Ten Little Algorithms, Part 5: Quadratic Extremum Interpolation and Chandrupatla's Method

Jason Sachs November 11, 20159 comments

Today we will be drifting back into the topic of numerical methods, and look at an algorithm that takes in a series of discretely-sampled data points, and estimates the maximum value of the waveform they were sampled from.

The 2024 Embedded Online Conference