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...
Polynomial Math
Elliptic Curve Cryptography is used as a public key infrastructure to secure credit cards, phones and communications links. All these devices use either FPGA's or embedded microprocessors to compute the algorithms that make the mathematics work. While the math is not hard, it can be confusing the first time you see it. This blog is an introduction to the operations of squaring and computing an inverse over a finite field which are used in computing Elliptic Curve arithmetic. ...
Linear Feedback Shift Registers for the Uninitiated
In 2017 and 2018 I wrote an eighteen-part series of articles about linear feedback shift registers, or LFSRs:
div.jms-article-content ol > li { list-style-type: upper-roman } Ex-Pralite Monks and Finite Fields, in which we describe what an LFSR is as a digital circuit; its cyclic behavior over time; the definition of groups, rings, and fields; the isomorphism between N-bit LFSRs and the field \( GF(2^N) \); and the reason why I wrote this seriesUnraveling the Enigma: Object Detection in the World of Pixels
Exploring the realm of embedded systems co-design for object recognition, this blog navigates the convergence of hardware and software in revolutionizing industries. Delving into real-time image analysis and environmental sensing, the discussion highlights advanced object detection and image segmentation techniques. With insights into Convolutional Neural Networks (CNNs) decoding pixel data and autonomously extracting features, the blog emphasizes their pivotal role in modern computer vision. Practical examples, including digit classification using TensorFlow and Keras on the MNIST dataset, underscore the power of CNNs. Through industry insights and visualization aids, the blog unveils a tapestry of innovation, charting a course towards seamless interaction between intelligent embedded systems and the world.
Round-robin or RTOS for my embedded system
First of all, I would like to introduce myself. I am Manuel Herrera. I am starting to write blogs about the situations that I have faced over the years of my career and discussed with colleagues.
To begin, I would like to open a conversation with a dilemma that is present when starting a project ... must I use or not any operating system?
I hope it helps you to form your own criteria and above all that you enjoy it.
Does my embedded system need an...
Bad Hash Functions and Other Stories: Trapped in a Cage of Irresponsibility and Garden Rakes
I was recently using the publish() function in MATLAB to develop some documentation, and I ran into a problem caused by a bad hash function.
In a resource-limited embedded system, you aren't likely to run into hash functions. They have three major applications: cryptography, data integrity, and data structures. In all these cases, hash functions are used to take some type of data, and deterministically boil it down to a fixed-size "fingerprint" or "hash" of the original data, such that...
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....
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 derivative wisdom I've sprinkled...
StrangeCPU #4. Microcode
Summary:
Sliding windows containing runs of microcode.
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.
Short Takes (EE Shanty): What shall we do with a zero-ohm resistor?
In circuit board design you often need flexibility. It can cost hundreds or thousands of dollars to respin a circuit board, so I need flexibility for two main reasons:
- sometimes it's important to be able to use one circuit board design to serve more than one purpose
- risk reduction: I want to give myself the option to add in or leave out certain things when I'm not 100% sure I'll need them.
And so we have jumpers and DIP switches and zero-ohm resistors:
Jumpers and...
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...
A Working Real Time Clock (RTC) Implementation
In one of my projects, data captured from various sensors had to be time stamped in the YearYear/DayDay/MonthMonth, HoursHours:MinutesMinutes:SecondsSeconds format. My initial thought was because there was already a GPRS modem in the system, I could simply configure it to use the network time delivered by the base station when it fired up. Once the GPRS module started up and retrieved the correct time, I could then invoke a simple AT command to read the time stamp into the microcontroller....
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.
...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...
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.
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.
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...
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...
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...
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...
