Linear Feedback Shift Registers for the Uninitiated, Part II: libgf2 and Primitive Polynomials
Last time, we looked at the basics of LFSRs and finite fields formed by the quotient ring \( GF(2)[x]/p(x) \).
LFSRs can be described by a list of binary coefficients, sometimes referred as the polynomial, since they correspond directly to the characteristic polynomial of the quotient ring.
Today we’re going to look at how to perform certain practical calculations in these finite fields. I maintain a Python library on bitbucket called...
Went 280km/h (174mph) in a Porsche Panamera in Germany!
Those of you who've been following my blog lately already know that I am going through some sort of mid-life crisis that involves going out there to meet people and make videos. It all started with Embedded World early this year, then continued at ESC Boston a couple of months ago and the latest chapter just concluded as I returned from Germany after spending a week at SEGGER's headquarters to produce a video to highlight their 25th anniversary.
Embedded Toolbox: Windows GUI Prototyping Toolkit
In this installment of my "Embedded Toolbox" series, I would like to interest you in the free Windows GUI Toolkit called QWin for prototyping, developing and debugging embedded C or C++ code on Windows.
If you work on devices with non-trivial user interfaces consisting of LCDs (segmented or graphic), buttons, LEDs, etc., QWin could be just the tool for you. It has improved my productivity in such projects dramatically. I personally consider it a gem in my "Embedded...
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,...
Tenderfoot: Recommended Reading
Twenty years ago I read Code Complete by Steve McConnell. And then read it again. And again. And again. Of all the books I have read during my career, I believe this was the book that catapulted me from a young electrical engineer to a young and aspiring embedded software engineer. So to all the ‘tenderfoots’ embarking upon an embedded systems and especially embedded software and firmware career, this entry is for you.
First, I would certainly recommend that all engineers read and read...
Embedded Toolbox: Programmer's Calculator
Like any craftsman, I have accumulated quite a few tools during my embedded software development career. Some of them proved to me more useful than others. And these generally useful tools ended up in my Embedded Toolbox. In this blog, I'd like to share some of my tools with you. Today, I'd like to start with my cross-platform Programmer's Calculator called QCalc.
I'm sure that you already have your favorite calculator online or on your smartphone. But can your calculator accept...
VERY Fast Japanese Sumo Robots
For some reasons, I could not stop watching. I would love to have the maker of one of these robots to blog about the project here on EmbeddedRelated.com, the sensors, microcontroller, algorithms and the challenges... This would make for a very interesting read! Do you know someone?
Ten Little Algorithms, Part 6: Green’s Theorem and Swept-Area Detection
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 4: Topological Sort
- Part 5: Quadratic Extremum Interpolation and Chandrupatla's Method
This article is mainly an excuse to scribble down some cryptic-looking mathematics — Don’t panic! Close your eyes and scroll down if you feel nauseous — and...
Going back to Germany!
A couple of blog posts ago, I wrote that the decision to go to ESC Boston ended up being a great one for many different reasons. I came back from the conference energized and really happy that I went.
These feelings were amplified a few days after my return when I received an email from Rolf Segger, the founder of SEGGER Microcontroller (check out their very new website), asking if I would be interested in visiting their headquarters...
ESC Boston's Videos are Now Up
In my last blog, I told you about my experience at ESC Boston and the few videos that I was planning to produce and publish. Here they are, please have a look and any feedback (positive or negative) is appreciated.
Short HighlightThis is a very short (one minute) montage of some of the footage that I shot at the show & conference. In future shows, I absolutely need to insert clips here and there of engineers saying a few words about the conference (why they...
Use DPLL to Lock Digital Oscillator to 1PPS Signal
Introduction
There are occasions where it is desirable to lock a digital oscillator to an external time reference such as the 1PPS (One Pulse Per Second) signal output from a GPS receiver. One approach would be to synchronize a fixed frequency oscillator on the leading edge of the 1PPS signal. In many cases, this will result in adequate performance. However, in situations where simple synchronization does not provide adequate performance, digital phase-lock techniques can be applied to a...
Introduction to Microcontrollers - Further Beginnings
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...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...
Choosing a Microcontroller for Your Vehicle
There are many things to take into consideration when choosing a microcontroller or microprocessor for your autonomous vehicle.
Voltage
Some processors run on 5V and others use 3.3V. Be sure to check the documentation before you buy. Make sure your supply has a high enough amp rating that your microcontroller doesn't lose pwer.
Power
Can the system run using batteries? Large, automotive sized vehicles can be run from large batteries or inverters in the vehicle. Smaller...
Embedded Programming Video Course Shows How OOP Works Under the Hood
If you'd like to understand how Object-Oriented Programming (OOP) really works under the hood, here is a free video course for you:
OOP part-1: Encapsulation: This first lesson on Object-Oriented Programming (OOP) introduces the concept of Encapsulation, which is the ability to package data and functions together into classes. You'll see how you can emulate Encapsulation in C, what kind of code is generated, and how to debug such code. Next, you will translate the C design into C++ using...
Digital PLL's -- Part 2
In Part 1, we found the time response of a 2nd order PLL with a proportional + integral (lead-lag) loop filter. Now let’s look at this PLL in the Z-domain [1, 2]. We will find that the response is characterized by a loop natural frequency ωn and damping coefficient ζ.
Having a Z-domain model of the DPLL will allow us to do three things:
Compute the values of loop filter proportional gain KL and integrator gain KI that give the desired loop natural...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...
BGA and QFP at Home 1 - A Practical Guide.
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...
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...
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...
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...
OOKLONE: a cheap RF 433.92MHz OOK frame cloner
Introduction
A few weeks ago, I bought a set of cheap wireless outlets and reimplemented the protocol for further inclusion in a domotics platform. I wrote a post about it here:
//www.embeddedrelated.com/showarticle/620.php
Following that, I had access to another outlet from a different vendor:
http://www.castorama.fr/store/Prise-telecommandee-BLYSS---Interieur-prod4470027.html
The device documentation mentions that it operates on the same frequency as the previous...
Introduction to Microcontrollers - Adding Some Real-World Hardware
When 2 LEDs Just Don't Cut It AnymoreSo far, we've done everything in this series using two LEDs and one button. I'm guessing that the thrill of blinking an LED has worn off by now, hard as that is to imagine. What's more, we've just about reached the limits of what we can learn with such limited I/O. We have come to the point where we need to add some hardware to our setup to continue with additional concepts and microcontroller...
StrangeCPU #2. Sliding Window Token Machines
Summary:An in-depth exploration of Sliding Window Token Machines; ARM notes.
Table of Contents:- Part 1: A new CPU - technology review, re-examination of the premises; StrangeCPU concepts; x86 notes.
- Part 2: Sliding-Window Token Machines, an in-depth exploration of this curious technology; ARM notes.
- Part 3. Instruction Slides - The Strangest CPU Yet! Decoding instructions with a Sliding Window...
Use DPLL to Lock Digital Oscillator to 1PPS Signal
IntroductionThere are occasions where it is desirable to lock a digital oscillator to an external time reference such as the 1PPS (One Pulse Per Second) signal output from a GPS receiver. One approach would be to synchronize a fixed frequency oscillator on the leading edge of the 1PPS signal. In many cases, this will result in adequate performance. However, in situations where simple synchronization does not provide adequate performance, digital phase-lock techniques can be applied to a...
Lessons Learned from Embedded Code Reviews (Including Some Surprises)
My software team recently finished a round of code reviews for some of our motor controller code. I learned a lot from the experience, most notably why you would want to have code reviews in the first place.
My background is originally from the medical device industry. In the United States, software in medical devices gets a lot of scrutiny from the Food and Drug Administration, and for good reason; it’s a place for complexity to hide latent bugs. (Can you say “
C++ on microcontrollers 2 - LPCXpresso, LPC-link, Code Sourcery, lpc21isp, linkerscript, LPC1114 startup
previous parts: 1
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 teach my students that...
VHDL tutorial - combining clocked and sequential logic
In an earlier article on VHDL programming ("VHDL tutorial" and "VHDL tutorial - part 2 - Testbench", I described a design for providing a programmable clock divider for a ADC sequencer. In this example, I showed how to generate a clock signal (ADCClk), that was to be programmable over a series of fixed rates (20MHz, 10MHz, 4MHz, 2MHz, 1MHz and 400KHz), given a master clock rate of 40MHz. A reader of that article had written to ask if it was possible to extend the design to...
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...
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,...
