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.
Linear Feedback Shift Registers for the Uninitiated, Part IX: Decimation, Trace Parity, and Cyclotomic Cosets
Taking every jth bit of a maximal-length LFSR uncovers a surprising algebraic structure. Jason Sachs walks through cyclotomic cosets, shows why decimation by powers of two preserves minimal polynomials, and connects LFSR output to trace parity and simple bitmask parity computations. The article uses hands-on Python with libgf2, Berlekamp-Massey, and state recovery so you can reproduce and automate these analyses.
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.
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.
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 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.
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.
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.
Mathematics and Cryptography
Cryptographic math can look intimidating, but this roundup trims it to what FPGA engineers actually need. It groups concise articles on number theory and elliptic curves, focusing on polynomial math over Galois fields, FPGA-friendly inversion and one-clock-cycle techniques, and elliptic-curve key exchange and digital signatures. Read this to learn which subroutines to implement first and how to turn math into Verilog or VHDL.
Elliptic Curve Digital Signatures
Elliptic curve digital signatures deliver compact, strong message authentication by combining a hash of the message with elliptic curve point math. This post walks through the standard sign and verify equations, showing why recomputing a point R' yields the same x coordinate only when the hash matches. It also explains the Nyberg-Rueppel alternative that removes modular inversion and an FPGA-friendly trick of transmitting point D to avoid integer modular arithmetic.
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 - 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.
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 XV: Error Detection and Correction
CRCs and Hamming codes look a lot less magical when you view them as redundancy with a purpose. Jason Sachs walks from parity bits and checksums into finite-field polynomial arithmetic, then shows how CRCs map cleanly onto LFSRs and how Hamming codes use syndromes to locate single-bit errors. It is a practical tour of error detection and correction, with enough worked examples to make the theory feel usable.
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.
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 IX: Decimation, Trace Parity, and Cyclotomic Cosets
Taking every jth bit of a maximal-length LFSR uncovers a surprising algebraic structure. Jason Sachs walks through cyclotomic cosets, shows why decimation by powers of two preserves minimal polynomials, and connects LFSR output to trace parity and simple bitmask parity computations. The article uses hands-on Python with libgf2, Berlekamp-Massey, and state recovery so you can reproduce and automate these analyses.
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.
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.
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.
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.
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.
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.
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.
You Don't Need an RTOS (Part 3)
In this third article I'll share with you a few cooperative schedulers (with a mix of both free and commercial licenses) that implement a few of the OS primitives that the "Superduperloop" is currently missing, possibly giving you a ready-to-go solution for your system. On the other hand, I don't think it's all that hard to add thread flags, binary and counting semaphores, event flags, mailboxes/queues, a simple Observer pattern, and something I call a "marquee" to the "Superduperloop"; I'll show you how to do that in the second half of this article and the next. Although it will take a little more work than just using one of the projects above, it will give you the maximum amount of control over your system and it will let you write tasks in ways you could only dream of using an RTOS or other off-the-shelf system.
Mathematics and Cryptography
Cryptographic math can look intimidating, but this roundup trims it to what FPGA engineers actually need. It groups concise articles on number theory and elliptic curves, focusing on polynomial math over Galois fields, FPGA-friendly inversion and one-clock-cycle techniques, and elliptic-curve key exchange and digital signatures. Read this to learn which subroutines to implement first and how to turn math into Verilog or VHDL.
One Clock Cycle Polynomial Math
Error correction codes and cryptographic computations are most easily performed working with GF(2^n)
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.
Polynomial Inverse
One of the important steps of computing point addition over elliptic curves is a division of two polynomials.
