Thursday, November 21, 2013

For GPS on a bladeRF you have to start with Gold-sequences to find signals buried in noise: it is all about correlation

My first styled page

Gold-sequence

GPS-signals is all about correlation. The signals are completely buried in the noise. Only by searching (or knowing) the code-sequences and the Doppler frequencies is it possible to decode the signals. And they are all transmitted at that same frequency!

I did some experiments in python to get aquainted (again) with Gold-sequences and correlation. So, I programmed a class Gold and wrote some test-programs. Very nice experiments!

I had a lot of fun with it. Python is a very simple language. Plotting is a breeze. And with a class that you can import you get nice short programs. The IDLE editor is sufficient to get experiments running.


A very nice article is: “Understanding Spread Spectrum for Communications” at http://www.ni.com/white-paper/4450/en/

A python class "Gold"


In python I programmed the following class:

class Gold: # Gold-sequence goldutil.py # Nov-2013 Kees de Groot # call: # myprn1 = Gold(3, 7) for code phase selection = (3,7) # or # myprn2 = Gold(4) for the 4th from the list # = satellite ID number = GPS PRN signal number # start with (0,0) to start numbering with 1 # note that PRN 34 and 37 are identical prnlist = [ (0,0), (2,6), (3,7), (4,8), (5,9), (1,9), (2,10), (1,8), (2,9), (3,10), (2,3), (3,4), (5,6), (6,7), (7,8), (8,9), (9,10), (1,4), (2,5), (3,6), (4,7), (5,8), (6,9), (1,3), (4,6), (5,7), (6,8), (7,9), (8,10), (1,6), (2,7), (3,8), (4,9), (5,10), (4,10), (1,7), (2,8), (4,10)] def __init__(self, a, b = 0): self.shreg1 = [1]*11 # don't use first bit-position [0] self.shreg2 = [1]*11 # so count bit-positions from 1 to 10 self.prnRegBinary = [] # contains 0 and 1 self.prnRegAnalogue = [] # contains -1 and +1 if b == 0: # a = GPS PRN signal number or satellite ID (self.prn1, self.prn2) = self.prnlist[a] else: # direct code phase selection (self.prn1, self.prn2) = (a, b) for i in range(1024): G1 = self.shreg1[10] G2 = self.shreg2[self.prn1] ^ self.shreg2[self.prn2] out = G1 ^ G2 self.prnRegBinary.append(out) self.prnRegAnalogue.append(2*out-1) val1 = self.shreg1[3] ^ self.shreg1[10] val2 = (self.shreg2[2] ^ self.shreg2[3] ^ self.shreg2[6] ^ self.shreg2[8] ^ self.shreg2[9] ^ self.shreg2[10]) # shift one position to the left for j in range(9): k = 10 - j self.shreg1[k] = self.shreg1[k-1] self.shreg2[k] = self.shreg2[k-1] self.shreg1[1] = val1 self.shreg2[1] = val2
A first test-program:

import goldutil as gl myGold37 = gl.Gold(3, 7) prn1 = myGold37.prnRegBinary prn2 = myGold37.prnRegAnalogue print "the first 20 points of the binary version of Gold37:" for i in range(20): print prn1[i], print "\n..." print "\nthe first 20 points of the analogue version of Gold37:" for i in range(20): print prn2[i], print "\n..."

with output:

Python 2.7.3 (default, Apr 10 2012, 23:31:26) [MSC v.1500 32 bit (Intel)] on win32 Type "copyright", "credits" or "license()" for more information. >>> ================================ RESTART ================================ >>> the first 20 points of the binary version of Gold37: 1 1 1 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 1 1 ... the first 20 points of the analogue version of Gold37: 1 1 1 -1 -1 1 -1 -1 -1 -1 1 1 1 -1 -1 -1 -1 -1 1 1 ... >>>
With this framework I can write simple programs by importing the class Gold with the command
import goldutil as gl

Autocorrelation

As a first test I calculate autocorrelation.

# Gold02b.py # autocorrelation # nov-2013 Kees de Groot import goldutil as gl import pylab as pl myGold37 = gl.Gold(3, 7) prn2 = myGold37.prnRegAnalogue # autocorrelation ac = [0]*1024 for m in range(1024): for l in range(1024): ac[m] += prn2[l] * prn2[(l + m)%1024] print "\nthe first 20 points of the autocorrelation of myGold37:" for i in range(20): print ac[i], print "\n..." pl.figure(1) pl.title("autocorrelation, note big peak of 1024 at x = 0") pl.vlines(range(1024),[0]*1024,ac) pl.show()
with output:

Python 2.7.3 (default, Apr 10 2012, 23:31:26) [MSC v.1500 32 bit (Intel)] on win32 Type "copyright", "credits" or "license()" for more information. >>> ================================ RESTART ================================ >>> the first 20 points of the autocorrelation of myGold37: 1024 0 0 0 -68 -4 0 0 60 -8 4 4 -4 0 -4 60 64 60 -8 4 ...


There is nice peak at x=0, indicating positive correlation, the codes overlaps perfectly

Now correlate two different Gold-sequences.

# Gold02c.py # correlation between different Gold-sequences # nov-2013 Kees de Groot import goldutil as gl import pylab as pl myGold37 = gl.Gold(3, 7) # code (3,7) prn1 = myGold37.prnRegAnalogue myGold15 = gl.Gold(15) # satellite 15 prn2 = myGold15.prnRegAnalogue # correlation ac = [0]*1024 for m in range(1024): for l in range(1024): ac[m] += prn1[l] * prn2[(l + m)%1024] print "\nthe first 20 points of the correlation:" for i in range(20): print ac[i], print "\n..." pl.figure(1) pl.title("correlation between two different Gold-codes") pl.vlines(range(1024),[0]*1024,ac) pl.show()
with output:

Python 2.7.3 (default, Apr 10 2012, 23:31:26) [MSC v.1500 32 bit (Intel)] on win32 Type "copyright", "credits" or "license()" for more information. >>> ================================ RESTART ================================ >>> the first 20 points of the correlation: 0 0 0 -64 0 0 0 0 0 -4 64 0 4 -4 -64 0 -4 -68 0 64 ...



There are some peaks, but not a single strong one, so there is no correlation.

The real thing


Now it is time for the real thing.
  • Take a Gold-sequence of sat 18
  • Shift it to the right 200 chips
  • Add two more Gold-sequences: sat 4 and sat 17
  • Now I have a shifted contaminated satellite signal.
First correlate with a Gold-sequence sat=20. Of course there is not any correlation, only noise
Then, the wonder: correlate with a Gold-sequence sat=18. We see an obvious peak at x=200.
So we know we found the satellite and we know the delay of the signal!

import goldutil1 as gl import pylab as pl # Gold04.py # Generate a Gold-sequence, shift it 200 chips # and add two more different Gold-sequences # then, correlate it with an arbitrary Gold-sequence # and finally correlate it with the same Gold-sequence # nov 2013 Kees de Groot sat1 = 18 # this is the sat we are looking for myGold1 = gl.Gold(sat1) pprn1 = myGold1.prnRegAnalogue sat2 = 20 # this is our guess1 myGold2a = gl.Gold(sat2) pprn2a = myGold2a.prnRegAnalogue sat2 = 18 # this is our guess2 myGold2b = gl.Gold(sat2) pprn2b = myGold2b.prnRegAnalogue # shift pprn1 200 bits to the right k = 200 for i in range(1024): temp = pprn1[(i + k)%1024] pprn1[(i + k)%1024] = pprn1[i] pprn1[i] = temp # add two different Gold-sequences to pprn1 myGold3 = gl.Gold(4) myGold4 = gl.Gold(17) for i in range(1024): pprn1[i] = (pprn1[i] + myGold3.prnRegAnalogue[i] + myGold4.prnRegAnalogue[i]) # now pprn1 is contaminated with two other sequences # cross-correlation with wrong Gold-sequence ac = [0]*1024 for m in range(1024): for l in range(1024): ac[m] += pprn1[l] * pprn2a[(l + m)%1024] print "\n 20 points around the peak at 200:" for i in range(190, 210): print ac[i], print "\n..." pl.figure(1) pl.title("correlation with different sequence") pl.vlines(range(1024),[0]*1024,ac) # cross-correlation with the right Gold-sequence ac = [0]*1024 for m in range(1024): for l in range(1024): ac[m] += pprn1[l] * pprn2b[(l + m)%1024] print "\n 20 points around the peak at 200:" for i in range(190, 210): print ac[i], print "\n..." pl.figure(2) pl.title("correlation with the right sequence") pl.vlines(range(1024),[0]*1024,ac) pl.show()
With output:

Python 2.7.3 (default, Apr 10 2012, 23:31:26) [MSC v.1500 32 bit (Intel)] on win32 Type "copyright", "credits" or "license()" for more information. >>> ================================ RESTART ================================ >>> 20 points around the peak at 200: 12 116 112 28 4 -4 -8 12 0 -48 -48 -36 -8 128 8 -4 -88 -20 -24 -28 ... 20 points around the peak at 200: 48 104 124 184 72 -12 -32 0 60 8 708 -40 -20 -32 -32 80 12 -24 -80 -48 ...
Note there is no peak in the first run, but in the second run there is a peak with a value of 708, indicating strong correlation around delay = 200 chips.



Only noisy correlation, not one obvious peak



And there it is: a peak around x=200. A clear indication of the existence of a signal in the noise.

Conclusion:

I implemented the Gold-sequence as a class Gold in python.
With that class I first demonstrated a working implementation.
Then I did some experiments with (auto)correlation and finally demonstrated that you can find a certain code-sequence in a noisy contaminated signal and even calculate the delay of that signal.


No comments:

Post a Comment