The Power of Patterns at Play
DSSS or Direct Sequence Spread Spectrum is used in a huge variety of wired and wireless systems—everything from Wi-Fi to Zigbee. In this article, Robert examines how DSSS works and why it’s so common. This may give readers some ideas for how to improve the performance of their next projects, because DSSS is easy to implement on an MCU.
Welcome back to “The Darker Side.” Regular readers may recall a column I wrote a while ago about correlations (“The Darker Side: Correlation techniques,” Circuit Cellar 299, June, 2015). In that article, I briefly stated that such correlations are used by a family of high-performance transmission systems nicknamed DSSS (Direct Sequence Spread Spectrum).
This month, why not dig a little more into this subject! As you will see, DSSS is used in dozens of wired and wireless systems, including Wi-Fi, GPS and Zigbee, so understanding it makes sense. As usual, my goal will be to show you how DSSS works and why it is so common, without any complex math. I hope this will give you some ideas about how to improve the performance of your next projects, since DSSS can be implemented easily on a microcontroller (MCU)!
REFRESHER ON CORRELATIONS
Let’s start with a short refresher. Basically, a correlation—or more exactly a cross-correlation—is a measure of similarity of two signals. These two signals are usually a short, known pattern and a longer signal that may include copies of this pattern. The goal is to find them, even if the signal is very noisy. You will not be surprised to learn that correlations are used everywhere, from acoustic echo cancellation and interference avoidance to high-performance receivers, but also from statistical analysis to cryptanalysis.
How does it work? In a nutshell, a correlation is a measure of the similarity of the two signals, as a function of the displacement of one relative to the other. When the pattern is aligned with its copy in the signal, then the correlation is high. You may think the algorithm should be complex, but you would be wrong. The calculation is simply a so-called “dot-product:” Start by positioning the pattern above the first points of the signal. For each sample of the pattern, multiply the corresponding pattern and signal values, then sum all these results. You’ve got the first point of the correlation. Then, shift the pattern by one sample on the right and do the same calculation again to find the second point of the correlation, and so on. You then just have to locate the peaks on the calculated correlation. Their position shows where the pattern is located in the signal, and their amplitudes are directly proportional to the amplitude of the replica.
An example is shown in Figure 1. The middle plot shows an arbitrary pattern. Here I took a pattern made with a saw-tooth, then a small step. The top plot shows a signal. It is noisy, but includes two replicas of the pattern, with different amplitudes. Where are these replications? Do you see them?
If not, then simply calculate the correlation of the signal and pattern. I did that for you, and the result is shown in the bottom plot. Two peaks are clearly visible, and they directly indicate the beginning of each replica of the pattern in the signal, along with their respective levels. Cool, isn’t it?
A last word on correlations. In my example, both the signal and pattern are analog values. The same algorithm also works for digital signals, made only with 0’s and 1’s. The multiplication operation has simply to be replaced by a negated XOR (1 if both logic levels are equal, otherwise 0), which is even simpler. One again, this was just a refresher, but now you have enough information on correlation to understand what DSSS is.
The first two letters of DSSS are “Direct Sequence.” Why? Imagine that you have a bit stream to transmit. Rather than transmitting each bit individually, you can implement a DSSS transmitter. For that, you have simply to replace each bit by a given sequence of 1s and 0s—a pattern. For example, you may send “1001011” for each 1 of the message, and another sequence for 0, say “0111010.” Assuming that the receiver knows these two patterns, it will be able to recover the initial bit stream by comparing the received sequence with the known patterns. How? By calculating a correlation between the received signal and each of the two patterns.
The advantages of DSSS over a direct transmission of the bit stream are numerous, especially if the patterns are long and complex. A DSSS signal looks like noise if you don’t know the patterns to look for. This is, of course, why its first applications were military. By the way, according to Wikipedia, the first patent on DSSS was granted in 1942 to a Swiss inventor, Gustav Guanella, and was entitled, “Means for and method of secret signaling.” The name of the patent is significant.
Later, I will discuss the other major advantages of DSSS, in particular its high immunity to noise. But first, let’s see how to design a good DSSS system. Of course, the patterns should be selected with care. First their length must be decided. Long patterns will increase the noise resilience, but will reduce the transmission speed. So long patterns should be preferred when noise immunity is a must, whereas shorter ones should be used for high-speed transmission. Then, for a given length, not all patterns are equal in performance. “Good” patterns have precise mathematical properties.
They must have roughly as many 0s and 1s, but, more importantly, they should have so-called “good auto-correlation properties.” This means that a pattern, when correlated with itself, must show only one peak. If not, the correlation with a real signal will show plenty of additional peaks, and this will reduce the performance of the transmission. Similarly, the two distinct patterns used for 0s and 1s, when correlated with each other, must not show any significant peak. If they do, 1s may be understood as 0s or vice-versa.
Mathematicians solved this problem for us a long time ago. We engineers have just to know what pattern to use. And the most common way to generate very good patterns for DSSS is to use so-called “Gold sequences,” named after their inventor, Robert Gold (1967, see References). Gold sequences are long, binary patterns that have low auto-correlation and low cross-correlation between any two sequences—perfect for this application. We will see later that they are heavily used for high-performance communications.
Nevertheless, for binary transmissions, a simpler solution is to use only one pattern. Imagine that a pattern is selected, and coded as +1 and -1 (easier to explain than with straight binary, but it is the same). This pattern could be used to transmit logic 1s, and its negation to transmit 0s. The correlation between the signal and the pattern will give a maximum positive value for 1s and a maximum negative value for 0s.
In that specific case, the pattern must simply have a low correlation with itself. Here our friends the mathematicians told us that the best solutions are to use one of the so-called “Barker sequences.” Barker sequences, or Barker codes were invented by R.H. Barker in 1953. They are far shorter and simpler than Gold sequences, but unfortunately, only seven Barker codes exist (see References). For example, the 11-bit Barker Code is the following: +1/-1/+1/+1/-1/+1/+1/+1/-1/-1/-1.
Let’s see how it works. In Figure 2, the first graph shows you this pattern (in green). Imagine that the signal to be transmitted is “101” (second graph, in grey). Rather than sending these three bits, a DSSS system will generate a signal with three groups of 11 bits: a copy of the pattern (1), a negated copy of the pattern (0), and a copy of the pattern (1). This signal is shown in the third graph, in red. This is the signal that will be transmitted. The receiver simply calculates the correlation of the received signal with the pattern. In the last graph (in blue), as expected, there is a high peak for each received bit, and its polarity states if the bit was a 0 or 1.
This example also shows you another strong advantage of DSSS that I will discuss a little later—the receiver can easily recover the bit rate and exact reception timestamp of each bit, because the peaks are very straight—one per bit.
This example used the 11-bit-long Barker code, and you may think I selected it only for simplicity, and that such simple codes are never used in real systems. You would be very wrong, because you use this code every day. This is the coding actually used by Wi-Fi, at least in its 802.11b version. Do you remember that this version supports bit rates of 1Mbps and 11Mbps? Now you know why: Without any coding, the 802.11b bit rate is 11Mbps. However, when the propagation is not good enough, then Wi-Fi switches on an 11-bit Barker code. As each bit is transmitted as an 11-bit pattern, this reduces the effective bit rate from 11Mbps to 1Mbps.
I already said that DSSS has the advantage of a high resilience to noise. Let’s try to show it with the same example. Compare Figure 3 with Figure 2. The red plot in Figure 3 is the same signal as the one in Figure 2 (“101” encoded with an 11-bit Barker code), but with a high level of noise added to the signal. Here, the initial signal value was +1/-1, and I added a random noise with the same amplitude (a number from -1 to +1). The signal is heavily distorted. However, look at the result of the correlation calculation (Figure 3, lower, in blue). There is still some noise, but the peaks for the three bits are clearly visible, and a receiver will decode them without any problem.
Now you’ve got the idea: As long as the noise is noise, its effect will be far lower on the result of the correlation than on the signal, itself. Since correlation is a linear operation, and for those who are not reluctant to use a small equation, this would be obvious:
The last term, the correlation of the noise with the pattern, will not show any significant peak if the noise is just noise. This term will be close to zero, and the noise will be nearly cancelled out.
Of course, there is no free beer. Another way to say that is to admit that I have cheated a little. Let’s explain it with the same Barker-code example. If you replace each original bit with a pattern of 11 bits, then you reduce the actual bit rate by a factor of 11. That means that the energy to send each bit of useful information will be 11 times higher, or that the battery will be exhausted 11 times sooner. Cheat. Of course, the resulting system will be more robust, but another solution would be to simply send the original bits at a lower rate, say 11 times slower. This would also increase the reliability of the link with a properly designed receiver.
The DSSS solution may be easier to implement, but both are theoretically equivalent. In fact, the Shannon-Nyquist theorem states that the signal-to-noise immunity will be exactly the same. If the overall bit rate is the same, and if the noise is a gentle (Gaussian) noise, then using DSSS isn’t better in terms of noise immunity than just repeating the bit for a longer time. Regular readers may remember two articles I wrote on this subject: “The Darker Side – Shannon and Noise,” Circuit Cellar 331, February, 2018, and “The Darker Side – Long-Range RF for the IoT (Part 1),” Circuit Cellar 313, August, 2016.
Ok, DSSS has other advantages such as secrecy, but why did I claim that DSSS was better for noise rejection? To understand why, it is time to come to the last two letters of the DSSS acronym. They are “Spread Spectrum”. Once again, an example will be clearer than a long explanation (Figure 4). On the top, I plotted both a random sequence of bits (grey) and the encoding, using the same 11-bit Barker code (red). This time I didn’t cheat. The actual transmission rate of the DSSS sequence is 11 times faster than the rate of the original bits, to compensate for the DSSS code expansion. So, in the time domain, the transmission has the same overall throughput.
However, there is an important difference when switching to the frequency domain. Look at the bottom two plots, which are the respective Fourier Transforms of the original and DSSS-encoded signals. In the frequency domain, thanks to the DSSS encoding, the signal is spread over a wide range of frequencies, whereas a narrow frequency band is used for raw transmission. The DSSS decoding operation, which is the correlation, makes the opposite. It takes a signal with a high bit rate and wide frequency band, and recovers the slower transmitted information.
The real advantage of DSSS in terms of noise immunity is shown in Figure 5. Real-life noises aren’t flat white noises. They are more often perturbers or interferences, meaning that they perturbate only a small subset of the overall frequency band. And then DSSS shines. Its decoding operation significantly reduces the impact on any narrow-band noise or interference on the overall performance. That’s why DSSS is a good idea for noisy environments—and they are all noisy.
Let’s look at some other examples of actual DSSS systems—slightly more complex, but more interesting than Wi-Fi 802.11b and its 11-bit Barker code.
Zigbee and Thread both use the IEEE 802.15.4 standard as their low-level protocol layers. The 802.15.4 standard provides a throughput of 250 kbps and uses DSSS, but in a slightly different way. Remember that for a DSSS system, you typically must select a pattern to encode the 0s and a pattern for the 1s. Rather than doing that, 802.15.4 starts by grouping the bits to be transmitted in groups of 4 bits. Such a group is called a “symbol,” and a symbol can have 16 different values (from 0000 to 1111 in binary). Because the useful bit rate is 250kbps, the symbol rate is a fourth of that, 62.5 ksymbol/s. Then the 802.15.4 standard defines a different pattern to encode for each of the 16 possible symbol values (Figure 6).
These patterns, called “chips,” are 32 bits long, and are selected for their good cross-correlation properties. The chips are sent with a bit rate of 32 × 62.5k = 2Mbps, so the overall throughput is unchanged. I guess you are now able to find by yourself how an 802.15.4 receiver works. It simply calculates a binary correlation of the received physical bit stream with each of the 16 possible patterns. The pattern that gives the higher correlation is likely the good one, and the corresponding 4 bits are recovered.
Such a protocol may be seen as an error-correction code. If a given sequence is received and differs from one of the patterns by only a couple of bits, then it will be recovered easily by the correlation. But once again, the real strength of such a DSSS protocol is in the frequency domain. As the physical bit rate is increased from 250kbps to 2Mbps, the channel is eight times wider, and the system is eight times more resistant to narrow-band noise or interferences.
GPS is another good example of DSSS. As you may imagine, the signal-to-noise ratio (SNR) of messages coming from a satellite is quite poor. GPS uses a kind of DSSS encoding with very long patterns. You will find plenty of information on GPS, but its most simple encoding, called “coarse acquisition mode,” uses a 1,023-bit-long Gold code, which provides a very high noise rejection (Figure 7). See RESOURCES at the end of this article for more information on GPS. From Figure 7, you will understand easily that such a long-pattern DSSS is great for geo-positioning.
Since the correlation shows a very narrow peak, it is easy to time-stamp the precise reception time of the signal, and then to calculate the transmission time from satellite to earth and the user’s location. The military-grade signals carried by the GPS satellites use far longer DSSS codes for higher accuracy. By the way, such a spread spectrum technique also has an advantage in terms of Doppler shift immunity, but that’s another story.
FROM DSSS TO CDMA
Bats are also good at geolocation. You know that these small and friendly animals send an ultrasonic pulse and listen for echoes to locate themselves. But how can it work if a bat flies in the middle of a hundred other bats? It does so simply by sending a specific pattern, different from those of the other bats. It recognizes its pattern from the overall noise. The same idea can be used for DSSS.
Nothing prevents you from running two different DSSS communications in the same room, as long as they use different patterns. If the pattern sets are well selected, meaning that their cross-correlations are low, then messages from system A will be noise for system B and vice versa.
The same can be done for thousands of simultaneous communications, assuming that there is an algorithm to generate thousands of independent sets of patterns (and assuming that you can tolerate some noise). This technique, very close to DSSS, has its own abbreviation—CDMA—which stands for Code-Division Multiple Access. And you use it daily too. It is the basic communication method of all cellular networks worldwide, at least since 3G. I coded a small illustration for you (Figure 8), but I guess I may need to write another article about this someday.
So, here we are. One again I have only touched the surface of the subject. I hope you grasped the most important points. DSSS protocols are not that complex. They simply send long patterns to encode each useful bit of information. On the receiver side, a correlation with the known patterns recover these bits. For the same actual bit rate, a DSSS system provides a drastically improved immunity to perturbers and interferences, thanks to its spectral spreading. It also provides a way to get precise time-stamping of the incoming messages, along with some secrecy. And, last but not least, DSSS—or more exactly CDMA—provides a nice way to accommodate plenty of simultaneous users on a single transmission channel.
Now, as always, I encourage you to dig a little deeper by yourself. Read the documents posted in RESOURCES below. You will find plenty of additional information on these topics. Then try to implement your own small DSSS system. That’s not so complex. Do it with a simulation on your PC, do it on a Raspberry Pi, do it with your preferred MCU or do it in an FPGA—whichever way you want, but try to do it. Experience is the only real way to understand something!
“The Darker Side: Correlation Techniques,” Circuit Cellar 299, June, 2015.
“The Darker Side – Shannon and Noise,” Circuit Cellar 331, February, 2018
“The Darker Side – “Long-Range RF for the IoT (Part 1)”, Circuit Cellar 313, August, 2016.
“Direct-sequence spread spectrum”
“An introduction to spread spectrum communications”
Tutorial 1890, Feb 18th, 2003, Maxim Integrated
“Understanding GPS – Principles and Applications”
Elliott D. Kaplan & Christopher J. Hegarty
Second Edition, Artech House, ISBN 1-58053-894-0
“Means for and method of secret signaling”
US patent 2405500, Gustav Guanella, 1942
EEE Std 802.15.4 – 2015
IEEE Standard for Local and metropolitan area networks – Part 15.4: Low-Rate Wireless Personal Area Networks (LR-WPANs)
“802.11b white paper”
VOCAL technologies Ltd
Pr. Dr. W. Skupin & Pr. S. Flament – Hochschule Konstanz university of science
PUBLISHED IN CIRCUIT CELLAR MAGAZINE • APRIL 2020 #357 – Get a PDF of the issueBecome a Sponsor