Linear Feedback Shift Registers for the Uninitiated, Part VIII: Matrix Methods and State Recovery
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 DregsElwyn Berlekamp’s 1966 paper Non-Binary BCH Encoding covers some work on
Obsolete? Yes. Still in use? Yes. How do you use it? Ummm...
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
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...
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...
Windows XP and Win32 - the Platform of the Future!
Over the past decade I often wondered why anyone uses Windows. It's just so... proprietary. And pedestrian. As I grew up my OS of choice went nothing to CPM to DOS (on Apple ][), GEM on Atari ST, MS-DOS, DOS extenders, Mac OS, Windows NT, Windows XP, Linux... Now, I again find myself a fan of Windows XP, the platform of the future. (I am still a fan of bare metal, of course).Maybe I am not totally serious, but I, a self-proclaimed freedom lover and...
Metal detection: building the detector
IntroductionBefore starting, you may want to read this post describing the BFO stage:
//www.embeddedrelated.com/showarticle/911.php
I have detailed the implementation of a BFO stage for detecting metal. Now it has been validated on the bench, the next step is to integrate it in a stand alone instrument for testing on the field. A few things have to be done to reach this goal:
- make a PCB for the electronics,
- house the PCB in a box,
- add a power supply,
- make a frame to hold...
C++ on microcontrollers 1 - introduction, and an output pin class
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...
Quaternions and the spatial rotations in motion enabled wearable devices. Exploiting the potential of smart IMUs attitude estimation.
Have you always wondered what a quaternion is? this is your post. Attitude or spatial orientation analysis is a powerful element in wearable devices (and many other systems). Commercially available sensors can provide this information out-of-the-box without requiring complex additional implementation of sensor fusion algorithms. Since these are already on-chip solutions devices can serve as a way to explore and analyze motion in several use cases. Mathematical analysis for processing quaternion is presented along with a brief introduction to them, Although they are not really easy to visualise, a couple fairly simple examples are provided which may allow you to gain some intuition on what's the logic behind them.
Little to no benefit from C based HLS
Last updated 07-Nov-2015
As I write this I am on a plane and my destination is EELive 2014 where I am going to give a talk hardware design: the grunge era. It is a shotgun introduction to three alternative hardware description languages (alt.hdl). The three languages briefly introduced in the talk are: bsv, chisel, and myhdl. The goal of the talk is simply to raise awareness of the three...
How to use SPI devices in NuttX RTOS
Previously in this EmbeddedRelated article, we saw how to use I2C device connected to your board. Although I2C devices are very common nowadays, probably you will need to use some SPI device as well. Today we will see how to do exactly that. So, lets to get started!
The SPI (Serial Peripheral Interface) is synchronous serial communication protocol (by synchronous it means there is a common clock signal to indicate when which signal transition will occur)....
A Beginner's Guide to Embedded Systems
I was in my Junior year of college when I first learned about embedded systems. Sure, I’d heard about this mystical world of sensors and IoT, the same way I’d heard about thermonuclear astrophysics; But, the phrase “embedded systems” didn’t really mean anything to me. This, here, is a guide for people like teenage me. We’re going to learn what an embedded system actually is, and why working on embedded software is the coolest thing you could ever do!
What's an embedded...The volatile keyword
Although the C keyword volatile is very useful in embedded applications, care is needed to use it correctly and vigilance is required to ensure its correct implementation by compilers.
How to Design Reliable Reset Circuits for Embedded Microcontrollers
In the world of embedded systems, the reset circuit is a critical component that ensures the microcontroller starts up correctly and recovers gracefully from unexpected events like power fluctuations or software crashes. A poorly designed reset circuit can lead to erratic behavior, system lockups, or even permanent damage to the microcontroller. For embedded engineers, designing a reliable reset circuit is essential for ensuring the stability and robustness of the system.
An absolute position encoder VHDL core
In this article, Fabien Le Mentec explains how to implement a unique VHDL core addressing absolute position encoder interfaces. He reviews existing instruments in use or being developed and considers their specific requirements. He also looks for details in current implementations and considers the projects to come so that the implementation can be designed to be extensible. The VHDL core dubbed absenc features both ENDAT, BISS and SSI interface. Due to its architecture, new interfaces are easily added. Also, the 3 interfaces can be enabled at synthesis while 1 is selected at runtime. As much as possible, resources common to the different interfaces are shared (counters, comparators…).
Getting Started With Zephyr: Kconfig
In this blog post, we briefly look at Kconfig, one of the core pieces of the Zephyr infrastructure. Kconfig allows embedded software developers to turn specific subsystems on or off within Zephyr efficiently and control their behavior. We also learn how we can practically use Kconfig to control the features of our application using the two most common mechanisms.
Developing software for a safety-related embedded system for the first time
I spend most of my working life with organisations that develop software for high-reliability, real-time embedded systems. Some of these systems are created in compliance with IEC 61508, ISO 26262, DO-178C or similar international standards.
When working with organisations that are developing software for their first safety-related design, I’m often asked to identify the key issues that distinguish this process from the techniques used to develop “ordinary” embedded software.
...Lightweight C++ Error-Codes Handling
The traditional C++ approach to error handling tends to distinguish the happy path from the unhappy path. This makes handling errors hard (or at least boring) to write and hard to read. In this post, I present a technique based on chaining operations that merges the happy and the unhappy paths. Thanks to C++ template and inlining the proposed technique is lightweight and can be used proficiently for embedded software.
Modern Embedded Systems Programming: Beyond the RTOS
An RTOS (Real-Time Operating System) is the most universally accepted way of designing and implementing embedded software. It is the most sought after component of any system that outgrows the venerable "superloop". But it is also the design strategy that implies a certain programming paradigm, which leads to particularly brittle designs that often work only by chance. I'm talking about sequential programming based on blocking.
Blocking occurs any time you wait explicitly in-line for...
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...
Designing Embedded System with FPGA - 1
With the introduction of soft processors and related tools (like EDK from Xilinx), implementation of basic embedded system in FPGA is made easy. This requires very little or almost no knowledge of VHDL programming. Actually that’s how I started. If user is interested in taking full advantage of FPGA and its parallel processing power, then yes, detail understanding of soft processor, its peripheral bus and VHDL programming is required.
I will start with...
FPGA Assemblers and Time Machines
Flashback to 1986. A young man has a crazy idea - he wants to make a CPU all by himself. He is reading early Xilinx manuals cover to cover as if they were novels. Yes, you are quick - this is indeed a (mostly) true story about me and my dream, suddenly made possible by this new FPGA technology.
Sadly more than 20 years went by before my first CPU ran in a Xilinx FPGA. Why did it take so long? Every few years I set up the tools and every time I walked away, scared silly. As the years...
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...
Good old multiplexed keypad in an embedded system
Good old multiplexed keypad in embedded systems
(My www.embeddedrelated.com Blog No.1)
Touch-screens, rotary encoder switches and other navigational aids rule the user interface these days. Navigation through menus and sub-menus is child’s play as icons and thumbnails rule the screen.
Jumping from one screen to another, switching between programs and event notification pop-ups are made possible due to high...
