| An Introduction to Spread Spectrum Techniques |
| Originally published May, 1997 |
| by
Carlo Kopp |
| ¿ 1997, 2005 Carlo Kopp |
| |
The emerging mobile Local Area Networking technology base exploits a technology which hitherto has been largely hidden in the domain of military communications and radar. This technology comprises a collection of ideas which are termed Spread Spectrum Techniques (SST). Spread Spectrum techniques have some powerful properties which make them an excellent candidate for networking applications. To better understand why, we will take a closer look at this fascinating area, and its implications for networking. Spreading the Spectrum The first major application of Spread Spectrum Techniques (SST) arose during the mid-sixties, when NASA employed the method to precisely measure the range to deep space probes. In the following years, the US military became enamoured of SST due to its ability to withstand jamming (ie intentional interference), and it ability to resist eavesdropping. Today this technology forms the basis for the ubiquitous NavStar Global Positioning System (GPS), the soon to become ubiquitous JTIDS (Joint Tactical Information Distribution System/Link-16) datalink (used between aircraft, ships and land vehicles), and last but not least, the virtually undetectable bombing and navigation radar on the bat-winged B-2 bomber. if you ever get asked what your mobile networked laptop shares in common with a stealth bomber (excluding astronomical cost), you can state without fear of contradiction that it uses the same class of modulation algorithm. How is this black magic achieved ? The starting point is Claude Shannon's information theory, a topic beloved by diehard communications engineers. Shannon's formula for channel capacity is a relationship between achievable bit rate, signal bandwidth and signal to noise ratio. Channel capacity is proportional to bandwidth and the logarithm to the base of two of one plus the signal to noise ratio, or: Capacity = Bandwidth*log2 (1 + SNR). What this means is that the more bandwidth and the better the signal to noise ratio, the more bits per second you can push through a channel. This is indeed common sense. However, let us consider a situation where the signal is weaker than the noise which is trashing it. Under these conditions this relationship becomes much simpler, and can be approximated by a ratio of Capacity/Bandwidth = 1.44* SNR. What this says is that we can trade signal to noise ratio for bandwidth, or vice versa. If we can find a way of encoding our data into a large signal bandwidth, then we can get error free transmission under conditions where the noise is much more powerful than the signal we are using. This very simple idea is the secret behind spread spectrum techniques. Consider the example of a 3 kHz voice signal which we wish to send through a channel with a noise level 100 times as powerful as the signal. Manipulating the preceding equation, we soon find that we require a bandwidth of 208 kHz, which is about 70 times greater than the voice signal we wish to carry. Readers with a knowledge of radio will note here that this idea of spreading is a central part of FM radio and the reason why it produces good sound quality compared to the simpler AM scheme. Other than punching through large levels of background noise, why would we otherwise consider using spread spectrum techniques ? There are a number of good practical reasons why spread spectrum modulation is technically superior to the intuitively more obvious techniques such as AM and FM, and all of the hybrids which lie in between.
These characteristics endeared spread spectrum comms to the military community, who are understandably paranoid about being eavesdropped and jammed. However, the same properties are no less useful for local area networking over radio links. Indeed these are the reasons why the current IEEE draft specification for radio LANs is written around spread spectrum modulations. To better understand the inner workings of this fascinating area, we will now more closely examine the various choices we have for spread spectrum designs. The two basic methods are indeed both used in LAN equipment.  Direct Sequence Systems Direct Sequence (DS) methods are the most frequently used spread spectrum technique, and also the conceptually simplest to understand. DS modulation is achieved by modulating the carrier wave with a digital code sequence which has a bit rate much higher than that of the message to be sent. This code sequence is typically a pseudorandom binary code (often termed "pseudo-noise" or PN), specifically chosen for desirable statistical properties. In effect we are transmitting a wideband noise like signal which contains embedded message data. The time period of a single bit in the PN code is termed a chip, and the bit rate of the PN code is termed the chip rate. A wide range of pseudorandom codes exist which can be applied to this task. These codes should ideally be balanced, with an equal number of ones and zeroes over the length of the sequence (also termed the code run), as well a good code should be cryptographically secure. A spread spectrum system which uses a cryptographically insecure code will still possess the properties previously discussed, but if an eavesdropper can synchronise on to the signal they should be able to eventually crack it and extract the data. Using a secure code prevents this. The mechanics of generating pseudorandom codes is a fascinating area within itself. The most commonly used approach for producing a wide range of code types is the use of a tapped register with feedback, very simple to implement in hardware. A PN code generator of this type uses a register with taps between selected stages. These taps are logically ORed and then fed back in to the input stage of the register. The state machine produced in this fashion will periodically cycle through the same PN sequence as the clock is applied. Significantly, code sequence lengths of up to thousands of bits in length can be produced with about a dozen register stages. With modern VLSI techniques it is feasible to build generators with clock speeds up to hundreds of MHz on any die, moreover recent high speed Emitter Coupled Logic devices allow the creation of generators with clock speeds into the GHz region.  Having produced a black box which generates a PN code with the required characteristics, the process of combining the PN modulation with the data to be transmitted, and modulating this upon a carrier is not technically difficult at all. The simplest technique, one of many, is to invert the PN code when a '0' bit of message data is to be sent, and to transmit the PN code unchanged when a '1' bit of message data is to be sent. This technique is termed Bit Inversion Modulation. The result is a PN code with an embedded data message. The simplest form of carrier modulation which can be used is AM, however in practice one or another form of Phase Shift Keying (PSK) is usually employed. PSK schemes are commonly used in modems, and involve the modulation of the carrier phase with the data signal. In a DS transmitter using Binary PSK, the carrier wave is phase shifted back and forth 180 degrees with each 1 or 0 in the PN code chip stream being sent. The process of modulating the carrier with the PN code is often termed spreading. The internals of a DS receiver are somewhat more complex than those of the transmitter, but not vastly so. The central idea in all SST receivers is the use of the correlation operation. Correlation, a favourite method of our friends in the statistics community, is a mathematical operation which determines a measure of likeness or similarity between two sets of data or two time processes. In an SST receiver, the correlation operation is use to measure the similarity of a received PN code sequence to an internally generated PN code sequence. Ideally, if these PN sequences are the same, a high correlation will be detected, whereas if the codes are different, a low correlation is detected. Mathematically the correlation operation, in its simplest form, is the integral of the product of two time varying functions. In a DS receiver of the simplest kind, the hardware maps directly onto the basic maths. The correlator is built by combining a multiplier with a low pass filter (ie integrator in a control engineer's language). One of the two time varying functions is the received PN modulated signal, the other is the PN sequence produced by a PN generator internal to the receiver. In the simplest situation, the receiver's PN generator is a clone of the PN generator in the transmitter. The multiplier can be one of many designs, importantly it multiplies in effect two single numbers and is therefore trivially simple. Classical textbooks cite the analogue doubly balanced mixer as the standard multiplier. The output from the multiplier is a time varying measure of the similarity between the two codes, blended with the remnants of uncorrelated (ie real) noise and interfering signals. The integration operation disposes of the latter, and we are then left with the data which we intended to extract. This series of operations is often termed despreading. In practice, we often need to synchronise our receiver's PN generator to the incoming SST signal, therefore there is often much additional complexity required to produce an internal reference PN sequence in proper lockstep with the incoming message PN sequence. At this point it is worth reflecting upon what we have. We can generate either cryptographically secure or insecure codes. We can embed a digital data stream in one or another fashion into the code stream. All of this can be performed with pure digital logic. Once we have a combined data/code stream, we can use a very simple analogue modulation to put the message upon a carrier. The resulting radio signal looks like white noise to a third party who doesn't know out code. Our receiver shares similar hardware design with our transmitter. It uses a trivial demodulation scheme, and extracts digital data from the incoming PN data/code stream. Other radio signals occupying our bandwidth are largely ignored. Whilst an SST transmitter-receiver pair may be conceptually more complex to understand than most classical analogue schemes, it is well suited to implementation in digital logic because most of the smarts at either end of the link are purely digital. This means that such hardware can be made much more compact than many classical narrowband analogue schemes, which often require a lot of analogue hardware which may or may not be easy to squeeze into Silicon. Consider a narrowband 16 or 64 level QAM scheme, which is not only vulnerable to interference and noise, but also requires a digital signal processing chip to demodulate. For those readers with a bent toward radio engineering, the spectral envelope of a DS system is typically a sinc function, with suppressed outer sidebands beyond the first null, and often a suppressed carrier. A parameter which radio types will appreciate is process gain, a measure of signal to noise ratio improvement achieved by despreading the received signal. For a DS system it is typically about twice the ratio of RF bandwidth to message bandwidth. Therefore to improve your ability to reject interference by 20 dB, you need to increase your chip rate by a factor of 100.  Frequency Hopping Systems Frequency Hoppers (FH) are a more sophisticated and arguably better family of spread spectrum techniques than the simpler DS systems. However, performance comes with a price tag here, and FH systems are significantly more complex than DS systems. The central idea behind a FH system is to retune the transmitter RF carrier frequency to a pseudorandomly determined frequency value. In this fashion the carrier keeps popping up a different frequencies, in a pseudorandom pattern. The carrier itself amy be modulated directly with the data using one of many possible schemes. The available radio spectrum is thus split up into a discrete number of frequency channels, which are occupied by the RF carrier pseudorandomly in time. Unless you know the PN code used, you have no idea where the carrier wave is likely to pop up next, therefore eavesdropping will be quite difficult. Frequency hoppers are typically divided into fast and slow hoppers. A slow frequency hopper will change carrier frequency pseudorandomly at a frequency which is much slower than the data bit rate on the carrier. A fast frequency hopper will do so at a frequency which is faster than that of the data message.  Hybrid (FH/DS) Systems If we are really paranoid about being eavesdropped, we can take further steps to make our signal difficult to find. A commonly used example is that of a hybrid spread spectrum system using both FH and DS techniques. Such schemes will typically employ frequency hopping of the carrier wave, while concurrently using a DS modulation technique to modulate the data upon the carrier. In this fashion an essentially DS modulated message is hopped about the spectrum. To successfully intercept such a signal you must first crack the FH code, and then crack the DS code. If you want to be further secure, you encrypt your data stream with a very secure crypto code before you feed it into your DS modulator, and employ cryptographically secure PN codes for the DS and FH operations. Your eavesdropper then has to chew his way through three levels of encoding. Such a scheme is used in the military JTIDS/Link 16 datalink. Summary Spread Spectrum techniques are technologically superior to conventional narrowband modulation techniques in a number of important areas. Because they form the datalink layer of the new generation of radio LANs, systems administrators and computer security experts are well advised to gain a good understanding of their strengths and limitations. Future features will look at the more practical implications of radio LAN technology. |
| $Revision: 1.1 $ |
| Last Updated: Sun Apr 24 11:22:45 GMT 2005 |
| Artwork and text ¿ 2005 Carlo Kopp |