Linear Feedback Shift Registers for the Uninitiated, Part XV: Error Detection and Correction

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

Linear Regression with Evenly-Spaced Abscissae

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 XIV: Gold Codes

April 18, 2018

Last time we looked at some techniques using LFSR output for system identification, making use of the peculiar autocorrelation properties of pseudorandom bit sequences (PRBS) derived from an LFSR.

This time we’re going to jump back to the field of communications, to look at an invention called Gold codes and why a single maximum-length PRBS isn’t enough to save the world using spread-spectrum technology. We have to cover two little side discussions before we can get into Gold...

Linear Feedback Shift Registers for the Uninitiated, Part XIII: System Identification

March 12, 20181 comment

Last time we looked at spread-spectrum techniques using the output bit sequence of an LFSR as a pseudorandom bit sequence (PRBS). The main benefit we explored was increasing signal-to-noise ratio (SNR) relative to other disturbance signals in a communication system.

This time we’re going to use a PRBS from LFSR output to do something completely different: system identification. We’ll show two different methods of active system identification, one using sine waves and the other...

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 XII: Spread-Spectrum Fundamentals

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

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

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

Counters

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

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

November 21, 2017

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

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

Adventures in Signal Processing with Python

Author’s note: This article was originally called Adventures in Signal Processing with Python (MATLAB? We don’t need no stinkin' MATLAB!) — the allusion to The Treasure of the Sierra Madre has been removed, in deference to being a good neighbor to The MathWorks. While I don’t make it a secret of my dislike of many aspects of MATLAB — which I mention later in this article — I do hope they can improve their software and reduce the price. Please note this...

How to Estimate Encoder Velocity Without Making Stupid Mistakes: Part I

Here's a common problem: you have a quadrature encoder to measure the angular position of a motor, and you want to know both the position and the velocity. How do you do it? Some people do it poorly -- this article is how not to be one of them.

Well, first we need to get position. Quadrature encoders are incremental encoders, meaning they can only measure relative changes in position. They produce a pair of pulse trains, commonly called A and B, that look like...

Chebyshev Approximation and How It Can Help You Save Money, Win Friends, and Influence People

Well... maybe that's a stretch. I don't think I can recommend anything to help you win friends. Not my forte.

But I am going to try to convince you why you should know about Chebyshev approximation, which is a technique for figuring out how you can come as close as possible to computing the result of a mathematical function, with a minimal amount of design effort and CPU power. Let's explore two use cases:

• Amy has a low-power 8-bit microcontroller and needs to compute $\sqrt{x}$...

Thermistor signal conditioning: Dos and Don'ts, Tips and Tricks

In an earlier blog entry,  I mentioned this circuit for thermistor signal conditioning:

It is worth a little more explanation on thermistor signal conditioning; it's something that's often done poorly, whereas it's among the easiest applications for signal conditioning.

The basic premise here is that there are two resistors in a voltage divider: Rth is the thermistor, and Rref is a reference resistor. Here Rref is either R3 alone, or R3 || R4, depending on the gain...

10 Software Tools You Should Know

Unless you're designing small analog electronic circuits, it's pretty hard these days to get things done in embedded systems design without the help of computers. I thought I'd share a list of software tools that help me get my job done. Most of these are free or inexpensive. Most of them are also for working with software. If you never have to design, read, or edit any software, then you're one of a few people that won't benefit from reading this.

Disclaimer: the "best" software...

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

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

Important Programming Concepts (Even on Embedded Systems) Part I: Idempotence

There are literally hundreds, if not thousands, of subtle concepts that contribute to high quality software design. Many of them are well-known, and can be found in books or the Internet. I’m going to highlight a few of the ones I think are important and often overlooked.

But first let’s start with a short diversion. I’m going to make a bold statement: unless you’re a novice, there’s at least one thing in computer programming about which you’ve picked up...

10 Circuit Components You Should Know

November 28, 20111 comment

Chefs have their miscellaneous ingredients, like condensed milk, cream of tartar, and xanthan gum. As engineers, we too have quite our pick of circuits, and a good circuit designer should know what's out there. Not just the bread and butter ingredients like resistors, capacitors, op-amps, and comparators, but the miscellaneous "gadget" components as well.

Here are ten circuit components you may not have heard of, but which are occasionally quite useful.

1. Multifunction gate (