Spread Spectrum Techniques

I had no idea how WiFi works and ...
>And you find that unusual?
Pay attention.
Suppose we want to broadcast an FM radio signal so everybody can hear it.
Then we'd apply for a license to broadcast our news, weather & sports at, say 95.3 MHz.
Everybody in the neighbourhood could tune to that station and hear it.
Aah, but suppose we did NOT want everybody to hear it ... just a special few.
>Huh?
We might be transmitting secret data or trade secrets or ...
>Okay, I get it.
Then we could transmit for a fraction of a second at 95.3 MHz then continue at 95.7 MHz then continue at 95.1 MHz then ...
>So you keep changing the frequency, right?
Exactly! And those who knew the sequence of frequencies would have receivers that changed their tuning appropriately.
Everybody else would get garbage. Neat, eh?
>You should patent the idea. The army would love it. They'd use it for ...
Too late.
Such a frequencyhopping scheme was patented in 1942.
After the patent expired, the U.S. navy used the scheme in 1962 (during the blockade of Cuba) and, since then ...
>Wait! On the patent I see a coinventor is called Hedy Kiesler Markey. Is that a girl?
Uh ... yes, that was her married name at the time  but you might better recognize her as Hedy Lamarr.
>You're kidding, right?
Would I kid you?
 
Okay, so this frequency hopping technique is known as frequencyhopping spread spectrum (or FHSS).
The "frequencyhopping" you understand, right?
The "spread spectrum" part is due to the fact that the frequency (95.3 MHz in the above example) is spread out to include a range of frequencies.
>So that's WiFi?
No. We're talking about the historical evolution of "spread spectrum" techniques.
WiFi uses what's called directsequence spread spectrum (or DSSS).
I should point out that WiFi doesn't stand for anything. Especially, it doesn't stand for "Wireless Fidelity".
WiFi is governed by the WiFi Alliance and the name was the brainchild of a company that invents names !!
In fact, WiFi and the Ying Yang style logo were invented by Interbrand (who also created the names Prozac, Compaq and Celebrex).
Interbrand also submitted the alternate names Skybridge, Torchlight, and Flyover ... but WiFi was selected.
I understand that the first choice was Trapeze, but perhaps the Ying Yang logo won for the name WiFi.
 
>I think that's better than a name like IEEE 802.11, eh?
I think so. Can you imagine saying "IEEE 802.11 encryption keys" or even "Trapezeenabled device"?
However, before we go too far, let's remember that, today, everything is digital so we should explain how to scramble and unscramble digital signals.
Suppose we have a digital signal  a sequence of 1s and 0s, like so:  11010011101 
We introduce a "scrambling key", like so:  11100010010 
We "multiply" the two together, digitbydigit, and get:  00110001111 
>Multiply them together?
Uh ... well, it's actually called Exclusive OR (XOR).
The result of "multiplying" two identical digits is a 0. The result of multiplying two different digits is a 1.
See how it goes? If we denote that XOR ritual as , we'd have:
1 1 = 0
and 0 0 = 0

0 1 = 1
and 1 0 = 1

To see this ritual in action, you can click here.
>Okay, so somebody gets that 00110001111. How does she regain the unscrambled signal?
Aah ... you mean the 11010011101.
Simple! She just does the digitbydigit XOR with the same scrambling key, namely 11100010010.
That'd go like so:
The scrambled signal received is this guy:  00110001111 
We use the same "scrambling key", namely:  11100010010 
We XOR the two together, digitbydigit, and get:  11010011101 
So, if we both know the scrambling key, then you can unscramble my messages ... but nobody else can.
>But they can try various combinations of 1s and 0s until they get it right. After all, there aren't many digits in that key.
One of the first scrambling keys was a sequence of 40 1s and 0s called WEP40.
(WEP stands for Wired Equivalent Privacy.)
To make it harder to unscramble, they now use 128bit (or even 256bit) encryption keys.
>Encryption key?
Yes, that's what it's called. I just said "scrambling key" for the fun of it.
Encryption keys might be a sequence of digits (0  9) and letters (A  F). That's 16 possible characters. Such a key might look like 98D9DE3ABCD5224F.
Each of these 16 characters can be represented by 4 binary digits: 0000 to 1111. That's 16 possible combinations of 1s and 0s.
A sequence of 64 such 4bit combinations would be a 256bit sequence. That'd give a 256bit encryption key denoted by (for example): 98D9DE3ABCD5224F.
In other words, the 16 characters (like 98D9DE3ABCD5224F) would be 256 bits long ... in binary.
In 2007, Erik Tews (a researcher in the computer science department at Darmstadt University of Technology in Germany) cracked the WEP encryption in 60 seconds.
However, a safer encryption is WPA (which stands for WiFi Protected Access).
With WEP, the encryption key don't hardly change. With WPA, the encryption key is changed every so often.
That's Temporary Key Integrity Protocol (TKIP).
In practice, one can generate encryption keys from a sequence of random numbers.
Many such random number generators begin with a socalled "random seed", then generate "random" numbers beginning with this seed.
If you know the seed (and the prescription for generating the numbers), then you can generate the same sequence of "random" numbers.
SO  I need only give you the seed (and the prescription for generating the numbers) and you can know the sequence of encryption keys and are able to decrypt my messages.
>Huh? A random number generator?
Actually, since they're completely determined by that "seed", they aren't truly random  they're "pseudorandom" numbers (PRN).
The first such pseudorandom number generator was the midsquare generator (originally suggested by von Neumann).
You start with an Ndigit number (that's the "seed") then square it and select the middle N digits.
That's your next pseudorandom number. Then you ...
>Then you repeat ... again and again, right?
You got it.
 
>Is there yet another encryption method? One that's got more security?
There's WPA2 which is more sophisticated.
Note that, in encryption schemes, a sequence of digits passes through some magic transformation T to get the encrypted sequence.
When the encrypted sequence is received, the "inverse" of that magic transformation is applied to the encrypted signal to recover the original signal.
Sexier schemes could apply several magical transformations:
At the receiving end, the inverses of these transformations are applied in reverse order to recover the original signal.

>But ain't a bunch of magic transformations the same as one HUGE transformation?
Yes, but they can be quite different.
In the diagram above, T_{1} might be some encrytionkey encoding and T_{2} might be shifting digits and T_{3} might be ...
>T_{3} might be filling the zeros with peanut butter and T_{4} might be jam and ...
Concentrate!
I (vaguely) recall schemes which are called public key cryptosystems. I think they use two keys  one secret and one "public".
In fact, I remember Ron Mullin and Scott Vanstone working on these guys while I was at the University of Waterloo.
>Public key cryptosystems? How do they work?
I have no idea. However, I recall Scott describing some software that he wanted me to write ... so I did.
>And what was the purpose of the software?
I have no idea.
Barker Codes and Autocorrelation

In DSSS, Direct Sequence Spread Spectrum, things get a mite complicated.
Suppose the original signal has a sequence of digits 1 0 1 1 as in Figure 1a.
Part of the WiFi ritual involves "modulating" each digit of this signal with, say, the sequence 10110111000.
This modulation results in the modified signal as shown in Figure 1b.
Note that the amplitude of each digit has the latter 11digit sequence superimposed.
>Except that the original 0 digit has a different sequence superimposed.
Uh ... yes. It has the complement, namely: 01001000111.
It's like sending 10110111000 instead of a 1 and 01001000111 in place of a 0.
Note: If the original signal has a bit rate of 1 Mega bit per second (Mbps), this high frequency superposition will result in a signal with a bit rate of 11 Mbps.
>So that widens the frequency range covered, right?
Yes, and that's ...
>Don't tell me! It's "spectrum spreading".
Apparently.
 Figure 1a
Figure 1b

>And that 11digit modulating thing ... that's picked out of thin air?
Not exactly. That 11digit spreading sequence is a Barker Code.
>Huh? Spreading sequence? Barker code?
That particular sequence of 1s and 0s, the Barker Code, is also called a "Chipping Sequence".
>Because the original signal looks "chipped" ... as in Fig. 1b?
Who knows? Note, however, that the actual information (in the above example) is contained in the 1 0 1 1, as in Figure 1a.
The addition of the chipping sequence introduces what could be considered "noise". It contains no information. Indeed, after decryption, it's gone!
The purpose of the Barker Code is to detect and correct errors in transmission and synchronizing transmitter and receiver. It has nothing to do "scrambling" the original signal.
The scrambling (or encryption) is done with that sequence of pseudorandomly selected encryption keys. Remember?
>No... and by the way, what's this synchronization stuff?
In order to "despread" the encoded signal, the receiver has a "synchronized" replica of the "pseudonoise" (or PN) Barker Code.
In fact, to the "stupid" receiver (not up to snuff in the details of WPA WiFi), the signal would appear to be noise.
Note that, once an encrypted and frequencyspread signal is generated, it's stuck onto a high frequency signal of (about) 2.4 GHz ... then sent to an antenna and transmitted.
In fact, there are 14 frequency bands in the neighbourhood of 2.4 GHz, each covering 22 MHz.
Yet, the total range of frequencies allocated to WiFi is only 84.5 MHz ... so most of them overlap!
Only 3 channels do NOT overlap.
In Canada and the U.S., only channels 1 to 11 are available for WiFi use.
>Have you noticed that 22 MHz is twice the 11 Mbps?
I noticed that, too. The frequency range for each channel is ±11 Mhz from the centre frequency.
 
>So what's so special about that Barker Code?
Barker codes have magic properties ... and there aren't many of them.
If you calculate the Maximum Autocorrelation for all 11digit codes, the Barker Code has the smallest, namely Max. Autocorrelation = 1.
>Autowho?
Before I talk about autocorrelation, play with this spreadsheet to see if you can find a "better" code ... with smaller Max. Autocorrelation:
Just click on the picture to download the spreadsheet.
Suppose we have two 5bit sequences of 1s and 1s, say: [a_{1} a_{2} a_{3} a_{4} a_{5}]
and [b_{1} b_{2} b_{3} b_{4} b_{5}].
For example:
[A] [1 1 1 1 1] and [1 1 1 1 1].
To see if they are "related" in some way, a "correlation" is calculated like so:
a_{1}b_{1} + a_{2}b_{2} + a_{3}b_{3} + a_{4}b_{4} + a_{5}b_{5}.
For example:
[B] (1)(1) + (1)(1) + (1)(1) + (1)(1) + (1)(1) = 1+1+1+1+1 = 3.
If, for example, the second sequence contained digits equal to those of the first sequence, the "correlation" would be 5.
If the second sequence digits were the negative of those of the first sequence, the "correlation" would be 5.
In either case, the absolute value of this "correlation" would be 5 which is the largest possible correlation for two 5digit sequences.
Because of this large "correlation", we'd conclude that they were "related".
>Huh? If the second sequence is identical to the first, then they're obviously related! Can't you see that?
Patience.
In the above [A] [B] example, the "correlation" was 3, so they are "less" related.
>If you wanted unrelated sequences, then pick a couple where the correlation is 0.
Is there such a pair of 5digit sequences? A pair where the absolute value of the maximum correlation is 0?
The answer is No!.
In any case, we're interested in Autocorrelation.
Instead of finding the "correlation" between distinct sequences, we find the "correlation" between two sequences where the second is obtained from the first by shifting.
In our 5digit example, we get the second sequence by shifting the first by one digit to the right and consider these two:
[a_{1} a_{2} a_{3} a_{4}] and [a_{2} a_{3} a_{4} a_{5}]
For this 1 digit shift, the "correlation" is then:
C_{1}= a_{1}a_{2} + a_{2}a_{3} + a_{3}a_{4} + a_{4}a_{5}.
Then we see if there's a "correlation" between the original and a second sequence shifted 2 digits:
C_{2} = a_{1}a_{3} + a_{2}a_{4} + a_{3}a_{5}.
Then we see if there's a "correlation" between the original and a second sequence shifted 3 digits:
C_{3} = a_{1}a_{4} + a_{2}a_{5}.
Then we see ...
>Don't tell me! Now you look at C_{4} = a_{1}a_{5}, right?
Exactly. Now you calculate the maximum of them Cs: Max. Autocorrelation = Max[ C_{j} ] for j = 1, 2, 3, 4.
Finally, you vary the initial sequence so that Max[ C_{j} ] is less than or equal to 1.
>And that's a Barker sequence?
Yes ... and you'd get the Barker Sequence: 1 1 1 1 1
You can play here. Keep pressing F9 to change the (random) code generated to see that you get the Barker Sequence when the Max. Autocorrelation is reduced to 1.
>Why do you always put "correlation" in quotes?
There are so many "correlations", but we're considering just the flavour defined above.
>Okay, so show me the first dozen Barker Codes ... just so I get a feel for how the digits are arranged.
They're shown in Figure 2.
>Show me the first dozen!
Alas, them's all that have been found ... so far.
>Hey! Didn't you say, earlier, that the 11digit Barker Code was 10110111000?
Uh ... yes, but ...
>So why doesn't that look like the 11digit Barker in Figure 2?
I haven't figured that out ... yet.
When I google "Barker Codes", I get the Barker sequences shown in Figure 2.
When I google WiFi "Barker Codes", I get 10110111000.
 Figure 2 
>Why is that?
I haven't figured that out ... yet.
>Well, let's see ... uh ... if you change all them 1s to 0s we'd get (from Figure 2, for the 11bit Barker): 11100010010
Good ... and if we take the complement we'd get: 00011101101.
>Aha! Now read it backwards and we get: 10110111000.
I GOT IT!!
>Well, I helped.
Yes, you did ... but why that ritual? I guess the properties of the Barker code aren't changed when we do that transformation.
>Can you prove that?
Let me cogitate.
When defining a Barker as the minimum of the absolute value of Max. Autocorrelation, we could certainly get 0 by choosing every digit equal to 0.
>So we avoid that by having only digits 1 and 1.
Right! So Barker codes look like the sequences in Figure 2 ... with 1s and 1s.
>Exactly ... then we do that complement and reverse thing.
