Intuitor.com Intuitor.com
by Tom Rogers, Twitter Link
Local hex time:   
Local standard time:   

Pseudo-Random Numbers and Wireless Signals – Why Cell Phone Are hard to Tap

 Applet

The attached applet simulates a spread spectrum broadcast. The original digital signal (applet fig 1) containing the information to be transmitted is combined with pseudo random noise pulses generated at a much higher frequency, hence shorter pulses (applet fig 2). Applet fig 3 shows the combined signal which is then transmitted. Once received, a decoding signal is then combined with the received signal. The decoding signal is generated by the same pseudo random process used to encode the signal. If the decoding signal is in sync with the encoding signal the transmitted information is recovered unaltered as shown in applet fig. 5. If not, then the recovered signal is useless.

A group of commandos contact their base by radio while hiding just outside a terrorist group's compound. Inside, some of the terrorists huddle in a room filled with electronic equipment listening intently for enemy broadcasts which might warn them of an impending attack. To them the transmissions outside look like nothing but random background noise. While it sounds like bad physics from a Hollywood movie, it's today's reality thanks to a unique use of pseudo random number generators (PRNGs)..

In World War II it was easy to detect and listen in on enemy radio communications since they were broadcast on a single dominate frequency.  Radio silence was  necessary to avoid detection. When it was not possible to avoid detection, radio communication still posed a dilemma. To keep messages from being understood by the enemy required encryption. However, by the time a battlefield radio message was encrypted and decrypted it was often too late to effectively act on it.

In the South Pacific, the American military resolved the problem by using Navaho Indians to relay lightly coded messages in their native Navaho language. This improved speed while maintaining secrecy but the transmissions could still be easily detected. Likewise, since it was at a particular frequency it could also be jammed by producing a noise signal at the same frequency.

The first patent with a possible solution for the detection and jamming problem came in 1942 from a highly unlikely source, a movie actress, Hedy Lamarr and a composer, George Antheil. In it they proposed a system for guiding torpedoes using radio controls. Obviously, this had to be done in a way which could neither be detected or jammed in order to be effective.

Lamarr and Antheil generously turned their patent over to the government to aid in the war effort. The government responded in turn by paying the inventors nothing and pretty much ignoring the idea at least for torpedoes. The military apparently did at some point see great potential for the spread spectrum communication but kept much of their work on it top secret.

Today military communications can not only be rapidly encrypted for secrecy, but are also much harder to detect or jam. Thanks to well developed technologies like spread spectrum broadcasting, an enemy will typically not even be able to detect a broadcast let alone jam it or understand what it says.

There's more than one way to do spread spectrum broadcasting and it's beyond the scope of this article to describe all of them. So let's focus on one called direct sequence. In it, the information to be broadcast is typically digitized, that is it's broken into a series of positive and negative voltage pulses representing binary digits (see Fig. 1). Simultaneously, a pseudo random number generator (PRNG) creates a similar series of seemingly random pulses at a much higher frequency than the pulses containing the information (see Fig. 2). The higher frequency pulses look shorter than the lower frequency information pulses since more of the higher frequency ones occur in a given period of time.

The information and PRNG pulses are then combined (see Fig 3). This can be thought of as a type of multiplication of negative and positive values of one. When the voltages in the pulses are both negative, combining them is like multiplying two values of negative one together. The pulse becomes positive one. Combining a negative and positive pulse is like multiplying a negative and positive value of one. The pulse becomes negative one. The output of this process looks random .

A typical AM radio signal would be broadcast in a narrow frequency range. Adding the random pulses spreads the signal over a much larger range. Since the energy in the broadcast is now divided among a range of frequencies in a random manner, it's hard to distinguish the signal from normal random background noise.

After the signal is received, it's decoded by combining it with a second pseudo random pulse series (PRS). This pulse series has to be identical to the first pseudo random pulse series and in perfect sync with it. The second PRS is combined in the same way as the first one. In other words it is the same multiplication-like process. If the original information pulse had a value of  negative one and it was multiplied by a random pulse of negative one the result would be positive one. Multiply this a second time by negative one and the output is restored to the original value of negative one. Hence, the information is restored to look as though it were never modified (see Fig. 4).

If the second PRS is even slightly out of sync with the first one, the "decoded" signal will still look random as shown in Fig. 5.  What's more, the random appearance does not tend to look any better until the first and second PRSs are almost perfectly in sync. Hence it's difficult to recover the transmitted information without knowing the settings for the PS pulse series and how it was generated.

The PRNG used in spread spectrum broadcasting is often a linear feedback shift register (LFSR). While it's beyond the scope of this article to describe how these units work, they are used since they can be built from relatively simple low cost digital components. Like all PRNGs, LFSR units are not true random number generators. They create extremely long number sequences which seem random and can generally pass at least some statistical tests for randomness. However, the sequence will eventually repeat itself.

 

Fig. 1) Digitized Information to be Transmitted

 

Fig. 2) Pseudo Random Noise Signal

 

Fig. 3) Combined Information and Pseudo Random Noise Signal

 

Fig. 4) Received Signal After Decoding - Decoding Signal in Sync
Fig. 5) Received Signal After Decoding - Decoding Signal Out of Sync
The starting point within a PRNG's lengthy sequence is determined by a seed value. Without this seed value it's very hard to decipher a spread spectrum broadcast. As was noted in the article Perfecting Simulations, the cycle for a 64 SR LFSR system is over 1.8 x 10^19 random numbers long. If we could generate a billion random numbers a second, which far exceeds the rate of even high end desktop computers, it would take roughly 585 years to generate the entire cycle! Although spread spectrum broadcasting might not meet CIA standards, for all practical purposes it is secure.

Spread spectrum broadcasting has enabled numerous new communication technologies including wireless networks and digital cell phones. Without it one could easily listen in on cell phone conversations. These conversations would also be much more susceptible to noise and interference. Spread spectrum broadcasting tends to make better use of available broadcasting frequencies. It is nothing short of revolutionary.

Although a lot of progress has been made in wireless communications, many challenges remain. Noise from truly random sources can alter bits of transmitted digital information. While an occasional garbled word in a cell phone conversation is no big deal, altering a single digit in someone's bank account as it is being transmitted over a wireless network could be serious. As new wireless technologies are increasingly used, electrical engineers will have to master probability and statistics as well as numerous other engineering skills in order to meet the challenge of designing and perfecting new wireless systems.

For Further Information:
The birth of spread spectrum

Center for Research in Wireless Communication - Clemson University:  (see information at right)

LFSR - New Wave Instruments

Sharing The Airwaves Spread spectrum technology could bring a new dawn for broadcasting  Hal Plotkin, Special to SF Gate

Spread Spectrum Scene : "... website dedicated exclusively to the art and science of Spread Spectrum digital communications."

For more information about wireless communication and the electromagnetic spectrum visit The Hidden World of the Electromagnetic Spectrum.

 

Acknowledgements

This page was supported by a National Science Foundation Research Experience for Teachers grant as part of Clemson University's Summer Undergraduate Research Experience in Wireless Communications

< Return to Contents

 
[ Intuitor Home | Mr. Rogers AP Statistics  | Physics | Insultingly Stupid Movie Physics | Forchess | Hex | Statistics t-Shirts | About Us | E-mail Intuitor ]
Copyright © 1996-2007 Intuitor.com, all rights reserved
on the web since April 2, 1996
Twitter Link