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.
Flood Fill, or: The Joy of Resource Constraints
When transferred from the PC world to a microcontroller, a famous, tried-and-true graphics algorithm is no longer viable. The challenge of creating an alternative under severe resource constraints is an intriguing puzzle, the kind that keeps embedded development fun and interesting.
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.
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.
Square root in fixed point VHDL
In this blog we will design and implement a fixed point square root function in VHDL. The algorithm is based on the recursive Newton Raphson inverse square root algorithm and the implementation offers parametrizable pipeline depth, word length and the algorithm is built with VHDL records and procedures for easy use.
Linear Feedback Shift Registers for the Uninitiated, Part XV: Error Detection and Correction
Last time, we talked about Gold codes, a specially-constructed set of pseudorandom bit sequences (PRBS) with low mutual cross-correlation, which are used in many spread-spectrum communications systems, including the Global Positioning System.
This time we are wading into the field of error detection and correction, in particular CRCs and Hamming codes.
Ernie, You Have a Banana in Your EarI have had a really really tough time writing this article. I like the...
Linear Regression with Evenly-Spaced Abscissae
Jason Sachs cuts through the matrix algebra to show a tiny trick for linear regression when x values are evenly spaced. You can compute the intercept as the mean and the slope as a simple weighted sum with arithmetic weights, using q = 12/(m^3 - m). The post includes Python examples and a compact routine to get least-squares coefficients without matrix solvers.
Linear Feedback Shift Registers for the Uninitiated, Part XI: Pseudorandom Number Generation
Jason Sachs breaks down when linear feedback shift registers make good pseudorandom sources and when they fail. He shows why LFSR output bits look very different from full-state integer samples, explains their two-valued autocorrelation and quasi-random behavior, and gives practical guidance on when an LFSR is acceptable for fast hardware bit generation and when you should use a proper PRNG instead.
From Baremetal to RTOS: A review of scheduling techniques
Jacob Beningo walks through five common embedded scheduling techniques, showing how each scales from a single super loop to a full RTOS. He highlights practical trade-offs for round-robin, interrupt-driven, queued, cooperative, and RTOS approaches so you can spot when timing becomes fragile and when added complexity is justified. This primer sets up the next post on when to adopt an RTOS.
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 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.
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.
Linear Feedback Shift Registers for the Uninitiated, Part VI: Sing Along with the Berlekamp-Massey Algorithm
Jason Sachs breaks down the Berlekamp-Massey algorithm and shows how to recover an LFSR's minimal connection polynomial from a stream of output bits. The article mixes intuition, worked examples, and Python code to demonstrate the update rule, visual debugging tables, and when the solution is unique. Expect practical implementation notes, a complexity discussion, and a libgf2 example you can run in an IPython notebook.
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.
Data Types for Control & DSP
Control engineers often default to double precision, but Tim Wescott shows that choice can waste CPU cycles on embedded targets. He separates numeric representation into floating point, integer, and fixed-point, then walks through the tradeoffs, including quantization, overflow, and performance. A concrete PID example highlights why integrator precision and ADC scaling should drive your choice of data type rather than habit.
Finite State Machines (FSM) in Embedded Systems (Part 3) - Unuglify C++ FSM with DSL
Domain Specific Languages (DSL) are an effective way to avoid boilerplate or repetitive code. Using DSLs lets the programmer focus on the problem domain, rather than the mechanisms used to solve it. Here I show how to design and implement a DSL using the C++ preprocessor, using the FSM library, and the examples I presented in my previous articles.
Number Theory for Codes
If CRCs have felt like black magic, this post peels back the curtain with basic number theory and polynomial arithmetic over GF(2). It shows how fixed-width processor arithmetic becomes arithmetic in a finite field, how bit sequences are treated as polynomials, and why primitive polynomials generate every nonzero element. You also get practical insights on CRC implementation with byte tables and LFSRs.
Linear Feedback Shift Registers for the Uninitiated, Part XI: Pseudorandom Number Generation
Jason Sachs breaks down when linear feedback shift registers make good pseudorandom sources and when they fail. He shows why LFSR output bits look very different from full-state integer samples, explains their two-valued autocorrelation and quasi-random behavior, and gives practical guidance on when an LFSR is acceptable for fast hardware bit generation and when you should use a proper PRNG instead.
Ten Little Algorithms, Part 6: Green’s Theorem and Swept-Area Detection
Jason shows how Green's Theorem becomes a practical, low-cost method to detect real-time rotation from two orthogonal sensors by accumulating swept area. The post derives a compact discrete integrator S[n] = S[n-1] + (x[n]*(y[n]-y[n-1]) - y[n]*(x[n]-x[n-1]))/2, compares integer and floating implementations, and analyzes noise scaling and sampling rate tradeoffs. Includes Python demos and threshold guidance.
Linear Feedback Shift Registers for the Uninitiated, Part VII: LFSR Implementations, Idiomatic C, and Compiler Explorer
Jason Sachs takes LFSR theory back to real hardware, showing multiple C implementations and dsPIC33E assembly to squeeze cycles out of Galois LFSR updates. He digs into idiomatic C pitfalls like rotate idioms, demonstrates tricks using unions and 16/32-bit views, and shows when inline assembly with SL/RLC and conditional-skip instructions pays off. The article also uses Compiler Explorer and supplies an MPLAB X test harness for verification.
Square root in fixed point VHDL
In this blog we will design and implement a fixed point square root function in VHDL. The algorithm is based on the recursive Newton Raphson inverse square root algorithm and the implementation offers parametrizable pipeline depth, word length and the algorithm is built with VHDL records and procedures for easy use.
Elliptic Curve Cryptography
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.
Data Types for Control & DSP
Control engineers often default to double precision, but Tim Wescott shows that choice can waste CPU cycles on embedded targets. He separates numeric representation into floating point, integer, and fixed-point, then walks through the tradeoffs, including quantization, overflow, and performance. A concrete PID example highlights why integrator precision and ADC scaling should drive your choice of data type rather than habit.
Linear Feedback Shift Registers for the Uninitiated, Part XV: Error Detection and Correction
Last time, we talked about Gold codes, a specially-constructed set of pseudorandom bit sequences (PRBS) with low mutual cross-correlation, which are used in many spread-spectrum communications systems, including the Global Positioning System.
This time we are wading into the field of error detection and correction, in particular CRCs and Hamming codes.
Ernie, You Have a Banana in Your EarI have had a really really tough time writing this article. I like the...
Linear Feedback Shift Registers for the Uninitiated, Part VI: Sing Along with the Berlekamp-Massey Algorithm
Jason Sachs breaks down the Berlekamp-Massey algorithm and shows how to recover an LFSR's minimal connection polynomial from a stream of output bits. The article mixes intuition, worked examples, and Python code to demonstrate the update rule, visual debugging tables, and when the solution is unique. Expect practical implementation notes, a complexity discussion, and a libgf2 example you can run in an IPython notebook.
Linear Feedback Shift Registers for the Uninitiated, Part VIII: Matrix Methods and State Recovery
Matrix methods for LFSRs look intimidating, but Jason Sachs walks through companion-matrix representations and shows why they matter for time shifts and state recovery. He derives lookahead masks from powers of the companion matrix, then translates those matrix insights into efficient bitwise and finite-field algorithms. The article includes two simple state-recovery methods and working Python/libgf2 examples you can run and adapt.
Finite State Machines (FSM) in Embedded Systems (Part 4) - Let 'em talk
No state machine is an island. State machines do not exist in a vacuum, they need to "talk" to their environment and each other to share information and provide synchronization to perform the system functions. In this conclusive article, you will find what kind of problems and which critical areas you need to pay attention to when designing a concurrent system. Although the focus is on state machines, the consideration applies to every system that involves more than one execution thread.
You Don't Need an RTOS (Part 2)
In this second article, we'll tweak the simple superloop in three critical ways that will improve it's worst-case response time (WCRT) to be nearly as good as a preemptive RTOS ("real-time operating system"). We'll do this by adding task priorities, interrupts, and finite state machines. Additionally, we'll discuss how to incorporate a sleep mode when there's no work to be done and I'll also share with you a different variation on the superloop that can help schedule even the toughest of task sets.
