## 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 called libgf2,...

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

## Ten Little Algorithms, Part 6: Green’s Theorem and Swept-Area Detection

Other articles in this series:

## Donald Knuth Is the Root of All Premature Optimization

TL;DR

The idea, basically, is that even though optimization of computer software to execute faster is a noble goal, with tangible benefits, this costs time and effort up front, and therefore the decision to do so should not be made on whims and intuition, but instead should be made after some kind of analysis to show that it has net...

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

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

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

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

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

## Padé Delay is Okay Today

This article is going to be somewhat different in that I’m not really writing it for the typical embedded systems engineer. Rather it’s kind of a specialized topic, so don’t be surprised if you get bored and move on to something else. That’s fine by me.

Anyway, let’s just jump ahead to the punchline. Here’s a numerical simulation of a step response to a $p=126, q=130$ Padé approximation of a time delay:

Impressed? Maybe you should be. This...

## The CRC Wild Goose Chase: PPP Does What?!?!?!

I got a bad feeling yesterday when I had to include reference information about a 16-bit CRC in a serial protocol document I was writing. And I knew it wasn’t going to end well.

The last time I looked into CRC algorithms was about five years ago. And the time before that… sometime back in 2004 or 2005? It seems like it comes up periodically, like the seventeen-year locust or sunspots or El Niño,...

## Second-Order Systems, Part I: Boing!!

I’ve already written about the unexciting (but useful) 1st-order system, and about slew-rate limiting. So now it’s time to cover second-order systems.

The most common second-order systems are RLC circuits and spring-mass-damper systems.

Spring-mass-damper systems are fairly common; you’ve seen these before, whether you realize it or not. One household example of these is the spring doorstop (BOING!!):

(For what it’s worth: the spring...

## 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 “

## First-Order Systems: The Happy Family

May 3, 20141 comment
Все счастли́вые се́мьи похо́жи друг на дру́га, ка́ждая несчастли́вая семья́ несчастли́ва по-сво́ему.

— Лев Николаевич Толстой, Анна Каренина

Happy families are all alike; every unhappy family is unhappy in its own way.

— Lev Nicholaevich Tolstoy, Anna Karenina

I was going to write an article about second-order systems, but then realized that it would be...

## Signal Processing Contest in Python (PREVIEW): The Worst Encoder in the World

When I posted an article on estimating velocity from a position encoder, I got a number of responses. A few of them were of the form "Well, it's an interesting article, but at slow speeds why can't you just take the time between the encoder edges, and then...." My point was that there are lots of people out there which take this approach, and don't take into account that the time between encoder edges varies due to manufacturing errors in the encoder. For some reason this is a hard concept...