Linear Feedback Shift Registers for the Uninitiated, Part XII: Spread-Spectrum Fundamentals
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
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 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...
Lost Secrets of the H-Bridge, Part III: Practical Issues of Inductor and Capacitor Ripple Current
We've been analyzing the ripple current in an H-bridge, both in an inductive load and the DC link capacitor. Here's a really quick recap; if you want to get into more details, go back and read part I and part II until you've got equations coming out of your ears. I promise there will be a lot less grungy math in this post. So let's get most of it out of the way:
Switches QAH and QAL are being turned on and off with pulse-width modulation (PWM), to produce an average voltage DaVdc on...
Zebras Hate You For No Reason: Why Amdahl's Law is Misleading in a World of Cats (And Maybe in Ours Too)
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
Lost Secrets of the H-Bridge, Part II: Ripple Current in the DC Link Capacitor
In my last post, I talked about ripple current in inductive loads.
One of the assumptions we made was that the DC link was, in fact, a DC voltage source. In reality that's an approximation; no DC voltage source is perfect, and current flow will alter the DC link voltage. To analyze this, we need to go back and look at how much current actually is being drawn from the DC link. Below is an example. This is the same kind of graph as last time, except we added two...
Modeling Gate Drive Diodes
This is a short article about how to analyze the diode in some gate drive circuits when figuring out turn-off characteristics --- specifically, determining the relationship between gate drive current and gate voltage during turn-off of a power transistor.
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:
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...
First-Order Systems: The Happy Family
Все счастли́вые се́мьи похо́жи друг на дру́га, ка́ждая несчастли́вая семья́ несчастли́ва по-сво́ему.— Лев Николаевич Толстой, Анна Каренина
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...
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...
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...
Optimizing Optoisolators, and Other Stories of Making Do With Less
It’s been a few months since I’ve rolled up my sleeves here and dug into some good old circuit design issues. I started out with circuit design articles, and I’ve missed it.
Today’s topic will be showing you some tricks for how to get more performance out of an optoisolator. These devices — and I’m tempted to be lazy and call them “optos”, but that sounds more like a cereal with Greek yogurt-covered raisins — are essentially just an LED...
Oscilloscope Dreams
My coworkers and I recently needed a new oscilloscope. I thought I would share some of the features I look for when purchasing one.
When I was in college in the early 1990's, our oscilloscopes looked like this:
Now the cathode ray tubes have almost all been replaced by digital storage scopes with color LCD screens, and they look like these:
Oscilloscopes are basically just fancy expensive boxes for graphing voltage vs. time. They span a wide range of features and prices:...
Ten Little Algorithms, Part 4: Topological Sort
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 5: Quadratic Extremum Interpolation and Chandrupatla's Method
- Part 6: Green’s Theorem and Swept-Area Detection
Today we’re going to take a break from my usual focus on signal processing or numerical algorithms, and focus on...
Tolerance Analysis
Today we’re going to talk about tolerance analysis. This is a topic that I have danced around in several previous articles, but never really touched upon in its own right. The closest I’ve come is Margin Call, where I discussed several different techniques of determining design margin, and ran through some calculations to justify that it was safe to allow a certain amount of current through an IRFP260N MOSFET.
Tolerance analysis...
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...
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...
Ten Little Algorithms, Part 5: Quadratic Extremum Interpolation and Chandrupatla's Method
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 the waveform they were sampled from.
The Other Kind of Bypass Capacitor
There’s a type of bypass capacitor I’d like to talk about today.
It’s not the usual power supply bypass capacitor, aka decoupling capacitor, which is used to provide local charge storage to an integrated circuit, so that the high-frequency supply currents to the IC can bypass (hence the name) all the series resistance and inductance from the power supply. This reduces the noise on a DC voltage supply. I’ve...
Another 10 Circuit Components You Should Know
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...
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,...
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...
