Linear Feedback Shift Registers for the Uninitiated, Part IX: Decimation, Trace Parity, and Cyclotomic Cosets
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...
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
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.
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...
Ten Little Algorithms, Part 6: Green’s Theorem and Swept-Area Detection
Other articles in this series:
- Part 1: Russian Peasant Multiplication
- Part 2: The Single-Pole Low-Pass Filter
- Part 3: Welford's Method (And Friends)
- Part 4: Topological Sort
- Part 5: Quadratic Extremum Interpolation and Chandrupatla's Method
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...
From Baremetal to RTOS: A review of scheduling techniques
Transitioning from bare-metal embedded software development to a real-time operating system (RTOS) can be a difficult endeavor. Many developers struggle with the question of whether they should use an RTOS or simply use a bare-metal scheduler. One of the goals of this series is to walk developers through the transition and decision making process of abandoning bare-metal thinking and getting up to speed quickly with RTOSes. Before diving into the details of RTOSes, the appropriate first step...
Data Types for Control & DSP
There's a lot of information out there on what data types to use for digital signal processing, but there's also a lot of confusion, so the topic bears repeating.
I recently posted an entry on PID control. In that article I glossed over the data types used by showing "double" in all of my example code. Numerically, this should work for most control problems, but it can be an extravagant use of processor resources. There ought to be a better way to determine what precision you need...
Mathematics and Cryptography
The mathematics of number theory and elliptic curves can take a life time to learn because they are very deep subjects. As engineers we don't have time to earn PhD's in math along with all the things we have to learn just to make communications systems work. However, a little learning can go a long way to helping make our communications systems secure - we don't need to know everything. The following articles are broken down into two realms, number theory and elliptic...
Elliptic Curve Digital Signatures
A digital signature is used to prove a message is connected to a specific sender. The sender can not deny they sent that message once signed, and no one can modify the message and maintain the signature. The message itself is not necessarily secret. Certificates of authenticity, digital cash, and software distribution use digital signatures so recipients can verify they are getting what they paid for.
Since messages can be of any length and mathematical algorithms always use fixed...
Elliptic Curve Key Exchange
Elliptic Curve Cryptography is used to create a Public Key system that allows two people (or computers) to exchange public data so that both sides know a secret that no one else can find in a reasonable time. The simplest method uses a fixed public key for each person. Once cracked, every message ever sent with that key is open. More advanced key exchange systems have "perfect forward secrecy" which means that even if one message key is cracked, no other message will...
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
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...
Ten Little Algorithms, Part 6: Green’s Theorem and Swept-Area Detection
Other articles in this series:
- Part 1: Russian Peasant Multiplication
- Part 2: The Single-Pole Low-Pass Filter
- Part 3: Welford's Method (And Friends)
- Part 4: Topological Sort
- Part 5: Quadratic Extremum Interpolation and Chandrupatla's Method
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...
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.
Ten Little Algorithms, Part 4: Topological Sort
Other articles in this series:
- Part 1: Russian Peasant Multiplication
- Part 2: The Single-Pole Low-Pass Filter
- Part 3: Welford's Method (And Friends)
- Part 5: Quadratic Extremum Interpolation and Chandrupatla's Method
- Part 6: Green’s Theorem and Swept-Area Detection
Today we’re going to take a break from my usual focus on signal processing or numerical algorithms, and focus on...
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
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.
Linear Regression with Evenly-Spaced Abscissae
What a boring title. I wish I could come up with something snazzier. One word I learned today is studentization, which is just the normalization of errors in a curve-fitting exercise by the sample standard deviation (e.g. point \( x_i \) is \( 0.3\hat{\sigma} \) from the best-fit linear curve, so \( \frac{x_i - \hat{x}_i}{\hat{\sigma}} = 0.3 \)) — Studentize me! would have been nice, but I couldn’t work it into the topic for today. Oh well.
I needed a little break from...
Elliptic Curve Key Exchange
Elliptic Curve Cryptography is used to create a Public Key system that allows two people (or computers) to exchange public data so that both sides know a secret that no one else can find in a reasonable time. The simplest method uses a fixed public key for each person. Once cracked, every message ever sent with that key is open. More advanced key exchange systems have "perfect forward secrecy" which means that even if one message key is cracked, no other message will...
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.
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.
Linear Feedback Shift Registers for the Uninitiated, Part IX: Decimation, Trace Parity, and Cyclotomic Cosets
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...
One Clock Cycle Polynomial Math
Error correction codes and cryptographic computations are most easily performed working with GF(2^n)
Elliptic Curve Key Exchange
Elliptic Curve Cryptography is used to create a Public Key system that allows two people (or computers) to exchange public data so that both sides know a secret that no one else can find in a reasonable time. The simplest method uses a fixed public key for each person. Once cracked, every message ever sent with that key is open. More advanced key exchange systems have "perfect forward secrecy" which means that even if one message key is cracked, no other message will...
Number Theory for Codes
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...
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.
Polynomial Inverse
One of the important steps of computing point addition over elliptic curves is a division of two polynomials.
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.
Elliptic Curve Digital Signatures
A digital signature is used to prove a message is connected to a specific sender. The sender can not deny they sent that message once signed, and no one can modify the message and maintain the signature. The message itself is not necessarily secret. Certificates of authenticity, digital cash, and software distribution use digital signatures so recipients can verify they are getting what they paid for.
Since messages can be of any length and mathematical algorithms always use fixed...
