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


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


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


Introduction to Microcontrollers - Driving WS2812 RGB LEDs

Mike Silva November 14, 201327 comments

This tutorial chapter is a bit of a detour, but I think an interesting and useful one.  It introduces a bit of assembly language programming, and demonstrates bit-banging a tight serial data protocol.  And it deals with RGB LEDs, which are just very fun in their own right, especially these new parts.  So I thought I'd post this to give readers time for some holiday lighting experimenting.

Back To The Future

Remember how we started this...


Boot Sequence for an ARM based embedded system

DM January 16, 201230 comments

Hello all,

Allow me to introduce myself. I am Deeksha and I come from plains of North India. My tryst with embedded technologies has been 5 years long and every single day I am amazed with the vastness and learning involved. The thing with embedded technologies is either you are into it, or you aren't. You cannot just hang around half-heartedly (I guess that holds true for every field, for that matter).You have to keep the learning and sharing process going on. And that is the reason I am...


An overview of Linux Boot Process for Embedded Systems

Kunal Singh December 25, 200811 comments

This Text provides an insight in to the Embedded Linux Boot Process. Reader should have a basic Knowledge of Boot Process in general and should be familiar with Embedded Linux Boot Process.

.................PART-A................(1) Software components Involved in Embedded Linux Boot Process    (a) Bootloader    (b) kernel Image    (c) root file system - either an initrd image or a NFS location(2) Steps during Booting process of a conventional...

VHDL tutorial

Gene Breniman October 4, 20077 comments

When I was first introduced to "Programmable Logic" several years ago, it was an answer to many of the challenges that I was struggling with. Though the parts were primitive by today's standards (simple PALs verses FPGA), they were an extremely cost effective tool addressing the need for specialized logic blocks.

I have continued to incorporate these powerful blocks into many of my latest designs. My current favorite part line is the Xilinx CoolRunner series (XC2Cxxx). In this...


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

Jason Sachs August 26, 20144 comments

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


C++ on microcontrollers 1 - introduction, and an output pin class

Wouter van Ooijen October 9, 20118 comments

 

This blog series is about the use of C++ for modern microcontrollers. My plan is to show the gradual development of a basic I/O library. I will introduce the object-oriented C++ features that are used step by step, to provide a gentle yet practical introduction into C++ for C programmers.  Reader input is very much appreciated, you might even steer me in the direction you find most interesting.

I am lazy. I am also a programmer. Luckily, being a lazy...


Introduction to Microcontrollers - Further Beginnings

Mike Silva September 1, 20133 comments
Embedded Programming Basics

This tutorial entry will discuss some further embedded programming basics that you will need to understand before proceeding on to the LED blinky and other example programs. We will do this by looking at the general organization and types of instructions found in most microcontrollers, and how that organization and those instructions are reflected (or, in some cases, ignored) by the C programming language.

Basic CPU...

VHDL tutorial - A practical example - part 2 - VHDL coding

Gene Breniman May 27, 2011

In part 1 of this series we focused on the hardware design, including some of the VHDL definitions of the I/O characteristics of the CPLD part.  In part 2, we will describe the VHDL logic of the CPLD for this design.

With any design, the first step to gather the requirements for the job at hand.  From part 1 of this article, I have copied two sections that address some of the requirements for the CPLD design.

The data acquisition engine has the...


How to Read a Power MOSFET Datasheet

Jason Sachs September 15, 201511 comments

One of my pet peeves is when my fellow engineers misinterpret component datasheets. This happened a few times recently in separate instances, all involving power MOSFETs. So it’s time for me to get on my soapbox. Listen up!

I was going to post an article on how to read component datasheets in general. But MOSFETs are a good place to start, and are a little more specific. I’m not the first person to write something about how to read datasheets; here are some other good...


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 DSPRelated.com 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"...


Free Embedded Systems Books

Stephane Boucher May 28, 2013

Following the success of the Collaborative Writing Experiment: What are your favorite Embedded Systems Online Resources? blog post, let's try a second collaborative writing experiment.  This time, let's work on a file that will list the best embedded systems books that are available online for free.  I am not talking about books that are illegally made available for download by pirates, but books that are made available online by authors and/or publishers.

Do you know of...


Collaborative Writing Experiment: What are your favorite Embedded Systems Online Resources?

Stephane Boucher May 20, 20139 comments

Edit 22/05 - Wow, this went better than expected.  I will try submitting this blog post to Reddit/ece and see if we can get a few more interesting links before I close the document.  Thanks to everyone who contributed!  

_______

Edit 28/05 - The document is now closed to editing.  If there is a link that you would like to see added, please use the comment system at the end of this blog.  Thanks to all who participated!  

Up next, Free...


Success Story

Stephane Boucher April 24, 20132 comments

A blog post has just broken the all-time record for the number of pageviews in 24 hours on the related sites. The blog post in question is titled Data Hiding in C and was written by Stephen Friederichs.  It has been viewed by more than 7000 individuals since its publication a few days ago.  

One reason that explains the success of this blog post is the wide appeal of the subject of the article (c programming) which allowed me to


Code Snippets Winners Announced

Stephane Boucher April 12, 20132 comments

Wow, thanks a lot for all the code snippets - I am pleasantly surprised by the quality of the code that has been shared and I am very grateful.  

Now, as you know, to give momentum to the section I had announced a special reward program for code snippets submitted by the end of March.

The partner members and I had a very hard time selecting the 5 "most useful" snippets out of the more than 50 who have been submitted. 

Here's our selection:


Now on Twitter + More Code Snippets Incentives

Stephane Boucher February 28, 20134 comments

Now on Twitter!

Better late than never, the three related sites (DSPRelated, FPGARelated and EmbeddedRelated) now have their Twitter accounts.  If you are already on Twitter, please consider following.  I'll make sure to keep the tweets interesting and informative.  Plus, once in a while, I will tweet a link where the first x persons to visit will receive a gift (book, gift certificate, etc).  

@DSPRelated


New Code Snippet Section

Stephane Boucher January 15, 20134 comments

More incentives announced

Following the success of the code snippet section on DSPRelated.com, I am happy today to announce the launch of the code snippet section on EmbeddedRelated.com.  

If you have a piece of code that you would like to share with the Embedded Systems community, please go ahead and fill the form.  

If the piece of code you submit is approved, you will be sent $10 through Paypal.

If...


Two jobs

Stephane Boucher December 5, 201223 comments

For those of you following closely embeddedrelated and the other related sites, you might have noticed that I have been less active for the last couple of months, and I will use this blog post to explain why. The main reason is that I got myself involved into a project that ended up using a better part of my cpu than I originally thought it would.

I currently have two jobs: one as an electrical/dsp engineer recycled as a web publisher and the other as a parent of three kids. My job...


October winner announced

Stephane Boucher November 15, 20121 comment

If you are a regular visitor of EmbeddedRelated, you are most likely aware that I have been running monthly draws lately for users of the site who are helping me to clean up the archives by rating threads in the forums section.  

For the month of August, the member "Cryptoman" won a iPad, and for the month of September, 10 members won $50 each.  

For October, the winner of the new iPod Touch is the member with the username "hssathya".

The winner of the next draw will win...


Behold, the New Comments System!

Stephane Boucher September 18, 201229 comments

I have just finished implementing a new system for commenting the blogs.  It uses Ajax extensively, so the page won't reload if you post a comment.  And it is a 'threaded' system, which means that if you post a reply to a comment, it will be attached to it.  

What do you think?  I personally love it.  Please go ahead and test it with a quick comment.

Although it is better to be logged in to post a comment, non-registered users can also comment, but they will have...