Linear Feedback Shift Registers for the Uninitiated, Part XI: Pseudorandom Number Generation
Last time we looked at the use of LFSRs in counters and position encoders.
This time we’re going to look at pseudorandom number generation, and why you may — or may not — want to use LFSRs for this purpose.
But first — an aside:
Science Fair 1983When I was in fourth grade, my father bought a Timex/Sinclair 1000. This was one of several personal computers introduced in 1982, along with the Commodore 64. The...
Linear Feedback Shift Registers for the Uninitiated, Part X: Counters and Encoders
Last time we looked at LFSR output decimation and the computation of trace parity.
Today we are starting to look in detail at some applications of LFSRs, namely counters and encoders.
CountersI mentioned counters briefly in the article on easy discrete logarithms. The idea here is that the propagation delay in an LFSR is smaller than in a counter, since the logic to compute the next LFSR state is simpler than in an ordinary counter. All you need to construct an LFSR is
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
Obsolete? Yes. Still in use? Yes. How do you use it? Ummm...
In today's world of constantly changing technology, quick parts availability, and seemingly endless options, some things can't change. It isn't a big deal to wait a day or less for a computer upgrade to arrive. It seems program size increases proportionally to hard drive size. The old is discarded and replaced with the new. Hard drives can hold terrabytes and even SD cards can hold gigabytes of information.
Now, suppose a system can't be changed. It is still...
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.
Lazy Properties in Python Using Descriptors
This is a bit of a side tangent from my normal at-least-vaguely-embedded-related articles, but I wanted to share a moment of enlightenment I had recently about descriptors in Python. The easiest way to explain a descriptor is a way to outsource attribute lookup and modification.
Python has a bunch of “magic” methods that are hooks into various object-oriented mechanisms that let you do all sorts of ridiculously clever things. Whether or not they’re a good idea is another...
Android for Embedded Devices - 5 Reasons why Android is used in Embedded Devices
The embedded purists are going to hate me for this. How can you even think of using Android on an embedded system ? It’s after all a mobile phone operating system/software.
Sigh !! Yes I did not like Android to begin with, as well - for use on an Embedded System. But sometimes I think the market and needs decide what has to be used and what should not be. This is one such thing. Over the past few years, I have learned to love Android as an embedded operating system....
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...
Linear Feedback Shift Registers for the Uninitiated, Part V: Difficult Discrete Logarithms and Pollard's Kangaroo Method
Last time we talked about discrete logarithms which are easy when the group in question has an order which is a smooth number, namely the product of small prime factors. Just as a reminder, the goal here is to find \( k \) if you are given some finite multiplicative group (or a finite field, since it has a multiplicative group) with elements \( y \) and \( g \), and you know you can express \( y = g^k \) for some unknown integer \( k \). The value \( k \) is the discrete logarithm of \( y \)...
Using the Beaglebone PRU to achieve realtime at low cost
Introduction
I work as an engineer in a synchrotron facility. A few weeks ago, I helped the people in charge of the power supply developments to integrate a realtime control algorithm on a prototype platform: a BeagleBone Black (BBB) running Linux. I had already worked with this board in the past, and I found it very interesting given its excellent resources versus price ratio (around 40 euros). This time, I was impressed by its realtime capabilities. I thought it would be a good idea to...
VHDL tutorial - Creating a hierarchical design
In earlier blog entries I introduced some of the basic VHDL concepts. First, developing a function ('VHDL tutorial') and later verifying and refining it ('VHDL tutorial - part 2 - Testbench' and 'VHDL tutorial - combining clocked and sequential logic'). In this entry I will describe how to...
How FPGAs work, and why you'll buy one
Today, pretty much everyone has a CPU, a DSP and a GPU, buried somewhere in their PC, phone, car, etc. Most don't know or care that they bought any of these, but they did.
Will everyone, at some future point, also buy an FPGA? The market size of FPGAs today is about 1% of the annual global semiconductor sales (~$3B vs ~$300B). Will FPGA eventually...
Lazy Properties in Python Using Descriptors
This is a bit of a side tangent from my normal at-least-vaguely-embedded-related articles, but I wanted to share a moment of enlightenment I had recently about descriptors in Python. The easiest way to explain a descriptor is a way to outsource attribute lookup and modification.
Python has a bunch of “magic” methods that are hooks into various object-oriented mechanisms that let you do all sorts of ridiculously clever things. Whether or not they’re a good idea is another...
Important Programming Concepts (Even on Embedded Systems) Part V: State Machines
Other articles in this series:
- Part I: Idempotence
- Part II: Immutability
- Part III: Volatility
- Part IV: Singletons
- Part VI: Abstraction
Oh, hell, this article just had to be about state machines, didn’t it? State machines! Those damned little circles and arrows and q’s.
Yeah, I know you don’t like them. They bring back bad memories from University, those Mealy and Moore machines with their state transition tables, the ones you had to write up...
Introduction to Microcontrollers - Buttons and Bouncing
What Is A Button?
To your hardware, that is. As discussed in Introduction to Microcontrollers - More On GPIO, a button (or key, or switch, or any form of mechanical contact) is generally hooked up to a microcontroller so as to generate a certain logic level when pushed or closed or "active," and the opposite logic level when unpushed or open or "inactive." The active logic level can be either '0' or '1', but for reasons both historical and electrical, an...
Android for Embedded Devices - 5 Reasons why Android is used in Embedded Devices
The embedded purists are going to hate me for this. How can you even think of using Android on an embedded system ? It’s after all a mobile phone operating system/software.
Sigh !! Yes I did not like Android to begin with, as well - for use on an Embedded System. But sometimes I think the market and needs decide what has to be used and what should not be. This is one such thing. Over the past few years, I have learned to love Android as an embedded operating system....
VHDL tutorial
When I was first introduced to "Programmable Logic" several years ago, it was an answer to many of the challenges that I was struggling with. Though the parts were primitive by today's standards (simple PALs verses FPGA), they were an extremely cost effective tool addressing the need for specialized logic blocks.
I have continued to incorporate these powerful blocks into many of my latest designs. My current favorite part line is the Xilinx CoolRunner series (XC2Cxxx). In this...
How to Build a Fixed-Point PI Controller That Just Works: Part I
This two-part article explains five tips to make a fixed-point PI controller work well. I am not going to talk about loop tuning -- there are hundreds of articles and books about that; any control-systems course will go over loop tuning enough to help you understand the fundamentals. There will always be some differences for each system you have to control, but the goals are the same: drive the average error to zero, keep the system stable, and maximize performance (keep overshoot and delay...
Chebyshev Approximation and How It Can Help You Save Money, Win Friends, and Influence People
Well... maybe that's a stretch. I don't think I can recommend anything to help you win friends. Not my forte.
But I am going to try to convince you why you should know about Chebyshev approximation, which is a technique for figuring out how you can come as close as possible to computing the result of a mathematical function, with a minimal amount of design effort and CPU power. Let's explore two use cases:
- Amy has a low-power 8-bit microcontroller and needs to compute \( \sqrt{x} \)...
VHDL tutorial - A practical example - part 2 - VHDL coding
In part 1 of this series we focused on the hardware design, including some of the VHDL definitions of the I/O characteristics of the CPLD part. In part 2, we will describe the VHDL logic of the CPLD for this design.
With any design, the first step to gather the requirements for the job at hand. From part 1 of this article, I have copied two sections that address some of the requirements for the CPLD design.
The data acquisition engine has the...
Zebras Hate You For No Reason: Why Amdahl's Law is Misleading in a World of Cats (And Maybe in Ours Too)
I’ve been wasting far too much of my free time lately on this stupid addicting game called the Kittens Game. It starts so innocently. You are a kitten in a catnip forest. Gather catnip.
And you click on Gather catnip and off you go. Soon you’re hunting unicorns and building Huts and studying Mathematics and Theology and so on. AND IT’S JUST A TEXT GAME! HTML and Javascript, that’s it, no pictures. It’s an example of an
Analog-to-Digital Confusion: Pitfalls of Driving an ADC
Imagine the following scenario:You're a successful engineer (sounds nice, doesn't it!) working on a project with three or four circuit boards. More than even you can handle, so you give one of them over to your coworker Wayne to design. Wayne graduated two years ago from college. He's smart, he's a quick learner, and he's really fast at designing schematics and laying out circuit boards. It's just that sometimes he takes some shortcuts... but in this case the circuit board is just something...
10 Circuit Components You Should Know
Chefs have their miscellaneous ingredients, like condensed milk, cream of tartar, and xanthan gum. As engineers, we too have quite our pick of circuits, and a good circuit designer should know what's out there. Not just the bread and butter ingredients like resistors, capacitors, op-amps, and comparators, but the miscellaneous "gadget" components as well.
Here are ten circuit components you may not have heard of, but which are occasionally quite useful.
1. Multifunction gate (
Byte and Switch (Part 1)
Imagine for a minute you have an electromagnet, and a microcontroller, and you want to use the microcontroller to turn the electromagnet on and off. Sounds pretty typical, right?We ask this question on our interviews of entry-level electrical engineers: what do you put between the microcontroller and the electromagnet?We used to think this kind of question was too easy, but there are a surprising number of subtleties here (and maybe a surprising number of job candidates that were missing...
Introduction to Microcontrollers - Interrupts
It's Too Soon To Talk About Interrupts!That, at least, could be one reaction to this chapter. But over the years I've become convinced that new microcontroller programmers should understand interrupts before being introduced to any complex peripherals such as timers, UARTs, ADCs, and all the other powerful function blocks found on a modern microcontroller. Since these peripherals are commonly used with interrupts, any introduction to them that does not...
VHDL tutorial - Creating a hierarchical design
In earlier blog entries I introduced some of the basic VHDL concepts. First, developing a function ('VHDL tutorial') and later verifying and refining it ('VHDL tutorial - part 2 - Testbench' and 'VHDL tutorial - combining clocked and sequential logic'). In this entry I will describe how to...
Help, My Serial Data Has Been Framed: How To Handle Packets When All You Have Are Streams
Today we're going to talk about data framing and something called COBS, which will make your life easier the next time you use serial communications on an embedded system -- but first, here's a quiz:
Quick Diversion, Part I: Which of the following is the toughest area of electrical engineering? analog circuit design digital circuit design power electronics communications radiofrequency (RF) circuit design electromagnetic...Arduino robotics #1 - motor control
Arduino Robotics
Beginner robotics is a series of article chronicling my first autonomous robot build, Clusterbot. This build is meant to be affordable, relatively easy and instructive. The total cost of the build is around $50.
1. Arduino robotics - motor control2. Arduino robotics - chassis, locomotion and power3. Arduino robotics - wiring, coding and a test run4.Data Hiding in C
Strictly speaking, C is not an object-oriented language. Although it provides some features that fit into the object-oriented paradigm it has never had the full object-oriented focus that its successor C++ offers. C++ introduced some very useful concepts and abilities that I miss when I’m developing in ANSI C. One such concept is protected member variables and functions.
When you declare a class in C++ you can also declare member variables and functions as part of that class. Often, these...
Two jobs
For those of you following closely embeddedrelated and the other related sites, you might have noticed that I have been less active for the last couple of months, and I will use this blog post to explain why. The main reason is that I got myself involved into a project that ended up using a better part of my cpu than I originally thought it would.
I currently have two jobs: one as an electrical/dsp engineer recycled as a web publisher and the other as a parent of three kids. My job...
October winner announced
If you are a regular visitor of EmbeddedRelated, you are most likely aware that I have been running monthly draws lately for users of the site who are helping me to clean up the archives by rating threads in the forums section.
For the month of August, the member "Cryptoman" won a iPad, and for the month of September, 10 members won $50 each.
For October, the winner of the new iPod Touch is the member with the username "hssathya".
The winner of the next draw will win...
Behold, the New Comments System!
I have just finished implementing a new system for commenting the blogs. It uses Ajax extensively, so the page won't reload if you post a comment. And it is a 'threaded' system, which means that if you post a reply to a comment, it will be attached to it.
What do you think? I personally love it. Please go ahead and test it with a quick comment.
Although it is better to be logged in to post a comment, non-registered users can also comment, but they will have...
Best Embedded Systems pdf Documents Out There
There are thousands of pdf documents related to Embedded Systems available online. In fact, when I do a search in Google for:
embedded systems filetype:pdf
I get 4,340,000 results! A huge mix of articles, promotional documents, theses, etc.
Out of these 4 millions+ documents, I suspect that there must be at least a few hundreds jewels that deserve to be given more visibility.
Today, I am asking for your help (again!) to build a directory of some of the most useful pdf files out...
New Discussion Group for Users of TI ARM based MCUs
If you are a user of an ARM based TI Microcontroller, please feel free to join the new "TI ARM processors MCUs" discussion group by sending a blank email to: tiarm-subscribe@yahoogroups.com This discussion group will be moderated, so you don't have to worry about receiving more spam than you probably already get. It usually takes a few weeks for a group to gain momentum, so don't worry if the activity level is low for a little while, but make sure to join so you don't miss the good...
New TI MCU Resource Center
I am happy to announce the publication of the new "TI MCU Resource Center" on EmbeddedRelated.com, where TI will regularly add videos and articles to keep you informed on their latest and greatest MCU related products.
To access the new section, you'll find a link in the main menu of the site at the top of the page.
Blogs Section Now Online!
I am happy to announce that the blog section is now online.
Last week, I sent an email to all the members of EmbeddedRelated.com to ask for embedded systems experts who would be interested in blogging on the site. The response was very positive and I have selected 10 highly qualified individuals who will soon be writing here about all sorts of embedded systems related subjects. I am currently in the process of receiving their info (bio, photo, username, etc) and creating their bloggers'...
