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...
Android for Embedded Devices - 5 Reasons why Android is used in Embedded Devices
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
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 \)...
Introduction to Deep Insight Analysis for RTOS Based Applications
Over the past several years, embedded systems have become extremely complex. As systems become more complex, they become harder and more time consuming to debug. It isn’t uncommon for development teams to spend more than 40% development cycle time just debugging their systems. This is where deep insight analysis has the potential to dramatically decrease costs and time to market.
Defining Deep Insight Analysis
Deep insight analysis is a set of tools and techniques that can be...
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...
Linear Feedback Shift Registers for the Uninitiated, Part III: Multiplicative Inverse, and Blankinship's Algorithm
Last time we talked about basic arithmetic operations in the finite field \( GF(2)[x]/p(x) \) — addition, multiplication, raising to a power, shift-left and shift-right — as well as how to determine whether a polynomial \( p(x) \) is primitive. If a polynomial \( p(x) \) is primitive, it can be used to define an LFSR with coefficients that correspond to the 1 terms in \( p(x) \), that has maximal length of \( 2^N-1 \), covering all bit patterns except the all-zero...
Continuous Integration for Embedded Systems
It is no secret that anyone who wants to streamline project management, reduce risk and improve the quality needs some form of "automation" in SW development processes. What is commonly used in most companies as a tool for such automation is called Continuous Integration (CI). It is a good practice for embedded systems as well even though it is much harder to use CI for embedded systems compared to pure software development because embedded systems mostly depend on...
Finally got a drone!
As a reader of my blog, you already know that I have been making videos lately and thoroughly enjoying the process. When I was in Germany early this summer (and went 280 km/h in a porsche!) to produce SEGGER's 25th anniversary video, the company bought a drone so we could get an aerial shot of the party (at about the 1:35 mark in this video). Since then, I have been obsessing on buying a drone for myself and finally made the move a few weeks ago - I acquired a used DJI...
8 Weeks - 8 Giveaways!
If for some reason, you've been putting off registering for the upcoming 2021 Embedded Online Conference, here are 8 good reasons to register today.
The idea is simple; if you are registered for the conference by the 'raffle date' for any of the following giveaways, you'll automatically be entered into the draw.
So for instance, if you are already registered for the conference or register before March the 22nd, you'll be automatically entered into the 8 draws...
Arduino robotics #1 - motor control
Arduino Robotics
Beginner 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.The habitat of hardware bugs
The Moscow apartment which little me called home was also home to many other creatures, from smallish cockroaches to biggish rats. But of course we rarely met them face to face. Evolution has weeded out those animals imprudent enough to crash your dinner. However, when we moved a cupboard one time, we had the pleasure to meet a few hundreds of fabulously evolved cockroaches.
In this sense, logical bugs aren't different from actual insects. You won't find...
Cortex-M Exception Handling (Part 2)
The first part of this article described the conditions for an exception request to be accepted by a Cortex-M processor, mainly concerning the relationship of its priority with respect to the current execution priority. This part will describe instead what happens after an exception request is accepted and becomes active.
PROCESSOR OPERATION AND PRIVILEGE MODEBefore discussing in detail the sequence of actions that occurs within the processor after an exception request...
The Least Interesting Circuit in the World
It does nothing, most of the time.
It cannot compute pi. It won’t oscillate. It doesn’t light up.
Often it makes other circuits stop working.
It is… the least interesting circuit in the world.
What is it?
About 25 years ago, I took a digital computer architecture course, and we were each given use of an ugly briefcase containing a bunch of solderless breadboards and a power supply and switches and LEDs — and a bunch of
Review: Hands-On RTOS with Microcontrollers
Full disclosure: I was given a free copy of this book for evaluation.
Hands-On RTOS with Microcontrollers: Building real-time embedded systems using FreeRTOS, STM32 MCUs, and SEGGER debug tools by Brian Amos is an outstanding book. It lives up to its name, extremely hands-on and practical, taking you from knowing nothing about RTOS's (Real-Time Operating Systems) up to building real multithreaded embedded system applications running on real hardware.
It uses the ST Micro
VHDL tutorial - A practical example - part 1 - Hardware
In previous posts I described some simple VHDL examples. This time let's try something a little more complex. This is part one of a multiple part article. This is intended to be a detailed description of one of several initial designs that I developed for a client. This design never made it into a product, but a similar design was used and is currently being produced. As a considerable amount of work was put into this effort, I decided to share this design...
Practical CRCs for Embedded Systems
CRCs are a very practical tool for embedded systems: you're likely to need to use one as part of a communications protocol or to verify the integrity of a program image before writing it to flash. But CRCs can be difficult to understand and tricky to implement. The first time I attempted to write CRC code from scratch I failed once. Then twice. Then three times. Eventually I gave up and used an existing library. I consider myself intelligent: I got A's...
My Guiding Principles As An Engineer
These are my guiding principles as an embedded systems software engineer, forged over 40 years of experience. They shape the way I work and approach problems, and maintain my attitude in the face of adversity.
You may find them useful as well, whether working as a developer, a manager, or an executive, alone or on a team, when things are going well, and when they aren't.
They're a combination of favorite quotes and my own bits of wisdom I've sprinkled...
Cortex-M Exception Handling (Part 1)
This article describes how Cortex-M processors handle interrupts and, more generally, exceptions, a concept that plays a central role in the design and implementation of most embedded systems. The main reason of discussing this topic in detail is that, in the past few years, the degree of sophistication (and complexity) of microcontrollers in handling interrupts steadily increased, bringing them on a par with general-purpose processors.
The Least Interesting Circuit in the World
It does nothing, most of the time.
It cannot compute pi. It won’t oscillate. It doesn’t light up.
Often it makes other circuits stop working.
It is… the least interesting circuit in the world.
What is it?
About 25 years ago, I took a digital computer architecture course, and we were each given use of an ugly briefcase containing a bunch of solderless breadboards and a power supply and switches and LEDs — and a bunch of
C Programming Techniques: Function Call Inlining
Introduction
Abstraction is a key to manage software systems as they increase in size and complexity. As shown in a previous post, abstraction requires a developper to clearly define a software interface for both data and functions, and eventually hide the underlying implementation.When using the C language, the interface is often exposed in a header '.h' file, while the implementation is put in one or more corresponding '.c' files.
First, separating an interface from its...
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...
Linear Feedback Shift Registers for the Uninitiated, Part I: Ex-Pralite Monks and Finite Fields
Later there will be, I hope, some people who will find it to their advantage to decipher all this mess.
— Évariste Galois, May 29, 1832
I was going to call this short series of articles “LFSRs for Dummies”, but thought better of it. What is a linear feedback shift register? If you want the short answer, the Wikipedia article is a decent introduction. But these articles are aimed at those of you who want a little bit deeper mathematical understanding,...
Absolute Beginner's Guide To Getting Started With Raspberry Pi
The Raspberry Pi is a great little computer for learning programming in general, as well as embedded systems. It runs a version of the Linux OS (Operating System) called Raspberry Pi OS (formerly called Raspbian, so you'll see that name a lot, including here), supporting multiple programming languages. It can be used as a full desktop computer.
But if you're an absolute beginner, the information can get overwhelming quickly. There are different versions of it, different software to run on...
Back from Embedded World 2019 - Funny Stories and Live-Streaming Woes
When the idea of live-streaming parts of Embedded World came to me, I got so excited that I knew I had to make it happen. I perceived the opportunity as a win-win-win-win.
- win #1 - Engineers who could not make it to Embedded World would be able to sample the huge event,
- win #2 - The organisation behind EW would benefit from the extra exposure
- win #3 - Lecturers and vendors who would be live-streamed would reach a (much) larger audience
- win #4 - I would get...
Cortex-M Exception Handling (Part 1)
This article describes how Cortex-M processors handle interrupts and, more generally, exceptions, a concept that plays a central role in the design and implementation of most embedded systems. The main reason of discussing this topic in detail is that, in the past few years, the degree of sophistication (and complexity) of microcontrollers in handling interrupts steadily increased, bringing them on a par with general-purpose processors.
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:...
Coding - Step 0: Setting Up a Development Environment
Articles in this series:
- Coding Step 0 - Development Environments
- Coding Step 1 - Hello World and Makefiles
- Coding Step 2 - Source Control
- Coding Step 3 - High-Level Requirements
- Coding Step 4 - Design
You can easily find a million articles out there discussing compiler nuances, weighing the pros and cons of various data structures or discussing the optimization of databases. Those sorts of articles are fascinating reads for advanced programmers but...
Slew Rate Limiters: Nonlinear and Proud of It!
I first learned about slew rate limits when I was in college. Usually the subject comes up when talking about the nonideal behavior of op-amps. In order for the op-amp output to swing up and down quickly, it has to charge up an internal capacitor with a transistor circuit that’s limited in its current capability. So the slew rate limit \( \frac{dV}{dt} = \frac{I_{\rm max}}{C} \). And as long as the amplitude and frequency aren’t too high, you won’t notice it. But try to...
