Basic Wireless Communication for Microcontrollers
Chapter 4 - Design Project 3: 900MHz Automatic Error-Correcting Data Link
Error Control Coding
When sending data over an RF link, it is inevitable that errors will sometimes occur. For systems where the signal to noise ratio is normally high, errors occur due to interference from other transmitters, lightning, or appliances which produce electrical noise. For RF links operating inside a house or in a town or city, multipath and intervening walls or buildings can cause tremendous variations in signal strength. This can cause errors even in the absence of interfering signals. There are also situations where the signal to noise ratio is inherently low (such as links to deep space probes which produce very weak signals) and it is necessary to extract the correct data from the incoming noisy data stream.
Your brain is exceptionally good at understanding speech even when noise and interference are present. It does this by exploiting redundant information (words are formed in such a way that they are still understandable even when garbled or distorted) and by prompting you to ask for a repetition when it cannot understand what was said. The field of Error Control Coding seeks to apply these same principles to electronic commmunication.
Frame Check Sequences and Automatic Repetition
In this particular project, we use a type of error control called automatic repeat request (or ARQ for short). Just as it sounds, this means that the microcontroller on one end of the link (call it microcontroller B) asks the other end (microcontroller A) to repeat what A sent when B detects an error. The error is detected by including a frame check sequence (FCS) in the data packet.
The FCS is computed mathematically,by the sender, from the bits in the message. The receiver then performs a similar computation to determine if the FCS still matches the data. When an error or errors occur in either the message or FCS, it is highly likely that the FCS will no longer match. I say likely because the FCS is much shorter (in bits) than the message and therefore more than one message corresponds to the same FCS. However, if you design the FCS computation method well, you can make it unlikely that errors will transform the original message into another which matches the same FCS. We will use a method called a Cyclic Redundancy Check (CRC) to compute and check the FCS. For more on how CRCs work or more information on error control coding in general, see the bibliography. Our CRC will take up 16 bits of each packet and based on my experience with systems that use the same type of CRC, should be very effective in detecting errors.
The references given in the bibliography explain CRCs in detail but it is worth mentioning the basis for how they work. If the entire message is treated as one long number(for a 10 byte message, an 80 bit number), and we divide it by another number (call it A), we get a remainder B, which is less than A. If we compute A-B=C, and add C to the original message, we get D, a new number which is guaranteed to be divisible by A. We can now send D over the radio rather than the original message, and the other end can get a good idea of whether an error or errors occurred by repeating the process. That is, divide what they receive (call it E) by A. If the result is zero, it is highly likely that E=D and no errors occurred. Otherwise, an error or errors corrupted the message. This is the basis for CRCs. To make the mathematical operations simpler, an operation similar to, but not exactly equivalent to, division is used to compute B. Also, instead of having to do addition on huge numbers, some zero bits are placed at the end of the original message so that adding C to it just means placing C in those bits.
Other Methods of Error Detection
Besides using an FCS, there are several other ways of determining if an error has occurred. One of the simplest is to send the message several times and compare the copies. Another method is called parity. In parity, a bit is added after every byte. This bit is set or cleared in order to make sure the number of one bits in the byte is always even (even parity) or always odd (odd parity). An alternative view of this is that a sum of all the bits, including the parity bit, in base 2 will always be either 0 (even parity) or 1 (odd parity) if the byte is correct.
These methods each have advantages and disadvantages and are useful in particular cases. The major figure of merit for error detection schemes is to compare the extra length they add to the packet with the probability that an error will be able to get past them. One of the reasons why CRCs are so popular is that they detect a large fraction of all possible errors, add very little data (only a few percent), and are easy to compute (the method is simple and is compatible with a serial data stream, that is, it only needs to look at one bit of the message at a time).
Forward Error Correction
Sometimes it isn't possible to use ARQ error control. For example, if you are communicating with a space probe out near Jupiter, it would take hours for the repeat request to even reach the probe. In more mundane cases, your link might not be bidirectional (that is, there is only a transmitter on one end and only a receiver on the other, so there is no way to send a repeat request). Finally, if you want to use error control coding on recorded data (like on a CD), there is no way to ask for a repeat. Using error control techniques, it is possible to handle these cases by correcting errors in the received data without needing more information from the transmitter. This is often called FEC for Forward Error Correction.
The simplest method of FEC is to send the message multiple times and then go through it bit by bit, determining what the most likely setting (0 or 1) for each bit is depending on whether the majority of the copies of the message have a 0 or a 1 in that bit position. This method, however, uses a large amount of redundant information. More efficient codes usually employ matrix algebra and number theory to produce mathematical operations which can correct multiple errors. Some of these schemes are Hamming,BCH (Bose Chaudhuri Hocquenghem), RS (Reed-Solomon), and Turbo codes. Unfortunately, explaining how these codes work is well beyond the scope of this tutorial. It is worthwhile, though, to try to gain some understanding of them because, from a communications engineering point of view, they are fascinating. They are a large part of what allows communication with deep space probes, as well as how CDs can store so much data yet be manufactured so cheaply (and imperfectly). Some of these codes can be implemented in microcontrolers and it isn't out of the question that you might possibly sometime have a project which could greatly benefit from forward error correction. For more information, please see the bibliography
BACK Table of Contents
NEXT