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

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

## A Wish for Things That Work

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 XI: Pseudorandom Number Generation

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 1983When 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

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.

CountersI 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

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

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

- multiplicative inverse
- discrete logarithm
- determining characteristic polynomial from the LFSR output

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

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

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

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 XVII: Reverse-Engineering the CRC

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

## Lazy Properties in Python Using Descriptors

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

## My Love-Hate Relationship with Stack Overflow: Arthur S., Arthur T., and the Soup Nazi

Warning: In the interest of maintaining a coherent stream of consciousness, I’m lowering the setting on my profanity filter for this post. Just wanted to let you know ahead of time.

I’ve been a user of Stack Overflow since December of 2008. And I say “user” both in the software sense, and in the drug-addict sense. I’m Jason S, user #44330, and I’m a programming addict. (Hi, Jason S.) The Gravatar, in case you were wondering, is a screen...

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

## Basic hand tools for electronics assembly

Though the software tools vary with different microcontrollers, many hardware tools are the same.

If you are working on larger robotic or automotive systems, you will need a 3/8" and 1/2" drive socket set. There are occasions when even larger drive socket sets are needed. For small robots and taking things apart, the 1/4" drive socket set is useful. The sizes usually range from 5/32" to 9/16" and 4mm to 15mm. You will need both shallow and deep sockets, both standard and...

## How to Include MathJax Equations in SVG With Less Than 100 Lines of JavaScript!

Today’s short and tangential note is an account of how I dug myself out of Documentation Despair. I’ve been working on some block diagrams. You know, this sort of thing, to describe feedback control systems:

And I had a problem. How do I draw diagrams like this?

I don’t have Visio and I don’t like Visio. I used to like Visio. But then it got Microsofted.

I can use MATLAB and Simulink, which are great for drawing block diagrams. Normally you use them to create a...

## Linear Feedback Shift Registers for the Uninitiated, Part VII: LFSR Implementations, Idiomatic C, and Compiler Explorer

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

- multiplicative inverse
- discrete logarithm
- determining characteristic polynomial from the LFSR output

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.

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

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 1983When 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 III: Multiplicative Inverse, and Blankinship's Algorithm

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

## Levitating Globe Teardown, Part 2

Part 1 of this article was really more of an extended (and cynical) product review. In this part of the article, I actually take things apart (sometimes a bit more suddenly than I meant to) and show you some innards.First the globe. I knew there was a magnet in there someplace, because it's obviously plastic and it also attracts metal. I had intended to gently part the globe at the glue bond along the equator. I started by trying to gently flex the thing on my work...

## My Love-Hate Relationship with Stack Overflow: Arthur S., Arthur T., and the Soup Nazi

Warning: In the interest of maintaining a coherent stream of consciousness, I’m lowering the setting on my profanity filter for this post. Just wanted to let you know ahead of time.

I’ve been a user of Stack Overflow since December of 2008. And I say “user” both in the software sense, and in the drug-addict sense. I’m Jason S, user #44330, and I’m a programming addict. (Hi, Jason S.) The Gravatar, in case you were wondering, is a screen...

## Levitating Globe Teardown, Part 2

Part 1 of this article was really more of an extended (and cynical) product review. In this part of the article, I actually take things apart (sometimes a bit more suddenly than I meant to) and show you some innards.First the globe. I knew there was a magnet in there someplace, because it's obviously plastic and it also attracts metal. I had intended to gently part the globe at the glue bond along the equator. I started by trying to gently flex the thing on my work...

## Basic hand tools for electronics assembly

Though the software tools vary with different microcontrollers, many hardware tools are the same.

If you are working on larger robotic or automotive systems, you will need a 3/8" and 1/2" drive socket set. There are occasions when even larger drive socket sets are needed. For small robots and taking things apart, the 1/4" drive socket set is useful. The sizes usually range from 5/32" to 9/16" and 4mm to 15mm. You will need both shallow and deep sockets, both standard and...

## How to Include MathJax Equations in SVG With Less Than 100 Lines of JavaScript!

Today’s short and tangential note is an account of how I dug myself out of Documentation Despair. I’ve been working on some block diagrams. You know, this sort of thing, to describe feedback control systems:

And I had a problem. How do I draw diagrams like this?

I don’t have Visio and I don’t like Visio. I used to like Visio. But then it got Microsofted.

I can use MATLAB and Simulink, which are great for drawing block diagrams. Normally you use them to create a...

## Tenderfoot: Embedded Software and Firmware Specialties

Once upon a time (seven years ago) I answered a question on Stack Overflow. Then Stephane suggested I turn that answer into a blog post. Great idea! This post dives deeper into the original question: “Is it possible to fragment this field (embedded software and firmware) into sub-fields?”

This post represents a detailed and updated response to my original Stack Overflow answer. I hope this post provides guidance and useful information to the “tenderfoots” in the...

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

## Levitating Globe Teardown, Part 1

I've been kicking some ideas around for a long time for a simple and inexpensive platform I could use for control systems experimentation for the beginner. I want something that can be controlled easily in a basic fashion, yet that provides some depth: I want to be able to present ever-more challenging goals to the student, that can be attained by fancier control algorithms all on the same device.

I'm currently looking at magnetic levitation. It's fun, it has the potential to be...

## Lazy Properties in Python Using Descriptors

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

## Oh Robot My Robot

Oh Robot! My Robot! You’ve broken off your nose! Your head is spinning round and round, your eye no longer glows, Each program after program tapped your golden memory, You used to have 12K, now there is none that I can see, Under smoldering antennae, Over long forgotten feet, My sister used your last part: The chip she tried to eat.

Oh Robot, My Robot, the remote controls—they call, The call—for...

## Margin Call: Fermi Problems, Highway Horrors, Black Swans, and Why You Should Worry About When You Should Worry

“Reports that say that something hasn’t happened are always interesting to me, because as we know, there are known knowns; there are things we know that we know. There are known unknowns; that is to say, there are things that we now know we don’t know. But there are also unknown unknowns — there are things we do not know we don’t know.” — Donald Rumsfeld, February 2002

Today’s topic is engineering margin.

XKCD had a what-if column involving Fermi...