EmbeddedRelated.com

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


Linear Feedback Shift Registers for the Uninitiated, Part VIII: Matrix Methods and State Recovery

Jason Sachs November 21, 20174 comments

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 Dregs

Elwyn 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

Jason Sachs November 13, 20171 comment

The last four articles were on algorithms used to compute with finite fields and shift registers:

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

Jason Sachs October 18, 20171 comment

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

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


From Baremetal to RTOS: A review of scheduling techniques

Jacob Beningo June 8, 201617 comments

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

Tim Wescott April 26, 20166 comments

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

Mike December 14, 20151 comment

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

Mike December 9, 2015

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

Mike December 3, 2015

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


Mathematics and Cryptography

Mike December 14, 20151 comment

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


You Don't Need an RTOS (Part 2)

Nathan Jones May 7, 20246 comments

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

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


One Clock Cycle Polynomial Math

Mike November 20, 20157 comments

Error correction codes and cryptographic computations are most easily performed working with GF(2^n)


Elliptic Curve Key Exchange

Mike December 3, 2015

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

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


You Don't Need an RTOS (Part 3)

Nathan Jones June 3, 20241 comment

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

Mike November 23, 20152 comments

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

Massimiliano Pagani May 22, 20244 comments

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

Mike December 9, 2015

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