EmbeddedRelated.com

Linear Feedback Shift Registers for the Uninitiated, Part III: Multiplicative Inverse, and Blankinship's Algorithm

Jason Sachs September 9, 2017

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


Linear Feedback Shift Registers for the Uninitiated, Part II: libgf2 and Primitive Polynomials

Jason Sachs July 17, 2017

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


Linear Feedback Shift Registers for the Uninitiated, Part I: Ex-Pralite Monks and Finite Fields

Jason Sachs July 3, 20176 comments

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


Ten Little Algorithms, Part 6: Green’s Theorem and Swept-Area Detection

Jason Sachs June 18, 20173 comments

Other articles in this series:

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


How to Succeed in Motor Control: Olaus Magnus, Donald Rumsfeld, and YouTube

Jason Sachs December 11, 2016

Almost four years ago, I had this insight — we were doing it wrong! Most of the application notes on motor control were about the core algorithms: various six-step or field-oriented control methods, with Park and Clarke transforms, sensorless estimators, and whatnot. It was kind of like a driving school would be, if they taught you how the accelerator and brake pedal worked, and how the four-stroke Otto cycle works in internal combustion engines, and handed you a written...


Round Round Get Around: Why Fixed-Point Right-Shifts Are Just Fine

Jason Sachs November 22, 20163 comments

Today’s topic is rounding in embedded systems, or more specifically, why you don’t need to worry about it in many cases.

One of the issues faced in computer arithmetic is that exact arithmetic requires an ever-increasing bit length to avoid overflow. Adding or subtracting two 16-bit integers produces a 17-bit result; multiplying two 16-bit integers produces a 32-bit result. In fixed-point arithmetic we typically multiply and shift right; for example, if we wanted to multiply some...


Elliptic Curve Cryptography

Mike November 16, 20156 comments

Secure online communications require encryption. One standard is AES (Advanced Encryption Standard) from NIST. But for this to work, both sides need the same key for encryption and decryption. This is called Private Key encryption.


Ten Little Algorithms, Part 5: Quadratic Extremum Interpolation and Chandrupatla's Method

Jason Sachs November 11, 20159 comments

Today we will be drifting back into the topic of numerical methods, and look at an algorithm that takes in a series of discretely-sampled data points, and estimates the maximum value of the waveform they were sampled from.


Polynomial Math

Mike November 3, 20152 comments

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


Number Theory for Codes

Mike October 22, 20156 comments

Everything in the digital world is encoded.  ASCII and Unicode are combinations of bits which have specific meanings to us.  If we try to interpret a compiled program as Unicode, the result is a lot of garbage (and beeps!)  To reduce errors in transmissions over radio links we use Error Correction Codes so that even when bits are lost we can recover the ASCII or Unicode original.  To prevent anyone from understanding a transmission we can encrypt the raw data...


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


How to Succeed in Motor Control: Olaus Magnus, Donald Rumsfeld, and YouTube

Jason Sachs December 11, 2016

Almost four years ago, I had this insight — we were doing it wrong! Most of the application notes on motor control were about the core algorithms: various six-step or field-oriented control methods, with Park and Clarke transforms, sensorless estimators, and whatnot. It was kind of like a driving school would be, if they taught you how the accelerator and brake pedal worked, and how the four-stroke Otto cycle works in internal combustion engines, and handed you a written...


Shibboleths: The Perils of Voiceless Sibilant Fricatives, Idiot Lights, and Other Binary-Outcome Tests

Jason Sachs September 29, 2019

AS-SALT, JORDAN — Dr. Reza Al-Faisal once had a job offer from Google to work on cutting-edge voice recognition projects. He turned it down. The 37-year-old Stanford-trained professor of engineering at Al-Balqa’ Applied University now leads a small cadre of graduate students in a government-sponsored program to keep Jordanian society secure from what has now become an overwhelming influx of refugees from the Palestinian-controlled West Bank. “Sometimes they visit relatives...


Elliptic Curve Cryptography - Basic Math

Mike October 10, 2023

An introduction to the math of elliptic curves for cryptography. Covers the basic equations of points on an elliptic curve and the concept of point addition as well as multiplication.


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


Number Theory for Codes

Mike October 22, 20156 comments

Everything in the digital world is encoded.  ASCII and Unicode are combinations of bits which have specific meanings to us.  If we try to interpret a compiled program as Unicode, the result is a lot of garbage (and beeps!)  To reduce errors in transmissions over radio links we use Error Correction Codes so that even when bits are lost we can recover the ASCII or Unicode original.  To prevent anyone from understanding a transmission we can encrypt the raw data...


A Second Look at Slew Rate Limiters

Jason Sachs January 14, 2022

I recently had to pick a slew rate for a current waveform, and I got this feeling of déjà vu… hadn’t I gone through this effort already? So I looked, and lo and behold, way back in 2014 I wrote an article titled Slew Rate Limiters: Nonlinear and Proud of It! where I explored the effects of two types of slew rate limiters, one feedforward and one feedback, given a particular slew rate \( R \).

Here was one figure I published at the time:

This...


What does it mean to be 'Turing complete'?

Nathan Jones October 16, 20235 comments

The term "Turing complete" describes all computers and even some things we don't expect to be as powerful as a typical computer. In this article, I describe what it means and discuss the implications of Turing completeness on projects that need just a little more power, on alternative processor designs, and even security.


Elliptic Curve Cryptography - Key Exchange and Signatures

Mike October 21, 2023

Elliptic curve mathematics over finite fields helps solve the problem of exchanging secret keys for encrypted messages as well as proving a specific person signed a particular document. This article goes over simple algorithms for key exchange and digital signature using elliptic curve mathematics. These methods are the essence of elliptic curve cryptography (ECC) used in applications such as SSH, TLS and HTTPS.


Polynomial Math

Mike November 3, 20152 comments

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