Practical CRCs for Embedded Systems
CRCs are a very practical tool for embedded systems: you're likely to need to use one as part of a communications protocol or to verify the integrity of a program image before writing it to flash. But CRCs can be difficult to understand and tricky to implement. The first time I attempted to write CRC code from scratch I failed once. Then twice. Then three times. Eventually I gave up and used an existing library. I consider myself intelligent: I got A's...
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...
Ten Little Algorithms, Part 3: Welford's Method (and Friends)
Other articles in this series:
- Part 1: Russian Peasant Multiplication
- Part 2: The Single-Pole Low-Pass Filter
- Part 4: Topological Sort
- Part 5: Quadratic Extremum Interpolation and Chandrupatla's Method
- Part 6: Green’s Theorem and Swept-Area Detection
Last time we talked about a low-pass filter, and we saw that a one-line...
Ten Little Algorithms, Part 2: The Single-Pole Low-Pass Filter
Other articles in this series:
- Part 1: Russian Peasant Multiplication
- Part 3: Welford's Method (And Friends)
- Part 4: Topological Sort
- Part 5: Quadratic Extremum Interpolation and Chandrupatla's Method
- Part 6: Green’s Theorem and Swept-Area Detection
I’m writing this article in a room with a bunch of other people talking, and while sometimes I wish they would just SHUT UP, it would be...
Ten Little Algorithms, Part 1: Russian Peasant Multiplication
This blog needs some short posts to balance out the long ones, so I thought I’d cover some of the algorithms I’ve used over the years. Like the Euclidean algorithm and Extended Euclidean algorithm and Newton’s method — except those you should know already, and if not, you should be locked in a room until you do. Someday one of them may save your life. Well, you never know.
Other articles in this series:
- Part 1:
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...
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...
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...
Polynomial Math
Elliptic Curve Cryptography is used as a public key infrastructure to secure credit cards, phones and communications links. All these devices use either FPGA's or embedded microprocessors to compute the algorithms that make the mathematics work. While the math is not hard, it can be confusing the first time you see it. This blog is an introduction to the operations of squaring and computing an inverse over a finite field which are used in computing Elliptic Curve arithmetic. ...
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.
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.
Unraveling the Enigma: Object Detection in the World of Pixels
Exploring the realm of embedded systems co-design for object recognition, this blog navigates the convergence of hardware and software in revolutionizing industries. Delving into real-time image analysis and environmental sensing, the discussion highlights advanced object detection and image segmentation techniques. With insights into Convolutional Neural Networks (CNNs) decoding pixel data and autonomously extracting features, the blog emphasizes their pivotal role in modern computer vision. Practical examples, including digit classification using TensorFlow and Keras on the MNIST dataset, underscore the power of CNNs. Through industry insights and visualization aids, the blog unveils a tapestry of innovation, charting a course towards seamless interaction between intelligent embedded systems and the world.
Elliptic Curve Cryptography - Multiple Signatures
The use of point pairing becomes very useful when many people are required to sign one document. This is typical in a contract situation when several people are agreeing to a set of requirements. If we used the method described in the blog on signatures, each person would sign the document, and then the verification process would require checking every single signature. By using pairings, only one check needs to be performed. The only requirement is the ability to verify the...
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.
