Linear Feedback Shift Registers for the Uninitiated, Part XII: Spread-Spectrum Fundamentals

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

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 X: Counters and Encoders

Jason Sachs December 9, 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

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


Obsolete? Yes. Still in use? Yes. How do you use it? Ummm...

Ed Nutter November 14, 20175 comments

In today's world of constantly changing technology, quick parts availability, and seemingly endless options, some things can't change.  It isn't a big deal to wait a day or less for a computer upgrade to arrive.  It seems program size increases proportionally to hard drive size.  The old is discarded and replaced with the new.  Hard drives can hold terrabytes and even SD cards can hold gigabytes of information.

Now, suppose a system can't be changed.  It is still...


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.


Lazy Properties in Python Using Descriptors

Jason Sachs November 7, 2017

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


Android for Embedded Devices - 5 Reasons why Android is used in Embedded Devices

Maharajan Veerabahu November 6, 20173 comments

The embedded purists are going to hate me for this. How can you even think of using Android on an embedded system ? It’s after all a mobile phone operating system/software. 

Sigh !! Yes I did not like Android to begin with, as well - for use on an Embedded System. But sometimes I think the market and needs decide what has to be used and what should not be. This is one such thing. Over the past few years, I have learned to love Android as an embedded operating system....


Linear Feedback Shift Registers for the Uninitiated, Part VI: Sing Along with the Berlekamp-Massey Algorithm

Jason Sachs October 18, 2017

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


BGA and QFP at Home 1 - A Practical Guide.

Victor Yurkovsky October 13, 20132 comments

It is almost universally accepted by the hobbyists that you can't work with high-density packages at home.  That is entirely incorrect.  I've been assembling and reflowing BGA circuit boards at home for a few years now.  BGAs and 0.5mm-pitch QFPs are well within the realm of a determined amateur. 

This series of articles presents practical information on designing and assembling boards with high-density packages at home.  While the focus is on FPGA packages, most of...


Which MOSFET topology?

Jason Sachs September 1, 20119 comments

A recent electronics.StackExchange question brings up a good topic for discussion. Let's say you have a power supply and a 2-wire load you want to be able to switch on and off from the power supply using a MOSFET. How do you choose which circuit topology to choose? You basically have four options, shown below:

From left to right, these are:

High-side switch, N-channel MOSFET High-side switch, P-channel MOSFET Low-side switch, N-channel...

How to Estimate Encoder Velocity Without Making Stupid Mistakes: Part II (Tracking Loops and PLLs)

Jason Sachs November 17, 201312 comments

Yeeehah! Finally we're ready to tackle some more clever ways to figure out the velocity of a position encoder. In part I, we looked at the basics of velocity estimation. Then in my last article, I talked a little about what's necessary to evaluate different kinds of algorithms. Now it's time to start describing them. We'll cover tracking loops and phase-locked loops in this article, and Luenberger observers in part III.

But first we need a moderately simple, but interesting, example...


PID Without a PhD

Tim Wescott April 26, 201611 comments

I both consult and teach in the area of digital control. Through both of these efforts, I have found that while there certainly are control problems that require all the expertise I can bring to bear, there are a great number of control problems that can be solved with the most basic knowledge of simple controllers, without resort to any formal control theory at all.

This article will tell you how to implement a simple controller in software and how to tune it without getting into heavy...


Implementing State Machines

Stephen Friederichs January 18, 20145 comments

State machines are a great way to design software but they can be difficult to implement well.To illustrate this I’ll develop a simple state machine then increase the complexity to demonstrate some of the difficulties

We’ve all washed dishes before - it’s easy isn’t it? Scrub, rinse, dry, scrub, rinse dry. Scrub the dish until all of the gunk is off of it, rinse until the soap is off, put it in the drying rack. If you want to design software to implement this you have options. You...


Arduino robotics #4 - HC-SR04 ultrasonic sensor

Lonnie Honeycutt October 20, 20131 comment
Arduino Robotics

Arduino robotics is a series of article chronicling my first autonomous robot build, Clusterbot.  This build is meant to be affordable, relatively easy and instructive.  The total cost of the build is around $50.  

1. Arduino robotics - motor control2. Arduino robotics - chassis, locomotion and power3. Arduino robotics - wiring, coding and a test run4.

Lost Secrets of the H-Bridge, Part IV: DC Link Decoupling and Why Electrolytic Capacitors Are Not Enough

Jason Sachs April 29, 20147 comments

Those of you who read my earlier articles about H-bridges, and followed them closely, have noticed there's some unfinished business. Well, here it is. Just so you know, I've been nervous about writing the fourth (and hopefully final) part of this series for a while. Fourth installments after a hiatus can bring bad vibes. I mean, look what it did to George Lucas: now we have Star Wars Episode I: The Phantom Menace 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...


How to Build a Fixed-Point PI Controller That Just Works: Part II

Jason Sachs March 24, 20122 comments

In Part I we talked about some of the issues around discrete-time proportional-integral (PI) controllers:

  • various forms and whether to use the canonical form for z-transforms (don't do it!)
  • order of operation in the integral term: whether to scale and then integrate (my recommendation), or integrate and then scale.
  • saturation and anti-windup

In this part we'll talk about the issues surrounding fixed-point implementations of PI controllers. First let's recap the conceptual structure...