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


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


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

Jason Sachs June 18, 20173 comments

Other articles in this series:

This article is mainly an excuse to scribble down some cryptic-looking mathematics — Don’t panic! Close your eyes and scroll down if you feel nauseous — and...


From Baremetal to RTOS: A review of scheduling techniques

Jacob Beningo June 8, 201617 comments

Transitioning from bare-metal embedded software development to a real-time operating system (RTOS) can be a difficult endeavor. Many developers struggle with the question of whether they should use an RTOS or simply use a bare-metal scheduler. One of the goals of this series is to walk developers through the transition and decision making process of abandoning bare-metal thinking and getting up to speed quickly with RTOSes. Before diving into the details of RTOSes, the appropriate first step...


Data Types for Control & DSP

Tim Wescott April 26, 20166 comments

There's a lot of information out there on what data types to use for digital signal processing, but there's also a lot of confusion, so the topic bears repeating.

I recently posted an entry on PID control. In that article I glossed over the data types used by showing "double" in all of my example code.  Numerically, this should work for most control problems, but it can be an extravagant use of processor resources.  There ought to be a better way to determine what precision you need...


Ten Little Algorithms, Part 2: The Single-Pole Low-Pass Filter

Jason Sachs April 27, 201516 comments

Other articles in this series:

I’m writing this article in a room with a bunch of other people talking, and while sometimes I wish they would just SHUT UP, it would be...


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:

From Baremetal to RTOS: A review of scheduling techniques

Jacob Beningo June 8, 201617 comments

Transitioning from bare-metal embedded software development to a real-time operating system (RTOS) can be a difficult endeavor. Many developers struggle with the question of whether they should use an RTOS or simply use a bare-metal scheduler. One of the goals of this series is to walk developers through the transition and decision making process of abandoning bare-metal thinking and getting up to speed quickly with RTOSes. Before diving into the details of RTOSes, the appropriate first step...


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


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

Jason Sachs November 11, 20159 comments

Other articles in this series:

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


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

Jason Sachs June 18, 20173 comments

Other articles in this series:

This article is mainly an excuse to scribble down some cryptic-looking mathematics — Don’t panic! Close your eyes and scroll down if you feel nauseous — and...


Practical CRCs for Embedded Systems

Stephen Friederichs October 20, 20157 comments

CRCs are a very practical tool for embedded systems: you're likely to need to use one as part of a communications protocol or to verify the integrity of a program image before writing it to flash. But CRCs can be difficult to understand and tricky to implement. The first time I attempted to write CRC code from scratch I failed once. Then twice. Then three times. Eventually I gave up and used an existing library. I consider myself intelligent: I got A's...


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

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


Elliptic Curve Cryptography

Mike November 16, 20156 comments

Secure online communications require encryption.  One standard is AES (Advanced Encryption Standard) from NIST.  But for this to work, both sides need the same key for encryption and decryption.  This is called Private Key encryption.  Public Key encryption is used to create a private key between two sides that have not previously communicated.  Compared to the history of encryption, Public Key methods are very recent having been started in the 1970's.  Elliptic...