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


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

Linear Feedback Shift Registers for the Uninitiated, Part V: Difficult Discrete Logarithms and Pollard's Kangaroo Method

Jason Sachs October 1, 2017

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

MSP430 Launchpad Tutorial - Part 1 - Basics

Enrico Garante June 14, 201319 comments

TI's LaunchPad is a complete MSP430 development environment: all you have to do is download and install CCS IDE (login required), connect your G2231-ready LaunchPad to your computer with the included mini-usb cable, and you are ready to code!

Texas Instrument MSP430 LaunchPad

So, let's see how to start a new project in Code Composer Studio. This IDE is derived from Eclipse, so if you used it before you shouldn't have much problems.

We'll write a simple program that will...

Coroutines in one page of C

Yossi Kreinin August 20, 201315 comments

A coroutine is a function that you can jump back into after returning from it - and it remembers where it was in the code, and all the variables. This is very useful at times.

One use is generating a sequence of values. Here's how you can generate all the x,y pairs in a 2D range in Python:

def iterate(max_x, max_y): for x in range(max_x): for y in range(max_y): yield x,y for x,y in iterate(2,2): print x,y

This prints:

0 0 0 1 1 0 1 1

The yield keyword is like...

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

Jason Sachs September 30, 201218 comments

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

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

Jason Sachs December 27, 201229 comments

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

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

Jason Sachs June 16, 201114 comments

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

MSP430 LaunchPad Tutorial - Part 3 - ADC

Enrico Garante June 25, 20138 comments

In this new episode of our journey into MSP430 I will explain the basics of Analog to Digital Conversion on the MSP430G2231.We will write a program that will read an ADC channel and will toggle some leds based on the result of the conversion. 

We start as usual with the inclusion of the header file for the MSP430G2231, the leds stuff and with the definition of a variable that will store the result of the conversion. We also declare a function that will initialize the ADC...

10 Software Tools You Should Know

Jason Sachs May 20, 201215 comments

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

Using the C language to program the am335x PRU

Fabien Le Mentec June 7, 201480 comments

Some weeks ago, I published an article on how we used the PRU to implement a power supply control loop having hard realtime constraints:


Writing this kind of logic in assembly language is not easy. First the assembly language itself may be difficult to learn depending on your background. Then, fixed and floating point arithmetics require lot of code. While macros help to handle the complexity, they still are error prone as you...

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

Jason Sachs April 27, 201512 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...

Introduction to Microcontrollers - Hello World

Mike Silva September 11, 201313 comments

Embedded Hello World

A standard first program on an embedded platform is the blinking LED.  Getting an LED to blink demonstrates that you have your toolchain set up correctly, that you are able to download your program code into the μC, and that the μC and associated circuitry (e.g. the power supply) is all working.  It can even give you good evidence as to the clock rate that your microcontroller is running (something that trips up a great many people,...

Launch of Youtube Channel: My First Videos - Embedded World 2017

Stephane Boucher April 5, 201721 comments

I went to Embedded World 2017 in Nuremberg with an ambitious plan; I would make video highlights of several exhibits (booths) to be presented to the *Related sites audience.  I would try to make the vendors focus their pitch on the essential in order to produce a one to three minutes video per booth.

So far my experience with making videos was limited to family videos, so I knew I had lots of reading to do and lots of Youtube videos and tutorials to watch.  Trade shows are...

Who else is going to Embedded World 2017 in Nuremberg?

Stephane Boucher February 2, 20171 comment

These days I am particularly excited.  In a little bit less than a month and a half, I will be travelling to Nuremberg in Germany to attend Embedded World, by far the biggest Embedded Systems trade show with over 1000 vendors displaying their products and services.

I have downloaded the Duolingo app and I'm trying to do a minimum of 30 minutes per day to learn some German.  So far, I know that 'Frau' is a woman, 'Mann' is a man, 'Danke' is thank you and 'tschüss' is bye - still a...

New Comments System (please help me test it)

Stephane Boucher October 4, 201618 comments

I thought it would take me a day or two to implement, it took almost two weeks...

But here it is, the new comments systems for blogs, heavily inspired by the forum system I developed earlier this year.  

Which means that:

  • You can easily add images, either by drag and drop or through the 'Insert Image' button
  • You can add MathML, TeX and ASCIImath equations and they will be rendered with Mathjax
  • You can add code snippets and they will be highlighted with highlights.js
  • You can edit...

3 Good News

Stephane Boucher March 9, 20161 comment
Good News #1

Last week, I announced a new and ambitious reward program that will be funded by the new Vendors Directory.

This week, I am happy to announce that we have our firsts two sponsors!  Quantum Leaps & Abelon Systems have agreed to pay the sponsorship fee to be listed in the new Vendors Directory.  Because of their support, there is now some money in the reward pool ($1,000) and enough to pay for the firsts 500 'beers' awarded.  Please...

Go Big or Go Home - Generating $500,000 for Contributors

Stephane Boucher February 18, 20168 comments
In a Nutshell
  • A new Vendors Directory has been created
  • Vendors will be invited to pay a sponsorship fee to be listed in the directory
  • 100% of the basic sponsorship fee will be distributed to the *Related Sites community through a novel reward system
  • The goal is for the directory to eventually generate - drum roll please -  $500,000 on a yearly basis for contributing members on the *Related Sites
  • Members will choose how the reward money gets distributed between...

The New Forum is LIVE!

Stephane Boucher February 18, 20161 comment

After months of hard word, I am very excited to introduce to you the new forum interface.  

Here are the key features:

1- Easily add images to a post by drag & dropping the images in the editor

2- Easily attach files to a post by drag & dropping the files in the editor

3- Add latex equations to a post and they will be rendered with Mathjax (tutorial)

4- Add a code snippet and surround the code with

Helping New Bloggers to Break the Ice: A New Ipad Pro for the Author with the Best Article!

Stephane Boucher November 9, 2015

Breaking the ice can be tough.  Over the years, many individuals have asked to be given access to the blogging interface only to never post an article.  Maybe they underestimated the time it takes to write a decent article, or maybe they got cold feet. I don't blame or judge them at all - how many times in my life have I had the intention to do something but didn't follow through?  Once, maybe twice 😉 (don't worry if you don't...

Welcoming MANY New Bloggers!

Stephane Boucher October 27, 20153 comments

The response to the latest call for bloggers has been amazing and I am very grateful.

In this post I present to you the individuals who, so far (I am still receiving applications at an impressive rate and will update this page as more bloggers are added),  have been given access to the blogging interface.  I am very pleased with the positive response and I think the near future will see the publication of many great articles, given the quality of the...

Recruiting New Bloggers!

Stephane Boucher October 16, 20157 comments

Previous calls for bloggers have been very successful in recruiting some great communicators - Rick LyonsJason Sachs, Victor Yurkovsky, Mike Silva, Markus NentwigGene BrenimanStephen Friederichs,

DSPRelated and EmbeddedRelated now on Facebook & I will be at EE Live!

Stephane Boucher February 27, 20148 comments

I have two news to share with you today.

The first one is that I finally created Facebook pages for and EmbeddedRelated (DSPRelated page - EmbeddedRelated page). For a long time I didn't feel that this was something that was needed, but it seems that these days more and more people are using their Facebook account to stay updated with their favorite websites. In any event, if you have a Facebook account, I would greatly appreciate if you could use the next 5 seconds to "like"...