Linear Feedback Shift Registers for the Uninitiated
Jason Sachs assembled an eighteen-part deep dive into linear feedback shift registers, connecting the simple shift-register circuit to finite-field algebra and practical tools. The series walks through primitive polynomials, Berlekamp-Massey state recovery, libgf2-based analysis, discrete-log methods, and real-world uses from PRNGs and Gold codes to Reed-Solomon and CRC reverse-engineering. It’s a single reference for engineers who want both theory and working code.
Ten Little Algorithms, Part 7: Continued Fraction Approximation
In this article we explore the use of continued fractions to approximate any particular real number, with practical applications.
Elliptic Curve Cryptography - Multiple Signatures
Point pairings let you compress many independent elliptic-curve signatures into a single verification, reducing n checks to one. This post explains how each signer derives a coefficient from the ordered list of public keys, aggregates signatures on the base group and public keys on the extension group, and verifies everything with one pairing computation. It also flags practical cautions like key validation and agreed ordering.
Elliptic Curve Cryptography - Extension Fields
An introduction to the pairing of points on elliptic curves. Point pairing normally requires curves over an extension field because the structure of an elliptic curve has two independent sets of points if it is large enough. The rules of pairings are described in a general way to show they can be useful for verification purposes.
Elliptic Curve Cryptography - Key Exchange and Signatures
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.
What does it mean to be 'Turing complete'?
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 - Security Considerations
The security of elliptic curve cryptography is determined by the elliptic curve discrete log problem. This article explains what that means. A comparison with real number logarithm and modular arithmetic gives context for why it is called a log problem.
Elliptic Curve Cryptography - Basic Math
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.
New book on Elliptic Curve Cryptography
New book on Elliptic Curve Cryptography now online. Deep discount for early purchase. Will really appreciate comments on how to improve the book because physical printing won't happen for a few more months. Check it out here: http://mng.bz/D9NA
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.
Chebyshev Approximation and How It Can Help You Save Money, Win Friends, and Influence People
Are expensive math libraries or huge lookup tables eating CPU and flash on your microcontroller? In this practical guide Jason Sachs shows how Chebyshev polynomial approximation (with range reduction, splitting, and small interpolated tables) can give near-minimax accuracy while using far less code and runtime. The post compares Taylor series, plain and interpolated tables, and explains how to fit empirical sensor data and evaluate coefficients efficiently.
Linear Feedback Shift Registers for the Uninitiated, Part XVIII: Primitive Polynomial Generation
Jason Sachs walks through how to find primitive polynomials for GF(2) LFSRs, moving from naive exhaustive checks to smarter synthetic constructions. The article compares sieve and constructive methods, shows practical optimizations like parity checks and companion-matrix updates, and demonstrates decimation plus Berlekamp-Massey to generate all primitives from one seed; it also teases a novel Falling Coyote Algorithm for additional speedups.
Elliptic Curve Cryptography - Basic Math
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 XVI: Reed-Solomon Error Correction
Jason Sachs demystifies Reed-Solomon codes with hands-on examples and pragmatic tips for embedded engineers. The article shows why RS encoding is just polynomial division in GF(2^m), why decoding is mathematically heavier, and how to implement encoders in Python and in C-friendly form using LFSRs and table-driven methods. Read this for working code, generator-polynomial examples, and an embedded-minded view of RS practicalities.
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 called libgf2,...
Return of the Delta-Sigma Modulators, Part 1: Modulation
Jason Sachs returns to delta-sigma modulators with a hands-on, code-first treatment that focuses on the DAC side of things. Part 1 walks through first- and second-order kernels, linearized analysis, spectra, and practical coefficient choices while illustrating results with Python simulations. Expect clear rules of thumb for A, R, and B, a derivation of noise shaping behavior, and a useful error bound for RC filtering.
Second-Order Systems, Part I: Boing!!
Jason Sachs takes the spring 'boing' of a doorstop into the math of second-order systems, using the series LRC circuit as a concrete example. He shows two standard transfer-function forms, explains why ωn only scales time while ζ sets the response shape, and derives pole locations plus an exact overshoot formula that helps tune embedded-system responses.
Round Round Get Around: Why Fixed-Point Right-Shifts Are Just Fine
Jason Sachs explains why, in most embedded systems, simple bitwise right-shifts are an acceptable way to do fixed-point division rather than paying the runtime cost to round. He shows the cheap trick of adding 2^(N-1) to implement round-to-nearest, explains unbiased "round-to-even" issues, and compares arithmetic error to much larger ADC and sensor errors. The takeaway: save cycles unless your algorithm or inputs require extra precision.
How to Estimate Encoder Velocity Without Making Stupid Mistakes: Part II (Tracking Loops and PLLs)
Jason Sachs explains why simple differentiation of encoder counts often fails and how tracking loops and PLLs give more robust velocity estimates. Using a pendulum thought experiment and Python examples, he shows how a PI-based tracking loop reduces noise and eliminates steady-state ramp error, and why vector PLLs with quadrature mixing avoid cycle slips and atan2 unwrap pitfalls in noisy or analog sensing.
Linear Feedback Shift Registers for the Uninitiated, Part V: Difficult Discrete Logarithms and Pollard's Kangaroo Method
Most discrete-log problems are hopeless by brute force, but clever algorithms cut that cost to feasible levels. This installment walks through baby-step giant-step, Pollard’s rho and kangaroo methods, and how Silver-Pohlig-Hellman and index calculus leverage group structure to speed attacks on GF(2^n) fields. Jason Sachs includes Python examples, heuristics, and complexity nuggets so you can see when each method is practical.
Chebyshev Approximation and How It Can Help You Save Money, Win Friends, and Influence People
Are expensive math libraries or huge lookup tables eating CPU and flash on your microcontroller? In this practical guide Jason Sachs shows how Chebyshev polynomial approximation (with range reduction, splitting, and small interpolated tables) can give near-minimax accuracy while using far less code and runtime. The post compares Taylor series, plain and interpolated tables, and explains how to fit empirical sensor data and evaluate coefficients efficiently.
How to Estimate Encoder Velocity Without Making Stupid Mistakes: Part II (Tracking Loops and PLLs)
Jason Sachs explains why simple differentiation of encoder counts often fails and how tracking loops and PLLs give more robust velocity estimates. Using a pendulum thought experiment and Python examples, he shows how a PI-based tracking loop reduces noise and eliminates steady-state ramp error, and why vector PLLs with quadrature mixing avoid cycle slips and atan2 unwrap pitfalls in noisy or analog sensing.
Ten Little Algorithms, Part 1: Russian Peasant Multiplication
Jason Sachs revisits a centuries-old multiplication trick and shows why it still matters. He lays out Russian Peasant Multiplication with simple Python code, then reveals how the same shift-and-add pattern maps to GF(2) polynomial arithmetic and to exponentiation by squaring. The post mixes historical context with practical bitwise techniques that are useful for embedded and low-level math work.
Round Round Get Around: Why Fixed-Point Right-Shifts Are Just Fine
Jason Sachs explains why, in most embedded systems, simple bitwise right-shifts are an acceptable way to do fixed-point division rather than paying the runtime cost to round. He shows the cheap trick of adding 2^(N-1) to implement round-to-nearest, explains unbiased "round-to-even" issues, and compares arithmetic error to much larger ADC and sensor errors. The takeaway: save cycles unless your algorithm or inputs require extra precision.
Linear Feedback Shift Registers for the Uninitiated, Part I: Ex-Pralite Monks and Finite Fields
Jason Sachs demystifies linear feedback shift registers with a practical, bitwise view and the algebra that explains why they work. Readable examples compare Fibonacci and Galois implementations, show a simple software implementation, and reveal the correspondence between N-bit Galois LFSRs and GF(2^N) so you can pick taps and reason about maximal-length pseudorandom sequences.
Linear Feedback Shift Registers for the Uninitiated, Part XVI: Reed-Solomon Error Correction
Jason Sachs demystifies Reed-Solomon codes with hands-on examples and pragmatic tips for embedded engineers. The article shows why RS encoding is just polynomial division in GF(2^m), why decoding is mathematically heavier, and how to implement encoders in Python and in C-friendly form using LFSRs and table-driven methods. Read this for working code, generator-polynomial examples, and an embedded-minded view of RS practicalities.
Slew Rate Limiters: Nonlinear and Proud of It!
Slew-rate limits are a small nonlinear detail that often decides whether a controller behaves nicely or wrecks hardware. Jason Sachs walks through why slew limits appear in electronics and actuators, then shows two practical digital ways to impose limits: constraining input increments and constraining input around the output. He compares performance on underdamped second-order systems, gives closed-form intuition for overshoot, and demonstrates simulations with scipy and ODE solvers.
Second-Order Systems, Part I: Boing!!
Jason Sachs takes the spring 'boing' of a doorstop into the math of second-order systems, using the series LRC circuit as a concrete example. He shows two standard transfer-function forms, explains why ωn only scales time while ζ sets the response shape, and derives pole locations plus an exact overshoot formula that helps tune embedded-system responses.
Ten Little Algorithms, Part 5: Quadratic Extremum Interpolation and Chandrupatla's Method
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.
Return of the Delta-Sigma Modulators, Part 1: Modulation
Jason Sachs returns to delta-sigma modulators with a hands-on, code-first treatment that focuses on the DAC side of things. Part 1 walks through first- and second-order kernels, linearized analysis, spectra, and practical coefficient choices while illustrating results with Python simulations. Expect clear rules of thumb for A, R, and B, a derivation of noise shaping behavior, and a useful error bound for RC filtering.
