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

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

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

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

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

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

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

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

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

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

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

## 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 4: Topological Sort

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

## The Least Interesting Circuit in the World

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

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

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

## Another 10 Circuit Components You Should Know

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

## Slew Rate Limiters: Nonlinear and Proud of It!

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

## Oscilloscope Dreams

My coworkers and I recently needed a new oscilloscope. I thought I would share some of the features I look for when purchasing one.

When I was in college in the early 1990's, our oscilloscopes looked like this:

Now the cathode ray tubes have almost all been replaced by digital storage scopes with color LCD screens, and they look like these:

Oscilloscopes are basically just fancy expensive boxes for graphing voltage vs. time. They span a wide range of features and prices:...

## Development of the MOS Technology 6502: A Historical Perspective

One ubiquitous microprocessor of the late 1970s and 1980s was the MOS Technology MCS 6502. I included a section on the development of the 6502 in Part 2 of Supply Chain Games, and have posted it as an excerpt here, as I believe it is deserving in its own right.

(Note: MOS Technology is pronounced with the individual letters M-O-S “em oh ess”,[1] not “moss”, and should not be confused with another semiconductor company,