Sunday, February 21, 2016

Understanding Spread Spectrum (Direct Sequence)

I've recently been working on some spread-spectrum DSP software for an experiment I'm conducting. I'm very familiar with frequency-hopping spread spectrum (FHSS). In fact, I own a pair of the discontinued TriSquare walkie-talkies. However, it took me a while to wrap my mind around direct-sequence spread spectrum, and now that I understand it I'm providing a simplified explanation for the benefit of others like me.

Background

Spread spectrum involves spreading a signal's bandwidth to enable many users to share a frequency band. It has the added benefit of providing decent privacy as it's very difficult to de-spread a signal unless you know the unique code used to spread it.

Before I got an SDRplay, I tuned my RTL-SDR to 900 MHz and spoke into a TriSquare walkie-talkie. On the waterfall I could see very short bursts of relatively wide FM. When a burst happened to land on my passband I could hear my voice momentarily. This came as a surprise since I had thought these walkie-talkies used encrypted digital voice. Even when not using my TriSquare I have seen similar bursts in the same band, and they are quite strong. These walkie-talkies are extremely rare so I knew it had to be another device. My research makes me think these are electric and gas meters.

I am particularly interested in creating a DSSS transmitter, but I didn't understand how to spread a signal evenly over a band, as opposed to hopping. This YouTube video was extremely helpful.

What doesn't work:

I misunderstood the video the first time around. Here's what I thought it meant:

Let's say I want to spread the string "SaaS" with a 20-byte spreading code of

"356A192B7913B04C54574D18C28D46E6395428AB".
(By the way, that's the SHA-1 hash of "1")

I thought spreading worked by literally spreading the whole message (or at least a chunk) over the spreading code. Here's what I imagined:

You repeat each letter of the string 5 times, and since the string is 4 bytes this becomes 20 bytes:

SSSSSaaaaaaaaaaSSSSS
In hex that is 5353535353616161616161616161615353535353

Then you XOR it with your 20-byte spreading code:
              5353535353616161616161616161615353535353
XOR     356A192B7913B04C54574D18C28D46E6395428AB
------------------------------------------------------------------------------
             6066651262585323565850522351551066676664

All seemed well and good until I wanted to despread it. I was completely at a loss as to how that would be done and, looking over the video again, saw that it would be a mess, if it was possible at all.
(On a side note, I know I could just XOR it again like a one-time pad and thereby recover the data, but if I had combined it with other signals then it likely would have been unrecoverable.)

What does work:

I found that in fact each bit of the message must be spread with the entire spreading code. So let's say I have a spreading code of 10010101. Just XOR each message bit by the entire spreading code. If I want to transmit a 1, then it would look like this:

            10010101 (entire spreading code)
XOR    11111111 (just one message bit)
----------------------
             01101010 (spreaded bits, chip rate 8x)

Now here's where it gets interesting. The signal must be transmitted as a waveform, so these bits are converted to voltages. The standard convention is 0 = +1 volt while 1 = -1 volt. However, when I was writing my modulator and demodulator I found it easier to think of it as 1 = +1 and 0 = -1. Using my convention, the message wave voltages would be:

-1 +1 +1 -1 +1 -1 +1 -1

Repeat the process with all the transmitters that must share the band. Then add their values together to get a composite waveform.

How do you recover just one stream? Assuming you tune in at the beginning of a bit's spreading cycle (which you can assume since you're working with samples in a file), simply multiply the +1/-1 values of the desired spreading code by the corresponding values of the composite waveform. This will yield a lot of crazy, fluctuating values. Average them. Unlike the YouTube tutorial, the average you get will not be clean-cut or precisely 1 or 0. You will have to depend on the sign to determine the actual bit. The software provided below takes this into account.

If you want to try this concept, I have written a program that generates *.CSV files of the waveforms of whatever text you like. It uses the 0=-1/1=+1 convention and uses just the sign of the average to determine the bits. Just save several different CSV files with different spreading codes and copy-paste them into their own Excel columns in one document. Then apply Excel's Average Add function to the final column. Copy-paste that column into its own file called "compositewaveform.csv" or whatever you like. The demodulator will read this file, accept the spreading code in a variable, despread the message, and show it on screen.

Here are download links for my program:
Written in Liberty BASIC v4.50

Spreader (proper_adjustable_spreader.bas)

Despreader (dsss_demod.bas)

Note that if you don't feel like combining several waveforms in Excel, you can still tell the demodulator to open just one waveform file and it will still despread it, provided you have given it the right spreading code.

You can experiment with spreading codes to see which ones coexist well. I have experimented with using the first 16 bits of SHA-512 hashes of consecutive numbers. My favorite hashing tool is a hex editor called HxD Hex Editor. It also has a great disk editor. However, I don't think it can copy-paste excessively large chunks. For that, use HHD Hex Editor Neo.

I have found that some of the data is corrupted when too many signals are together in the composite waveform. Also, some spreading codes do not coexist well at all, losing all the data in their streams. But higher chip rates, while reducing throughput, also reduce errors.

No comments:

Post a Comment