## A Second Look at Slew Rate Limiters

I recently had to pick a slew rate for a current waveform, and I got this feeling of déjà vu… hadn’t I gone through this effort already? So I looked, and lo and behold, way back in 2014 I wrote an article titled Slew Rate Limiters: Nonlinear and Proud of It! where I explored the effects of two types of slew rate limiters, one feedforward and one feedback, given a particular slew rate \( R \).

Here was one figure I published at the time:

This...

## Shibboleths: The Perils of Voiceless Sibilant Fricatives, Idiot Lights, and Other Binary-Outcome Tests

AS-SALT, JORDAN — Dr. Reza Al-Faisal once had a job offer from Google to work on cutting-edge voice recognition projects. He turned it down. The 37-year-old Stanford-trained professor of engineering at Al-Balqa’ Applied University now leads a small cadre of graduate students in a government-sponsored program to keep Jordanian society secure from what has now become an overwhelming influx of refugees from the Palestinian-controlled West Bank. “Sometimes they visit relatives...

## Wye Delta Tee Pi: Observations on Three-Terminal Networks

Today I’m going to talk a little bit about three-terminal linear passive networks. These generally come in two flavors, wye and delta.

Why Wye?The town of Why, Arizona has a strange name that comes from the shape of the original road junction of Arizona State Highways 85 and 86, which was shaped like the letter Y. This is no longer the case, because the state highway department reconfigured the intersection

## Linear Feedback Shift Registers for the Uninitiated, Part XVIII: Primitive Polynomial Generation

Last time we figured out how to reverse-engineer parameters of an unknown CRC computation by providing sample inputs and analyzing the corresponding outputs. One of the things we discovered was that the polynomial \( x^{16} + x^{12} + x^5 + 1 \) used in the 16-bit X.25 CRC is not primitive — which just means that all the nonzero elements in the corresponding quotient ring can’t be generated by powers of \( x \), and therefore the corresponding 16-bit LFSR with taps in bits 0, 5,...

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

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

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

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

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 EarI have had a really really tough time writing this article. I like the...

## Linear Regression with Evenly-Spaced Abscissae

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

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

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

## Fluxions for Fun and Profit: Euler, Trapezoidal, Verlet, or Runge-Kutta?

Today we're going to take another diversion from embedded systems, and into the world of differential equations, modeling, and computer simulation.

DON'T PANIC!First of all, just pretend I didn't bring up anything complicated. We're exposed to the effects of differential equations every day, whether we realize it or not. Your car speedometer and odometer are related by a differential equation, and whether you like math or not, you probably have some comprehension of what's going on: you...

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

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

## Elliptic Curve Cryptography - Key Exchange and Signatures

Elliptic curve mathematics over finite fields helps solve the problem of exchanging secret keys for encrypted messages as well as proving a specific person signed a particular document. This article goes over simple algorithms for key exchange and digital signature using elliptic curve mathematics. These methods are the essence of elliptic curve cryptography (ECC) used in applications such as SSH, TLS and HTTPS.

## What does it mean to be 'Turing complete'?

The term "Turing complete" describes all computers and even some things we don't expect to be as powerful as a typical computer. In this article, I describe what it means and discuss the implications of Turing completeness on projects that need just a little more power, on alternative processor designs, and even security.

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

## Ten Little Algorithms, Part 1: Russian Peasant Multiplication

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:

## Elliptic Curve Cryptography - Extension Fields

An introduction to the pairing of points on elliptic curves. Point pairing normally requires curves over an extension field because the structure of an elliptic curve has two independent sets of points if it is large enough. The rules of pairings are described in a general way to show they can be useful for verification purposes.

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

## Shibboleths: The Perils of Voiceless Sibilant Fricatives, Idiot Lights, and Other Binary-Outcome Tests

AS-SALT, JORDAN — Dr. Reza Al-Faisal once had a job offer from Google to work on cutting-edge voice recognition projects. He turned it down. The 37-year-old Stanford-trained professor of engineering at Al-Balqa’ Applied University now leads a small cadre of graduate students in a government-sponsored program to keep Jordanian society secure from what has now become an overwhelming influx of refugees from the Palestinian-controlled West Bank. “Sometimes they visit relatives...

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

Other articles in this series:

- Part 1: Russian Peasant Multiplication
- Part 2: The Single-Pole Low-Pass Filter
- Part 3: Welford's Method (And Friends)
- Part 4: Topological Sort
- Part 5: Quadratic Extremum Interpolation and Chandrupatla's Method

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

## Fluxions for Fun and Profit: Euler, Trapezoidal, Verlet, or Runge-Kutta?

Today we're going to take another diversion from embedded systems, and into the world of differential equations, modeling, and computer simulation.

DON'T PANIC!First of all, just pretend I didn't bring up anything complicated. We're exposed to the effects of differential equations every day, whether we realize it or not. Your car speedometer and odometer are related by a differential equation, and whether you like math or not, you probably have some comprehension of what's going on: you...

## Linear Feedback Shift Registers for the Uninitiated, Part XVIII: Primitive Polynomial Generation

Last time we figured out how to reverse-engineer parameters of an unknown CRC computation by providing sample inputs and analyzing the corresponding outputs. One of the things we discovered was that the polynomial \( x^{16} + x^{12} + x^5 + 1 \) used in the 16-bit X.25 CRC is not primitive — which just means that all the nonzero elements in the corresponding quotient ring can’t be generated by powers of \( x \), and therefore the corresponding 16-bit LFSR with taps in bits 0, 5,...

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

## Elliptic Curve Cryptography

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.

## Wye Delta Tee Pi: Observations on Three-Terminal Networks

Today I’m going to talk a little bit about three-terminal linear passive networks. These generally come in two flavors, wye and delta.

Why Wye?The town of Why, Arizona has a strange name that comes from the shape of the original road junction of Arizona State Highways 85 and 86, which was shaped like the letter Y. This is no longer the case, because the state highway department reconfigured the intersection

## Linear Feedback Shift Registers for the Uninitiated, Part II: libgf2 and Primitive Polynomials

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

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

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